Reconhecedor Descendente Preditivo

Tabela de decisão (parsing table)

Exemplo 1

Considere a gramática

• S -> a S b | end

Preencha a tabela de decisão de um reconhecedor descendente desta linguagem com lookahead de 1.

Não havendo células com 2 ou mais produções, a gramática é LL(1).

Para simplificação, optou-se por pôr mais células apenas no corpo da produção, uma vez que a cabeça é definida pela linha da tabela.

Exemplo 2

Considere a gramática

• S -> end | a B S | b A S A -> a | b A A B -> a B B | b

Preencha a tabela de decisão de um reconhecedor descendente desta linguagem com lookahead de 1.

As células vazias correspondem a situações de erro.

Exemplo 2b

Considere a gramática

• S -> end | a S b S | b S a S

Preencha a tabela de decisão de um reconhecedor descendente desta linguagem com lookahead de 1.

As células (S, a) e (S, b) têm duas produções cada, o que torna o reconhecimento inviável para um lookahead de 1, pelo que a linguagem não é LL(1)

Exemplo 3

Considere, sobre o alfabeto {i, f, v, , , ; }, a linguagem L4 descrita pela gramática

• D -> T L ; T -> i | f L -> v | v, L

Obtenha-se uma tabela de decisão de um reconhecedor descendente, com lookahead de 1, que reconheça a linguagem L4.

• Pretende-se que, se necessário, se transform a gramática numa equivalente que seja LL(1).

• Neste caso, existem produções com prefixos comuns (os conjuntos predict não são disjuntos).

Antes de calcular os conjuntos predict é necessário começar por fatorizar à esquerda, por causa das produções com cabeça L.