❧ Lab - Analisador Sintático II ❧

Introdução12.1

No capítulo anterior, construímos o núcleo do parser descendente recursivo para expressões. Isso foi importante para consolidar três ideias centrais:

• leitura recursiva guiada pela gramática;
• precedência e associatividade;
• construção de uma AST durante a análise.

Mas o compilador ainda está longe de entender um programa real. Neste momento, ele só sabe reconhecer entradas como:

x + 3 * y

ou:

not (a < b)

Isso não basta para analisar arquivos reais da linguagem, porque um programa do Slang contém elementos estruturais muito maiores:

• declarações de variável;
• blocos;
• funções;
• condicionais if e else;
• laços loop;
• comandos break, continue e return;
• chamadas de função usadas como expressão e também como comando isolado.

É justamente isso que vamos finalizar neste laboratório.

Ao final deste capítulo, o projeto ficará no mesmo estado do código atual do repositório, incluindo:

• AST completa em ast.h e ast.c;
• parser estrutural em parser.h e parser.c;
• main.c com dois modos de execução: lex e parse;
• impressão final da AST do programa inteiro;
• reorganização da suíte de testes em tests/lexer e tests/parser;
• contrato sintático do parser em tests/parser/contract.md.

Em outras palavras: este capítulo fecha a transição da fase “parser de expressões” para a fase “parser de programa”.

O que muda nessa etapa12.2

No laboratório anterior, a AST tinha apenas quatro tipos de nó e o main.c estava temporariamente voltado para análise de expressões.

Agora vamos fazer quatro mudanças grandes.

1. A AST deixará de representar apenas expressões.
   Agora ela representará também declarações, comandos, blocos, funções e programa inteiro.

2. O parser deixará de começar por parse_expression.
   Agora ele começará por program -> declaration* EOF.

3. O parser passará a precisar de um pequeno lookahead de token.
   Isso será necessário para distinguir casos como:

x: int = 5

de:

x = 5

e também para separar expressão comum de chamada de função usada como comando.

4. A interface do executável será finalizada.
   O compilador passará a aceitar:

./build/compiler lex arquivo.slang
./build/compiler parse arquivo.slang

Para organizar a implementação, vamos trabalhar com a gramática abaixo.

program        -> declaration* EOF
declaration    -> function_decl | var_decl | statement

function_decl  -> "fn" IDENT "(" params? ")" "->" type block
params         -> param ("," param)*
param          -> IDENT ":" type
var_decl       -> IDENT ":" type "=" expression
type           -> "int" | "float" | "bool" | "char" | "string" | "void"

statement      -> if_stmt
               | loop_stmt
               | return_stmt
               | break_stmt
               | continue_stmt
               | assign_stmt
               | call_stmt
               | block

block          -> "{" declaration* "}"
if_stmt        -> "if" expression block ("else" block | "else" if_stmt)?
loop_stmt      -> "loop" block | "loop" expression block
return_stmt    -> "return" expression?
break_stmt     -> "break"
continue_stmt  -> "continue"
assign_stmt    -> IDENT "=" expression
call_stmt      -> call

expression     -> or
or             -> and (("or" | "||") and)*
and            -> equality (("and" | "&&") equality)*
equality       -> comparison (("==" | "!=") comparison)*
comparison     -> term ((">" | ">=" | "<" | "<=") term)*
term           -> factor (("+" | "-") factor)*
factor         -> unary (("*" | "/" | "%") unary)*
unary          -> ("!" | "not" | "-") unary | call
call           -> primary ("(" arguments? ")")*
arguments      -> expression ("," expression)*
primary        -> NUMBER | STRING | CHAR | "true" | "false" | IDENT | "(" expression ")"

Alguns detalhes importantes dessa gramática:

• uma declaração de variável é reconhecida por IDENT :;
• uma atribuição é reconhecida por IDENT =;
• uma chamada como print(x) pode aparecer tanto dentro de expressão quanto como comando isolado;
• loop { ... } representa laço infinito;
• loop expr { ... } representa laço condicional;
• return pode aparecer com ou sem expressão neste marco.

Da AST mínima para a AST final do projeto12.3

No capítulo 11, a árvore era pequena porque servia apenas às expressões. Agora vamos substituí-la pela estrutura final do projeto atual.

Esta nova AST segue uma estratégia mais direta do que a versão antiga com union:

• cada nó tem um kind;
• três ponteiros genéricos (first, second, third) são usados para relacionamentos fixos;
• um vetor dinâmico children é usado quando o número de filhos varia;
• dois tokens auxiliares (token e extra) carregam nomes, operadores e tipos.

Essa abordagem é menos “bonita” no papel do que uma grande union, mas fica muito prática para um compilador didático. Ela reduz bastante a quantidade de código cerimonial e deixa o parser mais direto.

Substituindo include/compiler/ast.h12.3.1

Substitua completamente include/compiler/ast.h por:

#ifndef COMPILER_AST_H_
#define COMPILER_AST_H_

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

