❧ Lab - Analisador Sintático I ❧

Introdução11.1

No capítulo anterior você estudou a ideia de parsing descendente recursivo no plano conceitual. Agora chegou a hora de aplicar esse algoritmo ao compilador que estamos construindo.

Até aqui, o nosso projeto já é capaz de realizar análise léxica. Isso significa que ele consegue transformar o código-fonte em uma sequência de tokens. Porém, ainda existe uma limitação importante: o compilador sabe reconhecer as peças da linguagem, mas ainda não sabe verificar como essas peças se organizam estruturalmente.

Por exemplo, o lexer consegue ler corretamente a entrada abaixo:

x + 3 * y

mas ele não responde a perguntas como estas:

• o + é o operador principal da expressão ou o *?
• 3 * y deve ser agrupado antes ou depois da soma?
• os parênteses foram fechados corretamente?
• existe uma expressão completa antes do fim do arquivo?

Essas perguntas pertencem à análise sintática.

Neste laboratório, vamos dar esse próximo passo de forma cuidadosa e incremental. O objetivo aqui não é parsear a linguagem inteira ainda. Vamos focar apenas em expressões, porque esse é o ponto em que precedência, associatividade e recursão aparecem com mais força. Antes de parser blocos, funções, condicionais e laços, precisamos consolidar muito bem essa base.

Ao final deste capítulo, o projeto será capaz de:

• receber os tokens reais já produzidos pelo lexer;
• reconhecer expressões do Slang com precedência correta;
• construir uma AST simples para essas expressões;
• imprimir essa árvore em um formato legível;
• detectar alguns erros sintáticos básicos.

No próximo laboratório, vamos expandir essa base para chegar ao parser estrutural completo que reconhece programas inteiros.

O subconjunto do Slang que vamos analisar11.2

Nesta primeira etapa, o parser reconhecerá expressões como estas:

x + 3 * y
x >= 10 and not done
(a + b) == c
nome != "admin" or ativo
10 % 3 + 1

Note que já estamos usando os tokens reais do projeto, vindos diretamente do lexer implementado nos laboratórios anteriores.

Os tipos de tokens relevantes aqui são:

• TOK_IDENTIFIER
• TOK_NUMBER
• TOK_STRING
• TOK_CHAR
• TOK_KW_TRUE e TOK_KW_FALSE
• TOK_PLUS e TOK_MINUS
• TOK_STAR, TOK_SLASH e TOK_PERCENT
• TOK_EQ e TOK_BANG_EQ
• TOK_GT, TOK_GT_EQ, TOK_LT e TOK_LT_EQ
• TOK_AND, TOK_OR e TOK_NOT
• TOK_LPAREN e TOK_RPAREN

Isso é importante porque, a partir de agora, o parser deixa de ser um algoritmo abstrato e passa a trabalhar sobre a linguagem do próprio projeto.

Ajuste pendente vindo do lexer: suporte a %11.2.1

Antes de continuar, precisamos alinhar uma pequena pendência entre o estado que os alunos já têm e o estado que vamos usar neste laboratório.

Ao longo deste capítulo, a nossa gramática tratará o operador de módulo % no mesmo nível de precedência de * e /. Isso significa que o parser precisará reconhecer TOK_PERCENT.

Se você tentar escrever parse_factor usando TOK_PERCENT sem atualizar antes a definição dos tokens, o projeto nem chegará a compilar. O erro será algo na linha de:

error: 'TOK_PERCENT' undeclared

Esse erro não está no parser em si. Ele acontece porque o enum de tokens ainda não conhece esse nome.

Portanto, antes de implementar o parser, faça estes dois ajustes no lexer.

Adicionando TOK_PERCENT em include/compiler/token.h11.2.1.1

Abra include/compiler/token.h e insira TOK_PERCENT junto dos operadores aritméticos:

#define TOKEN_LIST \
    X(TOK_PLUS)          /* + */ \
    X(TOK_MINUS)         /* - */ \
    X(TOK_STAR)          /* * */ \
    X(TOK_SLASH)         /* / */ \
    X(TOK_PERCENT)       /* % */ \
    X(TOK_ASSIGN)        /* = */ \
    /* restante da lista */

