❧ Parsing LL(1) ❧

Introdução13.1

Agora vamos transformar a ideia de parser preditivo em um procedimento mecânico. Em vez de tentar caminhos e voltar atrás, o analisador vai olhar um único símbolo da entrada e decidir qual produção usar.

Até aqui, você já viu que um parser descendente pode falhar por três motivos muito parecidos por fora, mas diferentes por dentro. Ele pode não saber qual regra escolher, pode voltar ao mesmo não terminal sem avançar, ou pode ter uma gramática boa para a linguagem mas ruim para decisão local. O LL(1) aparece justamente para organizar esse ponto de decisão.

O problema da decisão local13.2

Na aula anterior, vimos que uma gramática pode ser correta do ponto de vista da linguagem e ainda assim ser ruim para um parser descendente. Às vezes, o problema não é mais a estrutura semântica, mas a capacidade de decidir cedo o bastante.

O LL(1) surge exatamente para isso. Ele organiza a análise sintática em torno de três elementos:

• o buffer de entrada, que guarda a cadeia a reconhecer e termina em $;
• a pilha de análise, que começa com $ no fundo e o símbolo inicial no topo;
• a tabela de análise, que diz qual produção usar a partir do topo da pilha e do símbolo atual da entrada.

Em termos práticos, o parser sempre pergunta a mesma coisa. O que está no topo da pilha, o que está olhando na entrada e qual produção a tabela manda usar para esse par.

Repare que o parser não precisa adivinhar. Ele precisa apenas consultar a tabela certa.

O que significa LL(1)13.3

A sigla LL(1) resume a estratégia do analisador.

• O primeiro L significa left-to-right. A leitura da entrada acontece da esquerda para a direita.
• O segundo L significa leftmost derivation. A derivação construída é sempre a mais à esquerda.
• O 1 indica lookahead de um símbolo. Em cada decisão, o parser olha apenas o próximo terminal da entrada.

Essa combinação é importante porque liga a teoria da derivação ao comportamento real do algoritmo.

Conjuntos FIRST e FOLLOW13.4

Para montar a tabela LL(1), precisamos de dois tipos de informação. Primeiro, o que pode começar uma derivação. Depois, o que pode aparecer logo após um não terminal quando ele ainda está no meio de uma frase.

A ideia por trás dos dois conjuntos é bem diferente. O FIRST responde à pergunta sobre início. O FOLLOW responde à pergunta sobre continuidade. Um olha para dentro da produção, o outro olha para fora dela, para o contexto em que o símbolo aparece.

FIRST13.4.1

O conjunto $FIRST(A)$ contém os terminais que podem iniciar alguma cadeia derivada de $A$.

Se você quiser decidir qual produção pode ser usada sem tentativa e erro, esse é o primeiro dado que precisa. O FIRST diz o que pode aparecer logo na frente quando o não terminal for expandido.

Ele pode conter $\epsilon$, porque uma variável pode desaparecer por completo antes de qualquer terminal aparecer.

Se $A \to a\alpha$, então $a \in FIRST(A)$.

Se $A$ pode derivar o vazio, então $\epsilon \in FIRST(A)$.

Exemplo mínimo de FIRST13.4.1.1

Considere apenas:

$$ A \to a \mid \epsilon $$

Aqui a leitura é direta. Se a derivação escolhe a primeira produção, a cadeia começa com $a$. Se escolhe a segunda, ela desaparece. O conjunto precisa registrar as duas possibilidades porque o parser também precisa saber quando uma variável pode sumir sem consumir entrada.

$$ FIRST(A) = \{a, \epsilon\} $$

Isso serve para entender a notação. Não há segredo aqui, só a pergunta certa. Qual símbolo pode aparecer primeiro nessa expansão.

Em produções maiores, o raciocínio é o mesmo, só que você precisa atravessar os símbolos da direita até encontrar o primeiro terminal obrigatório. Se o começo puder desaparecer, o próximo símbolo passa a ser o novo candidato para o FIRST.

FOLLOW13.4.2

