Centro de Estudos, Desenvolvimento e Inovação em Software — CEDIS | UnB

Análise sintática: gramáticas livres de contexto e ferramentas

Semana 4 · teoria · FGA0003 — Compiladores 1

Prof. Sergio Antônio Andrade de Freitas
Curso de Engenharia de Software · 2026
símbolo CEDIS logo UnB
símbolo CEDISCEDIS
2/30

Roteiro da aula

  1. 01Retomada: do lexer ao parser
  2. 02Gramáticas livres de contexto
  3. 03Derivações e árvores
  4. 04Pilha, PDA e estruturas aninhadas
  5. 05Bison e integração com Flex
  6. 06Conexão com o projeto PBL
Parte 1

Do token à estrutura

A análise léxica produz unidades; a análise sintática organiza essas unidades.

símbolo CEDISCEDIS
4/30

Onde entra a análise sintática?

Entrada do parser

  • Sequência de tokens produzida pelo lexer.
  • Ex.: NUM, ID, PLUS, LPAREN.
  • Cada token já representa uma categoria léxica.

Responsabilidade do parser

  • Verificar a gramática da linguagem.
  • Construir árvore sintática ou AST.
  • Disparar ações semânticas iniciais.
símbolo CEDISCEDIS
5/30

Hierarquia de Chomsky: foco em GLC

A análise sintática de linguagens de programação é baseada, em grande parte, em gramáticas livres de contexto.

  • Tipo-3: expressões regulares e análise léxica.
  • Tipo-2: GLCs e análise sintática.
  • O reconhecedor conceitual das GLCs é o autômato com pilha.
Hierarquia de Chomsky com destaque para GLCs
símbolo CEDISCEDIS
6/30
atividade

Atividade 1 — Componentes da GLC

Em G = (V, Σ, P, S), qual componente contém as regras de produção?

  1. V
  2. Σ
  3. P
  4. S

Responder

Resumo ao vivo

QR Code para acesso à atividade
Parte 2

Gramáticas livres de contexto

Uma GLC descreve como construir sentenças válidas a partir de regras de produção.

símbolo CEDISCEDIS
8/30
Anatomia formal de uma GLC

Definição formal de GLC

Uma gramática livre de contexto é definida por G = (V, Σ, P, S).

  • V: conjunto de não terminais.
  • Σ: conjunto de terminais.
  • P: conjunto de produções.
  • S: símbolo inicial.
símbolo CEDISCEDIS
9/30

Componentes da gramática em linguagem de programação

Não terminais

Categorias abstratas, como expr, term, factor ou decl.

Terminais

Tokens concretos, como ID, NUM, +, *, (, ) e ;.

Produções

Regras que indicam como uma categoria pode ser expandida.

Inicial

Símbolo a partir do qual a análise começa.

símbolo CEDISCEDIS
10/30

Exemplos de GLC

Expressões

E → E + E | E * E | (E) | id

Pares aⁿbⁿ

S → aSb | ab

Declarações

Decl → int id = num ;

Blocos

Bloco → { lista_comandos }

símbolo CEDISCEDIS
11/30
atividade

Atividade 2 — Produção livre de contexto

Qual regra possui a forma válida de uma produção de GLC?

  1. aB → b
  2. A → aBb
  3. AB → a
  4. a → AB

Responder

Resumo ao vivo

QR Code para acesso à atividade
Parte 3

Derivações e árvores

A gramática não apenas aceita ou rejeita: ela mostra a estrutura da sentença.

símbolo CEDISCEDIS
13/30

Derivação de uma expressão

Derivar é aplicar produções sucessivamente até obter apenas terminais.

  • Começamos pelo símbolo inicial.
  • Escolhemos uma produção aplicável.
  • Repetimos até chegar à sentença terminal.
Processo de derivação da expressão id mais id
símbolo CEDISCEDIS
14/30
Árvore de derivação para expressão simples

Árvore de derivação

A árvore explicita a hierarquia sintática produzida pelas regras da gramática.

  • Nós internos representam não terminais.
  • Folhas representam terminais.
  • A ordem das folhas corresponde à sentença.
símbolo CEDISCEDIS
15/30
atividade

Atividade 3 — Cadeia gerada pela gramática

Considere S → aSb | ab. Qual cadeia pode ser gerada por essa gramática?

  1. aab
  2. abb
  3. aabb
  4. abab

Responder

Resumo ao vivo

QR Code para acesso à atividade
Parte 4

Ambiguidade e precedência

Nem toda gramática adequada para gerar sentenças é adequada para um parser sem ajustes.

símbolo CEDISCEDIS
17/30

O problema da ambiguidade