Como usamos X-Macros, esse único acréscimo já atualiza automaticamente:

• o enum TokenType;
• o array TokenNames.

Fazendo o lexer reconhecer % em src/compiler/lexer.c11.2.1.2

Agora abra src/compiler/lexer.c e, dentro do switch principal de lexer_next_token, adicione o caso do operador %:

.
.
.
case '%': return make_token(lexer, TOK_PERCENT);

Esse ajuste é pequeno, mas muito importante. Sem ele, o parser até poderia compilar, porém o lexer produziria erro sempre que encontrasse % no código-fonte.

Em resumo:

• token.h ensina ao compilador que TOK_PERCENT existe;
• lexer.c ensina o lexer a emitir esse token;
• parser.c passa a usar esse token dentro da regra de factor.

Agora sim estamos com a base pronta para a análise sintática das expressões.

Do fluxo linear de tokens para uma estrutura hierárquica11.3

O lexer enxerga uma expressão como uma sequência linear de tokens. Para ele, a entrada:

x + 3 * y

vira algo conceitualmente assim:

IDENT  PLUS  NUMBER  STAR  IDENT

Essa informação é necessária, mas não é suficiente. O parser precisa reconstruir a estrutura hierárquica implícita nessa sequência. Nesse caso, a leitura correta não é:

(x + 3) * y

mas sim:

x + (3 * y)

Em outras palavras, o parser não trabalha apenas com a pergunta “quais tokens apareceram?”. Ele trabalha com a pergunta “como esses tokens se encaixam nas regras da gramática da linguagem?”.

Essa é a razão de existir da AST: ela preserva a estrutura essencial da expressão depois que a leitura sintática foi concluída.

A gramática de expressões do Slang11.4

Se tentarmos escrever a gramática de expressões da forma mais natural possível, podemos cair em algo como:

$$ E \to E + T \mid T $$

O problema é que essa gramática é recursiva à esquerda, e um parser descendente recursivo entra em loop infinito quando tenta implementá-la diretamente.

Por isso, precisamos reorganizar a gramática por níveis de precedência.

Uma forma apropriada para este laboratório é:

$$ \begin{split} Expr &\to Or \\ Or &\to And\ Or' \\ Or' &\to (\texttt{or})\ And\ Or' \mid \epsilon \\ And &\to Equality\ And' \\ And' &\to (\texttt{and})\ Equality\ And' \mid \epsilon \\ Equality &\to Comparison\ Equality' \\ Equality' &\to (== \mid !=)\ Comparison\ Equality' \mid \epsilon \\ Comparison &\to Term\ Comparison' \\ Comparison' &\to (> \mid >= \mid < \mid <=)\ Term\ Comparison' \mid \epsilon \\ Term &\to Factor\ Term' \\ Term' &\to (+ \mid -)\ Factor\ Term' \mid \epsilon \\ Factor &\to Unary\ Factor' \\ Factor' &\to (* \mid / \mid \%)\ Unary\ Factor' \mid \epsilon \\ Unary &\to (! \mid \texttt{not} \mid -)\ Unary \mid Primary \\ Primary &\to id \mid num \mid string \mid char \mid true \mid false \mid (Expr) \end{split} $$

Essa organização resolve dois problemas ao mesmo tempo:

1. elimina a recursão à esquerda direta;
2. incorpora a precedência naturalmente na estrutura das funções do parser.

Lendo essa gramática de cima para baixo, temos a seguinte ordem de precedência:

• or
• and
• igualdade
• comparação
• soma e subtração
• multiplicação, divisão e módulo
• operadores unários
• literais, identificadores e agrupamentos entre parênteses

Quanto mais fundo o parser desce, maior é a precedência daquele nível.

Lendo uma expressão manualmente11.5

Antes de escrever código, vale fazer uma simulação manual da entrada:

x + 3 * y

O parser começa em parse_expression, que delega para parse_or. Como não há or, descemos para parse_and, depois para parse_equality, depois para parse_comparison, até chegar em parse_term.

Dentro de parse_term, a primeira coisa feita é chamar parse_factor. Esse factor inicial acaba reconhecendo apenas x, porque x sozinho já é um operando válido.

