Parser — Análise Sintática

O Lexer entrega uma lista de tokens, mas uma lista não diz se o programa é válido — nem qual é a estrutura dele. É o trabalho do Parser descobrir como os tokens se encaixam segundo a gramática da linguagem e gerar bytecode diretamente.

A pergunta central que o Parser responde é:

Os tokens formam um programa gramaticalmente válido? E qual é o bytecode dele?

Neste artigo vamos estudar o recursive descent, o algoritmo usado no Parser no Drax. Vamos ver a gramática da linguagem, como precedência e associatividade são resolvidas, como o parser gera bytecode diretamente e como os erros de sintaxe são tratados.

1. O problema da análise sintática

A lista de tokens do Lexer é linear. Mas um programa não é linear: blocos contêm statements, statements contêm expressões, expressões contêm subexpressões. Existe uma hierarquia no código.

flowchart LR
    Tokens[("if | nota | >= | 6 | { | ... | }")] --> Parser[Parser] --> BC[Bytecode]

O Lexer responde "o que existe aqui?". O Parser responde "como essas coisas se encaixam?". Para isso ele usa uma gramática, o conjunto de regras que define quais sequências de tokens formam programas válidos na linguagem — e gera bytecode diretamente, sem uma etapa intermediária de AST.

Considere o código:

if nota >= 6 {
  print("aprovado")
}

O parser precisa entender que if, nota >= 6 e o bloco { ... } formam uma única unidade, e que nota >= 6 é a condição, não uma lista de tokens soltos.

2. A gramática do Drax

Uma gramática é escrita com regras de produção. O lado esquerdo é o "nome" do conceito; o direito descreve como ele é formado. Um subconjunto da gramática do Drax:

program     := statement*
block       := '{' statement* '}'
statement   := 'fun' IDENT '(' params ')' block
             | 'if' expr block ('else' block)?
             | 'while' expr block
             | 'return' expr?
             | IDENT '=' expr
             | expr
params      := IDENT (',' IDENT)*

expr        := equality
equality    := comparison (('==' | '!=') comparison)*
comparison  := term (('<' | '<=' | '>' | '>=') term)*
term        := factor (('+' | '-') factor)*
factor      := unary (('*' | '/' | '%') unary)*
unary       := ('!' | '-') unary | call
call        := primary ('(' args ')')*
args        := expr (',' expr)*
primary     := NUMBER | STRING | 'true' | 'false' | 'nil'
             | IDENT | '(' expr ')'

Observe como a gramática está estruturada por precedência: expr é o nível mais "baixo" (menos restrito), e primary o mais "alto". * aparece em factor, acima de + em term. É essa ordem que garante que 1 + 2 * 3 seja lido como 1 + (2 * 3).

3. Recursive descent

O recursive descent é a técnica mais comum para parsers manuais: uma função para cada símbolo não-terminal da gramática. A função de um nível chama as funções dos níveis abaixo — por isso "recursive" e "descent".

no Drax, cada função segue o mesmo esqueleto:

static void dparse_equality(d_vm* vm, d_parser* parser) {
  dparse_comparison(vm, parser);                       /* desce um nível */

  while (match(parser, D_TOKEN_EQ) || match(parser, D_TOKEN_NE)) {
    d_token op = previous(parser);
    dparse_comparison(vm, parser);                     /* lado direito */
    emit(vm, op_to_opcode(op.type), op.line);          /* emite o operador */
  }
}

O padrão é sempre o mesmo: parsear o nível inferior, e enquanto o próximo token for um operador desse nível, consumi-lo e emitir a instrução correspondente. É a tradução direta das regras equality := comparison (('==' | '!=') comparison)*.

A gramática e o código se correspondem linha a linha:

4. Precedência e associatividade

Precedência

O parser resolve precedência pela ordem das chamadas: term chama factor, que chama unary. Quando o parser vê 1 + 2 * 3:

1. dparse_expression → dparse_equality → ... → dparse_term
2. dparse_term lê 1, consome +, e pede dparse_factor para o lado direito
3. dparse_factor lê 2, consome *, e pede dparse_unary para o lado direito → 3
4. Resultado: as instruções ficam na ordem correta — * é emitido antes de +, garantindo precedência

flowchart LR
    PUSH1[PUSH 1] --> PUSH2[PUSH 2] --> PUSH3[PUSH 3] --> MUL[MULT] --> ADD[ADD]

Associatividade

Operadores como - e / são associativos à esquerda: 8 / 4 / 2 deve ser (8 / 4) / 2 = 1, não 8 / (4 / 2) = 4. No loop while, a instrução emitida na iteração anterior fica à esquerda na pilha — por isso a associação é à esquerda. Operadores que fossem associativos à direita usariam recursão no operando direito.

5. Statements

Statements não produzem valor — eles fazem algo: declaram, controlam o fluxo, atribuem. O parser do Drax despacha por tipo de token:

