Aula 11: Análise Sintática Ascendente (LR)

Objetivos

• Entender o paradigma Bottom-Up (Shift-Reduce).
• A mecânica da pilha de parsing.

Conteúdo

A análise Bottom-Up (Ascendente) é mais poderosa que a Top-Down. Ela constrói a árvore das Folhas para a Raiz. Em vez de “expandir” regras, ela tenta “reduzir” (encolher) a entrada até chegar ao símbolo inicial \(S\).

Mecânica Shift-Reduce

O parser possui uma Pilha e um Buffer de Entrada. Existem quatro ações possíveis:

1. Shift: Move o token atual da entrada para o topo da pilha.
2. Reduce: Reconhece que os \(N\) símbolos no topo da pilha formam o lado direito de uma produção \(A \to \beta\). Remove \(\beta\) da pilha e empilha \(A\).
   • O “Handle” é a substring na pilha que combina com a produção e deve ser reduzida.
3. Accept: Quando a pilha tem apenas $S$ e a entrada acabou. Sucesso!
4. Error: Nenhuma ação válida é possível.

Exemplo Visual

Entrada: id + id 1. Pilha: [] Entrada: id + id \(\to\) Shift 2. Pilha: [id] Entrada: + id \(\to\) Reduce (\(F \to id\)) 3. Pilha: [F] \(\to\) Reduce (\(T \to F\)) 4. Pilha: [T] \(\to\) Reduce (\(E \to T\)) 5. Pilha: [E] Entrada: + id \(\to\) Shift …

Parsers Bottom-Up lidam nativamente com recursão à esquerda sem problemas.

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.