Aula 7 · LL(1), FIRST/FOLLOW · Revisão + Prova 1

Objetivos da aula

O que você vai aprender

Calcular FIRST e FOLLOW de uma gramática.

Montar e usar a tabela preditiva LL(1).

Diagnosticar conflitos e por que uma gramática não é LL(1).

Consolidar os conceitos para a Avaliação 1.

1 · Motivação

Como o parser decide sem errar?

No parser descendente, ao expandir um não-terminal com várias produções, qual escolher? Olhar o próximo token e adivinhar dá errado se a escolha for ruim. Precisamos de um critério seguro.

Os conjuntos FIRST e FOLLOW dão exatamente isso: ao ver o próximo token, o parser sabe qual produção aplicar — sem retroceder. É a base do parsing preditivo LL(1).

🔑

FIRST e FOLLOW transformam o parser de "tentativa e erro" em "decisão certeira com 1 token de antecipação".

2 · Mapa

O que veremos nesta aula

FIRST→FOLLOW→Tabela LL(1)→Revisão Prova 1

O conjunto FIRST e como calculá-lo.
O conjunto FOLLOW e seu papel com ε.
A construção da tabela preditiva e o que é uma gramática LL(1).
Consolidação das semanas 1 a 6.

3 · Definição

FIRST e FOLLOW

FIRST(α). Conjunto de terminais que podem iniciar uma cadeia derivada de α (inclui ε se α pode derivar a cadeia vazia).
FOLLOW(A). Conjunto de terminais que podem aparecer imediatamente após o não-terminal A em alguma derivação.

4 · Aprofundamento

Calculando FIRST

Regras para FIRST(X):

Se X é terminal, FIRST(X) = { X }.
Se X → ε é produção, adicione ε a FIRST(X).
Se X → Y1 Y2 ... Yk, adicione FIRST(Y1) (sem ε). Se Y1 pode derivar ε, inclua também FIRST(Y2), e assim por diante.

💡

FIRST responde: "que terminais posso ver primeiro se eu seguir por aqui?". É olhar o começo de tudo que aquele símbolo gera.

5 · Exemplo

FIRST e FOLLOW da gramática de expressões

Para E → T E', E' → + T E' | ε, T → F T', T' → * F T' | ε, F → ( E ) | id:

Não-terminal	FIRST	FOLLOW
E	( id	) $
E'	+ ε	) $
T	( id	+ ) $
T'	* ε	+ ) $
F	( id	+ * ) $

O símbolo $ marca o fim da entrada.

6 · Interativo

Passo a passo: FOLLOW(T)

Passo 1

Em E → T E', após T vem E'. Adicionamos FIRST(E') sem ε a FOLLOW(T): logo + entra.

Passo 2

Como E' pode derivar ε, T também pode estar no fim de E. Então FOLLOW(T) recebe FOLLOW(E).

Passo 3

FOLLOW(E) = { ) , $ }. Adicionamos esses a FOLLOW(T).

Passo 4

Resultado: FOLLOW(T) = { + , ) , $ }.

7 · Definição

Gramática LL(1)

LL(1). Left-to-right scan, Leftmost derivation, 1 token de lookahead. Uma gramática é LL(1) se sua tabela preditiva não tiver conflitos (nenhuma célula com mais de uma produção).

8 · Aprofundamento

Montando a tabela preditiva

Para cada produção A → α, preenche-se a tabela (linha A, coluna terminal):

Coloque A → α em cada coluna t de FIRST(α).
Se ε ∈ FIRST(α), coloque A → α também em cada coluna t de FOLLOW(A).

💡

Em uso: o parser olha o topo da pilha (um não-terminal A) e o token atual (t); consulta a célula [A][t]; aplica a produção indicada. Sem ambiguidade, sem retrocesso.

9 · Analogia

O mapa de decisões

🔧 Analogia

A tabela LL(1) é como um GPS: em cada cruzamento (não-terminal) e com a placa que você vê adiante (o token de lookahead), ele diz exatamente qual rua pegar (qual produção). Se duas ruas aparecessem para a mesma situação, o GPS estaria confuso — e a gramática não seria LL(1).

10 · Comparação

FIRST × FOLLOW

	FIRST(α)	FOLLOW(A)
O que descreve	O que pode começar α	O que pode vir depois de A
Aplica-se a	Qualquer cadeia α	Não-terminais A
Pode conter ε?	Sim	Não (mas contém $)
Uso na tabela	Colunas onde a produção entra	Colunas extras quando α deriva ε

11 · Fluxo

Do cálculo à decisão

A construção do parser preditivo segue uma cadeia bem definida:

Gramática→FIRST→FOLLOW→Tabela LL(1)→Parser

12 · Aprofundamento

Quando NÃO é LL(1)

⚠️

Um conflito na tabela (duas produções na mesma célula) significa que a gramática não é LL(1). As causas típicas são: ambiguidade, recursão à esquerda não eliminada, ou falta de fatoração (FIRST de duas alternativas se sobrepõem).