typedef enum {
    AST_PROGRAM,
    AST_FUNCTION,
    AST_PARAM,
    AST_BLOCK,
    AST_VAR_DECL,
    AST_IF,
    AST_LOOP,
    AST_RETURN,
    AST_BREAK,
    AST_CONTINUE,
    AST_ASSIGN,
    AST_EXPR_STMT,
    AST_BINARY,
    AST_UNARY,
    AST_CALL,
    AST_IDENTIFIER,
    AST_NUMBER,
    AST_STRING,
    AST_CHAR,
    AST_BOOL
} AstKind;

typedef struct AstNode AstNode;

typedef struct {
    AstNode **items;
    int count;
    int capacity;
} AstNodeArray;

struct AstNode {
    AstKind kind;
    Token token;
    Token extra;
    AstNode *first;
    AstNode *second;
    AstNode *third;
    AstNodeArray children;
};

AstNode *ast_new_node(AstKind kind);
void ast_add_child(AstNode *node, AstNode *child);
void ast_print(FILE *stream, const AstNode *node);
void ast_free(AstNode *node);

#endif

Entendendo essa estrutura12.3.2

Vale entender bem o papel de cada campo.

kind12.3.2.1

Identifica o tipo do nó atual. É ele que diz se estamos olhando para:

• um programa;
• uma função;
• um if;
• uma expressão binária;
• um identificador;
• um literal numérico.

token12.3.2.2

Guarda o token principal do nó. Alguns exemplos:

• em AST_FUNCTION, token guarda o nome da função;
• em AST_VAR_DECL, token guarda o nome da variável;
• em AST_BINARY, token guarda o operador;
• em AST_IDENTIFIER, token guarda o identificador;
• em AST_NUMBER, token guarda o literal numérico.

extra12.3.2.3

Serve como um segundo token auxiliar. Ele é útil quando o nó precisa guardar mais de uma informação textual.

Por exemplo:

• em AST_FUNCTION, extra guarda o tipo de retorno;
• em AST_PARAM, extra guarda o tipo do parâmetro;
• em AST_VAR_DECL, extra guarda o tipo declarado.

first, second, third12.3.2.4

São usados para relações estruturais fixas.

Exemplos:

• em AST_IF:
  • first = condição
  • second = bloco then
  • third = ramo else
• em AST_ASSIGN:
  • first = expressão do lado direito
• em AST_LOOP:
  • first = condição opcional
  • second = corpo

children12.3.2.5

É usado quando a quantidade de filhos não é fixa.

Exemplos:

• AST_PROGRAM armazena suas declarações em children;
• AST_FUNCTION armazena seus parâmetros em children;
• AST_BLOCK armazena suas declarações internas em children;
• AST_CALL armazena seus argumentos em children.

Implementando src/compiler/ast.c12.4

Agora substitua src/compiler/ast.c pelo código abaixo.

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

static void ast_print_tree(FILE *stream, const AstNode *node, const char *prefix, bool is_last);

static void *xrealloc(void *pointer, size_t size) {
    void *result = realloc(pointer, size);
    if (result == NULL) {
        fprintf(stderr, "Erro: memória insuficiente.\n");
        exit(74);
    }
    return result;
}

AstNode *ast_new_node(AstKind kind) {
    AstNode *node = (AstNode *)calloc(1, sizeof(AstNode));
    if (node == NULL) {
        fprintf(stderr, "Erro: memória insuficiente.\n");
        exit(74);
    }

    node->kind = kind;
    return node;
}

void ast_add_child(AstNode *node, AstNode *child) {
    if (node->children.count == node->children.capacity) {
        int old_capacity = node->children.capacity;
        int new_capacity = old_capacity < 8 ? 8 : old_capacity * 2;
        node->children.items = (AstNode **)xrealloc(node->children.items,
                                                    sizeof(AstNode *) * new_capacity);
        node->children.capacity = new_capacity;
    }

    node->children.items[node->children.count++] = child;
}

static void print_token(FILE *stream, Token token) {
    fprintf(stream, "%.*s", token.length, token.start);
}

static void build_child_prefix(char *buffer, size_t size, const char *prefix, bool is_last) {
    snprintf(buffer, size, "%s%s", prefix, is_last ? "    " : "│   ");
}

static void print_branch(FILE *stream, const char *prefix, bool is_last, const char *label) {
    fprintf(stream, "%s%s%s\n", prefix, is_last ? "└── " : "├── ", label);
}