Ao retornar para parse_term, o parser olha o token atual e encontra +. Como + pertence ao nível de term, ele entende que a expressão ainda não acabou. Então:

1. guarda o operador +;
2. chama parse_factor novamente para reconhecer o operando da direita.

Agora o operando da direita começa em:

3 * y

Dentro de parse_factor, o parser reconhece 3. Em seguida, encontra *. Como * pertence ao nível de factor, ele continua nesse nível e constrói primeiro a subárvore:

*
├── 3
└── y

Só depois essa subárvore inteira volta para parse_term, que monta a árvore maior:

+
├── x
└── *
    ├── 3
    └── y

É justamente por isso que o algoritmo respeita a precedência sem precisar de truques extras.

O que vamos adicionar ao projeto11.6

Para sair da teoria e entrar no compilador real, vamos adicionar dois módulos novos ao projeto:

1. ast.h e ast.c, para representar árvores sintáticas de expressões;
2. parser.h e parser.c, para consumir tokens e construir essas árvores.

Ao final deste capítulo, a estrutura do projeto ficará assim:

compilador/
├── CMakeLists.txt
├── include/
│   └── compiler/
│       ├── ast.h
│       ├── lexer.h
│       ├── parser.h
│       └── token.h
└── src/
    ├── compiler/
    │   ├── ast.c
    │   ├── lexer.c
    │   ├── parser.c
    │   └── token.c
    └── main.c

Observe que, por enquanto, essa AST será uma estrutura mínima focada apenas em expressões. No próximo laboratório ela será expandida para representar programa completo.

Modelando uma AST mínima para expressões11.7

Uma AST não precisa guardar todos os detalhes da derivação formal. Ela guarda apenas a estrutura semântica e sintática importante para as próximas etapas do compilador.

Neste laboratório, vamos trabalhar com quatro categorias de nós:

• nó binário, para operadores como +, *, ==, >= e and;
• nó unário, para operadores como -, ! e not;
• nó literal, para identificadores, números, strings, chars e booleanos;
• nó de agrupamento, para expressões entre parênteses.

Se a entrada for:

x >= 10 and not done

a árvore conceitual esperada será parecida com isto:

and
├── >=
│   ├── id(x)
│   └── num(10)
└── not
    └── id(done)

Essa árvore deixa claro que:

• a operação mais externa é and;
• à esquerda temos a comparação x >= 10;
• à direita temos a operação unária not done.

Criando include/compiler/ast.h11.7.1

Crie o arquivo include/compiler/ast.h com a definição básica da árvore:

#ifndef COMPILER_AST_H_
#define COMPILER_AST_H_

#include "compiler/token.h"

typedef enum {
    AST_BINARY,
    AST_UNARY,
    AST_LITERAL,
    AST_GROUPING
} AstNodeType;

typedef struct AstNode AstNode;

struct AstNode {
    AstNodeType type;

    union {
        struct {
            Token operator;
            AstNode *left;
            AstNode *right;
        } binary;

        struct {
            Token operator;
            AstNode *operand;
        } unary;

        struct {
            Token value;
        } literal;

        struct {
            AstNode *expression;
        } grouping;
    } as;
};

AstNode *ast_make_binary(Token operator, AstNode *left, AstNode *right);
AstNode *ast_make_unary(Token operator, AstNode *operand);
AstNode *ast_make_literal(Token value);
AstNode *ast_make_grouping(AstNode *expression);

void ast_print(const AstNode *node);
void ast_free(AstNode *node);

#endif

Algumas observações importantes sobre essa modelagem:

1. usamos um enum para registrar qual tipo de nó está armazenado;
2. usamos union porque um nó nunca será binário, unário e literal ao mesmo tempo;
3. o nó literal guarda um Token, e não uma string copiada, porque isso reaproveita a mesma estratégia eficiente que já usamos no lexer.

Essa AST ainda é enxuta. No próximo laboratório, vamos trocá-la por uma versão maior que representa funções, blocos, declarações e comandos.

Implementando src/compiler/ast.c11.7.2