O conjunto $FOLLOW(A)$ contém os terminais que podem aparecer imediatamente à direita de $A$ em alguma derivação.

Esse conjunto é o que permite ao parser tomar a decisão quando uma produção termina com vazio. Se você expandiu uma variável e ela desapareceu, o que importa agora é o símbolo que estava esperando para entrar no lugar dela.

O FOLLOW nunca contém $\epsilon$. Se a variável desapareceu, o vazio não vira símbolo visível na entrada. Ele só indica que precisamos olhar para o que vem depois.

O símbolo $ sempre pertence a $FOLLOW(S)$, onde $S$ é o símbolo inicial.

Leia essas regras assim.

• Se depois de $B$ ainda existe um pedaço $\beta$, então tudo o que pode começar esse pedaço pode aparecer logo depois de $B$.
• Se esse pedaço $\beta$ pode sumir, então $B$ também pode herdar o que vem depois de $A$.

Na forma formal:

• Se $A \to \alpha B\beta$, então tudo de $FIRST(\beta)$, exceto $\epsilon$, entra em $FOLLOW(B)$.
• Se $\beta \Rightarrow^* \epsilon$, então $FOLLOW(A)$ entra em $FOLLOW(B)$.
• Em particular, se $A \to \alpha B$, então $FOLLOW(A)$ entra em $FOLLOW(B)$.

Exemplo mínimo de FOLLOW13.4.2.1

Considere:

$$ \begin{split} S &\to AB \\ A &\to a \\ B &\to b \end{split} $$

Como $S$ é o símbolo inicial, temos:

$$ FOLLOW(S) = \{\$\} $$

Como $A$ aparece antes de $B$, tudo o que pode começar $B$ também pode aparecer logo depois de $A$. Em outras palavras, o FOLLOW(A) precisa incluir o começo de quem vem na sequência, porque esse começo ocupa exatamente a posição que sobra depois de $A$.

E como $B$ está no fim da produção de $S$, ele herda o que pode seguir $S$. O símbolo de fim entra aqui porque ele representa o contexto onde a análise pode terminar de verdade.

Exemplo guiado de FIRST e FOLLOW13.4.3

Considere a gramática:

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{S, A, B, C, D\} \\ T &= \{a, b, c, d\} \\ S &= S \end{split} \hspace{1cm} \begin{split} P = S &\to ABCD \\ A &\to a \mid \epsilon \\ B &\to b \mid \epsilon \\ C &\to c \mid \epsilon \\ D &\to d \mid \epsilon \end{split} $$

Vamos calcular os conjuntos completos primeiro, e só depois interpretar o que eles significam.

$$ \begin{split} FIRST(A) &= \{a, \epsilon\} \\ FIRST(B) &= \{b, \epsilon\} \\ FIRST(C) &= \{c, \epsilon\} \\ FIRST(D) &= \{d, \epsilon\} \end{split} $$

$$ \begin{split} FIRST(S) &= \{a, b, c, d, \epsilon\} \end{split} $$

$$ \begin{split} FOLLOW(S) &= \{\$\} \\ FOLLOW(A) &= \{b, c, d, \$\} \\ FOLLOW(B) &= \{c, d, \$\} \\ FOLLOW(C) &= \{d, \$\} \\ FOLLOW(D) &= \{\$\} \end{split} $$

Agora olhe para $S \to ABCD$. Como $A$ pode sumir, o parser precisa continuar olhando para $B$. Como $B$ também pode sumir, ele continua para $C$. Como $C$ também pode sumir, ele continua para $D$.

Isso significa que o começo de $S$ pode vir de qualquer um deles.

$$ \begin{split} FIRST(S) &= \{a, b, c, d, \epsilon\} \end{split} $$

Agora os conjuntos FOLLOW. Começamos com o símbolo inicial.

$$ \begin{split} FOLLOW(S) &= \{\$\} \\ FOLLOW(A) &= \{b, c, d, \$\} \\ FOLLOW(B) &= \{c, d, \$\} \\ FOLLOW(C) &= \{d, \$\} \\ FOLLOW(D) &= \{\$\} \end{split} $$