static void print_node_label(FILE *stream, const AstNode *node) {
    switch (node->kind) {
        case AST_PROGRAM:
            fputs("Programa", stream);
            break;

        case AST_FUNCTION:
            fputs("Funcao nome=", stream);
            print_token(stream, node->token);
            fputs(" retorno=", stream);
            print_token(stream, node->extra);
            break;

        case AST_PARAM:
            fputs("Parametro nome=", stream);
            print_token(stream, node->token);
            fputs(" tipo=", stream);
            print_token(stream, node->extra);
            break;

        case AST_BLOCK:
            fputs("Bloco", stream);
            break;

        case AST_VAR_DECL:
            fputs("DeclVar nome=", stream);
            print_token(stream, node->token);
            fputs(" tipo=", stream);
            print_token(stream, node->extra);
            break;

        case AST_IF:
            fputs("Se", stream);
            break;

        case AST_LOOP:
            fputs("Laco", stream);
            break;

        case AST_RETURN:
            fputs("Retorno", stream);
            break;

        case AST_BREAK:
            fputs("Pare", stream);
            break;

        case AST_CONTINUE:
            fputs("Continua", stream);
            break;

        case AST_ASSIGN:
            fputs("Atrib nome=", stream);
            print_token(stream, node->token);
            break;

        case AST_EXPR_STMT:
            fputs("ComandoExpr", stream);
            break;

        case AST_BINARY:
            fputs("Binario op=", stream);
            print_token(stream, node->token);
            break;

        case AST_UNARY:
            fputs("Unario op=", stream);
            print_token(stream, node->token);
            break;

        case AST_CALL:
            fputs("Chamada", stream);
            break;

        case AST_IDENTIFIER:
            fputs("Identificador nome=", stream);
            print_token(stream, node->token);
            break;

        case AST_NUMBER:
            fputs("Numero valor=", stream);
            print_token(stream, node->token);
            break;

        case AST_STRING:
            fputs("Texto valor=", stream);
            print_token(stream, node->token);
            break;

        case AST_CHAR:
            fputs("Caractere valor=", stream);
            print_token(stream, node->token);
            break;

        case AST_BOOL:
            fputs("Booleano valor=", stream);
            fputs(node->token.type == TOK_KW_TRUE ? "true" : "false", stream);
            break;
    }
}

static void print_labeled_child(FILE *stream,
                                const char *prefix,
                                bool is_last,
                                const char *label,
                                const AstNode *child) {
    char child_prefix[1024];

    print_branch(stream, prefix, is_last, label);
    build_child_prefix(child_prefix, sizeof(child_prefix), prefix, is_last);
    ast_print_tree(stream, child, child_prefix, true);
}

static void ast_print_tree(FILE *stream, const AstNode *node, const char *prefix, bool is_last) {
    char child_prefix[1024];

    if (node == NULL) {
        return;
    }

    fprintf(stream, "%s%s", prefix, is_last ? "└── " : "├── ");
    print_node_label(stream, node);
    fputc('\n', stream);

    build_child_prefix(child_prefix, sizeof(child_prefix), prefix, is_last);

    switch (node->kind) {
        case AST_PROGRAM:
            for (int i = 0; i < node->children.count; i++) {
                ast_print_tree(stream,
                               node->children.items[i],
                               child_prefix,
                               i == node->children.count - 1);
            }
            break;

        case AST_FUNCTION:
            for (int i = 0; i < node->children.count; i++) {
                ast_print_tree(stream,
                               node->children.items[i],
                               child_prefix,
                               i == node->children.count - 1 && node->first == NULL);
            }
            if (node->first != NULL) {
                ast_print_tree(stream, node->first, child_prefix, true);
            }
            break;

        case AST_BLOCK:
            for (int i = 0; i < node->children.count; i++) {
                ast_print_tree(stream,
                               node->children.items[i],
                               child_prefix,
                               i == node->children.count - 1);
            }
            break;

        case AST_VAR_DECL:
        case AST_RETURN:
        case AST_ASSIGN:
        case AST_EXPR_STMT:
        case AST_UNARY:
            if (node->first != NULL) {
                ast_print_tree(stream, node->first, child_prefix, true);
            }
            break;

        case AST_IF:
            print_labeled_child(stream, child_prefix, node->third == NULL && node->second == NULL, "Condicao", node->first);
            print_labeled_child(stream, child_prefix, node->third == NULL, "Entao", node->second);
            if (node->third != NULL) {
                print_labeled_child(stream, child_prefix, true, "Senao", node->third);
            }
            break;

        case AST_LOOP:
            if (node->first != NULL) {
                print_labeled_child(stream, child_prefix, node->second == NULL, "Condicao", node->first);
            }
            if (node->second != NULL) {
                ast_print_tree(stream, node->second, child_prefix, true);
            }
            break;

        case AST_BINARY:
            if (node->first != NULL) {
                ast_print_tree(stream, node->first, child_prefix, false);
            }
            if (node->second != NULL) {
                ast_print_tree(stream, node->second, child_prefix, true);
            }
            break;

        case AST_CALL:
            print_labeled_child(stream,
                                child_prefix,
                                node->children.count == 0,
                                "Alvo",
                                node->first);
            for (int i = 0; i < node->children.count; i++) {
                print_labeled_child(stream,
                                    child_prefix,
                                    i == node->children.count - 1,
                                    "Argumento",
                                    node->children.items[i]);
            }
            break;

        case AST_PARAM:
        case AST_BREAK:
        case AST_CONTINUE:
        case AST_IDENTIFIER:
        case AST_NUMBER:
        case AST_STRING:
        case AST_CHAR:
        case AST_BOOL:
            break;
    }
}

