Aula 08: Gramáticas Livres de Contexto

Objetivos

• Diagnosticar e resolver problemas em gramáticas.
• Ambiguidade, Recursão à Esquerda e Fatoração.

Conteúdo

Projetar gramáticas é uma arte. Uma gramática “ingênua” raramente serve para ser implementada diretamente em um parser Top-Down (LL).

1. Ambiguidade

Um problema crítico. Uma gramática é ambígua se existe uma string que pode ter mais de uma árvore de derivação. - Ex clássico: E -> E + E | E * E | id. - Para a entrada 2 + 3 * 4, posso agrupar como (2+3)*4 ou 2+(3*4). - O compilador precisa de certeza absoluta. - Solução: Reescrever a gramática em camadas (Termo, Fator) para forçar precedência, ou usar diretivas de desambiguidade no gerador de parser.

2. Recursão à Esquerda

Regras da forma \(A \to A\alpha\) (direta ou indireta) são fatais para parsers de Descida Recursiva. O parser entra num loop infinito chamando a si mesmo (parseA chama parseA instantaneamente). - Solução: Transformar em recursão à direita. - \(A \to A\alpha | \beta\) vira: - \(A \to \beta A'\) - \(A' \to \alpha A' | \epsilon\)

3. Fatoração à Esquerda (Left Factoring)

Quando duas regras começam com o mesmo símbolo: \(A \to \alpha\beta_1 | \alpha\beta_2\). O parser preditivo não sabe qual escolher apenas olhando \(\alpha\). - Solução: Fatorar o prefixo comum. - \(A \to \alpha A'\) - \(A' \to \beta_1 | \beta_2\)

Referências

• Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools.
• Cooper, K., & Torczon, L. (2011). Engineering a Compiler.