Agora implemente src/compiler/ast.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "compiler/ast.h"

static AstNode *ast_allocate(void) {
    AstNode *node = (AstNode *)malloc(sizeof(AstNode));
    if (node == NULL) {
        fprintf(stderr, "Erro: memória insuficiente para criar AST.\n");
        exit(74);
    }
    return node;
}

AstNode *ast_make_binary(Token operator, AstNode *left, AstNode *right) {
    AstNode *node = ast_allocate();
    node->type = AST_BINARY;
    node->as.binary.operator = operator;
    node->as.binary.left = left;
    node->as.binary.right = right;
    return node;
}

AstNode *ast_make_unary(Token operator, AstNode *operand) {
    AstNode *node = ast_allocate();
    node->type = AST_UNARY;
    node->as.unary.operator = operator;
    node->as.unary.operand = operand;
    return node;
}

AstNode *ast_make_literal(Token value) {
    AstNode *node = ast_allocate();
    node->type = AST_LITERAL;
    node->as.literal.value = value;
    return node;
}

AstNode *ast_make_grouping(AstNode *expression) {
    AstNode *node = ast_allocate();
    node->type = AST_GROUPING;
    node->as.grouping.expression = expression;
    return node;
}

static void print_lexeme(Token token) {
    printf("%.*s", token.length, token.start);
}

static void print_node_label(const AstNode *node) {
    switch (node->type) {
        case AST_BINARY:
            print_lexeme(node->as.binary.operator);
            break;
        case AST_UNARY:
            print_lexeme(node->as.unary.operator);
            break;
        case AST_GROUPING:
            printf("group");
            break;
        case AST_LITERAL:
            switch (node->as.literal.value.type) {
                case TOK_IDENTIFIER:
                    printf("id(");
                    print_lexeme(node->as.literal.value);
                    printf(")");
                    break;
                case TOK_NUMBER:
                    printf("num(");
                    print_lexeme(node->as.literal.value);
                    printf(")");
                    break;
                case TOK_STRING:
                    printf("string(");
                    print_lexeme(node->as.literal.value);
                    printf(")");
                    break;
                case TOK_CHAR:
                    printf("char(");
                    print_lexeme(node->as.literal.value);
                    printf(")");
                    break;
                case TOK_KW_TRUE:
                case TOK_KW_FALSE:
                    printf("bool(");
                    print_lexeme(node->as.literal.value);
                    printf(")");
                    break;
                default:
                    print_lexeme(node->as.literal.value);
                    break;
            }
            break;
    }
}

static void ast_print_tree(const AstNode *node, const char *prefix, int is_last) {
    char next_prefix[256];

    printf("%s", prefix);
    printf("%s", is_last ? "└── " : "├── ");
    print_node_label(node);
    printf("\n");

    snprintf(next_prefix, sizeof(next_prefix), "%s%s", prefix, is_last ? "    " : "│   ");

    switch (node->type) {
        case AST_BINARY:
            ast_print_tree(node->as.binary.left, next_prefix, 0);
            ast_print_tree(node->as.binary.right, next_prefix, 1);
            break;
        case AST_UNARY:
            ast_print_tree(node->as.unary.operand, next_prefix, 1);
            break;
        case AST_GROUPING:
            ast_print_tree(node->as.grouping.expression, next_prefix, 1);
            break;
        case AST_LITERAL:
            break;
    }
}

void ast_print(const AstNode *node) {
    if (node == NULL) {
        printf("<ast vazia>\n");
        return;
    }

    print_node_label(node);
    printf("\n");

    switch (node->type) {
        case AST_BINARY:
            ast_print_tree(node->as.binary.left, "", 0);
            ast_print_tree(node->as.binary.right, "", 1);
            break;
        case AST_UNARY:
            ast_print_tree(node->as.unary.operand, "", 1);
            break;
        case AST_GROUPING:
            ast_print_tree(node->as.grouping.expression, "", 1);
            break;
        case AST_LITERAL:
            break;
    }
}