void ast_print(FILE *stream, const AstNode *node) {
    if (node == NULL) {
        return;
    }

    print_node_label(stream, node);
    fputc('\n', stream);

    for (int i = 0; i < node->children.count; i++) {
        ast_print_tree(stream, node->children.items[i], "", i == node->children.count - 1);
    }
}

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

    ast_free(node->first);
    ast_free(node->second);
    ast_free(node->third);

    for (int i = 0; i < node->children.count; i++) {
        ast_free(node->children.items[i]);
    }

    free(node->children.items);
    free(node);
}

O que mudou conceitualmente na AST12.4.1

Aqui há três diferenças importantes em relação ao capítulo anterior.

Não existem mais construtores específicos para cada forma de expressão12.4.1.1

Antes havia funções como ast_make_binary e ast_make_literal. Agora usamos um construtor genérico:

AstNode *ast_new_node(AstKind kind);

Depois disso, o próprio parser preenche os campos token, extra, first, second, third e children.

Isso simplifica muito a implementação do parser estrutural.

A AST agora suporta filhos em quantidade variável12.4.1.2

Sem children, seria muito difícil representar:

• vários parâmetros de função;
• várias declarações dentro de um bloco;
• vários argumentos de chamada.

Por isso ast_add_child se torna uma peça central.

A impressão da árvore fica mais semântica12.4.1.3

Em vez de imprimir apenas +, * e id(x), a AST agora imprime rótulos mais ricos, como:

• Funcao nome=main retorno=void
• DeclVar nome=x tipo=int
• Atrib nome=x
• Binario op=%
• Chamada

Isso deixa a inspeção do programa muito mais clara.

Atualizando a definição do parser12.5

Agora precisamos substituir o parser mínimo do capítulo 11 pela versão final usada no projeto atual.

Substituindo include/compiler/parser.h12.5.1

Substitua include/compiler/parser.h por:

#ifndef COMPILER_PARSER_H_
#define COMPILER_PARSER_H_

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

typedef struct {
    Lexer lexer;
    Token previous;
    Token current;
    Token next;
    bool had_error;
    FILE *error_stream;
} Parser;

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

#endif

Por que agora existe next12.5.2

No capítulo 11, current e previous bastavam para parsear expressões.

Agora precisamos olhar um token à frente para distinguir construções como estas:

x: int = 5
x = 5

No primeiro caso, x inicia uma declaração de variável.
No segundo caso, x inicia uma atribuição.

Sem next, o parser teria que consumir tokens prematuramente ou criar mecanismos de retrocesso. Com next, basta fazer perguntas como:

parser_check(parser, TOK_IDENTIFIER) && parser_check_next(parser, TOK_COLON)

ou:

parser_check(parser, TOK_IDENTIFIER) && parser_check_next(parser, TOK_ASSIGN)

Por que agora existe error_stream12.5.3

No parser do capítulo 11, os erros eram enviados diretamente para stderr. Agora o parser recebe o fluxo onde quer escrever erros.

Isso é útil porque:

• o main.c final passa stderr normalmente;
• testes automatizados podem capturar a saída com mais flexibilidade;
• o parser deixa de depender rigidamente de um fluxo fixo.

Implementando o parser estrutural final12.6

Agora substitua src/compiler/parser.c pela versão final do projeto:

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

static void parser_advance(Parser *parser);
static bool parser_check(Parser *parser, TokenType type);
static bool parser_check_next(Parser *parser, TokenType type);
static bool parser_match(Parser *parser, TokenType type);
static Token parser_consume(Parser *parser, TokenType type, const char *message);
static void parser_error_at(Parser *parser, Token token, const char *message);
static AstNode *parse_declaration(Parser *parser);
static AstNode *parse_function(Parser *parser);
static AstNode *parse_var_decl(Parser *parser);
static AstNode *parse_statement(Parser *parser);
static AstNode *parse_block(Parser *parser);
static AstNode *parse_if(Parser *parser);
static AstNode *parse_loop(Parser *parser);
static AstNode *parse_return(Parser *parser);
static AstNode *parse_assignment(Parser *parser);
static AstNode *parse_expression_statement(Parser *parser);
static Token parse_type(Parser *parser);
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_call(Parser *parser);
static AstNode *parse_primary(Parser *parser);

void parser_init(Parser *parser, const char *source, FILE *error_stream) {
    lexer_init(&parser->lexer, source);
    parser->previous.type = TOK_ERROR;
    parser->previous.start = "";
    parser->previous.length = 0;
    parser->previous.line = 1;
    parser->current = lexer_next_token(&parser->lexer);
    parser->next = lexer_next_token(&parser->lexer);
    parser->had_error = false;
    parser->error_stream = error_stream;
}

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

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

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

