Elementar meu caro Watson! Mesmo que Sherlock nunca tenha dito esta frase nos livros de Sir Arthur Conan Doyle, a lembrança do grande detetive ocupa meu imaginário sempre que falo de parsers. Assim como o grande detetive, o trabalho do parser será verificar todos os detalhes de uma cena e validar cada um dos seus itens em relação a um contexto. No nosso caso, a cena será formada por um string e o contexto do crime, será determinado por uma Tabela de Derivação. Infelizmente nosso detetive, o parser $LL(1)$, nem de perto terá a mesma capacidade de Sherlock Holmes. Ainda que seja eficiente, um parser $LL(1)$ é linear e determinístico e, pensando bem, esta foi uma metáfora ruim. Mas, eu sempre quis começar um texto falado: elementar meu caro Watson!.

Em geral, ainda que muitos lenços de papel tenham sido gastos durantes as avaliações de final de período, parsers $LL(1)$ são algoritmos simples.

Um parser $LL(1)$ é um tipo de analisador sintático descendente que utiliza a análise preditiva, e uma tabela que chamarei de Tabela de Derivação, para determinar qual será a regra de produção que deverá ser aplicada em cada etapa da análise a regra de produção que será utilizada para substituir um símbolo não-terminal por um terminal, criando uma árvore sintática e permitindo a identificação de um string como parte de uma determinada linguagem. Esta ideia começou com o trabalho On the Translation of Languages from Left to Right de Donald Knuth mas foi sendo aprimorada ao longo do tempo por pesquisadores como Alfred Aho e Jeffrey Ullman, nos anos 1970 1980.

A análise preditiva é um tipo de análise descendente que usa uma pilha para armazenar os símbolos esperados e os conjuntos $FIRST$ e $FOLLOW$ para prever qual regra de produção aplicar em cada etapa do processo de análise. Essa previsão permite que o analisador tome decisões sem precisar retroceder, tornando a análise mais eficiente computacionalmente. Esta análise preditiva será a ação que um parser $LL(1)$ irá utilizar para validar os strings de uma determinada linguagem, símbolo por símbolo.

Para atingir meu objetivo, com este texto, as linguagens que usaremos como exemplo serão representadas apenas pelo conjunto de regras de produção da sua gramática. Vou manter a álgebra o mais longe possível e se o conjunto de regras de produção estiver perfeitamente construído todos os elementos da gramática poderão ser identificados. isso permitirá que aqueles com arrepios algébricos possam se dedicar a uma análise formal da linguagem.

Outro ponto importante, neste texto, símbolos não-terminais serão representados em caracteres latinos maiúsculos e símbolos terminais em caracteres latinos minúsculos. A única exceção será $ɛ$ para representar uma produção vazia.

Os parsers preditivos são analisadores sintáticos descendentes (top-down) que utilizam um único símbolo de lookahead (antecipação) para determinar a regra de produção correta a ser aplicada em cada etapa da análise. Eles predizem qual regra usar com base no próximo símbolo da entrada e no não-terminal atualmente sendo analisado. O termo $LL(1)$ significa:

• L: Left-to-right scan (varredura da esquerda para a direita) da entrada.
• L: Leftmost derivation (derivação mais à esquerda) da gramática.
• 1: Um símbolo de lookahead (antecipação) para tomada de decisão.

Um parser $LL(1)$, requer uma gramática $LL(1)$. Nesta gramática não pode existir qualquer ambiguidade na escolha da regra de produção que será aplicada a cada símbolo de lookahead. Além disso, a gramática não pode ter recursão à esquerda, seja esta recursão direta ou indireta. A recursão à esquerda é um desafio considerável. Existem duas formas de recursão à esquerda:

• Recursão à Esquerda Direta: ocorre quando um símbolo não-terminal pode ser derivado em uma sequência que começa com ele mesmo. Por exemplo, na regra $A → Aa \mid b$, o símbolo $A$ pode ser substituído no processo de derivação em $Aa$, onde $A$ aparece novamente no início da regra. E aqui está o laço infinito.