void ast_free(AstNode *node) {
    if (node == NULL) return;

    switch (node->type) {
        case AST_BINARY:
            ast_free(node->as.binary.left);
            ast_free(node->as.binary.right);
            break;
        case AST_UNARY:
            ast_free(node->as.unary.operand);
            break;
        case AST_GROUPING:
            ast_free(node->as.grouping.expression);
            break;
        case AST_LITERAL:
            break;
    }

    free(node);
}

Vamos analisar as partes mais importantes.

Alocação segura11.7.2.1

A função ast_allocate centraliza a criação de nós. Em vez de espalhar chamadas a malloc pelo código inteiro, concentramos esse comportamento em um único lugar.

Isso traz duas vantagens:

1. o código fica mais limpo;
2. a checagem de erro por falta de memória fica padronizada.

As funções ast_make_binary, ast_make_unary, ast_make_literal e ast_make_grouping tornam a construção da árvore muito mais clara dentro do parser.

Sem esses helpers, cada função do parser teria que:

• alocar memória;
• preencher tipo;
• preencher campos internos.

Com os construtores, o parser pode se concentrar apenas na lógica sintática.

A função ast_print imprime a raiz, e a função recursiva ast_print_tree cuida do restante dos filhos usando os caracteres de caixa.

Isso é muito útil pedagogicamente, porque permite observar visualmente a hierarquia da expressão. Em vez de simplesmente dizer “a precedência está correta”, nós conseguimos ver a precedência na forma da árvore.

A função ast_free visita a árvore recursivamente e libera todos os nós. Isso é importante porque o parser aloca nós dinamicamente durante a construção da AST.

Mesmo em projetos pequenos, vale manter essa disciplina desde cedo.

Agora precisamos criar a estrutura que vai dirigir a análise sintática. Crie include/compiler/parser.h:

#ifndef COMPILER_PARSER_H_
#define COMPILER_PARSER_H_

#include <stdbool.h>
#include "compiler/ast.h"
#include "compiler/lexer.h"

typedef struct {
    Lexer lexer;
    Token current;
    Token previous;
    bool had_error;
} Parser;

void parser_init(Parser *parser, const char *source);
AstNode *parser_parse(Parser *parser);

#endif

Essa estrutura guarda o estado mínimo necessário para nosso parser de expressões:

• lexer: o analisador léxico que fornecerá os tokens sob demanda;
• current: o token atual que está sendo examinado;
• previous: o token consumido imediatamente antes;
• had_error: uma flag para indicar que a análise falhou.

O campo previous pode parecer pequeno, mas ele é extremamente útil. Quando reconhecemos um operador com match, o parser avança. O operador reconhecido deixa de estar em current e passa a estar em previous. É exatamente isso que permite construir um nó binário ou unário com o operador correto.

Implementando os helpers básicos do parser11.8

Abra src/compiler/parser.c e comece pela infraestrutura essencial:

#include <stdio.h>
#include "compiler/parser.h"

static void advance_parser(Parser *parser);
static bool check(Parser *parser, TokenType type);
static bool match(Parser *parser, TokenType type);
static void consume(Parser *parser, TokenType type, const char *message);
static void syntax_error(Parser *parser, const char *message);

static AstNode *parse_expression(Parser *parser);
static AstNode *parse_or(Parser *parser);
static AstNode *parse_and(Parser *parser);
static AstNode *parse_equality(Parser *parser);
static AstNode *parse_comparison(Parser *parser);
static AstNode *parse_term(Parser *parser);
static AstNode *parse_factor(Parser *parser);
static AstNode *parse_unary(Parser *parser);
static AstNode *parse_primary(Parser *parser);

void parser_init(Parser *parser, const char *source) {
    lexer_init(&parser->lexer, source);
    parser->had_error = false;
    parser->previous.type = TOK_ERROR;
    parser->current = lexer_next_token(&parser->lexer);
}

static void advance_parser(Parser *parser) {
    parser->previous = parser->current;
    parser->current = lexer_next_token(&parser->lexer);
}

static bool check(Parser *parser, TokenType type) {
    return parser->current.type == type;
}

static bool match(Parser *parser, TokenType type) {
    if (!check(parser, type)) return false;
    advance_parser(parser);
    return true;
}