static bool parser_match(Parser *parser, TokenType type) {
    if (!parser_check(parser, type)) {
        return false;
    }

    parser_advance(parser);
    return true;
}

static void parser_error_at(Parser *parser, Token token, const char *message) {
    if (parser->had_error) {
        return;
    }

    parser->had_error = true;
    fprintf(parser->error_stream, "[linha %d] Erro perto de ", token.line);

    if (token.type == TOK_EOF) {
        fputs("fim do arquivo", parser->error_stream);
    } else if (token.type == TOK_ERROR) {
        fprintf(parser->error_stream, "'%.*s'", token.length, token.start);
    } else {
        fprintf(parser->error_stream, "'%.*s'", token.length, token.start);
    }

    fprintf(parser->error_stream, ": %s\n", message);
}

static Token parser_consume(Parser *parser, TokenType type, const char *message) {
    if (parser_check(parser, type)) {
        Token token = parser->current;
        parser_advance(parser);
        return token;
    }

    parser_error_at(parser, parser->current, message);
    return parser->current;
}

static Token parse_type(Parser *parser) {
    switch (parser->current.type) {
        case TOK_KW_INT:
        case TOK_KW_FLOAT:
        case TOK_KW_VOID:
        case TOK_KW_BOOL:
        case TOK_KW_CHAR:
        case TOK_KW_STRING: {
            Token type = parser->current;
            parser_advance(parser);
            return type;
        }
        default:
            parser_error_at(parser, parser->current, "Esperado um tipo.");
            return parser->current;
    }
}

AstNode *parser_parse(Parser *parser) {
    AstNode *program = ast_new_node(AST_PROGRAM);

    while (!parser_check(parser, TOK_EOF) && !parser->had_error) {
        AstNode *declaration = parse_declaration(parser);
        if (parser->had_error) {
            ast_free(declaration);
            break;
        }
        ast_add_child(program, declaration);
    }

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

    return program;
}

static AstNode *parse_declaration(Parser *parser) {
    if (parser_match(parser, TOK_KW_FN)) {
        return parse_function(parser);
    }

    if (parser_check(parser, TOK_IDENTIFIER) && parser_check_next(parser, TOK_COLON)) {
        return parse_var_decl(parser);
    }

    return parse_statement(parser);
}

static AstNode *parse_function(Parser *parser) {
    AstNode *function = ast_new_node(AST_FUNCTION);
    function->token = parser_consume(parser, TOK_IDENTIFIER, "Esperado nome da funcao.");
    parser_consume(parser, TOK_LPAREN, "Esperado '(' apos o nome da funcao.");

    if (!parser_check(parser, TOK_RPAREN)) {
        do {
            AstNode *param = ast_new_node(AST_PARAM);
            param->token = parser_consume(parser, TOK_IDENTIFIER, "Esperado nome do parametro.");
            parser_consume(parser, TOK_COLON, "Esperado ':' apos o nome do parametro.");
            param->extra = parse_type(parser);
            ast_add_child(function, param);
        } while (parser_match(parser, TOK_COMMA));
    }

    parser_consume(parser, TOK_RPAREN, "Esperado ')' apos os parametros.");
    parser_consume(parser, TOK_ARROW, "Esperado '->' apos os parametros.");
    function->extra = parse_type(parser);
    function->first = parse_block(parser);
    return function;
}

static AstNode *parse_var_decl(Parser *parser) {
    AstNode *var_decl = ast_new_node(AST_VAR_DECL);
    var_decl->token = parser_consume(parser, TOK_IDENTIFIER, "Esperado nome da variavel.");
    parser_consume(parser, TOK_COLON, "Esperado ':' apos o nome da variavel.");
    var_decl->extra = parse_type(parser);
    parser_consume(parser, TOK_ASSIGN, "Esperado '=' apos o tipo da variavel.");
    var_decl->first = parse_expression(parser);
    return var_decl;
}

static AstNode *parse_statement(Parser *parser) {
    if (parser_check(parser, TOK_LBRACE)) {
        return parse_block(parser);
    }

    if (parser_match(parser, TOK_KW_IF)) {
        return parse_if(parser);
    }

    if (parser_match(parser, TOK_KW_LOOP)) {
        return parse_loop(parser);
    }

    if (parser_match(parser, TOK_KW_RETURN)) {
        return parse_return(parser);
    }

    if (parser_match(parser, TOK_KW_BREAK)) {
        return ast_new_node(AST_BREAK);
    }

    if (parser_match(parser, TOK_KW_CONTINUE)) {
        return ast_new_node(AST_CONTINUE);
    }

    if (parser_check(parser, TOK_IDENTIFIER) && parser_check_next(parser, TOK_ASSIGN)) {
        return parse_assignment(parser);
    }

    return parse_expression_statement(parser);
}