Por isso as transformações da aula 6 (eliminar recursão à esquerda, fatorar) são pré-requisitos: sem elas, a tabela quase certamente terá conflitos.

13 · Verifique

Verifique você mesmo: onde entra ε?

Para a produção E' → + T E' | ε, em quais colunas entra a produção E' → ε na tabela?

Como E' → ε tem FIRST = { ε }, a produção entra nas colunas de FOLLOW(E') = { ), $ }. O '+' fica reservado para a produção E' → + T E'.

14 · Caso prático

Geradores de parser LL

Ferramentas como ANTLL e bibliotecas de parser combinators usam a teoria LL. Geradores LL(1) clássicos constroem a tabela automaticamente a partir da gramática.

💡

Quando um gerador reclama de "conflito", é a tabela LL(1) acusando duas produções na mesma célula. A correção costuma ser exatamente fatorar ou eliminar recursão à esquerda — o que estudamos na aula 6.

15 · Erros comuns

Enganos com FIRST/FOLLOW

⚠️

Cuidado. Não inclua ε em FOLLOW (FOLLOW só tem terminais e $). Não esqueça de propagar FOLLOW quando o símbolo pode estar no fim de uma produção (via ε). E lembre: FIRST aplica-se a cadeias (α), enquanto FOLLOW aplica-se só a não-terminais.

16 · Boas práticas

Calculando com segurança

✅

Dica. Calcule todos os FIRST antes de começar os FOLLOW — o cálculo de FOLLOW depende de FIRST. Repita o processo até nada mudar (ponto fixo): os conjuntos crescem por iterações sucessivas até estabilizar.

17 · Revelar

Reflita: LL(1) é o limite?

Toda linguagem livre de contexto tem uma gramática LL(1)?

Não. Existem linguagens livres de contexto para as quais nenhuma gramática LL(1) existe — elas exigem mais lookahead ou um método ascendente (LR). LL(1) é uma subclasse conveniente, porque permite parsers preditivos simples e eficientes, mas não cobre todas as GLC. Quando LL(1) não dá conta, recorre-se a LL(k), LR(1), LALR e similares.

18 · Flashcards

Termos-chave da aula

FIRST(α)virar

Terminais que podem iniciar uma cadeia derivada de α (com ε se α deriva vazio).

FOLLOW(A)virar

Terminais que podem aparecer logo após A em alguma derivação (inclui $).

LL(1)virar

Left-to-right, Leftmost, 1 lookahead. Tabela sem conflitos.

Conflitovirar

Célula da tabela com duas produções: a gramática não é LL(1).

19 · Conexões

O quadro geral das semanas 1 a 6

Esta semana fecha o primeiro bloco. Veja como tudo se conecta:

Aulas 1-2: o panorama e as linguagens formais (Chomsky).
Aulas 3-4: léxico — tokens, ER, autômatos (tipo 3).
Aulas 5-6: sintaxe — GLC, ambiguidade, parsing descendente (tipo 2).
Aula 7: FIRST/FOLLOW e LL(1) coroam o parsing preditivo. A Prova 1 cobre tudo isso.

20 · Síntese

Resumo visual

🔑

FIRST = terminais iniciais; FOLLOW = terminais seguintes. LL(1) = top-down, derivação à esquerda, 1 lookahead. A tabela preditiva sem conflitos significa gramática LL(1). Conflitos vêm de ambiguidade, recursão à esquerda ou falta de fatoração.

21 · Simulador

Calcule FIRST/FOLLOW automaticamente

O simulador abaixo recebe uma gramática e mostra FIRST e FOLLOW de cada não-terminal. Use a gramática de expressões já carregada como ponto de partida e experimente alterá-la.

Tente: o que acontece com os conjuntos se você adicionar uma produção com ε? E se introduzir recursão à esquerda? Observe como os conjuntos mudam.

Mão na massa · colaborativo

Atividade em grupo · Mutirão de revisão (Prova 1)

Em grupos, montem um mapa de revisão das semanas 1–6.

⏱️ 30 min👥 grupos de 4🧩 estudo colaborativo

Roteiro

Cada integrante fica responsável por um tema: léxico, ER/autômatos, GLC, parsing descendente.
Montem um mapa mental conectando os temas (uma página).
Criem 2 questões originais por tema e troquem com outro grupo.
Resolvam as questões recebidas e discutam.

Léxicotokens, ER, autômatos

SintaxeGLC, árvores, ambiguidade

Parsingdescendente, FIRST/FOLLOW

Curadormonta o mapa final

📤 Entrega: Mapa mental de revisão + 8 questões autorais com gabarito.

Teste seu conhecimento

Mini-quiz · Aula 7

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

0/20

📌 Resumo — leve isto para a prova

FIRST = terminais iniciais (pode conter ε); FOLLOW = terminais seguintes (contém $, nunca ε).
LL(1) = leitura da esquerda para a direita, derivação mais à esquerda, 1 lookahead.
A tabela preditiva sem conflitos significa gramática LL(1).
Conflitos vêm de ambiguidade, recursão à esquerda ou falta de fatoração.
Nem toda linguagem livre de contexto admite gramática LL(1).