Apresente a Análise Preditiva Tabular, com recuperação local de erros, da entrada id * (id id) * id sobre a gramática a seguir.
G = ({A, B, C}, {id, +, *, (, )}, P, A)
P = {A → A+B | B
B → B*C | C
C → (A) | id}
Eliminação de Recursividade à Esquerda:
G = ({A, A₁, B, B₁, C}, {id, +, *, (, )}, P, A)
P = {A → BA₁
A₁ → +BA₁ | ε
B → CB₁
B₁ → *CB₁ | ε
C → (A) | id}
Fatoração à Esquerda:
G = ({A, A₁, B, B₁, C}, {id, +, *, (, )}, P, A)
P = {A → BA₁
A₁ → +BA₁ | ε
B → CB₁
B₁ → *CB₁ | ε
C → (A) | id}
Conjuntos FIRST(α) e FOLLOW(A):
FIRST(A) = {id, (}
FIRST(A₁) = {+, ε}
FIRST(B) = {id, (}
FIRST(B₁) = {*, ε}
FIRST(C) = {id, (}
FOLLOW(A) = {), $}
FOLLOW(A₁) = {), $}
FOLLOW(B) = {+, ), $}
FOLLOW(B₁) = {+, ), $}
FOLLOW(C) = {+, *, ), $}
Tabela de Análise Preditiva:
id | + | * | ( | ) | $ | |
---|---|---|---|---|---|---|
A | A → BA₁ | erro 1 | erro 1 | A → BA₁ | erro 1 | erro 1 |
A₁ | A₁ → ε | A₁ → +BA₁ | A₁ → ε | A₁ → ε | A₁ → ε | A₁ → ε |
B | B → CB₁ | erro 1 | erro 1 | B → CB₁ | erro 1 | erro 1 |
B₁ | B₁ → ε | B₁ → ε | B₁ → *CB₁ | B₁ → ε | B₁ → ε | B₁ → ε |
C | C → id | erro 1 | erro 1 | C → (A) | erro 1 | erro 1 |
id | desempilha | |||||
+ | desempilha | |||||
* | desempilha | |||||
( | desempilha | |||||
) | erro 2 | erro 2 | erro 2 | erro 2 | desempilha | erro 2 |
$ | erro 3 | erro 3 | erro 3 | erro 3 | erro 3 | aceita |
erro 1 - insere o token id na entrada e emite a mensagem: operando esperado.
erro 2 - retira o token ) da pilha e emite a mensagem: parêntese direito esperado.
erro 3 - retira o token da entrada e emite a mensagem: fim de arquivo encontrado.
Analisador Preditivo Tabular:
Pilha | Entrada | Derivação |
---|---|---|
$ A | id * (id id) * id $ | A → BA₁ |
$ A₁ B | id * (id id) * id $ | B → CB₁ |
$ A₁ B₁ c | id * (id id) * id $ | C → id |
$ A₁ B₁ id | id * (id id) * id $ | |
$ A₁ B₁ | * (id id) * id $ | B₁ → *CB₁ |
$ A₁ B₁ C * | * (id id) * id $ | |
$ A₁ B₁ C | (id id) * id $ | C → (A) |
$ A₁ B₁ ) A ( | (id id) * id $ | |
$ A₁ B₁ ) A | id id) * id $ | A → BA₁ |
$ A₁ B₁ ) A₁ B | id id) * id $ | B → CB₁ |
$ A₁ B₁ ) A₁ B₁ C | id id) * id $ | C → id |
$ A₁ B₁ ) A₁ B₁ id | id id) * id $ | |
$ A₁ B₁ ) A₁ B₁ | id) * id $ | B₁ → ε |
$ A₁ B₁ ) A₁ | id) * id $ | A₁ → ε |
$ A₁ B₁ ) | id) * id $ | erro 2 |
$ A₁ B₁ | id) * id $ | B₁ → ε |
$ A₁ | id) * id $ | A₁ → ε |
$ | id) * id $ | erro 3 |
$ | ) * id $ | erro 3 |
$ | * id $ | erro 3 |
$ | id $ | erro 3 |
$ | $ | aceita |