Problemas do Parser

No caminho de volta hoje pensei sobre o assunto que discutimos e cheguei a conclusão de que realmente pode dar problema. Caso a regra seja:

a{b*}{b*}bb → /1a/2

Podemos converter a regra para a gramática:

S → aG₁G₂bb
G₁ → bG₁ | ε
G₂ → bG₂ | ε

Simplificado:

S → aA
A → G₁B
B → G₂C
C → bD
D → b
G₁ → bG₁ | ε
G₂ → bG₂ | ε

Grupo FIRST:


First(S) = a
First(A) = b
First(B) = b
First(C) = b
First(D) = b
First(G₁) = b, ε
First(G₂) = b, ε

Grupo FOLLOW:


Follow(S) = #
Follow(A) = #
Follow(B) = #
Follow(C) = #
Follow(D) = #
Follow(G₁) = b
Follow(G₂) = b


Tabela de Parser:

S → aA

FIRST(aA FOLLOW(S)) = a

A → G₁B

FIRST(G₁B FOLLOW(A)) = {b, ε}{b}

B → G₂C

FIRST(G₂C FOLLOW(B)) = {b, ε}{b}

C → bD

FIRST(bD FOLLOW(C)) = b

D → b

FIRST(b FOLLOW(D)) = b

G₁ → bG₁

FIRST(bG₁ FOLLOW(G₁)) = b

G₁ → ε

FIRST(ε FOLLOW(G₁)) = {ε}{b}

G₂ → bG₂

_{FIRST(bG2 FOLLOW(G2)) = b}

G₂ → ε

FIRST(ε FOLLOW(G₂)) = {ε}{b}

Podemos seguir a seguinte derivação com a cadeia abbb:

(abbb) S → aA
(bbb) A → G₁B
(bbb) G₁ → ε
(bbb) B → G₂C
(bbb) G₂ → ε
(bb) C → bD
(b) D → b

Ou seja, esta derivação não termina corretamente, logo temos que descartá-la. Caso fizéssemos uma tabela de parser LL 2, 3 ou maior, é possível fazer a derivação de forma determinística.
Temos que prever este tipo de derivações que não terminam corretamente e derivações diferentes também podem gerar as mesmas cadeias substituídas.

Pode-se perguntar então se é útil ter todo este trabalho para no final termos um parser não determinístico. Não me lembro agora qual, mas vi em um paper a informação de que sim. Mesmo que uma linguagem seja LL 2, 3, 4 é viável utilizar um parser LL(1) e tratar o não determinismo. Por outro lado, lá diz que é muito viável também utilizar um parser LL(1) ao invés de um parser simples não determinístico pois evitaria muitas derivações desnecessárias.