Aula 08: Gramáticas Livres de Contexto

Data de Publicação

25/03/2026

Data de Modificação

08/03/2026

Objetivos

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

  • Diagnosticar e resolver ambiguidade, recursão à esquerda e falta de fatoração em gramáticas livres de contexto.
  • Reescrever gramáticas para precedência e associatividade desejadas (camadas de expressões).
  • Aplicar as transformações clássicas: eliminação de recursão à esquerda e fatoração à esquerda, para obter gramáticas adequadas a parsers LL(1).
  • Relacionar essas técnicas com o projeto de linguagens e com ferramentas como ANTLR e Bison.

Motivação

Projetar gramáticas é central para quem quer:

  • Definir novas linguagens (de propósito geral ou DSLs).
  • Especificar formatos de arquivos, protocolos ou linguagens de configuração de forma rigorosa.
  • Entender e depurar mensagens de conflito em geradores de parser (ANTLR, Bison/Yacc).

Uma gramática “ingênua” raramente serve para implementação direta em parser preditivo (LL): ambiguidade, recursão à esquerda e ausência de fatoração impedem a construção de tabelas de parsing determinísticas.

Conteúdo

1. Revisão: GLC e árvores de derivação

Uma gramática livre de contexto (GLC) é uma quadrupla \(G = (V, T, P, S)\):

  • \(V\): símbolos não terminais (variáveis).
  • \(T\): símbolos terminais (tokens).
  • \(P\): produções da forma \(A \to \alpha\), com \(A \in V\) e \(\alpha \in (V \cup T)^*\).
  • \(S \in V\): símbolo inicial.

Uma derivação é uma sequência de substituições a partir de \(S\) até uma string de terminais. Uma árvore de derivação (parse tree) representa essa derivação: raiz \(S\), folhas terminais, nós internos não terminais expandidos por produções.

2. Ambiguidade

Definição: Uma gramática é ambígua se existe pelo menos uma string que possui mais de uma árvore de derivação (ou mais de uma derivação mais à esquerda/direita).

O compilador precisa de interpretação única: uma única árvore (e depois uma única AST) por programa. Gramáticas ambíguas impedem isso.

Exemplo clássico: expressões

Gramática “óbvia” para expressões aritméticas:

\[E \to E + E \mid E * E \mid \texttt{id}\]

Para a entrada a + b * c existem duas árvores:

flowchart TB
  subgraph arvore1 [Interpretação a + b * c]
    E1[E] --> E2[E]
    E1 --> plus[+]
    E1 --> E3[E]
    E2 --> id1[id a]
    E3 --> E4[E]
    E3 --> ast[*]
    E3 --> E5[E]
    E4 --> id2[id b]
    E5 --> id3[id c]
  end

Uma árvore agrupa (a + b) * c, a outra a + (b * c). Sem convenção adicional, o compilador não saberia qual escolher. A solução é remover a ambiguidade reescrevendo a gramática em camadas que impõem precedência (ex.: Termo para *, Expressão para +) e associatividade (ex.: recursão à esquerda para associar à esquerda).

Solução: gramática em camadas

Exemplo (expressões com +, * e átomos):

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

  • * fica “mais abaixo” na árvore (em \(T\)), portanto tem maior precedência que +.
  • Recursão à esquerda em \(E\) e \(T\) faz com que a + b + c seja agrupado como (a + b) + c (associatividade à esquerda).

Assim, cada string tem uma única árvore de derivação (para essa gramática).

3. Recursão à esquerda

Uma produção (ou sequência de produções) é recursiva à esquerda quando um não terminal \(A\) pode derivar uma forma que começa com \(A\): \(A \Rightarrow^+ A\alpha\).

Problema para parsers LL: em um parser descendente recursivo, a função que implementa \(A\) chamaria a si mesma sem consumir nenhum token, gerando loop infinito.

Eliminação de recursão à esquerda direta

Produção da forma \(A \to A\alpha \mid \beta\) (onde \(\beta\) não começa com \(A\)). Substituir por:

\[A \to \beta A'\] \[A' \to \alpha A' \mid \epsilon\]

\(A'\) absorve a “cauda” recursiva; a expansão passa a ser à direita (recursão à direita), que parsers LL tratam sem problema (consumindo tokens antes de nova chamada).

Recursão à esquerda indireta

Ocorre em cadeias como \(A \to B \to \ldots \to A\alpha\). O algoritmo completo (Aho et al.) reordena não terminais e elimina recursão à esquerda direta em cada um, passo a passo, até não restar recursão à esquerda.

4. Fatoração à esquerda (Left Factoring)

Quando duas produções de \(A\) começam com o mesmo símbolo (terminal ou não terminal), o parser LL não sabe qual escolher olhando apenas o prefixo já lido.

Exemplo: \(A \to \alpha\beta_1 \mid \alpha\beta_2\). O parser vê \(\alpha\) e não sabe se deve usar a primeira ou a segunda produção.

Solução: fatorar o prefixo comum:

\[A \to \alpha A'\] \[A' \to \beta_1 \mid \beta_2\]

Assim, após reconhecer \(\alpha\), o parser usa apenas \(A'\) e decide entre \(\beta_1\) e \(\beta_2\) com base no próximo token (desde que FIRST(\(\beta_1\)) e FIRST(\(\beta_2\)) sejam disjuntos ou que se use FOLLOW quando houver \(\epsilon\)).

5. Resumo das transformações

flowchart LR
  G[Gramática G] --> Amb{Ambígua?}
  Amb -->|Sim| Camadas[Camadas precedência]
  Amb -->|Não| Rec{Rec. esquerda?}
  Rec -->|Sim| Elim[Eliminação]
  Elim --> Fat{Fatorável?}
  Rec -->|Não| Fat
  Fat -->|Sim| Fator[Fatoração]
  Fat -->|Não| OK[Gramática LL]
  Fator --> OK
  Camadas --> Rec
  • Ambiguidade → reescrever com camadas (precedência/associatividade).
  • Recursão à esquerda → eliminar (nova variável \(A'\), recursão à direita).
  • Conflito de prefixo → fatorar à esquerda.

6. Exemplo integrado: expressões sem ambiguidade e sem recursão à esquerda

Objetivo: gramática para expressões com +, *, parênteses e id, adequada a LL(1).

  1. Camadas: \(E\) (expressão), \(T\) (termo), \(F\) (fator).
  2. Recursão à esquerda em \(E\) e \(T\) é eliminada, introduzindo \(E'\) e \(T'\):

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

Para a entrada id + id * id, o parser constrói uma única árvore, com * abaixo de +, refletindo precedência e associatividade.

Conexões com o projeto Mini-Pascal

  • Na Etapa 3 (parser manual LL), a gramática de Mini-Pascal deve estar livre de ambiguidade e de recursão à esquerda nas partes que o parser preditivo usa; fatoração evita conflitos de escolha.
  • Na Etapa 4 (ANTLR), a gramática pode usar recursão à esquerda em muitos casos (ANTLR trata internamente), mas a clareza de precedência e associatividade (via regras de precedência da ferramenta) continua importante.
  • Saber diagnosticar ambiguidade e aplicar eliminação de recursão e fatoração ajuda a interpretar mensagens de erro do ANTLR e a ajustar a gramática.

Resumo

  • Ambiguidade: uma string com duas árvores de derivação; elimina-se com gramática em camadas (precedência/associatividade).
  • Recursão à esquerda: \(A \Rightarrow^+ A\alpha\); fatal para LL; elimina-se com nova variável e recursão à direita.
  • Fatoração à esquerda: quando duas produções compartilham prefixo; extrai-se o prefixo comum para uma produção e um novo não terminal para os sufixos.
  • Essas transformações são padrão para obter gramáticas LL(1) ou próximas disso.

Perguntas de reflexão

  • Dê um exemplo de gramática ambígua (diferente do exemplo de expressões) e descreva duas árvores para a mesma string.
  • Por que a recursão à direita não causa o mesmo problema de loop infinito que a recursão à esquerda em um parser descendente?
  • Em uma gramática com muitas operadores (+, -, *, /, ^), como você organizaria as camadas para respeitar precedência e associatividade de cada um?

Referências

  • Aho et al. (2006). Compilers: Principles, Techniques, and Tools. Cap. 4 (gramáticas, ambiguidade, eliminação de recursão à esquerda, fatoração).
  • Cooper & Torczon (2011). Engineering a Compiler.

Materiais da aula

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

De volta ao topo