• Recursão à Esquerda Indireta: acontece quando um símbolo não-terminal pode ser derivado em uma sequência que começa com outro símbolo não-terminal, que por sua vez pode ser derivado de volta ao símbolo original. Ilustrando, nas regras $A → Ba$ e $B → Ab$, $A$ deriva para $Ba$, $B$ deriva para $Ab$ e $Ab$ pode derivar novamente para $A$, criando outro laço infinito.

Além do perigo do laço de repetição infinito que faz o pobre Turing se revolver no túmulo, a recursão à esquerda impede o desenvolvimento de uma Tabela de Derivação. Graças a criação de regras em conflito. Duas ou mais regras, para a mesma combinação de símbolo terminal e símbolo não-terminal em um determinado momento do processo de parser.

Felizmente, existem técnicas para eliminar a recursão à esquerda em gramáticas livres de contexto. Uma técnica comum e eficaz envolve a introdução de novos símbolos não terminais e a substituição de regras recursivas por regras equivalentes que não apresentem recursão. Em alguns casos, a substituição direta dos símbolos não terminais recursivos por suas respectivas regras pode ser suficiente para eliminar a recursão à esquerda direta. Outra técnica, a fatoração à esquerda, pode ser utilizada para eliminar ambiguidades na gramática, mas não resolve diretamente o problema da recursão.

Exemplo 1: eliminando a Recursão à Esquerda Direta, considere a regra $A → Aa \mid b$. Esta regra pode ser reescrita como:

1. $A \to bA’$
2. $A’ \to aA’ \mid \varepsilon$

Agora, a gramática não contém mais recursão à esquerda direta. Este é um exemplo simples, adequado a este texto cujo objetivo é o parser em si. A nova regra inclui o não-terminal $A’$, que permite zero ou mais repetições do símbolo $a$. O uso de $\varepsilon$ (a produção vazia) permite terminar a derivação de $A’$. Será?

Para verificar a recursão à esquerda indireta, você precisa observar se é possível derivar uma recursão através de uma cadeia de substituições:o:

1. Substituindo $A$:
   • $A \rightarrow bA’$
2. Substituindo $A’$:
   • $A’ \rightarrow aA’$
   • $A’ \rightarrow \varepsilon$

Observe que substituindo $A$ por $bA’$ e depois $A’$ por $aA’$ ou $\varepsilon$ não leva de volta a $A$. E parece não haver recursão. Contudo, é necessário verificar se foi criada alguma recursão à esquerda indireta, focando em $A’$:

• Primeira substituição:
  • $A \rightarrow bA’$
• Substituindo $A’$ por $aA’$:
  • $bA’ \rightarrow b(aA’)$
  • $bA’ \rightarrow baA’$
• Substituindo novamente $A’$ por $aA’$:
  • $baA’ \rightarrow baaA’$

• E assim por diante… Aqui, $A’$ substitui a si próprio com um prefixo $a$, mas isto não cria recursão indireta ao $A’$ inicial de forma a levar a uma cadeia circular que retorne ao símbolo inicial $A$. A gramática transformada não apresenta recursão à esquerda indireta para $A’$.

• $A$: Não tem recursão à esquerda direta nem indireta, pois $A \rightarrow bA’$ começa com um terminal.
• $A’$: A regra $A’ \rightarrow aA’ \mid \varepsilon$ apenas permite que $A’$ produza cadeias de $a$ seguidos possivelmente por $\varepsilon$, sem retornar a um estado anterior que causaria recursão indireta.

Portanto, a transformação feita elimina a recursão à esquerda direta sem introduzir recursão à esquerda indireta. A recursão â esquerda indireta é mais complexa e requer um texto específico para o assunto. Mas, em linhas gerais você terá que refazer a gramática em face dos objetivos originais para eliminar este tipo de recursão. Vou deixar por sua conta resolver a recursão à esquerda indireta e a ambiguidade que surjam nas gramáticas que você criar.