A gramática E → E + E | E * E | id permite mais de uma árvore para a mesma expressão.

  • A sentença é a mesma.
  • A estrutura sintática pode mudar.
  • A interpretação da expressão pode mudar.
Duas árvores possíveis para id mais id vezes id
símbolo CEDISCEDIS
18/30

Como reduzir a ambiguidade em expressões

Por declarações no Bison

  • %left '+' '-'
  • %left '*' '/'
  • Define precedência e associatividade.

Por reestruturação da gramática

  • expr → expr + term | term
  • term → term * factor | factor
  • factor → ( expr ) | id
Parte 5

Autômatos com pilha

A pilha permite reconhecer estruturas que exigem memória de aninhamento ou contagem.

símbolo CEDISCEDIS
20/30
Funcionamento simplificado de um PDA com pilha

Por que uma pilha?

Autômatos finitos não guardam memória suficiente para reconhecer dependências como aⁿbⁿ ou parênteses aninhados.

  • Cada símbolo pode registrar uma pendência.
  • A pilha permite desempilhar quando a pendência é resolvida.
  • Essa ideia está por trás de estruturas sintáticas recursivas.
símbolo CEDISCEDIS
21/30
atividade

Atividade 4 — Papel da pilha

Por que a pilha é útil para reconhecer a linguagem aⁿbⁿ?

  1. Porque armazena todo o código-fonte permanentemente.
  2. Porque registra quantos símbolos a ainda precisam ser associados a b.
  3. Porque substitui o analisador léxico.
  4. Porque elimina a necessidade de uma gramática.

Responder

Resumo ao vivo

QR Code para acesso à atividade
Parte 6

Construção de parsers com Bison

Bison recebe regras gramaticais e gera código C para o analisador sintático.

símbolo CEDISCEDIS
23/30

Anatomia do parser.y

O arquivo do Bison organiza declarações, regras gramaticais e código auxiliar.

  • Declara tokens e precedência.
  • Define produções da linguagem.
  • Permite ações semânticas em C.
Anatomia do arquivo parser.y no Bison
símbolo CEDISCEDIS
24/30
Fluxo de integração entre Flex e Bison

Integração Flex + Bison

O scanner gerado pelo Flex retorna tokens para o parser gerado pelo Bison.

  • Bison gera parser.tab.c e parser.tab.h.
  • Flex inclui parser.tab.h para conhecer os tokens.
  • O parser chama yylex() para obter o próximo token.
símbolo CEDISCEDIS
25/30
atividade

Atividade 5 — Integração Flex e Bison

Qual artefato permite que o scanner use os tokens definidos pelo Bison?

  1. lex.yy.c
  2. parser.tab.h
  3. scanner.out
  4. Makefile.h

Responder

Resumo ao vivo

QR Code para acesso à atividade
símbolo CEDISCEDIS
26/30

Tratamento de erros sintáticos

Detecção

  • Token inesperado.
  • Produção incompatível.
  • Fim de entrada antes do esperado.

Resposta do parser

  • Chamar yyerror().
  • Usar produções com error quando necessário.
  • Tentar recuperar para continuar análise.
símbolo CEDISCEDIS
27/30

Conexão com o projeto PBL

Agora

Transformar a lista de tokens em primeiras regras gramaticais.

Próxima prática

Implementar um parser inicial com Bison.

Repositório

Código-base e materiais: https://github.com/sergioaafreitas/COMP1

Entrega incremental

Manter README, testes e commits organizados desde o início.

símbolo CEDISCEDIS
28/30

Síntese

GLC

Define a estrutura sintática das sentenças da linguagem.

Derivação

Mostra a aplicação progressiva das produções.

Árvore

Torna explícita a hierarquia sintática.

PDA

Fornece o modelo conceitual com pilha.

Bison

Gera o parser a partir da gramática.

Flex

Fornece os tokens que alimentam o parser.

símbolo CEDISCEDIS
29/30

Referências

  1. Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2007). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson.
  2. GNU Project. (2026). GNU Bison Manual. Free Software Foundation. https://www.gnu.org/software/bison/manual/
  3. Tremblay, J. P., & Sorenson, P. G. (2008). Theory and Practice of Compiler Writing. BS Publications.
  4. Wirth, N. (2005). Compiler Construction. ETH Zürich.
  5. Freitas, S. A. A. (2026). Material da disciplina FGA0003 — Compiladores 1. GitHub: https://github.com/sergioaafreitas/COMP1
símbolo CEDISCEDIS
30/30

Próxima aula prática

Implementação inicial do parser com Bison, integrando o scanner desenvolvido com Flex. Materiais e código-base: https://github.com/sergioaafreitas/COMP1

→ avançar · ← voltar · deslize (touch) · n notas · f tela cheia · p imprimir