static void syntax_error(Parser *parser, const char *message) {
    fprintf(stderr, "[linha %d] Erro sintático próximo de \"%.*s\": %s\n",
            parser->current.line,
            parser->current.length,
            parser->current.start,
            message);
    parser->had_error = true;
}

static void consume(Parser *parser, TokenType type, const char *message) {
    if (check(parser, type)) {
        advance_parser(parser);
        return;
    }
    syntax_error(parser, message);
}

Essas funções são pequenas, mas formam o coração do parser.

advance_parser11.8.1

Essa função move a janela de leitura para frente. Antes do avanço:

• current é o token sendo analisado agora.

Depois do avanço:

• previous recebe o token antigo;
• current recebe o próximo token vindo do lexer.

Isso acontece continuamente ao longo da análise.

check apenas responde: “o token atual é deste tipo?”. Ele não consome nada. Por isso, check é ideal quando queremos apenas inspecionar o estado atual antes de decidir o próximo passo.

match faz duas coisas:

1. verifica se o token atual é do tipo esperado;
2. se for, consome esse token.

Portanto:

• check olha;
• match olha e avança.

Essa diferença parece pequena, mas é central para o comportamento correto do parser.

Usamos consume quando um token é obrigatório pela gramática.

Por exemplo, após abrir um parêntese em um agrupamento, esperamos obrigatoriamente um ) ao final. Se ele não aparecer, não se trata apenas de uma escolha gramatical diferente; trata-se de um erro sintático.

A rotina de syntax_error produz uma mensagem simples, mas útil, indicando:

• a linha do erro;
• o lexema próximo ao qual o erro ocorreu;
• a expectativa do parser naquele ponto.

Mais à frente, no próximo laboratório, vamos melhorar algumas mensagens e ampliar os contextos de erro.

Implementando a cadeia de precedência11.9

Agora vamos construir o parser propriamente dito.

A ideia geral é simples:

• cada função representa um nível da gramática;
• cada nível chama o próximo nível, que tem precedência maior;
• quando encontra operadores do seu próprio nível, constrói nós binários ou unários.

Regra inicial: parse_expression11.9.1

static AstNode *parse_expression(Parser *parser) {
    return parse_or(parser);
}

Essa função é apenas a porta de entrada da gramática de expressões.

Operadores or11.9.2

static AstNode *parse_or(Parser *parser) {
    AstNode *expr = parse_and(parser);

    while (match(parser, TOK_OR)) {
        Token operator = parser->previous;
        AstNode *right = parse_and(parser);
        expr = ast_make_binary(operator, expr, right);
    }

    return expr;
}

A lógica é sempre esta:

1. parsear primeiro o operando esquerdo com precedência maior;
2. enquanto houver operadores do nível atual, continuar consumindo;
3. a cada repetição, construir uma nova árvore binária.

Operadores and11.9.3

static AstNode *parse_and(Parser *parser) {
    AstNode *expr = parse_equality(parser);

    while (match(parser, TOK_AND)) {
        Token operator = parser->previous;
        AstNode *right = parse_equality(parser);
        expr = ast_make_binary(operator, expr, right);
    }

    return expr;
}

Esse padrão se repete. Apenas o nível chamado internamente muda.

Igualdade11.9.4

static AstNode *parse_equality(Parser *parser) {
    AstNode *expr = parse_comparison(parser);

    while (match(parser, TOK_EQ) || match(parser, TOK_BANG_EQ)) {
        Token operator = parser->previous;
        AstNode *right = parse_comparison(parser);
        expr = ast_make_binary(operator, expr, right);
    }

    return expr;
}

Aqui entram == e !=.

Comparação11.9.5

static AstNode *parse_comparison(Parser *parser) {
    AstNode *expr = parse_term(parser);

    while (match(parser, TOK_GT) || match(parser, TOK_GT_EQ) ||
           match(parser, TOK_LT) || match(parser, TOK_LT_EQ)) {
        Token operator = parser->previous;
        AstNode *right = parse_term(parser);
        expr = ast_make_binary(operator, expr, right);
    }

    return expr;
}

Esse nível trabalha com >, >=, < e <=.

Soma e subtração11.9.6