Como a classe de gramáticas para um parser $LL(1)$ é limitada (nem todas as gramáticas livres de contexto são $LL(1)$, é muito comum que seja necessário modificar a sua ideia original de gramática para eliminar ambiguidades e recursões à esquerda. Um parser $LL(1)$, para funcionar, precisa dos seguintes elementos:

1. Tabela de Derivação: O parser $LL(1)$ utiliza uma Tabela de Derivação, ou Tabela de Derivação, que mapeia cada combinação de não-terminal e terminal (ou símbolo de fim de entrada) para a regra de produção que deve ser aplicada. Essa tabela é construída a partir da gramática e dos conjuntos $FIRST$ e $FOLLOW$ e será o mapa que guiará todo o processo de análise sintática.

2. Pilha e Buffer: O parser mantém uma pilha e lê a entrada da esquerda para a direita, carácter por carácter. A pilha inicialmente contém o símbolo inicial da gramática e o símbolo de fim de entrada, $$$. A entrada frequentemente é mantida em uma estrutura de dados com funcionalidades de buffer, que pode ser a própria string que está sendo analisada.

3. Análise: Em cada passo:
   • O parser consulta a Tabela de Derivação usando como índices o não-terminal no topo da pilha e o próximo símbolo da entrada.
   • A tabela indica a produção a ser aplicada.
   • O não-terminal no topo da pilha é substituído pelos símbolos da produção (empilhados em ordem inversa).
   • Se o topo da pilha for um terminal que coincide com o próximo símbolo da entrada, ambos são removidos da pilha e da entrada.
4. Sucesso ou Erro: A análise termina com sucesso quando a pilha e a entrada estão vazias. Caso contrário, ocorre um erro sintático. Erros poderão ocorrer durante o processo sempre que a combinação de símbolos na pilha e no buffer apontarem para uma célula vazia da Tabela de Derivação.

Criar um parser $LL(1)$ geralmente exige mais do que apenas os conjuntos $FIRST$ e $FOLLOW$. Este é um processo que envolve garantir a adequação da gramática e seguir etapas específicas para construir a Tabela de Derivação. Vou explorar esse processo de forma mais clara e detalhada, ainda neste texto.

A gramática criada para o parser $LL(1)$ não pode ter qualquer ambiguidade. Ou seja, cada string da linguagem deve ser derivada em uma e apenas uma árvore sintática. Acrescente-se a isso que a gramática não deve ter regras do tipo $A \rightarrow A\alpha$ (recursão direta) nem $A \rightarrow B\alpha$ e $B \rightarrow AB$ (recursão indireta). Ou seja, uma gramática sem recursão à esquerda.

Uma vez que tenha uma gramática adequada, será possível construir uma Tabela de Derivação $LL(1)$. Para isso vamos precisar:

1. Encontrar os conjuntos $FIRST$ e $FOLLOW$:

   • $FIRST(A)$: O conjunto de terminais que podem iniciar uma derivação de $A$.

   • $FOLLOW(A)$: O conjunto de terminais que podem aparecer imediatamente após $A$ em uma derivação.

2. Considerar Símbolos Nullable:

   • Um símbolo é nullable se pode derivar a cadeia vazia ($\epsilon$).

   • O cálculo de $FIRST$ e $FOLLOW$ precisa levar em conta os símbolos nullable.

3. Preencher a Tabela:
   • Para cada produção $A \rightarrow \alpha$:

     • Se $\alpha$ começa com um terminal $a$, adicione a produção à célula $(A, a)$.

     • Se $\alpha$ é nullable e $b$ está em $FOLLOW(A)$, adicione a produção à célula $(A, b)$.

Um símbolo não-terminal é nullable se ele pode ser derivado para a cadeia vazia ($\varepsilon$), ou seja, se ele pode desaparecer durante uma derivação. Por exemplo, na produção $A \rightarrow BC$, se tanto $B$ quanto $C$ são nullable, então $A$ também é nullable. A presença de símbolos nullable exige alguns ajustes nos algoritmos de identificação de $FIRST$ e $FOLLOW$:

• $FIRST$: Se um símbolo é nullable, será necessário adicioná-lo $\epsilon$ ao seu conjunto $FIRST$. Além disso, ao calcular o $FIRST$ de uma sequência de símbolos, se um símbolo é nullable, também é necessário considerar o $FIRST$ do próximo símbolo.

• $FOLLOW$: Se um símbolo é nullable, ao calcular o $FOLLOW$ de um símbolo que o precede, também é imprescindível considerar o $FOLLOW$ do símbolo anterior.

Exemplo 2: Considere a gramática representada pelo conjunto de regras de produção a seguir:

1. $S → AB$
2. $A → \varepsilon$
3. $B → b \mid \varepsilon$

Cálculo de Nullable

• $A \rightarrow \epsilon$, então $A$ é nullable.
• $B \rightarrow \epsilon$, então $B$ é nullable.
• Para $S$, ambos $A$ e $B$ são nullable, então $S$ é nullable.

Cálculo de $FIRST$

• $FIRST(A) = { \epsilon }$
• $FIRST(B) = { b, \epsilon }$
• $FIRST(S) = FIRST(AB) = FIRST(A) ∪ FIRST(B) = { \epsilon } ∪ { b, \epsilon } = { b, \epsilon }$

Cálculo de $FOLLOW$

• $FOLLOW(S) = { $ }$
• $FOLLOW(A) = FIRST(B) = { b, \epsilon } (excluindo \quad \epsilon)$
• $FOLLOW(B) = FOLLOW(S) = { $ }$

Neste exemplo, os símbolos nullable influenciam diretamente os conjuntos $FIRST$ e $FOLLOW$, permitindo a construção correta da tabela de parsing $LL(1)$ e garantindo que a gramática pode ser analisada de forma preditiva com um símbolo de lookahead.

Tabela de Derivação $LL(1)$

	$b$	$\$$
$S$	$S \rightarrow AB$	$S \rightarrow AB$
$A$	$A \rightarrow \varepsilon$	$A \rightarrow \varepsilon$
$B$	$B \rightarrow b$	$B \rightarrow \varepsilon$

Observações Importantes sobre as regras de produção:

1. $S \rightarrow AB$: se o próximo símbolo de entrada for $b$ ou $$$, a produção $S \rightarrow AB$ deve ser aplicada.

2. $A \rightarrow \epsilon$: se o próximo símbolo de entrada for $b$ ou $$$, a produção $A \rightarrow \epsilon$ deve ser aplicada.

3. $B \rightarrow b$: se o próximo símbolo de entrada for $b$, a produção $B \rightarrow b$ deve ser aplicada.

4. $B \rightarrow \epsilon$: se o próximo símbolo de entrada for $$$, a produção $B \rightarrow \epsilon$ deve ser aplicada.

Voltando à gramática original: perceba que a gramática original é ambígua, pois a string vazia, $\varepsilon$, pode ser derivada de formas diferentes. Esta gramática foi criada, simples, para destacar a ambiguidade. Mas podemos modificar a esta gramática a nosso bel prazer. Lembre-se a linguagem é sua. Sendo assim:

$1. S \rightarrow b \mid \varepsilon $

Se observarmos as regras de produção:

• $S \rightarrow b$: essa produção gerará a string $b$.
• $S \rightarrow \epsilon$: essa produção gerará a string vazia.

Tabela de Derivação $LL(1)$ para a Gramática Modificada

	b	$\$$
$S$	$S \rightarrow b$	$S \rightarrow \epsilon$

Observações importantes sobre as regras de produção:

• Se o próximo símbolo de entrada for $b$, a produção $S \rightarrow b$ será aplicada.

• Se o próximo símbolo de entrada for $$$ (fim da entrada), a produção $S \rightarrow \epsilon$ será aplicada.

E pronto! Neste ponto do texto vimos tudo que precisamos ver e podemos parar. A pobre leitora, nesta altura do campeonato, deve estar pensando mal de mim. Eu sei, parece confuso. Talvez dois exemplos mais detalhados ajudem.

O Exemplo mais comum de todos

O exemplo a seguir está em todos os sites, livros e aulas que eu já vi disponíveis na internet. É tão comum que não me dei ao trabalho de procurar sua origem. Meu instinto me diz que deve ser do livro do Aho, mas não fui conferir. É um exemplo tão bom que deve ser do Aho. Enfim, vamos ao trabalho:

Gramática

Considere a gramática representada pelo conjunto de regras de produção a seguir:

$1. S \rightarrow E$

$2. E \rightarrow E + T \mid T$

$3. T \rightarrow T * F \mid F$

$4. F \rightarrow (E) \mid id$

Que permite criar os seguintes conjuntos:

$FIRST$

• $FIRST(S) = FIRST(E)$
• $FIRST(E) = { id, ( }$
• $FIRST(T) = { id, ( }$
• $FIRST(F) = { id, ( }$

$FOLLOW$

• $FOLLOW(S) = { $ }$
• $FOLLOW(E) = { +, ), $ }$
• $FOLLOW(T) = { +, *, ), $ }$
• $FOLLOW(F) = { +, *, ), $ }$

$NULLABLE$

Nenhuma das produções é nullable.

Os quais, por sua vez, irão permitir a criação da seguinte Tabela de Derivação

Tabela de Derivação $LL(1)$

	id	+	*	(	)	$
S	E			E
E	T			T
E	T	E + T		T	ε	ε
T	F	ε	T * F	F	ε	ε
F	id			(E)

Com a Tabela de Derivação em mãos, podemos partir para a criação do parser. Não vou criar nenhum algoritmo agora, na verdade, vou apenas reproduzir o processo passo a passo, na esperança que a corajosa leitora entenda o algoritmo muito antes de vê-lo formalizado ou implementado.

Processo de Parser Testando com $id + id * id$

Para verificar se a string id + id * id faz parte da linguagem representada na gramática dada pode ser identificada por um parser $LL(1)$ usando a Tabela de Derivação acima. Seguiremos um processo de análise preditiva descendente, começando pelo símbolo inicial. Usaremos uma pilha e a própria string de entrada como buffer

Vou começar com a pilha contendo o símbolo inicial da gramática, $S$, e a string de entrada id + id * id$, onde o $$$ indica o final da entrada. Se você estiver fazendo o parser na mão deverá seguir os seguintes passos:

1. Verificar o topo da pilha ($S$) e o próximo símbolo de entrada (‘id’).
2. Use a Tabela de Derivação para encontrar a produção apropriada, que, neste caso, será $S \rightarrow E$.
3. Substituir $S$ pela produção $E$ na pilha.
4. O próximo passo é verificar o topo da pilha ($E$) e o próximo símbolo de entrada (‘id’).
5. A Tabela indica a regra $E \rightarrow T$. Substitua $E$ por $T$.
6. O próximo passo é verificar o topo da pilha ($T$) e o próximo símbolo de entrada (‘id’).
7. A Tabela indica a regra $T \rightarrow F$. Substitua $T$ por $F$.
8. O próximo passo é verificar o topo da pilha ($F$) e o próximo símbolo de entrada (‘id’).
9. A Tabela indica $F \rightarrow id$. Substitua $F$ por ‘id’.
10. Agora a pilha tem ‘id’ e a entrada é “id + id * id$”. O próximo passo é consumir ‘id’ da entrada e da pilha, o valor na pilha e no buffer coincidem.
11. O topo da pilha agora é $T$ e o próximo símbolo de entrada é ‘+’.
12. A Tabela indica $E \rightarrow E + T$. Substituir $E$ por $E + T$.
13. Agora a pilha tem $T + T$ e a entrada é “+ id * id$”. Consumir ‘+’ da entrada e da pilha, pois eles coincidem.
14. O próximo passo é verificar o topo da pilha $T$ e o próximo símbolo de entrada (‘id’).
15. A Tabela indica $T \rightarrow F$. Substituir $T$ por $F$.
16. O próximo passo é verificar o topo da pilha $F$ e o próximo símbolo de entrada (‘id’).
17. A Tabela indica $F \rightarrow id$. Substituir $F$ por ‘id’.
18. Consumir ‘id’ da entrada e da pilha, pois eles coincidem.
19. O topo da pilha agora é $T$ e o próximo símbolo de entrada é ‘*’.
20. A Tabela indica $T \rightarrow T * F$. Substituir $T$ por $T * F$.
21. Consumir ‘*’ da entrada e da pilha, pois eles coincidem.
22. O próximo passo é verificar o topo da pilha $T$ e o próximo símbolo de entrada (‘id’).
23. A Tabela indica $T \rightarrow F$. Substituir $T$ por $F$.
24. O próximo passo é verificar o topo da pilha $F$ e o próximo símbolo de entrada (‘id’).
25. A Tabela indica $F \rightarrow id$. Substituir $F$ por ‘id’.
26. Consumir ‘id’ da entrada e da pilha, pois eles coincidem.
27. Finalmente, a pilha está vazia e a entrada foi completamente consumida.

Como foi possível consumir toda string da entrada, id + id * id$, e esvaziar a pilha sem encontrar nenhum erro, a string id + id * id é de fato parte da linguagem identificada pelo parser $LL(1)$ que poderá ser criado pela Tabela de Derivação que definimos. Mas estamos em universo onde o céu é sempre azul e as rosas estão sempre desbrochadas.

Testando com a string id - id * id

Vamos analisar a string id - id * id utilizando a Tabela de Derivação $LL(1)$ que foi estabelecida anteriormente, seguindo os passos do parser $LL(1)$. Começamos com a pilha inicial contendo o símbolo inicial $S$ e a entrada “id - id * id$”.

1. Verificar o topo da pilha ($S$) e o próximo símbolo de entrada (‘id’).
2. Use a Tabela de Derivação para encontrar a produção apropriada, que, neste caso, será $S \rightarrow E$.
3. Substituir $S$ pela produção $E$ na pilha.
4. O próximo passo é verificar o topo da pilha ($E$) e o próximo símbolo de entrada (‘id’).
5. A Tabela indica a regra $E \rightarrow T$. Substitua $E$ por $T$.
6. O próximo passo é verificar o topo da pilha ($T$) e o próximo símbolo de entrada (‘id’).
7. A Tabela indica a regra $T \rightarrow F$. Substitua $T$ por $F$.
8. O próximo passo é verificar o topo da pilha ($F$) e o próximo símbolo de entrada (‘id’).
9. A Tabela indica $F \rightarrow id$. Substitua $F$ por ‘id’.
10. Agora a pilha tem ‘id’ e a entrada é “id - id * id$”. O próximo passo é consumir ‘id’ da entrada e da pilha, o valor na pilha e no buffer coincidem.
11. Verificar o topo da pilha ($) e o próximo símbolo de entrada (‘-‘).
12. A Tabela não fornece uma produção para $T$ com entrada ‘-‘, indicando que a string não é aceita pela gramática dada.

Portanto, a string id - id id* não faz parte da linguagem definida pela gramática fornecida. O que deveria ser óbvio, já que a gramática não tem regras para lidar com o símbolo ‘-‘. Para que a gramática suporte outros símbolos como o ‘-‘, regras de produção adicionais devem ser incluídas.

Vimos, com a mesma gramática, as duas situações possíveis: ou a string faz parte da linguagem definida pela gramática, ou não. Simples assim.

Um exemplo nem tão comum

Este exemplo saiu das vozes da minha cabeça. Pode ser que exista em algum outro lugar, mas não me dei ao trabalho de verificar. É um exemplo que uso há muitos anos, em aula e já nem me preocupo com ele. Se souber a origem, fico grato.

Gramática

Considere a seguinte gramática para expressões booleanas ($OR, AND, NOT$), definida pelo conjunto de regras de produção a seguir:

$1. S \rightarrow B$

$2. B \rightarrow B \,\, OR \,\, M \mid M$

$3. M \rightarrow M \,\, AND \,\, N \mid N$

$4. N \rightarrow NOT \,\, N \mid (B) \,\mid id$

Novamente, graças ao conjunto de regras de produção podemos criar os seguintes conjuntos:

$FIRST$

• $FIRST(S) = FIRST(B)$
• $FIRST(B) = FIRST(M) = FIRST(N)$
• $FIRST(M) = FIRST(N)$
• $FIRST(N) = { NOT, (, id }$

$FOLLOW$

• $FOLLOW(S) = { $ }$
• $FOLLOW(B) = { OR, ), $ }$
• $FOLLOW(M) = { OR, AND, ), $ }$
• $FOLLOW(N) = { OR, AND, ), $ }$