static AstNode *parse_block(Parser *parser) {
    AstNode *block = ast_new_node(AST_BLOCK);

    parser_consume(parser, TOK_LBRACE, "Esperado '{' antes do bloco.");

    while (!parser_check(parser, TOK_RBRACE) && !parser_check(parser, TOK_EOF) && !parser->had_error) {
        AstNode *declaration = parse_declaration(parser);
        if (parser->had_error) {
            ast_free(declaration);
            break;
        }
        ast_add_child(block, declaration);
    }

    parser_consume(parser, TOK_RBRACE, "Esperado '}' apos o bloco.");
    return block;
}

static AstNode *parse_if(Parser *parser) {
    AstNode *node = ast_new_node(AST_IF);
    node->first = parse_expression(parser);
    node->second = parse_block(parser);

    if (parser_match(parser, TOK_KW_ELSE)) {
        if (parser_match(parser, TOK_KW_IF)) {
            node->third = parse_if(parser);
        } else {
            node->third = parse_block(parser);
        }
    }

    return node;
}

static AstNode *parse_loop(Parser *parser) {
    AstNode *node = ast_new_node(AST_LOOP);

    if (parser_check(parser, TOK_LBRACE)) {
        node->second = parse_block(parser);
        return node;
    }

    node->first = parse_expression(parser);
    node->second = parse_block(parser);
    return node;
}

static AstNode *parse_return(Parser *parser) {
    AstNode *node = ast_new_node(AST_RETURN);

    if (!parser_check(parser, TOK_RBRACE) && !parser_check(parser, TOK_EOF)) {
        node->first = parse_expression(parser);
    }

    return node;
}

static AstNode *parse_assignment(Parser *parser) {
    AstNode *node = ast_new_node(AST_ASSIGN);
    node->token = parser_consume(parser, TOK_IDENTIFIER, "Esperado alvo da atribuicao.");
    parser_consume(parser, TOK_ASSIGN, "Esperado '=' apos o alvo da atribuicao.");
    node->first = parse_expression(parser);
    return node;
}

static AstNode *parse_expression_statement(Parser *parser) {
    AstNode *expr_stmt = ast_new_node(AST_EXPR_STMT);
    expr_stmt->first = parse_expression(parser);

    if (expr_stmt->first != NULL && expr_stmt->first->kind != AST_CALL) {
        parser_error_at(parser, parser->previous, "Esperado comando de chamada de funcao.");
    }

    return expr_stmt;
}

static AstNode *make_binary(Token operator, AstNode *left, AstNode *right) {
    AstNode *node = ast_new_node(AST_BINARY);
    node->token = operator;
    node->first = left;
    node->second = right;
    return node;
}

static AstNode *make_unary(Token operator, AstNode *operand) {
    AstNode *node = ast_new_node(AST_UNARY);
    node->token = operator;
    node->first = operand;
    return node;
}

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

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

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

    return expr;
}

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

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

    return expr;
}

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

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

    return expr;
}

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

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

    return expr;
}

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

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

    return expr;
}

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

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

    return expr;
}

static AstNode *parse_unary(Parser *parser) {
    if (parser_match(parser, TOK_NOT) || parser_match(parser, TOK_MINUS)) {
        Token operator = parser->previous;
        AstNode *operand = parse_unary(parser);
        return make_unary(operator, operand);
    }

    return parse_call(parser);
}

static AstNode *parse_call(Parser *parser) {
    AstNode *expr = parse_primary(parser);

    while (parser_match(parser, TOK_LPAREN)) {
        AstNode *call = ast_new_node(AST_CALL);
        call->first = expr;

        if (!parser_check(parser, TOK_RPAREN)) {
            do {
                ast_add_child(call, parse_expression(parser));
            } while (parser_match(parser, TOK_COMMA));
        }

        parser_consume(parser, TOK_RPAREN, "Esperado ')' apos os argumentos.");
        expr = call;
    }

    return expr;
}

static AstNode *parse_primary(Parser *parser) {
    AstNode *node = NULL;

    switch (parser->current.type) {
        case TOK_NUMBER:
            node = ast_new_node(AST_NUMBER);
            node->token = parser->current;
            parser_advance(parser);
            return node;

        case TOK_STRING:
            node = ast_new_node(AST_STRING);
            node->token = parser->current;
            parser_advance(parser);
            return node;

        case TOK_CHAR:
            node = ast_new_node(AST_CHAR);
            node->token = parser->current;
            parser_advance(parser);
            return node;

        case TOK_KW_TRUE:
        case TOK_KW_FALSE:
            node = ast_new_node(AST_BOOL);
            node->token = parser->current;
            parser_advance(parser);
            return node;

        case TOK_IDENTIFIER:
            node = ast_new_node(AST_IDENTIFIER);
            node->token = parser->current;
            parser_advance(parser);
            return node;

        case TOK_LPAREN: {
            parser_advance(parser);
            node = parse_expression(parser);
            parser_consume(parser, TOK_RPAREN, "Esperado ')' apos a expressao.");
            return node;
        }

        case TOK_ERROR:
            parser_error_at(parser, parser->current, parser->current.start);
            return NULL;

        default:
            parser_error_at(parser, parser->current, "Esperada uma expressao.");
            return NULL;
    }
}