static AstNode *parse_term(Parser *parser) {
    AstNode *expr = parse_factor(parser);

    while (match(parser, TOK_PLUS) || match(parser, TOK_MINUS)) {
        Token operator = parser->previous;
        AstNode *right = parse_factor(parser);
        expr = ast_make_binary(operator, expr, right);
    }

    return expr;
}

Esse é o nível que garante, por exemplo, que + e - fiquem acima de * e / na árvore.

Multiplicação, divisão e módulo11.9.7

static AstNode *parse_factor(Parser *parser) {
    AstNode *expr = parse_unary(parser);

    while (match(parser, TOK_STAR) || match(parser, TOK_SLASH) ||
           match(parser, TOK_PERCENT)) {
        Token operator = parser->previous;
        AstNode *right = parse_unary(parser);
        expr = ast_make_binary(operator, expr, right);
    }

    return expr;
}

Observe a inclusão de TOK_PERCENT. O operador de módulo pertence ao mesmo nível de precedência de multiplicação e divisão, então ele naturalmente entra nesta função.

Operadores unários11.9.8

static AstNode *parse_unary(Parser *parser) {
    if (match(parser, TOK_NOT) || match(parser, TOK_MINUS)) {
        Token operator = parser->previous;
        AstNode *right = parse_unary(parser);
        return ast_make_unary(operator, right);
    }

    return parse_primary(parser);
}

Aqui temos um ponto importante: a chamada recursiva para parse_unary faz com que o parser aceite cadeias como:

not -x

ou:

--10

Se o token atual não for um operador unário, então a expressão deve ser um primário.

Primários11.9.9

static AstNode *parse_primary(Parser *parser) {
    if (match(parser, TOK_IDENTIFIER) ||
        match(parser, TOK_NUMBER) ||
        match(parser, TOK_STRING) ||
        match(parser, TOK_CHAR) ||
        match(parser, TOK_KW_TRUE) ||
        match(parser, TOK_KW_FALSE)) {
        return ast_make_literal(parser->previous);
    }

    if (match(parser, TOK_LPAREN)) {
        AstNode *expr = parse_expression(parser);
        consume(parser, TOK_RPAREN, "Esperado ')' após a expressão.");
        return ast_make_grouping(expr);
    }

    syntax_error(parser, "Esperado literal, identificador ou '('.");
    return NULL;
}

Essa função representa as folhas da gramática.

Se o token atual for:

• identificador;
• número;
• string;
• char;
• true;
• false;

então produzimos diretamente um nó literal.

