Aula 12: Tabelas de Parsing LR/LALR

Objetivos

  • Aprofundar nos algoritmos LR.
  • Diferenciar LR(0), SLR, LR(1) e LALR.

Conteúdo

Todos os parsers Bottom-Up usam a mesma mecânica de Shift-Reduce. A diferença entre eles está na inteligência da Tabela de Parsing que decide quando fazer Shift ou Reduce.

Estados da Tabela e Itens LR

Os estados do autômato do parser são compostos por conjuntos de Itens LR. Um item é uma produção com um ponto (\(\cdot\)) indicando o quanto já vimos. - \(A \to \cdot X Y\) (Espero ver um X). - \(A \to X \cdot Y\) (Vi um X, espero um Y). - \(A \to X Y \cdot\) (Vi tudo, hora de reduzir!).

A Hierarquia LR

  1. LR(0): O mais simples. Se o estado tem um item completo (\(A \to \alpha \cdot\)), ele reduz.
    • Problema: Se houver outro item pedindo Shift (Conflito Shift/Reduce), ele trava. Não olha o próximo token.
  2. SLR (Simple LR): Melhora o LR(0). Só reduz \(A \to \alpha \cdot\) se o próximo token \(a\) estiver no \(FOLLOW(A)\).
    • Resolve muitos conflitos, mas falha em gramáticas complexas.
  3. LR(1): O mais poderoso. O item carrega o Lookahead exato dentro dele: \([A \to \alpha \cdot, b]\). Só reduz se o próximo for exatamente \(b\).
    • Desvantagem: A quantidade de estados explode (milhares de estados para C/Java).
  4. LALR (Look-Ahead LR): O padrão industrial (Yacc/Bison). Ele “funde” os estados do LR(1) que são iguais ignorando o lookahead.
    • Tamanho de tabela similar ao SLR, potência próxima do LR(1).

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.
Back to top