Entendendo a nova organização do parser12.7

Agora que a implementação inteira está no arquivo, vamos percorrer a lógica por partes.

parser_init com três posições: previous, current e next12.7.1

Logo na inicialização, o parser já consome dois tokens do lexer:

parser->current = lexer_next_token(&parser->lexer);
parser->next = lexer_next_token(&parser->lexer);

Isso significa que, desde o começo, o parser já tem acesso ao token atual e ao próximo token.

Esse pequeno lookahead é o que viabiliza decisões estruturais sem retrocesso.

parser_parse agora constrói um AST_PROGRAM12.7.2

No capítulo 11, a função principal chamava parse_expression e devolvia uma única árvore de expressão.

Agora o parser faz isto:

AstNode *program = ast_new_node(AST_PROGRAM);

while (!parser_check(parser, TOK_EOF) && !parser->had_error) {
    AstNode *declaration = parse_declaration(parser);
    ast_add_child(program, declaration);
}

Ou seja, a raiz da AST passa a ser sempre um programa, e suas declarações ficam armazenadas em children.

parse_declaration separa topo do programa12.7.3

Essa função decide qual grande construção começa no ponto atual.

O raciocínio é:

1. se vier fn, então é função;
2. se vier IDENT :, então é declaração de variável;
3. caso contrário, tratamos como comando.

Esse é um ótimo exemplo de por que next foi adicionado ao parser.

parse_function12.7.4

Essa função monta um nó AST_FUNCTION com:

• nome em token;
• tipo de retorno em extra;
• parâmetros em children;
• corpo em first.

Essa convenção é a mesma usada pela impressão da AST em ast.c.

parse_var_decl12.7.5

Reconhece entradas como:

x: int = 5

e constrói um AST_VAR_DECL com:

• nome em token;
• tipo em extra;
• expressão inicializadora em first.

Note que, neste marco, a inicialização é obrigatória.

parse_statement12.7.6

Essa função centraliza a decisão entre:

• bloco;
• if;
• loop;
• return;
• break;
• continue;
• atribuição;
• chamada de função como comando.

Essa última parte é particularmente importante: uma expressão isolada só é aceita como comando se o resultado for um AST_CALL.

É por isso que existe esta checagem:

if (expr_stmt->first != NULL && expr_stmt->first->kind != AST_CALL) {
    parser_error_at(parser, parser->previous, "Esperado comando de chamada de funcao.");
}

Ou seja, algo como:

foo(1, 2)

é permitido como comando, mas algo como:

x + 1

não é.

parse_block12.7.7

O bloco é uma peça estrutural importante porque ele contém outras declarações e comandos. Portanto, ele não chama parse_statement diretamente em loop. Ele chama parse_declaration.

Isso permite coisas como:

{
    x: int = 5
    if x > 0 {
        print(x)
    }
}

parse_if12.7.8

Aqui aparece um detalhe elegante: else if é tratado recursivamente.

if (parser_match(parser, TOK_KW_ELSE)) {
    if (parser_match(parser, TOK_KW_IF)) {
        node->third = parse_if(parser);
    } else {
        node->third = parse_block(parser);
    }
}

Isso faz com que else if vire simplesmente um ramo else cujo conteúdo é outro nó AST_IF.

parse_loop12.7.9

Essa função reconhece dois formatos:

loop {
    ...
}

e:

loop x < 10 {
    ...
}

No primeiro caso, o laço é infinito e first fica NULL.
No segundo, first guarda a condição.

parse_call12.7.10

No capítulo 11, o parser parava em parse_primary. Agora ele possui um nível intermediário parse_call, que permite reconhecer chamadas encadeadas sobre um primário.

Se a entrada for:

print(factorial(value))

o parser:

1. reconhece print como identificador;
2. vê (;
3. cria um AST_CALL cujo first é o callee;
4. armazena cada argumento em children.

Essa é a mudança que permite chamadas tanto em expressões quanto em comandos.

Finalizando o main.c12.8

Agora vamos substituir o main.c temporário do capítulo 11 pela interface final do projeto.

Substitua src/main.c por:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "compiler/ast.h"
#include "compiler/lexer.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 fileSize = ftell(file);
    rewind(file);

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

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

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

static int run_lexer_mode(const char *source) {
    Lexer lexer;
    lexer_init(&lexer, source);

    Token token;
    do {
        token = lexer_next_token(&lexer);
        token_println(&token);
    } while (token.type != TOK_EOF && token.type != TOK_ERROR);

    return 0;
}

static int run_parser_mode(const char *source) {
    Parser parser;
    parser_init(&parser, source, stderr);

    AstNode *program = parser_parse(&parser);
    if (program == NULL) {
        return 65;
    }

    ast_print(stdout, program);
    ast_free(program);
    return 0;
}

int main(int argc, char* argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Uso: compiler <lex|parse> <arquivo>\n");
        return 64;
    }

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

    int result = 0;

    if (strcmp(argv[1], "lex") == 0) {
        result = run_lexer_mode(source);
    } else if (strcmp(argv[1], "parse") == 0) {
        result = run_parser_mode(source);
    } else {
        fprintf(stderr, "Uso: compiler <lex|parse> <arquivo>\n");
        free(source);
        return 64;
    }

    free(source);
    return result;
}

