Aula 18 - Análise Sintática e Árvores de Sintaxe Abstrata (AST) 🌳

📑 1. Fundamentos Teóricos & Análise Técnica

A segunda fase da esteira de compilação é a Análise Sintática (Parsing). Enquanto o analisador léxico opera sobre expressões regulares e caracteres isolados, o parser opera sobre Gramáticas Livres de Contexto (Context-Free Grammars - CFG) descritas formalmente na notação EBNF (Extended Backus-Naur Form).

O objetivo do Parser é verificar se a sequência linear de tokens obedece às regras estruturais da linguagem e construir uma representação hierárquica em árvore em memória: a Árvore de Sintaxe Abstrata (AST - Abstract Syntax Tree).

Diferente da Parse Tree concreta (que armazena detalhes triviais como parênteses ou pontos-e-vírgulas), a AST retém estritamente os nós semânticos de operação: - Nós de Expressão Binária (BinaryOp: +) - Nós Literais (Literal: 42) - Nós de Declaração de Variável (VarDeclaration)

O algoritmo mais pedagógico e extensivamente adotado em compiladores industriais modernos (como GCC, Clang e Rustc) é o Parser Descendente Recursivo (Recursive Descent Parser) com tratamento de precedência de operadores via Pratt Parsing.

📐 Arquitetura Conceitual & Diagrama de Fluxo

graph TD
    Tokens["Tokens: 'let total = x + 10;'"] --> Parser["Recursive Descent Parser (Gramática EBNF)"]
    Parser --> AST["Árvore de Sintaxe Abstrata (AST)"]
    AST --> VarDecl["Declaração: 'total'"]
    VarDecl --> AddOp["Operação Binária (+)"]
    AddOp --> VarX["Variável: 'x'"]
    AddOp --> Const10["Constante: '10'"]
    style Tokens fill:#e1f5fe,stroke:#01579b
    style Parser fill:#fff3e0,stroke:#e65100
    style AST fill:#e8f5e9,stroke:#2e7d32

🔍 Pilares e Diretrizes Técnicas

Nesta unidade, aprofundamos os seguintes conceitos fundamentais: - Precedência e Associatividade: Garantia de que a multiplicação * seja avaliada antes da adição + na hierarquia da árvore. - Recursão Mútua: Funções gramaticais que chamam umas às outras (parse_expression -> parse_term -> parse_factor). - Recuperação Graciosa de Erros (Panic Mode): Capacidade de avançar até o próximo ponto-e-vírgula após um erro sintático para continuar checando o arquivo. - Estruturas Polimórficas de AST: Cada nó da árvore representa uma construção formal do programa.

🛠️ 2. Implementação Prática em Compiladores e Gramáticas Livres de Contexto

Abaixo está a implementação técnica de referência, estruturada com padrões de engenharia de software e foco em robustez:

// ast_nodes.h (Estrutura de Nós da AST em C)
#include <stdlib.h>

typedef enum {
    NODE_INT_LITERAL,
    NODE_BINARY_OP,
    NODE_VAR_REF
} NodeType;

typedef struct ASTNode {
    NodeType type;
    union {
        int int_val;
        char var_name[64];
        struct {
            char op;
            struct ASTNode* left;
            struct ASTNode* right;
        } binary;
    } data;
} ASTNode;

// Construtor de nó binário
ASTNode* create_binary_node(char op, ASTNode* left, ASTNode* right) {
    ASTNode* node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = NODE_BINARY_OP;
    node->data.binary.op = op;
    node->data.binary.left = left;
    node->data.binary.right = right;
    return node;
}

💡 Análise Passo a Passo do Código

1. Union para Economia de Memória: Permite que o mesmo nó armazene tanto inteiros quanto nomes de variáveis ou ponteiros de subárvores.
2. Ponteiros Recursivos: left e right apontam para subárvores arbitrariamente complexas na Heap.
3. Representação Canônica: A árvore encapsula a ordem matemática de execução dos nós sem ambiguidades.

🎯 3. Próximos Passos & Sequência Didática