CEDIS | Universidade de Brasília (UnB)

Nivelamento: gramáticas e derivações para análise sintática

Da sequência de tokens à regra Bison e à árvore sintática

Prof. Dr. Sergio Antônio Andrade de Freitas
FGA0003 – Compiladores 1 · 2026/2
símbolo CEDIS logo UnB
símbolo CEDISCEDIS · COMP1
2/40

Por que este segundo nivelamento existe

O diagnóstico apontou lacunas em gramáticas livres de contexto e análise sintática. A meta é criar uma ponte curta entre gramática formal e parser Bison.

símbolo CEDISCEDIS · COMP1
3/40

Ao final, você deve conseguir

Ler

Identificar terminais, não terminais e produções.

Derivar

Mostrar como uma cadeia de tokens pode ser gerada.

Traduzir

Converter uma produção simples para Bison.

Analisar

Explicar precedência, associatividade e erros sintáticos.

símbolo CEDISCEDIS · COMP1
4/40

Roteiro de estudo

  1. 01O que chega ao parser
  2. 02GLC, produções e derivações
  3. 03Árvore sintática e regra Bison
  4. 04Ambiguidade, precedência e associatividade
  5. 05Recuperação de erros e prática no GitHub
seção

1. O parser não lê caracteres

Ele recebe tokens produzidos pela etapa léxica.

símbolo CEDISCEDIS · COMP1
6/40

Entrada do parser

Depois do scanner, a entrada já foi categorizada. O parser verifica se a sequência de tokens obedece à gramática.

pipeline sintático
símbolo CEDISCEDIS · COMP1
7/40

Caractere, lexema e token

Scanner

Lê caracteres, reconhece lexemas e devolve tokens.

Parser

Lê tokens e verifica combinações válidas segundo produções.

símbolo CEDISCEDIS · COMP1
8/40
atividade

Atividade 1 · Entrada do parser

Para a entrada x = 3 + 4, qual sequência o parser deve receber?

  1. ID ASSIGN NUM PLUS NUM
  2. x = 3 + 4
  3. IDENTIFICADOR + OPERADOR
  4. Apenas uma AST pronta
símbolo CEDISCEDIS · COMP1
9/40

Feedback da atividade 1

  • O parser consome categorias, não caracteres crus.
  • Os lexemas x, =, 3, + e 4 já foram classificados pelo scanner.
  • A AST ainda será construída durante ou após a análise sintática.
seção

2. Gramática livre de contexto

Uma GLC descreve como construções válidas podem ser formadas.

símbolo CEDISCEDIS · COMP1
11/40

Componentes de uma gramática

V

Não terminais: categorias sintáticas abstratas.

Σ

Terminais: tokens que aparecem na entrada.

R

Produções: regras de formação.

S

Símbolo inicial: ponto de partida da derivação.

símbolo CEDISCEDIS · COMP1
12/40
relação entre gramática e Bison

Produção formal e regra Bison

O Bison não elimina a gramática formal; ele a torna executável.

símbolo CEDISCEDIS · COMP1
13/40

Terminais e não terminais

Terminal

Vem do scanner: NUM, ID, PLUS, LPAREN.

Não terminal

Organiza estruturas: expr, term, factor, stmt.

Produção

Define como um não terminal pode ser reescrito.

símbolo CEDISCEDIS · COMP1
14/40
atividade

Atividade 2 · Classificação

Na regra expr: expr PLUS term | term ; qual símbolo é terminal?

  1. expr
  2. term
  3. PLUS
  4. A regra inteira
símbolo CEDISCEDIS · COMP1
15/40

Feedback da atividade 2

  • PLUS é um token produzido pelo scanner.
  • expr e term são não terminais da gramática.
  • A produção combina esses símbolos para formar expressões.
seção

3. Derivação e árvore sintática

Derivar é mostrar como a gramática gera uma cadeia.

símbolo CEDISCEDIS · COMP1
17/40

Derivação curta

Uma derivação registra os passos de reescrita até chegar apenas a terminais.

derivação de expressão simples
símbolo CEDISCEDIS · COMP1
18/40

Derivação e árvore contam a mesma história

Derivação

Sequência linear de reescritas.

Árvore sintática

Estrutura hierárquica que organiza a mesma construção.

símbolo CEDISCEDIS · COMP1
19/40
atividade

Atividade 3 · Próximo passo

Se expr ⇒ expr PLUS term e o primeiro expr vira NUM, qual forma surge?

  1. NUM PLUS term
  2. expr NUM term
  3. PLUS NUM term
  4. NUM expr PLUS
símbolo CEDISCEDIS · COMP1
20/40

Feedback da atividade 3

  • A reescrita substitui apenas o não terminal escolhido.
  • O terminal PLUS permanece na cadeia.
  • O term ainda precisa ser derivado para chegar à cadeia final.
seção

4. Da produção para o Bison

A regra Bison explicita a gramática e associa ações semânticas.

símbolo CEDISCEDIS · COMP1
22/40

Anatomia de uma regra Bison

Cabeça

Não terminal à esquerda: expr.

Alternativas

Formas possíveis à direita, separadas por |.

Ação

Código em C executado quando a produção reduz.

Valor semântico