O ponto importante aqui é observar como os conjuntos se propagam. Como $A$ pode desaparecer, o que vem depois dele em $S$ passa a influenciar seu FOLLOW. O mesmo acontece com $B$, $C$ e $D$.

Essa propagação existe porque o parser precisa saber o que pode ocupar o lugar de um símbolo que sumiu. O FOLLOW é, na prática, um conjunto de contextos permitidos.

Se você quiser enxergar isso como uma regra de leitura, pense assim. O FOLLOW sempre pergunta qual símbolo pode ocupar o lugar que ficou livre depois que uma parte some.

Por isso ele nunca é calculado isoladamente só olhando a própria variável. Ele depende do lado direito das produções e, quando necessário, do FOLLOW de outras variáveis que estão mais à esquerda na mesma cadeia.

Segundo Exemplo de Conjuntos First-Follow13.4.3.1

Considere:

$$ \begin{split} S &\to A B c \\ A &\to a \mid \epsilon \\ B &\to b \mid \epsilon \end{split} $$

Aqui o raciocínio já exige mais cuidado.

Primeiro, feche todos os FIRST.

$$ \begin{split} FIRST(A) &= \{a, \epsilon\} \\ FIRST(B) &= \{b, \epsilon\} \\ FIRST(S) &= \{a, b, c\} \end{split} $$

Depois, feche todos os FOLLOW.

$$ \begin{split} FOLLOW(S) &= \{\$\} \\ FOLLOW(B) &= \{c\} \\ FOLLOW(A) &= \{b, c\} \end{split} $$

O objetivo agora é ver como os dois conjuntos se combinam. O FIRST nos diz o que pode surgir imediatamente depois de um símbolo. O FOLLOW entra quando esse símbolo pode sumir e o próximo da fila precisa assumir a posição.

• Como $B$ vem antes de $c$, temos $c \in FOLLOW(B)$.
• Como $A$ vem antes de $B$, tudo de $FIRST(B)$, exceto $\epsilon$, entra em $FOLLOW(A)$, porque qualquer coisa que possa começar B pode aparecer logo depois de A.
• Como $B$ pode sumir, $c$ também entra em $FOLLOW(A)$, porque nesse caso o c passa a ser o primeiro símbolo realmente visível depois de A.

Esse é o tipo de passagem que mais costuma confundir. Não basta olhar o símbolo imediatamente depois. Você precisa continuar andando enquanto o que está à direita puder desaparecer.

É exatamente essa ideia que torna o cálculo útil para a tabela LL(1). O conjunto não está tentando descrever a gramática inteira, e sim o contexto imediato que o parser precisa enxergar para decidir sem voltar atrás.

Como montar a tabela LL(1)13.5

Antes de preencher qualquer célula, feche os conjuntos de FIRST e FOLLOW da gramática que você vai usar.

Por exemplo, na gramática de expressões:

$$ \begin{split} E &\to T E' \\ E' &\to + T E' \mid \epsilon \\ T &\to F T' \\ T' &\to * F T' \mid \epsilon \\ F &\to (E) \mid id \end{split} $$

Primeiro, os conjuntos de início.

$$ \begin{split} FIRST(E) &= FIRST(T) = \{(, id\} \\ FIRST(E') &= \{+, \epsilon\} \\ FIRST(T) &= FIRST(F) = \{(, id\} \\ FIRST(T') &= \{*, \epsilon\} \\ FIRST(F) &= \{(, id\} \end{split} $$

Depois, os conjuntos de continuidade.

$$ \begin{split} FOLLOW(E) &= \{\$, )\} \\ FOLLOW(E') &= \{\$, )\} \\ FOLLOW(T) &= \{+, \$, )\} \\ FOLLOW(T') &= \{+, \$, )\} \\ FOLLOW(F) &= \{*, +, \$, )\} \end{split} $$

Agora sim, a tabela LL(1) tem uma linha para cada não terminal e uma coluna para cada terminal, mais a coluna do $.

