Gramática
Descreve o que pode existir na linguagem.
CEDIS | Universidade de Brasília (UnB)
Dentro do parser: pilha, decisões, conflitos e recuperação sintática
FGA0003 — Compiladores 1 · Semana 5 · Aula teórica
CEDISRoteiro da aula
- 01A ponte entre as aulas 04, 05 prática e 06
- 02A sala de controle do parser
- 03Deslocar, reduzir, aceitar e errar
- 04Conflitos e ambiguidades
- 05Precedência e associatividade
- 06Erro sintático e recuperação
- 07Reduções, ações semânticas e AST
CEDISPor que esta aula existe?
- A aula 04 explicou gramáticas e Bison.
- A prática 05 exige recuperação e mensagens de erro.
- A aula 06 usa reduções para construir ASTs e símbolos.
CEDISO problema que ainda faltava responder
Parser
Decide passo a passo se a entrada cabe na gramática.
Erro
Aparece quando nenhuma ação válida resta para o estado atual.
AST
Pode ser construída no momento das reduções.
CEDIS
O parser não recebe caracteres
- O Flex já transformou caracteres em tokens.
- O parser observa o token de antecipação.
- A pilha registra o contexto já reconhecido.
- O estado define as ações possíveis.
CEDISAs quatro ações fundamentais
shift
Desloca o próximo token para a pilha.
reduce
Substitui o topo da pilha pelo lado esquerdo de uma produção.
accept
Confirma que a entrada pertence à linguagem.
error
Indica que nenhuma ação válida está disponível.
CEDISPor que não estudaremos a tabela LR completa?
- O objetivo da disciplina é construir um compilador funcional.
- O Bison gera as tabelas automaticamente.
- Precisamos entender o suficiente para depurar conflitos e erros.
CEDISDeslocar versus reduzir
Deslocar
- Consumir mais um token da entrada.
- Indica que o parser ainda precisa de contexto.
- Exemplo: mover NUM para a pilha.
Reduzir
- Reconhecer uma estrutura já completa.
- Aplicar uma produção gramatical.
- Exemplo: NUM vira factor.
CEDISSimulação: primeiros passos em 3 + 4 * 2
A simulação mostra que o parser alterna consumo de tokens e reconhecimento de estruturas.
- Cada redução aproxima a pilha de um símbolo não terminal.
- A precedência pode aparecer na gramática ou em diretivas do Bison.
CEDISatividade
Atividade 1 — Próxima ação
Considere: pilha = $ expr PLUS; entrada = NUM $. Qual é a próxima ação mais provável?
CEDIS
O conflito shift/reduce
- Reduzir: reconhecer uma estrutura imediatamente.
- Deslocar: consumir mais um token antes de decidir.
- Em expressões, isso costuma envolver precedência.
CEDISGramática ambígua para expressões
Regras simples
- expr → expr PLUS expr
- expr → expr TIMES expr
- expr → NUM
Problema
- 3 + 4 * 2 permite duas árvores.
- O parser precisa decidir entre reduzir e deslocar.
- A matemática esperada exige precedência.
CEDISDuas árvores possíveis
(3 + 4) * 2
A soma vira subexpressão esquerda da multiplicação.
3 + (4 * 2)
A multiplicação fica dentro da subexpressão direita da soma.
Sem regra adicional
A gramática não escolhe sozinha qual interpretação é desejada.
CEDISatividade
Atividade 2 — Ambiguidade
Na gramática expr → expr + expr | expr * expr | NUM, qual é o problema com NUM + NUM * NUM?
CEDISConflito não é apenas ruído do compilador
- Pode indicar ambiguidade real.
- Pode indicar precedência ausente.
- Pode indicar uma regra redundante.
- Pode mascarar uma linguagem diferente da pretendida.
CEDISConflito redução/redução
Situação
- Duas produções parecem reconhecer a mesma sequência.
- O parser não sabe qual redução aplicar.
Exemplo conceitual
- item → IDENT
- valor → IDENT
- Em determinado contexto, ambas servem.
CEDISPrecedência
Ideia
- Alguns operadores agrupam antes de outros.
- TIMES deve ter precedência maior que PLUS.
No Bison
- %left PLUS
- %left TIMES
- Declarações posteriores têm maior precedência.
CEDISAssociatividade
À esquerda
- 10 - 3 - 2
- Interpreta como (10 - 3) - 2
À direita
- a = b = c
- Interpreta como a = (b = c)
CEDISatividade
Atividade 3 — Associatividade
Com %left MINUS, como a expressão 10 - 3 - 2 é interpretada?
CEDISDuas formas de resolver expressões
Diretivas
- %left PLUS MINUS
- %left TIMES DIVIDE
- Útil para gramáticas compactas.
Gramática estruturada
- expr → expr + term | term
- term → term * factor | factor
- Mais explícita para fins didáticos.
CEDISComando útil para investigar conflitos
- bison -Wall -d -v parser.y
- O arquivo .output funciona como um microscópio do parser.
- Use os relatórios para localizar estados, conflitos e ações possíveis.
CEDISQuando o erro é declarado?
Estado atual
- A pilha indica o contexto.
- O estado contém as ações possíveis.
Lookahead
- O próximo token não permite shift.
- Nenhuma redução ou aceitação é válida.
Exemplo: pilha = $ expr PLUS; lookahead = SEMICOLON.
CEDISO erro pode ter começado antes
Entrada
- (3 + 4 * 2;
Diagnóstico
- O erro pode aparecer no ponto e vírgula.
- A causa real é o parêntese não fechado.
CEDISTrês responsabilidades diferentes
Detecção
Perceber que a entrada não cabe no estado atual.
Diagnóstico
Explicar o token encontrado, o contexto e a linha.
Recuperação
Encontrar ponto seguro para continuar a análise.
CEDISRecuperar não é corrigir
- O parser pode descartar tokens.
- Pode procurar delimitadores como ponto e vírgula.
- Não deve inventar silenciosamente o programa desejado.
CEDISatividade
Atividade 4 — Token de sincronização
Em uma linguagem na qual comandos terminam com ;, qual é um bom token inicial de sincronização?
CEDISO token especial error
O que é
- Símbolo especial do Bison.
- Não é retornado pelo Flex.
- Representa uma região inválida.
Exemplo
- statement: expr SEMICOLON
- statement: error SEMICOLON
- yyerrok;
CEDISProdução de recuperação por ponto e vírgula
- statement: expr SEMICOLON
- | error SEMICOLON { yyerrok; }
- O ponto e vírgula serve como token de sincronização.
- A próxima sentença pode ser analisada normalmente.
CEDISyyerrok e yyclearin
yyerrok
- Encerra o estado de recuperação.
- Permite que novos erros sejam reportados.
yyclearin
- Descarta o lookahead atual.
- Só deve ser usado quando esse token não é mais útil.
CEDISEstratégias ruins de recuperação
- Descartar todo o restante do arquivo.
- Imprimir mensagens genéricas demais.
- Repetir o mesmo erro várias vezes.
- Corrigir silenciosamente o código do usuário.
CEDISAutópsia de uma entrada com erro
Entrada 1
3 + 4 * 2; → Resultado: 11
Entrada 2
5 + ; → erro próximo de ;
Entrada 3
6 * 7; → Resultado: 42
CEDISatividade
Atividade 5 — Resposta aberta
Em até 250 caracteres, explique por que recuperar-se de um erro sintático não significa corrigir o programa do usuário.
Resposta aberta · até 250 caracteres
CEDIS
Redução, ação semântica e AST
- A ação ocorre quando a produção é reduzida.
- $1, $2 e $3 carregam valores dos símbolos da direita.
- $$ produz o valor semântico do lado esquerdo.
CEDISExemplo de ação semântica no Bison
- expr: expr PLUS expr { $$ = criar_no_operacao('+', $1, $3); }
- A redução cria o nó correspondente ao operador.
- Os filhos do nó vêm dos valores semânticos já reconhecidos.
CEDISO que perguntar ao projeto da equipe?
Gramática
- Há conflitos relatados pelo Bison?
- A precedência está explícita?
- A associatividade está definida?
Recuperação e AST
- Quais tokens sincronizam comandos?
- Quais reduções criarão nós?
- Quais mensagens ajudam o usuário?
CEDISRepositório oficial da disciplina
- https://github.com/sergioaafreitas/COMP1
- Use os exemplos da disciplina como ponto de partida.
- Adapte a gramática à linguagem da equipe.
- Mantenha commits pequenos e testáveis.
CEDISSíntese em cinco frases
1
O parser decide usando pilha, estado e lookahead.
2
Deslocar consome; reduzir reconhece.
3
Conflitos indicam decisões não determinadas pela gramática.
4
Recuperar encontra ponto seguro para continuar.
5
Reduções podem construir a AST.
CEDISReferências e materiais
- GNU Bison Manual. Seções sobre parser states, shift/reduce conflicts, operator precedence e error recovery.
- Aho, A. V.; Lam, M. S.; Sethi, R.; Ullman, J. D. Compilers: Principles, Techniques, and Tools. 2. ed. Pearson, 2006.
- Wirth, N. Compiler Construction. ETH Zurich, 2005.
- Repositório da disciplina: https://github.com/sergioaafreitas/COMP1
CEDISPróxima conexão
Na prática, vamos transformar esse entendimento em mensagens de erro e recuperação. Depois, cada redução começará a produzir AST e símbolos.