Tutoriais - Compiladores
Tutoriais
Compiladores

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:

Tabela de análise preditiva da gramática `G`
	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:

Movimentos do analisador preditivo tabular para `id * (id id) * id`
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`