LL(1), FIRST/FOLLOW · Revisão

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).

A aula 6 terminou com um parser que funciona: uma função por não-terminal, a gramática sem recursão à esquerda e fatorada. Mas deixou uma pergunta sem resposta: como saber que a escolha com um token está sempre certa? A descida escolhe “a primeira alternativa cujo FIRST contém o token” — e, quando nenhuma contém, segue pela ε, sem olhar o que vem depois. Isso funciona na gramática da aula. Em outras, falha em silêncio. E, antes da aula 6, só com a gramática da aula 5, a única saída seria tentar: derivar, conferir os terminais com a entrada e voltar atrás a cada engano.

É essa a vantagem para o compilador: a aula 6 dá um parser rápido; a aula 7 dá a certeza de que ele está certo — ou aponta a célula exata onde não está, antes de o primeiro programa ser compilado. A bancada abaixo põe as três aulas lado a lado: a mesma gramática, o mesmo programa e a mesma unidade de trabalho. Siga as três fases — antes do primeiro programa, este programa, todos os programas curtos — e repare em quando cada uma descobre o defeito: na gramática ③, o checklist da aula 6 aprova tudo e a descida recusa um programa válido; a tabela recusa a gramática antes de rodar e aponta a célula.

• 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 aulas 1 a 6.

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.

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

O símbolo $ marca o fim da entrada.

Esse quadro não sai de uma vez: sai de repetir as regras, produção por produção, até uma rodada inteira não acrescentar nada — o ponto fixo. Na bancada abaixo o cálculo roda exatamente assim, na ordem em que você faria no papel: dá para ver E esperando T, que espera F, e clicar em qualquer símbolo para saber quem o colocou ali.

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).

Hora de montar a tabela com as suas mãos. Na bancada abaixo, uma produção por vez: marque as colunas em que ela entra e confira — a correção diz, coluna a coluna, se ela entrou pelo FIRST, pelo FOLLOW, ou por que não entra. Repare em E' → ε: é a produção que só entra pelo FOLLOW.

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

O último elo é a decisão. Na bancada abaixo, o analisador preditivo usa a tabela: com um não-terminal no topo da pilha, ele consulta uma célula — M[topo, token] — e ela acende na tabela. Com um terminal no topo, ele nem olha a tabela: só confere se o token é o esperado.

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.

Os conflitos têm dois tipos, e vale saber dar nome a eles:

Na bancada abaixo, oito gramáticas: decida se cada uma é LL(1) e, se não for, que conflito ela tem. Depois da resposta, a tabela mostra a célula culpada e, quando existe, o remédio da aula 6 é aplicado na hora.

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.

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.

Todas as bancadas desta aula aceitam a sua gramática: escreva na caixa de texto e tudo se recalcula. Para os conjuntos e a tabela prontos, use a mesa LL(1); para ver o cálculo acontecer, o ponto fixo rodada a rodada.

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 — e em que célula da tabela o conflito aparece.