Para cada produção $A \to \alpha$:

1. coloque essa produção em todas as células $M[A, a]$ para todo $a \in FIRST(\alpha)$, exceto $\epsilon$;
2. se $\epsilon \in FIRST(\alpha)$, coloque a produção em todas as células $M[A, b]$ para todo $b \in FOLLOW(A)$.

Em outras palavras, quando o lado direito pode virar vazio, a produção não entra por uma coluna de vazio. Ela entra pelas colunas de contexto, isto é, pelas colunas de $FOLLOW(A)$.

Se alguma célula receber mais de uma produção, a gramática não é LL(1).

Exemplo curto13.5.1

Considere:

$$ \begin{split} S &\to aA \mid b \\ A &\to c \mid \epsilon \end{split} $$

Antes de discutir a tabela, feche os conjuntos.

$$ \begin{split} FIRST(S) &= \{a, b\} \\ FIRST(A) &= \{c, \epsilon\} \end{split} $$

$$ \begin{split} FOLLOW(S) &= \{\$\} \\ FOLLOW(A) &= \{\$\} \end{split} $$

Com isso em mãos, a leitura da tabela fica imediata. $M[S, a]$ recebe $S \to aA$ e $M[S, b]$ recebe $S \to b$. Para $A$, a produção $A \to c$ entra em $M[A, c]$ e a produção $A \to \epsilon$ vai para as colunas de $FOLLOW(A)$.

Esse exemplo é pequeno de propósito. Ele mostra a regra sem esconder nada atrás de uma expressão maior.

$$ \begin{array}{c|ccc} & a & b & c \\ \hline S & S \to aA & S \to b & \\ A & & & A \to c \end{array} $$

Quando $\epsilon$ aparece em uma produção, o preenchimento deixa de olhar apenas para o que a produção começa e passa a olhar para o contexto que vem depois.

Exemplo completo com a gramática de parênteses13.5.2

Considere:

$$ S \to (S) \mid \epsilon $$

Os conjuntos são simples, mas a lógica é muito útil.

$$ \begin{split} FIRST(S) &= \{(, \epsilon\} \\ FOLLOW(S) &= \{\$, )\} \end{split} $$

Agora a tabela.

$$ \begin{array}{c|ccc} & ( & ) & \$ \\ \hline S & S \to (S) & S \to \epsilon & S \to \epsilon \end{array} $$

Essa tabela já permite reconhecer qualquer número de pares de parênteses bem formados, inclusive a cadeia vazia.

Exemplo completo com expressões13.6

Agora vamos para a gramática clássica de expressões.

$$ \begin{split} E &\to T E' \\ E' &\to + T E' \mid \epsilon \\ T &\to F T' \\ T' &\to * F T' \mid \epsilon \\ F &\to (E) \mid id \end{split} $$

Os conjuntos necessários são:

$$ \begin{split} FIRST(E) &= FIRST(T) = \{(, id\} \\ FIRST(E') &= \{+, \epsilon\} \\ FIRST(T) &= FIRST(F) = \{(, id\} \\ FIRST(T') &= \{*, \epsilon\} \\ FIRST(F) &= \{(, id\} \end{split} $$

E os FOLLOW mais importantes são:

$$ \begin{split} FOLLOW(E) &= \{\$, )\} \\ FOLLOW(E') &= \{\$, )\} \\ FOLLOW(T) &= \{+, \$, )\} \\ FOLLOW(T') &= \{+, \$, )\} \\ FOLLOW(F) &= \{*, +, \$, )\} \end{split} $$

Isso basta para preencher a tabela. As produções com $\epsilon$ vão exatamente para as colunas do FOLLOW correspondente.

Tabela de análise13.6.1

$$ \begin{array}{c|cccccc} & id & + & * & ( & ) & \$ \\ \hline E & E \to T E' & & & E \to T E' & & \\ E' & & E' \to + T E' & & & E' \to \epsilon & E' \to \epsilon \\ T & T \to F T' & & & T \to F T' & & \\ T' & & T' \to \epsilon & T' \to * F T' & & T' \to \epsilon & T' \to \epsilon \\ F & F \to id & & & F \to (E) & & \end{array} $$

