Tutoriais - Compiladores
Tutoriais
Compiladores

Apresente a Análise Preditiva Tabular 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₁`			`A → BA₁`
`A₁`		`A₁ → +BA₁`			`A₁ → ε`	`A₁ → ε`
`B`	`B → CB₁`			`B → CB₁`
`B₁`		`B₁ → ε`	`B₁ → *CB₁`		`B₁ → ε`	`B₁ → ε`
`C`	`C → id`			`C → (A)`

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₁ → +BA₁`
`$ A₁ B₁ ) A₁ B +`	`+ id * id) $`
`$ A₁ B₁ ) A₁ B`	`id * id) $`	`B → CB₁`
`$ A₁ B₁ ) A₁ B₁ C`	`id * id) $`	`C → id`
`$ A₁ B₁ ) A₁ B₁ id`	`id * id) $`
`$ A₁ B₁ ) A₁ B₁`	`* id) $`	`B₁ → *CB₁`
`$ A₁ B₁ ) A₁ B₁ C *`	`* id) $`
`$ A₁ B₁ ) A₁ B₁ C`	`id) $`	`C → id`
`$ A₁ B₁ ) A₁ B₁ id`	`id) $`
`$ A₁ B₁ ) A₁ B₁`	`) $`	`B₁ → ε`
`$ A₁ B₁ ) A₁`	`) $`	`A₁ → ε`
`$ A₁ B₁ )`	`) $`
`$ A₁ B₁`	`$`	`B₁ → ε`
`$ A₁`	`$`	`A₁ → ε`
`$`	`$`	`aceita`