Antes, o executável estava temporariamente voltado para um único fluxo de parsing de expressões. Agora ele passa a suportar dois modos explícitos:

• lex, para imprimir a sequência de tokens;
• parse, para imprimir a AST do programa.

Isso é importante porque o compilador volta a expor as duas fases que já temos implementadas.

Como a interface final do projeto também mantém o modo léxico, vale alinhar o token_print com o estado atual do repositório. Substitua src/compiler/token.c por:

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

void token_print(Token *token) {
    printf("<%s, \"%.*s\", linha=%d>",
           TokenNames[token->type],
           token->length,
           token->start,
           token->line);
}

void token_println(Token *token) {
    token_print(token);
    printf("\n");
}

Esse ajuste é pequeno, mas útil. Ele faz a saída do lexer carregar também a linha em que o token foi encontrado, o que ajuda muito em testes e em depuração.

Reorganizando os testes do projeto12.9

Em vez de pedir que você crie manualmente cada arquivo de teste desta etapa, vamos fazer algo mais prático: substituir a pasta tests inteira pela versão final já preparada. Baixe testes-c2.zip. Esse arquivo contém a estrutura final da suíte de testes usada no estado atual do repositório.

1. Remova ou renomeie a pasta tests antiga do projeto.
2. Extraia testes-c2.zip na raiz do projeto.
3. Verifique se, ao final, você ficou novamente com uma pasta tests/.

Depois da substituição, a estrutura ficará assim:

tests/
├── lexer/
│   ├── expected/
│   └── input/
├── parser/
│   ├── contract.md
│   ├── expected/
│   └── input/
└── run_tests.sh

As mudanças mais importantes são:

• os testes do lexer deixaram de ficar todos soltos em tests/ e passaram para tests/lexer/;
• os testes do parser agora ficam em tests/parser/;
• cada suíte passou a ter input/ e expected/ separados;
• o arquivo tests/parser/contract.md documenta a gramática que essa etapa está validando;
• o script tests/run_tests.sh agora sabe rodar as duas fases do compilador;
• ele aceita lexer, parser e all como alvo.

Essa reorganização melhora muito a manutenção do projeto, porque separa claramente o que pertence à análise léxica e o que pertence à análise sintática.

Com a nova pasta tests no lugar, compile o projeto:

cmake -B build
cmake --build build

Agora rode a suíte do lexer:

./tests/run_tests.sh lexer

Saída esperada:

=============================================
   EXECUTANDO TESTES DE LEXER
=============================================
  [OK] lexer/01_delimiters
  [OK] lexer/02_simple_operators
  [OK] lexer/03_lookahead_tokens
  [OK] lexer/04_logical_operators
  [OK] lexer/05_keywords
  [OK] lexer/06_identifiers
  [OK] lexer/07_numbers
  [OK] lexer/08_strings
  [OK] lexer/09_chars
  [OK] lexer/10_comments
  [OK] lexer/11_invalid_number_error
  [OK] lexer/12_single_ampersand_error
  [OK] lexer/13_complete_program
  [OK] lexer/14_modulo_operator
  [OK] lexer/15_single_pipe_error
  [OK] lexer/16_unterminated_string_error

=============================================
   RESULTADO: 16 PASSARAM | 0 FALHARAM | 16 TOTAL
=============================================

Agora rode a suíte do parser:

./tests/run_tests.sh parser

Saída esperada:

=============================================
   EXECUTANDO TESTES DE PARSER
=============================================
  [OK] parser/01_variable_declaration
  [OK] parser/02_function_declaration
  [OK] parser/03_expression_precedence
  [OK] parser/04_control_flow
  [OK] parser/05_complete_program
  [OK] parser/06_infinite_loop
  [OK] parser/07_missing_initializer
  [OK] parser/08_missing_block_end
  [OK] parser/09_invalid_parameter

=============================================
   RESULTADO: 9 PASSARAM | 0 FALHARAM | 9 TOTAL
=============================================

Se quiser rodar tudo de uma vez:

./tests/run_tests.sh all

Testando diretamente os dois modos do compilador12.9.1

Você também pode testar os modos manualmente.

Modo léxico:

./build/compiler lex tests/lexer/input/14_modulo_operator.slang

Modo sintático:

./build/compiler parse tests/parser/input/05_complete_program.slang

Esse segundo comando deve imprimir a árvore sintática completa do programa de teste.

Próximos Passos12.10

No próximo capítulo, Parsing LL(1), vamos formalizar a decisão preditiva com FIRST, FOLLOW e a tabela de análise sintática.