Se o token atual for (, iniciamos um agrupamento. Nesse caso:

1. consumimos (;
2. parseamos uma expressão completa dentro dele;
3. exigimos um ) ao final.

Se nada disso acontecer, então a expressão está malformada.

Fechando a análise com parser_parse11.10

Para finalizar src/compiler/parser.c, adicione:

AstNode *parser_parse(Parser *parser) {
    AstNode *root = parse_expression(parser);

    if (!parser->had_error && !check(parser, TOK_EOF)) {
        syntax_error(parser, "Esperado fim da entrada.");
    }

    if (parser->had_error) {
        ast_free(root);
        return NULL;
    }

    return root;
}

Essa função faz duas verificações importantes:

1. a análise começa pela regra inicial expression;
2. ao final da expressão, não deve sobrar lixo sintático antes do EOF.

Isso evita aceitar entradas parcialmente válidas como:

x + 1 abc

Nesse exemplo, x + 1 é uma expressão válida, mas abc sobra no final, então a entrada completa deve ser rejeitada.

Por que usamos while em vez de funções com apóstrofo?11.11

Na gramática formal, usamos símbolos auxiliares como Or', Term' e Factor'. Na implementação, poderíamos criar uma função separada para cada continuação. No entanto, isso deixaria o código mais verboso sem trazer ganho real aqui.

Por isso, transformamos essas continuações em laços while.

Quando você vê um trecho como:

while (match(parser, TOK_PLUS) || match(parser, TOK_MINUS)) {
    ...
}

deve ler isso como:

“enquanto ainda existir uma continuação válida deste nível de precedência, continue consumindo operadores e operandos”.

Essa escolha mantém o código compacto sem alterar a lógica do algoritmo.

Atualizando o CMakeLists.txt11.12

Como adicionamos dois módulos novos, precisamos incluí-los na biblioteca do projeto.

No CMakeLists.txt, atualize add_library para:

add_library(compiler_lib
    src/compiler/token.c
    src/compiler/lexer.c
    src/compiler/ast.c
    src/compiler/parser.c
)

Sem isso, o compilador não saberá que esses arquivos fazem parte da build.

Integrando temporariamente ao main.c11.13

Para testar o parser neste laboratório, vamos substituir temporariamente o main.c por uma versão focada em parsing de expressões. No próximo capítulo, essa integração será ampliada para conviver com o lexer e com o parser estrutural completo.

Substitua src/main.c por:

#include <stdio.h>
#include <stdlib.h>
#include "compiler/ast.h"
#include "compiler/parser.h"

static char *read_file(const char *path) {
    FILE *file = fopen(path, "rb");
    if (file == NULL) {
        fprintf(stderr, "Erro: Não foi possível abrir o arquivo \"%s\".\n", path);
        exit(74);
    }

    fseek(file, 0L, SEEK_END);
    size_t file_size = ftell(file);
    rewind(file);

    char *buffer = (char *)malloc(file_size + 1);
    if (buffer == NULL) {
        fprintf(stderr, "Erro: Memória insuficiente para ler \"%s\".\n", path);
        exit(74);
    }

    size_t bytes_read = fread(buffer, sizeof(char), file_size, file);
    if (bytes_read < file_size) {
        fprintf(stderr, "Erro: Falha na leitura do arquivo \"%s\".\n", path);
        exit(74);
    }

    buffer[bytes_read] = '\0';
    fclose(file);
    return buffer;
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Uso: compiler [caminho_do_arquivo]\n");
        return 64;
    }

    char *source = read_file(argv[1]);

    Parser parser;
    parser_init(&parser, source);

    AstNode *root = parser_parse(&parser);
    if (root == NULL) {
        free(source);
        return 65;
    }

    printf("Sucesso: análise sintática concluída.\n");
    printf("=== AST ===\n");
    ast_print(root);

    ast_free(root);
    free(source);
    return 0;
}

Essa versão faz apenas o necessário para este laboratório:

• lê o arquivo fonte;
• chama o parser;
• se a análise der certo, imprime a AST;
• se a análise falhar, encerra com código de erro.

No próximo capítulo, essa interface será substituída pela forma definitiva do projeto.

Testando a implementação11.14

Crie um arquivo expr.slang com o conteúdo:

x >= 10 and not done

Compile o projeto:

cmake -B build
cmake --build build

Agora execute:

./build/compiler expr.slang

A saída esperada será:

Sucesso: análise sintática concluída.
=== AST ===
and
├── >=
│   ├── id(x)
│   └── num(10)
└── not
    └── id(done)

Teste também um caso que mistura precedências:

x + 3 * y

A árvore deve mostrar + na raiz e * mais abaixo.

Por exemplo:

+
├── id(x)
└── *
    ├── num(3)
    └── id(y)

Agora teste um exemplo com módulo:

10 % 3 + 1

A árvore correta deve tratar % antes do +.

Por fim, experimente uma entrada inválida:

x + * y

A análise deve falhar com algo próximo de:

[linha 1] Erro sintático próximo de "*": Esperado literal, identificador ou '('.

Você também pode testar um parêntese não fechado:

(x + 2

Nesse caso, a mensagem deverá indicar que faltou ) após a expressão.

Próximos Passos11.15

No próximo capítulo, AST completa e erros sintáticos comuns no Slang, vamos expandir essa base para chegar ao parser estrutural do projeto.

Lá, iremos:

• substituir essa AST mínima por uma AST de programa completo;
• adicionar suporte a declarações, blocos, funções e comandos;
• melhorar mensagens de erro sintático;
• reorganizar a execução do compilador para o fluxo final do projeto.

Em outras palavras: neste capítulo você construiu o núcleo do parser. No próximo, vamos transformá-lo em um analisador sintático de verdade para o Slang completo.