Essa tabela já mostra o ponto essencial. Quando a produção pode desaparecer, ela aparece exatamente nas colunas do FOLLOW.

Agora vale ler uma linha por vez.

• Em $E$, o parser só entra por id ou (.
• Em $E'$, o parser continua quando encontra +, ou para quando vê o fim da expressão ou um ).
• Em $T'$, o parser continua com *, ou encerra o nível de multiplicação quando encontra um símbolo de nível mais fraco.

O que essa tabela prova13.6.1.1

Ela prova que a gramática foi organizada para que cada símbolo da entrada leve a uma única decisão local. Quando isso acontece, o parser descendente não precisa testar alternativas.

Traço curto com expressão simples13.6.2

Antes de ir para a execução completa, veja uma leitura mínima.

Entrada:

$$ id $$

Execução inicial:

Passo	Pilha	Entrada	Ação
1	[$, E]	id$	Consulta $M[E, id]$
2	[$, E', T]	id$	Expande $E \to T E'$
3	[$, E', T', F]	id$	Expande $T \to F T'$
4	[$, E', T', id]	id$	Expande $F \to id$
5	[$, E', T']	$	Faz match de id
6	[$, E']	$	Expande $T' \to \epsilon$
7	[$]	$	Expande $E' \to \epsilon$
8	[$]	$	Sucesso

Esse traço é pequeno, mas já mostra a mecânica completa. A pilha cresce com expansões e encolhe com match.

Executando o algoritmo13.7

O parser começa com a pilha:

$$ [\$, S] $$

e com a entrada terminada em:

$$ \text{palavra}\$ $$

Em cada passo, acontecem duas possibilidades.

• Se o topo da pilha é um terminal igual ao símbolo atual da entrada, ocorre match. O terminal sai da pilha e o ponteiro avança.
• Se o topo da pilha é um não terminal, o parser consulta a tabela e expande o símbolo pela produção indicada.

Se a célula da tabela estiver vazia, há erro sintático.

Rastreamento da palavra (())13.7.1

Considere a gramática:

$$ S \to (S) \mid \epsilon $$

Uma execução possível é:

Passo	Pilha	Entrada	Ação
1	[$, S]	(())\$	Consulta $M[S, (]$
2	[$, ), S, (]	(())\$	Expande $S \to (S)$
3	[$, ), S]	(())\$	Faz match de (
4	[$, ), S]	())\$	Consulta $M[S, (]$
5	[$, ), ), S, (]	())\$	Expande $S \to (S)$
6	[$, ), ), S]	())\$	Faz match de (
7	[$, ), )]	))\$	Consulta $M[S, )]$
8	[$, ), )]	))\$	Expande $S \to \epsilon$
9	[$, )]	))\$	Faz match de )
10	[$]	)\$	Faz match de )
11	[$]	$	Sucesso

O rastreamento mostra a ideia central do LL(1) na prática. A pilha dirige a análise e a tabela evita qualquer tentativa e erro.

Outro traço curto, agora com três decisões diferentes13.7.1.1

Considere a palavra:

$$ id + id * id $$

Você não precisa seguir toda a execução para perceber o padrão. Primeiro o parser reconhece o primeiro identificador. Depois ele vê o + e sabe que precisa continuar em $E'$. Em seguida, ao entrar no lado direito, ele encontra id * id e deixa o nível de multiplicação resolver * antes de voltar ao nível da soma.

Esse é o ponto mais importante do LL(1). A precedência não aparece como uma regra separada no algoritmo. Ela aparece embutida na tabela e na forma da gramática.

Questões13.8

Próximos passos13.9

Agora você já tem a base formal do parser preditivo. Na próxima aula, vamos fazer uma revisão para consolidar esses conceitos antes de avançar. Depois disso, o próximo passo será a geração de código na parte sintática.