Aula 11: Análise Sintática Ascendente (LR)
Objetivos
Ao final desta aula, você será capaz de:
- Descrever o paradigma bottom-up (ascendente): construção da árvore das folhas para a raiz.
- Explicar a mecânica shift-reduce: pilha, buffer de entrada, ações Shift, Reduce, Accept e Error.
- Identificar o handle (substring a ser reduzida) e a relação com as produções da gramática.
- Relacionar parsers LR com ferramentas (Bison/Yacc) e com o projeto Mini-Pascal.
Motivação
Parsers ascendentes (LR) são a base de muitos compiladores industriais porque:
- Aceitam uma classe maior de gramáticas do que parsers LL (incluindo recursão à esquerda).
- Lidam naturalmente com gramáticas escritas de forma “natural” para expressões e listas.
- São gerados por ferramentas (Bison/Yacc, ANTLR em modo LR), produzindo parsers eficientes e mantíveis.
Visão geral: Top-Down vs Bottom-Up
flowchart LR
subgraph LL [Top-Down LL]
A1[Raiz] --> A2[Expandir]
A2 --> A3[Folhas]
end
subgraph LR [Bottom-Up LR]
B1[Folhas] --> B2[Reduzir]
B2 --> B3[Raiz]
end- Top-Down (LL): começa pelo símbolo inicial e “expande” produções até obter os tokens; a árvore cresce da raiz para as folhas.
- Bottom-Up (LR): começa pelos tokens e “reduz” sequências ao lado direito de produções, substituindo pelo não terminal do lado esquerdo; a árvore é construída das folhas para a raiz.
Conteúdo
1. Mecânica Shift-Reduce
O parser mantém:
- Uma pilha de símbolos (terminais e não terminais).
- Um buffer de entrada com os tokens restantes (da esquerda para a direita).
Configuração em um instante: (conteúdo da pilha, entrada restante). O parser repete ações até Accept ou Error.
As quatro ações possíveis:
| Ação | Descrição |
|---|---|
| Shift | Remover o próximo token da entrada e empilhá-lo no topo da pilha. |
| Reduce | Escolher uma produção \(A \to \beta\); os \(|\beta|\) símbolos no topo da pilha formam exatamente \(\beta\) (da ordem topo → base). Desempilhar esses símbolos e empilhar \(A\). (Construir nó da árvore associado a \(A\) com filhos \(\beta\).) |
| Accept | A pilha contém apenas o símbolo inicial \(S\) e a entrada está vazia. Parsing concluído com sucesso. |
| Error | Nenhuma ação (Shift, Reduce ou Accept) é aplicável. Erro de sintaxe; reportar e, se houver estratégia de recuperação, aplicá-la. |
A decisão de qual ação tomar em cada configuração é feita por uma tabela de parsing (ou equivalente), construída a partir da gramática (LR(0), SLR, LR(1), LALR). O próximo token da entrada (lookahead) e o estado atual (que resume o conteúdo da pilha) indexam a tabela.
2. Handle
O handle é uma substring no topo da pilha que é o lado direito de alguma produção \(A \to \beta\) e que deve ser reduzida nesse passo. Ou seja, é o \(\beta\) que o parser escolhe para a ação Reduce.
Em gramáticas adequadas para LR, em cada configuração há no máximo um handle (e a decisão é determinística com o lookahead). O algoritmo LR garante que o handle correto seja identificado no momento certo.
3. Exemplo passo a passo
Gramática simplificada:
\[E \to E + T \mid T\] \[T \to T * F \mid F\] \[F \to \texttt{id}\]
Entrada: id + id.
| Passo | Pilha | Entrada | Ação |
|---|---|---|---|
| 1 | \(\varepsilon\) | id + id | Shift id |
| 2 | id | + id | Reduce \(F \to \texttt{id}\) |
| 3 | F | + id | Reduce \(T \to F\) |
| 4 | T | + id | Reduce \(E \to T\) |
| 5 | E | + id | Shift + |
| 6 | E + | id | Shift id |
| 7 | E + id | \(\varepsilon\) | Reduce \(F \to \texttt{id}\) |
| 8 | E + F | \(\varepsilon\) | Reduce \(T \to F\) |
| 9 | E + T | \(\varepsilon\) | Reduce \(E \to E + T\) |
| 10 | E | \(\varepsilon\) | Accept |
A pilha evolui até conter apenas \(E\) com entrada vazia; nesse momento Accept.
4. Diagrama do ciclo do parser LR
flowchart TD
Início([Início]) --> Estado[Estado atual + lookahead]
Estado --> Decisão{Consulta tabela}
Decisão -->|Shift| Shift[Empilhar token]
Decisão -->|Reduce| Reduce[Desempilhar beta, empilhar A]
Decisão -->|Accept| Fim([Sucesso])
Decisão -->|Vazio/Error| Erro([Erro])
Shift --> Estado
Reduce --> EstadoO “estado atual” em um parser LR por tabela é um estado do autômato LR (conjunto de itens LR), não apenas o conteúdo literal da pilha; a pilha pode armazenar símbolos e estados. O diagrama acima é conceitual: a cada passo consulta-se a tabela e aplica-se Shift, Reduce, Accept ou Error.
5. Recursão à esquerda
Parsers LL (top-down) têm dificuldade com recursão à esquerda (risco de loop). Parsers LR (bottom-up) não têm esse problema: a redução ocorre após os tokens terem sido empilhados, então a ordem das produções com recursão à esquerda é tratada naturalmente pela tabela. Por isso gramáticas com expressões escritas como \(E \to E + T \mid T\) são comuns em geradores LR (Bison/Yacc).
Conexões com ferramentas e projeto
- Bison/Yacc geram parsers baseados em LALR(1) (ou LR(1)); a máquina de estados e a tabela ACTION/GOTO são construídas a partir da gramática. Entender shift-reduce ajuda a interpretar conflitos (shift/reduce, reduce/reduce) e a ajustar a gramática ou as regras de precedência.
- No projeto Mini-Pascal você usa parser LL nas etapas 3 e 4; mesmo assim, conhecer LR ajuda a ler documentação de compiladores, a analisar ambiguidades e a entender como ferramentas industriais funcionam.
Resumo
- Bottom-up: árvore construída das folhas para a raiz; o parser reduz sequências ao lado direito de produções.
- Shift: empilha token; Reduce: desempilha \(\beta\), empilha \(A\) para \(A \to \beta\); Accept: pilha = \(S\), entrada vazia; Error: nenhuma ação aplicável.
- O handle é o \(\beta\) no topo da pilha escolhido para reduzir.
- Parsers LR lidam bem com recursão à esquerda e são a base de geradores como Bison.
Perguntas de reflexão
- Em que situações você consideraria migrar de um parser LL manual para um parser LR gerado por ferramenta?
- Que informação extra (além da pilha de símbolos) o parser LR mantém para decidir entre Shift e Reduce? (Dica: estado do autômato LR, lookahead.)
Referências
- Aho et al. (2006). Compilers: Principles, Techniques, and Tools. Cap. 4 (parsing LR).
- Cooper & Torczon (2011). Engineering a Compiler.
Materiais da aula
Última atualização: 08/03/2026