Aula 5 · Gramáticas livres de contexto

Objetivos da aula

O que você vai aprender

Ler e escrever produções de uma GLC.

Construir derivações e árvores sintáticas.

Reconhecer e resolver ambiguidade com precedência e associatividade.

Traduzir entre BNF e EBNF.

1 · Motivação

Por que regex não basta

A análise léxica nos deu tokens. Mas como descrever que "( ( ) )" é válido e "( ) )" não é? Aninhamento arbitrário foge das expressões regulares — precisamos de uma ferramenta mais forte.

As gramáticas livres de contexto (tipo 2 de Chomsky) são essa ferramenta. Elas descrevem a estrutura sintática das linguagens de programação.

🔑

GLC são para a sintaxe o que as expressões regulares são para o léxico: a linguagem de especificação da fase.

2 · Mapa

O que veremos nesta aula

GLC→Derivações e árvores→Ambiguidade→BNF/EBNF

A definição formal de uma GLC.
Como gerar cadeias e registrar sua estrutura.
O problema da ambiguidade e como resolvê-lo.
As notações padrão de gramáticas.

3 · Definição

Gramática livre de contexto

GLC. Quádrupla (N, T, P, S): não-terminais N, terminais T, produções P (da forma A → α) e símbolo inicial S.

Os não-terminais são variáveis sintáticas (como E para "expressão"); os terminais são os tokens; as produções dizem como reescrever cada não-terminal; S é o ponto de partida.

4 · Aprofundamento

A gramática de expressões

O exemplo clássico, que usaremos o curso inteiro, é o das expressões aritméticas:

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

Há três níveis: E (expressão, soma), T (termo, produto) e F (fator). Essa estratificação não é casual — ela codifica a precedência dos operadores, como veremos.

5 · Exemplo

Derivação e árvore sintática

Derivação. Sequência de aplicações de produções, partindo de S, até chegar a uma cadeia só de terminais.
Árvore sintática. Estrutura em árvore que registra como a cadeia foi derivada, com S na raiz e os terminais nas folhas.

Para "id + id", uma derivação é: E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + F ⇒ id + id.

6 · Interativo

Passo a passo: derivando "id * id"

Passo 1

Início: E. Aplicamos E → T, obtendo T.

Passo 2

Aplicamos T → T * F, obtendo T * F.

Passo 3

Aplicamos T → F e depois F → id no primeiro fator: id * F.

Passo 4

Aplicamos F → id no segundo fator: id * id. Derivação concluída.

7 · Definição

Gramática ambígua

Ambiguidade. Uma gramática é ambígua quando uma mesma cadeia admite duas (ou mais) árvores sintáticas distintas — e, portanto, dois significados.

Ambiguidade é um defeito: o compilador não saberia qual interpretação adotar.

8 · Aprofundamento

O perigo da ambiguidade

⚠️

A entrada id + id * id, numa gramática mal escrita (E → E + E | E * E | id), poderia agrupar como (id+id)*id ou id+(id*id). São resultados numéricos diferentes! A ambiguidade muda o significado.

A gramática estratificada (E, T, F) elimina esse problema: ela só produz uma árvore para cada cadeia, com o agrupamento correto id+(id*id).

9 · Analogia

A frase ambígua

🔧 Analogia

"Vi o homem com o telescópio" é ambígua em português: quem tem o telescópio, eu ou o homem? Há duas "árvores" de interpretação. Numa linguagem de programação isso seria inaceitável — por isso projetamos gramáticas sem ambiguidade, em que cada frase tem uma única leitura.

10 · Comparação

BNF × EBNF

A EBNF acrescenta açúcares sintáticos à BNF, deixando as gramáticas mais compactas:

Em BNF	Em EBNF	Significado
L → a L \| a	L → a { a }	repetição
S → if E then S \| if E then S else S	S → if E then S [ else S ]	opcional

Em EBNF: chaves { } repetem (zero ou mais), colchetes [ ] tornam opcional, parênteses ( ) agrupam.

11 · Fluxo

Da gramática à árvore

A gramática gera; a árvore registra. O parser, que veremos na próxima aula, faz o caminho inverso: recebe a cadeia e reconstrói a árvore.

Gramática (GLC)→Derivação→Árvore sintática

12 · Aprofundamento

Precedência e associatividade

A estrutura da gramática codifica dois conceitos:

