Aula 12: Tabelas de Parsing LR/LALR

Data de Publicação

25/03/2026

Data de Modificação

08/03/2026

Objetivos

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

Motivação

Na prática de Engenharia de Compiladores, quase nunca implementamos manualmente o algoritmo LR; em vez disso, usamos ferramentas que geram tabelas de parsing a partir da gramática.

Entender como essas tabelas são construídas é essencial para:

  • Interpretar mensagens de conflito (shift/reduce, reduce/reduce) emitidas por Bison/Yacc e ferramentas similares.
  • Ajustar a gramática ou declarar precedências para resolver conflitos de forma consciente.
  • Avaliar o impacto de mudanças na gramática (por exemplo, adicionar um novo construto) sobre a complexidade do parser.

Conteúdo

Todos os parsers Bottom-Up usam a mesma mecânica de Shift-Reduce. A diferença entre eles está na tabela de parsing (ACTION e GOTO) que decide, em cada estado e para cada lookahead, se fazemos Shift, Reduce (e qual produção), Accept ou Error. A tabela é construída a partir da gramática usando itens LR e o autômato de itens.

flowchart LR
  Gram[Gramática] --> Itens[Itens LR]
  Itens --> Aut[Autômato de estados]
  Aut --> Action[ACTION]
  Aut --> Goto[GOTO]
  Action --> Parser[Parser]
  Goto --> Parser

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).

Resumo

  • Itens LR: produção com um ponto (\(\cdot\)) indicando o progresso; estados do autômato são conjuntos de itens (closure e goto).
  • LR(0), SLR, LR(1) e LALR diferem na quantidade de lookahead e na forma de decidir Reduce; LALR é o compromisso usado por Bison/Yacc.
  • Conflitos shift/reduce e reduce/reduce indicam que a tabela teria mais de uma ação em uma célula; resolvem-se com precedência/associatividade ou reescrevendo a gramática.

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