static void dparse_statement(d_vm* vm, d_parser* parser) {
  if (check(parser, D_TOKEN_FUN))   { dparse_fun_decl(vm, parser); return; }
  if (check(parser, D_TOKEN_IF))    { dparse_if(vm, parser); return; }
  if (check(parser, D_TOKEN_WHILE)) { dparse_while(vm, parser); return; }
  if (check(parser, D_TOKEN_RETURN)){ dparse_return(vm, parser); return; }
  if (check(parser, D_TOKEN_IDENT) && match(parser, D_TOKEN_ASSIGN)) {
    dparse_assignment(vm, parser);
    return;
  }
  dparse_expr_statement(vm, parser);
}

O if é um bom exemplo de como um statement gera várias instruções:

static void dparse_if(d_vm* vm, d_parser* parser) {
  consume(parser, D_TOKEN_IF, "esperava 'if'");
  dparse_expression(vm, parser);                        /* condição */

  int jump = emit(vm, OP_JUMP_IF_FALSE, parser->previous.line);
  dparse_block(vm, parser);                             /* bloco then */

  if (match(parser, D_TOKEN_ELSE)) {
    int skip = emit(vm, OP_JUMP, parser->previous.line);
    patch(vm, jump, here(vm));                          /* preenche o desvio do if */
    dparse_block(vm, parser);                           /* bloco else */
    patch(vm, skip, here(vm));                          /* preenche o pulo do else */
  } else {
    patch(vm, jump, here(vm));
  }
}

consume é o que valida a expectativa: se o token atual não for o esperado, reporta um erro de sintaxe. match verifica e consome de uma vez.

6. Como o Drax lida com erros

Um parser ingênuo para no primeiro erro. o Drax usa uma estratégia simples: modo pânico. Quando encontra um erro, o parser reporta e "pula" tokens até achar um ponto de sincronização seguro — geralmente o fim de um statement.

static void synchronize(d_vm* vm, d_parser* parser) {
  advance(parser); /* descarta o token problemático */

  while (!is_at_end(parser)) {
    if (previous(parser).type == D_TOKEN_RBRACE) return;

    switch (peek(parser).type) {
      case D_TOKEN_FUN:
      case D_TOKEN_IF:
      case D_TOKEN_WHILE:
      case D_TOKEN_RETURN:
        return; /* ponto de sincronização: começo de um statement */
      default:
        break;
    }

    advance(parser);
  }
}

A mensagem de erro usa a posição do token (guardada pelo Lexer) para dizer exatamente onde o problema está:

linha 3, coluna 10: esperava ')' depois de expressão

O custo: o parser pode reportar erros cascata que são consequência do erro original. O ganho: o desenvolvedor vê vários erros de uma vez e corrige mais rápido.

7. A implementação no Drax (dparser.c)

O parser está em src/dparser.c. O estado é simples: o array de tokens, o índice atual e flags de erro:

typedef struct d_parser {
  d_token* tokens;
  int count;
  int current;
  bool had_error;
} d_parser;

A API pública recebe os tokens do Lexer e devolve o bytecode do programa parseado:

d_instructions* dparse_program(d_vm* vm, d_token* tokens, int count);

E o fluxo completo, ligando o que o Lexer produz ao que o parser entrega:

flowchart TB
    Source[Código-fonte] --> Lexer[Lexer<br/>dlex_next_token] --> Tokens[Lista de tokens] --> Parser[Parser<br/>dparse_program] --> BC[Bytecode]
    Parser -- erro de sintaxe --> Error["Mensagem com linha e coluna"]

O parser não avalia nada: ele valida a forma e gera instruções bytecode diretamente. O que exatamente ele gera é o assunto do próximo artigo — a Virtual Machine.

8. Complexidade e trade-offs

O recursive descent é eficiente: cada token é consumido uma única vez, O(n) no número de tokens. Não há backtracking — a decisão entre as alternativas de statement é tomada olhando apenas o token atual (é um parser LL(1) na prática).

Trade-offs de design:

Hand-written vs gerado (Yacc/Bison, ANTLR): parsers gerados são menos código e geralmente mais rápidos, mas o código gerado é difícil de depurar e as mensagens de erro são péssimas sem trabalho extra. O recursive descent permite mensagens de erro excelentes e é direto de ler — para o Drax, vale a pena.

Precedência na gramática vs no código: dá para escrever a gramática "plana" e resolver precedência com lógica extra no parser (Pratt parser). o Drax usa a abordagem clássica de níveis na gramática, que é mais verbosa mas mais transparente.

Erros: modo pânico é simples, mas pode gerar mensagens enganosas. Parsers mais sofisticados (recovery por produções) são bem mais complexos de implementar.

9. Conclusão

O Parser transforma a pergunta "os tokens formam um programa?" em "qual é a estrutura do programa?":

flowchart LR
    Tokens[Lista de tokens] --> Check[Verifica gramática] --> Emit[Emite bytecode] --> BC[Bytecode]
    Check -- inválido --> Error[Erro com posição]

no Drax, isso é tangível: d_parser caminha sobre os tokens produzidos por dlex_next_token, cada regra da gramática vira uma função (dparse_equality, dparse_term, dparse_statement…), a ordem das chamadas resolve precedência, o while de cada nível resolve associatividade, emit gera as instruções e synchronize recupera de erros mantendo a análise viva.

Com a gramática validada e o bytecode gerado, o próximo passo é executá-lo — a Virtual Machine.