Precedência: operadores que ligam mais forte ficam em níveis mais profundos. Como * está abaixo de + (no nível T), ele agrupa primeiro.
Associatividade: a recursão à esquerda (E → E + T) torna o operador associativo à esquerda, então a - b - c é lido como (a - b) - c.

✅

Estratificar (expressão → termo → fator) resolve precedência; escolher recursão à esquerda ou à direita define a associatividade.

13 · Verifique

Verifique você mesmo: ambígua?

A gramática E → E + E | id é ambígua para a cadeia id + id + id?

Sem estratificação nem recursão definida, a soma pode agrupar à esquerda ou à direita, gerando duas árvores. A gramática é ambígua.

14 · Caso prático

O problema do else pendente

O clássico "dangling else": em if E then if E then S else S, a quem pertence o else? Ao if interno ou ao externo?

💡

A gramática ingênua de if-then-else é ambígua justamente por isso. A convenção universal (e a solução prática) é associar o else ao if mais próximo (o interno). Linguagens reais adotam essa regra ou exigem chaves.

15 · Erros comuns

Enganos ao escrever GLC

⚠️

Cuidado. Não confunda ambiguidade com não determinismo do parser. Uma gramática pode ser não ambígua e ainda assim difícil de analisar. E lembre: colocar todos os operadores no mesmo nível (E → E + E | E * E) destrói a precedência e gera ambiguidade.

16 · Boas práticas

Projetando boas gramáticas

✅

Dica. Comece sempre estratificando por precedência: um nível de não-terminal por nível de precedência, do menos para o mais forte. Reserve o fator (F) para os parênteses e os átomos. Esse padrão evita ambiguidade desde o início.

17 · Revelar

Reflita: ambiguidade é decidível?

Existe um algoritmo que decide se qualquer GLC é ambígua?

Não. Determinar se uma GLC arbitrária é ambígua é um problema indecidível — não há algoritmo geral que sempre responda. Na prática, projetamos gramáticas de forma a garantir a ausência de ambiguidade por construção (estratificando por precedência, definindo associatividade), em vez de testar uma gramática qualquer.

18 · Flashcards

Termos-chave da aula

Não-terminalvirar

Variável sintática que pode ser reescrita por produções (ex.: E, T, F).

Derivaçãovirar

Sequência de aplicações de produções, de S até uma cadeia de terminais.

Árvore sintáticavirar

Registro em árvore da estrutura da derivação; raiz S, folhas terminais.

EBNFvirar

BNF estendida: { } repetição, [ ] opcional, ( ) agrupamento.

19 · Conexões

Onde isto se encaixa no curso

Esta é a aula-base da análise sintática:

Vem da aula 2: GLC é o tipo 2 (livre de contexto) de Chomsky.
Continua na aula 6: o parser descendente percorre a gramática para reconstruir a árvore.
Prepara a aula 7: FIRST/FOLLOW e LL(1) dependem de a gramática estar bem formada (sem ambiguidade).

20 · Síntese

Resumo visual

🔑

GLC = (N, T, P, S). Derivações geram cadeias; árvores registram a estrutura. Ambiguidade (duas árvores) muda o significado e deve ser eliminada estratificando por precedência e definindo associatividade. BNF/EBNF são as notações padrão.

Mão na massa · colaborativo

Atividade em grupo · Caça à ambiguidade

Em duplas, mostrem que uma gramática é ambígua exibindo duas árvores.

⏱️ 25 min👥 duplas🧩 prova por contraexemplo

Roteiro

Dada E → E + E | E * E | ( E ) | id, derivem id + id * id de duas formas.
Desenhem as duas árvores sintáticas distintas.
Reescrevam a gramática em níveis (E, T, F) para eliminar a ambiguidade.
Verifiquem que agora só há uma árvore.

Derivador Aagrupa pela soma primeiro

Derivador Bagrupa pelo produto primeiro

📤 Entrega: Duas árvores da gramática ambígua + a gramática estratificada corrigida.

Teste seu conhecimento

Mini-quiz · Aula 5

20 questões sobre esta aula. Escolha e veja a explicação na hora.

0/20

📌 Resumo — leve isto para a prova

GLC = (N, T, P, S); derivações geram cadeias; árvores registram a estrutura.
Ambiguidade (duas árvores) muda o significado e deve ser eliminada.
Estratificar a gramática codifica precedência; a recursão define a associatividade.
O dangling else liga-se, por convenção, ao if mais próximo.
BNF/EBNF são as notações padrão de gramáticas.