$NULLABLE$

Nenhuma das produções é nullable.

Com os conjuntos já criados podemos criar uma Tabela de Derivação:

Tabela de Derivação $LL(1)$

	id	OR	AND	NOT	(	)	$
S	B			B	B
B	M			M	M
B	M	B OR M		M	M	ε	ε
M	N	ε	M AND N	N	N	ε	ε
N	id			NOT N	(B)

Com a Tabela de Derivação, podemos partir para o passo a passo do parser $LL(1)$.

Testando com id OR NOT id AND (id OR id)

Para verificar se a string id OR NOT id AND (id OR id) faz parte da linguagem definida pela gramática dada e se pode ser analisada por um parser $LL(1)$ usando a Tabela de Derivação encontrada, seguiremos o processo de análise preditiva descendente, começando pelo símbolo inicial, $S$, utilizando a Tabela de Derivação para guiar a derivação.

Novamente o processo iniciará com a pilha contendo o símbolo inicial da gramática, $S$, e a string de entrada id OR NOT id AND (id OR id)$ será usada como buffer, onde o “$” indica o final da entrada. Siga os seguintes passos:

1. Verificar o topo da pilha ($S$( e o próximo símbolo de entrada (‘id’).
2. Usar a Tabela de Derivação para encontrar a produção apropriada: $S \rightarrow B$.
3. Substituir $S$ pela produção $B$ na pilha.
4. O próximo passo é verificar o topo da pilha ($B$) e o próximo símbolo de entrada (‘id’).
5. A Tabela indica $B \rightarrow M$. Substituir $B$ por $M$.
6. O próximo passo é verificar o topo da pilha ($M$) e o próximo símbolo de entrada (‘id’).
7. A Tabela indica $M \rightarrow N$. Substituir $M$ por $N$.
8. O próximo passo é verificar o topo da pilha ($N$) e o próximo símbolo de entrada (‘id’).
9. A Tabela indica $N \rightarrow id$. Substituir $N$ por ‘id’.
10. Agora a pilha tem ‘id’ e a entrada é id OR NOT id AND (id OR id)$. O próximo passo é consumir ‘id’ da entrada e da pilha, pois eles coincidem.
11. O topo da pilha agora é $M$ e o próximo símbolo de entrada é ‘OR’.
12. A Tabela indica $B \rightarrow B OR M$. Substituir $B$ por $B OR M$.
13. Agora a pilha tem $M OR M$ e a entrada é “OR NOT id AND (id OR id)$”. Consumir ‘OR’ da entrada e da pilha, pois eles coincidem.
14. O próximo passo é verificar o topo da pilha $M$ e o próximo símbolo de entrada (‘NOT’).
15. A Tabela indica $M \rightarrow N$. Substituir $M$ por $N$.
16. O próximo passo é verificar o topo da pilha $N$ e o próximo símbolo de entrada (‘NOT’).
17. A Tabela indica $N \rightarrow NOT N$. Substituir $N$ por $NOT N$.
18. Consumir ‘NOT’ da entrada e da pilha, pois eles coincidem.
19. O próximo passo é verificar o topo da pilha $N$ e o próximo símbolo de entrada (‘id’).
20. A Tabela indica $N \rightarrow id$. Substituir $N$ por ‘id’.
21. Consumir ‘id’ da entrada e da pilha, pois eles coincidem.
22. O topo da pilha agora é $M$ e o próximo símbolo de entrada é ‘AND’.
23. A Tabela indica $M \rightarrow M AND N$. Substituir $M$ por $M AND N$.
24. Consumir ‘AND’ da entrada e da pilha, pois eles coincidem.
25. O próximo passo é verificar o topo da pilha $M$ e o próximo símbolo de entrada (‘(‘).
26. A Tabela indica $M \rightarrow N$. Substituir $M$ por $N$.
27. O próximo passo é verificar o topo da pilha $N$ e o próximo símbolo de entrada (‘(‘).
28. A Tabela indica $N \rightarrow (B)$. Substituir $N$ por $(B)$.
29. Consumir ‘(‘ da entrada e da pilha, pois eles coincidem.
30. O próximo passo é verificar o topo da pilha $B$ e o próximo símbolo de entrada (‘id’).
31. A Tabela indica $B \rightarrow M$. Substituir $B$ por $M$.
32. O próximo passo é verificar o topo da pilha $M$ e o próximo símbolo de entrada (‘id’).
33. A Tabela indica $M \rightarrow N$. Substituir $M$ por $N$.
34. O próximo passo é verificar o topo da pilha $N$ e o próximo símbolo de entrada (‘id’).
35. A Tabela indica $N \rightarrow id$. Substituir $N$ por ‘id’.
36. Consumir ‘id’ da entrada e da pilha, pois eles coincidem.
37. O topo da pilha agora é $B$ e o próximo símbolo de entrada é ‘OR’.
38. A Tabela indica $B \rightarrow B OR M$. Substituir $B$ por $B OR M$.
39. Consumir ‘OR’ da entrada e da pilha, pois eles coincidem.
40. O próximo passo é verificar o topo da pilha $M$ e o próximo símbolo de entrada (‘id’).
41. A Tabela indica $M \rightarrow N$. Substituir $M$ por $N$.
42. O próximo passo é verificar o topo da pilha $N$ e o próximo símbolo de entrada (‘id’).
43. A Tabela indica $N \rightarrow id$. Substituir $N$ por ‘id’.
44. Consumir ‘id’ da entrada e da pilha, pois eles coincidem.
45. Consumir ‘)’ da entrada e da pilha, pois eles coincidem.
46. Finalmente, a pilha está vazia e a entrada foi completamente consumida.

Como foi possível consumir toda a string de entrada id OR NOT id AND (id OR id)$ e esvaziar a pilha sem encontrar nenhum erro, a string id OR NOT id AND (id OR id) é de fato parte da linguagem definida e pode ser identificada por um parser $LL(1)$.

Até agora, o conjuntos $FIRST$, $FOLLOW$ E $NULLABLE$, e a Tabela de Derivação, caíram do céu. Se você é corajoso, sério, destemido e acompanhou todos os passos dos dois últimos exemplos, entendeu como o algoritmo de um parser $LL(1)$ deve funcionar. Se era isso que estava procurado, pode parar por aqui. Agora se quiser entender como são criados os conjuntos e a Tabela de Derivação, tome uma água, respire fundo e continue. Seu próximo passo será entender como criamos os conjuntos $FIRST$ e $FOLLOW$