$$, $1, $2 representam valores dos símbolos.

símbolo CEDISCEDIS · COMP1
23/40

Exemplo de regra executável

Produção

expr → expr PLUS expr

Ação

{ $$ = $1 + $3; }

símbolo CEDISCEDIS · COMP1
24/40
atividade

Atividade 4 · Ação semântica

Em expr PLUS expr { $$ = $1 + $3; }, o que $3 representa?

  1. O valor da primeira expr
  2. O token PLUS
  3. O valor da segunda expr
  4. O símbolo inicial da gramática
símbolo CEDISCEDIS · COMP1
25/40

Feedback da atividade 4

  • $1 corresponde ao primeiro símbolo da direita.
  • $2 corresponde ao PLUS.
  • $3 corresponde à segunda expr.
  • $$ define o valor da redução atual.
seção

5. Ambiguidade, precedência e conflitos

Uma gramática pode permitir mais de uma leitura estrutural.

símbolo CEDISCEDIS · COMP1
27/40
exemplo de precedência

Por que precedência importa

Sem critério adicional, uma expressão pode ter leituras diferentes. O parser precisa de uma decisão formal.

símbolo CEDISCEDIS · COMP1
28/40

Termos essenciais

Ambiguidade

A mesma cadeia admite mais de uma árvore sintática.

Shift/reduce

O parser não sabe se desloca o próximo token ou reduz agora.

Precedência

Define qual operador agrupa primeiro.

Associatividade

Resolve empates entre operadores de mesma precedência.

símbolo CEDISCEDIS · COMP1
29/40
atividade

Atividade 5 · Precedência

Com precedência usual, como 3 + 4 * 2 deve ser agrupado?

  1. (3 + 4) * 2
  2. 3 + (4 * 2)
  3. (3 + 4 * 2)
  4. Não pode ser analisado
símbolo CEDISCEDIS · COMP1
30/40

Feedback da atividade 5

  • Multiplicação tem precedência maior que soma.
  • O parser deve construir a estrutura como 3 + (4 * 2).
  • No Bison, isso pode ser declarado com níveis de precedência.
símbolo CEDISCEDIS · COMP1
31/40

Como o GitHub mostra isso

Semana 04

  • parser.y
  • scanner.l
  • expressões aritméticas
  • precedência de operadores

Semana 05

  • tratamento de erro
  • declarações %left
  • recuperação com error e ;
  • mensagens de erro
seção

6. Erro sintático e recuperação

Um parser robusto não precisa parar no primeiro erro.

símbolo CEDISCEDIS · COMP1
33/40

O que é erro sintático?

Não é token inválido

Isso pertence à análise léxica.

É combinação inválida

Os tokens existem, mas a sequência viola a gramática.

Recuperação

Descarta ou sincroniza tokens para continuar analisando.

símbolo CEDISCEDIS · COMP1
34/40
atividade

Atividade 6 · Diagnóstico

A entrada 3++2; tende a produzir que tipo de erro?

  1. Erro léxico
  2. Erro sintático
  3. Erro semântico
  4. Erro de geração de código
símbolo CEDISCEDIS · COMP1
35/40

Feedback da atividade 6

  • Os tokens NUM, PLUS, PLUS, NUM e SEMI podem existir.
  • A sequência viola a gramática esperada para expressões.
  • Por isso, o erro é sintático.
símbolo CEDISCEDIS · COMP1
36/40

Mini laboratório sugerido

1

1. Compile

Execute o parser da semana 04.

2

2. Teste

Use entradas válidas e inválidas.

3

3. Explique

Para cada erro, diga se é léxico ou sintático.

4

4. Modifique

Acrescente uma produção e justifique a mudança.

símbolo CEDISCEDIS · COMP1
37/40

Critério de saída deste módulo

Consigo ler

Dada uma regra Bison, identifico terminais e não terminais.

Consigo derivar

Mostro como uma cadeia simples é gerada.

Consigo justificar

Explico precedência, associatividade e recuperação de erro.

símbolo CEDISCEDIS · COMP1
38/40
O parser não é uma caixa-preta: ele executa uma gramática. Entender a gramática torna o Bison compreensível.
Síntese do módulo
símbolo CEDISCEDIS · COMP1
39/40

Próximo passo

Use este módulo antes da prática de Bison. Ao abrir parser.y, explique cada produção antes de modificar o código.

símbolo CEDISCEDIS · COMP1
40/40

Referências

  1. Freitas, S. A. A. (2026). Relatório de análise da avaliação diagnóstica FGA0003 – Compiladores 1, semestre 2026/2. Universidade de Brasília.
  2. Freitas, S. A. A. (2025). Semana 02 – Fundamentos de linguagens formais e autômatos. FGA0003 – Compiladores 1. Universidade de Brasília.
  3. Freitas, S. A. A. (2025). Guia rápido das expressões regulares mais usadas no Flex. Repositório COMP1.
  4. Freitas, S. A. A. (2025). Repositório COMP1: exemplos progressivos com Flex e Bison. Universidade de Brasília.
  5. Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, techniques, and tools (2nd ed.). Pearson.
→ avançar · ← voltar · deslize (touch) · n notas · f tela cheia · p imprimir