Aula 07: Análise Sintática: Fundamentos

Data de Publicação

25/03/2026

Data de Modificação

08/03/2026

Objetivos

Ao final desta aula, você será capaz de:

  • Explicar o papel do parser no pipeline: verificar estrutura gramatical e construir a árvore de análise.
  • Definir gramática livre de contexto (GLC) e os conceitos de derivação e árvore de derivação (parse tree).
  • Justificar por que expressões regulares não bastam para a análise sintática (estruturas aninhadas/recursivas).
  • Diferenciar parse tree (árvore concreta) de AST (árvore sintática abstrata) e seu uso nas fases seguintes.

Motivação em Engenharia de Computação

O analisador léxico garante que as “palavras” (tokens) existem; o parser garante que as frases fazem sentido segundo a gramática da linguagem.

  • Erros sintáticos bem reportados (mensagem clara, linha/coluna) são essenciais para produtividade.
  • A gramática escolhida impacta diretamente a implementação do parser (LL vs LR) e a manutenção.
  • A árvore produzida (parse tree ou AST) é a estrutura sobre a qual repousam semântica, otimização e geração de código.

Posição do parser no pipeline

flowchart LR
  Tokens[Tokens] --> Parser[Parser]
  Parser --> AST[AST]
  AST --> Sem[Semântica]
  AST --> Codegen[Codegen]

O parser consome a sequência de tokens fornecida pelo scanner e produz uma árvore (parse tree ou, mais comum, AST). Essa árvore é a entrada da análise semântica e da geração de código.

Conteúdo

1. Por que não apenas Expressões Regulares?

Expressões regulares (e autômatos finitos) são adequadas para padrões lineares e finitos (ou finitamente descritíveis): identificadores, números, comentários. Elas não conseguem descrever:

  • Parênteses balanceados: linguagens como \(\{ (^n )^n \mid n \ge 0 \}\) exigem “contagem” ilimitada, o que requer memória ilimitada (pilha). Autômatos finitos não têm pilha.
  • Aninhamento arbitrário: blocos begin ... end, expressões com parênteses ( ( a + b ) * c ), estruturas de controle aninhadas.

Para isso usamos gramáticas livres de contexto (GLC) e autômatos de pilha (ou algoritmos de parsing que mantêm uma pilha implicitamente).

2. Gramáticas Livres de Contexto (GLC)

Uma GLC é uma quadrupla \(G = (V, T, P, S)\):

  • \(V\): conjunto de não terminais (variáveis), representando conceitos sintáticos (Expressão, Comando, Declaração, Bloco).
  • \(T\): conjunto de terminais (tokens): os átomos retornados pelo scanner (identificador, número, +, if, etc.).
  • \(P\): conjunto de produções (regras) da forma \(A \to \alpha\), onde \(A \in V\) e \(\alpha \in (V \cup T)^*\). Indica que \(A\) pode ser substituído pela string \(\alpha\).
  • \(S \in V\): símbolo inicial, a partir do qual todas as derivações começam.

Exemplo: produções para expressões aritméticas simples:

\[E \to E + T \mid T\] \[T \to T * F \mid F\] \[F \to \texttt{id} \mid ( E )\]

Aqui \(V = \{E, T, F\}\), \(T = \{\texttt{id}, +, *, (, )\}\), \(S = E\).

3. Derivação

Uma derivação é uma sequência de substituições: começando em \(S\), substituímos repetidamente um não terminal \(A\) pela string \(\alpha\) lado direito de alguma produção \(A \to \alpha\), até restar apenas terminais.

  • Derivação mais à esquerda: sempre substituímos o não terminal mais à esquerda.
  • Derivação mais à direita: sempre substituímos o não terminal mais à direita.

Uma string de terminais pertence à linguagem da gramática se existir pelo menos uma derivação de \(S\) até essa string. O parser é o algoritmo que, dada uma string de tokens, decide se ela pertence à linguagem e, em caso positivo, constrói uma derivação (ou uma árvore que a representa).

4. Árvore de derivação (Parse Tree)

A árvore de derivação (parse tree) representa visualmente uma derivação:

  • Raiz: símbolo inicial \(S\).
  • Folhas: terminais (tokens), da esquerda para a direita formam a string de entrada.
  • Nós internos: não terminais; cada nó \(A\) com filhos corresponde a uma produção \(A \to \alpha\).

A estrutura da árvore captura precedência e associatividade. Por exemplo, na gramática acima, para id + id * id, o nó * fica abaixo do nó +, indicando que a multiplicação tem maior precedência e é avaliada primeiro.

flowchart TB
  E[E] --> E2[E]
  E --> plus[+]
  E --> T[T]
  E2 --> T2[T]
  T2 --> F1[F]
  F1 --> id1[id]
  T --> F2[F]
  F2 --> ast[*]
  F2 --> F3[F]
  F3 --> id2[id]
  ast --> id3[id]

(Em uma notação mais precisa, a árvore teria um nó para cada símbolo da produção; o diagrama acima é esquemático.)

5. Parse Tree vs AST

  • Parse Tree (árvore concreta): reflete todas as produções usadas na derivação, incluindo nós “sintáticos” puros (ex.: um nó para cada E, T, F). Pode ser verbosa e redundante.
  • AST (Abstract Syntax Tree): simplifica a árvore, mantendo apenas a estrutura lógica relevante para semântica e código: operadores, operandos, comandos, declarações. Parênteses e vírgulas desaparecem; nós redundantes são fundidos.

Na prática, muitos compiladores constroem diretamente uma AST durante o parsing (cada regra gramatical gera nós da AST em vez de uma parse tree completa). A AST é a representação que as fases seguintes (análise semântica, geração de IR) utilizam.

6. O que o parser deve fazer

  1. Reconhecer: decidir se a sequência de tokens pertence à linguagem (sim/não).
  2. Construir a árvore: produzir parse tree ou AST.
  3. Reportar erros: em caso de token inesperado ou fim prematuro, indicar localização e, quando possível, recuperar para continuar a análise e encontrar mais erros.

Conexões com o projeto Mini-Pascal

  • A gramática de Mini-Pascal é a base do parser manual (Etapa 3) e da gramática ANTLR (Etapa 4).
  • Decisões na gramática (como representar condicionais, laços, expressões) afetam a forma da AST, a facilidade da análise semântica e o mapeamento para código intermediário.
  • A AST definida na Etapa 1 é preenchida pelo parser nas etapas 3 e 4.

Resumo

  • O parser verifica a estrutura gramatical e constrói a árvore (parse tree ou AST).
  • GLC são necessárias para estruturas aninhadas/recursivas; ERs não bastam.
  • Derivação = sequência de substituições; parse tree = representação em árvore.
  • AST simplifica a árvore para o que importa em semântica e codegen.

Perguntas de reflexão

  • Por que uma gramática correta pode ser ruim para implementação de um parser? (Dica: ambiguidade, recursão à esquerda.)
  • Quando você preferiria uma gramática com muitos níveis (E, T, F) em vez de uma mais “plana”?

Referências

  • Aho et al. (2006). Compilers: Principles, Techniques, and Tools. Cap. 4.
  • Cooper & Torczon (2011). Engineering a Compiler.

Materiais da aula

Última atualização: 08/03/2026

De volta ao topo