Ybadoo - Soluções em Software Livre
Tutoriais
Compiladores

  1. Ybadoo
  2. Tutoriais
  3. Compiladores
  4. Análise Sintática
  5. Exercício 03.30

Exercício 03.30

Apresente a Análise Preditiva Tabular da entrada a(e;e) sobre a gramática a seguir.

G = ({S, A, B, C, X, Y}, {a, e, (, ), ;}, P, S)
P = {S → A)
     A → CB
     B → ;XB | ε
     C → Y(X
     X → e
     Y → a}

 

Solução do Exercício

Eliminação de Recursividade à Esquerda:

G = ({S, A, B, C, X, Y}, {a, e, (, ), ;}, P, S)
P = {S → A)
     A → CB
     B → ;XB | ε
     C → Y(X
     X → e
     Y → a}

Fatoração à Esquerda:

G = ({S, A, B, C, X, Y}, {a, e, (, ), ;}, P, S)
P = {S → A)
     A → CB
     B → ;XB | ε
     C → Y(X
     X → e
     Y → a}

Conjuntos FIRST(α) e FOLLOW(A):

FIRST(S) = {a}
FIRST(A) = {a}
FIRST(B) = {;, ε}
FIRST(C) = {a}
FIRST(X) = {e}
FIRST(Y) = {a}
FOLLOW(S) = {$}
FOLLOW(A) = {)}
FOLLOW(B) = {)}
FOLLOW(C) = {), ;}
FOLLOW(X) = {), ;}
FOLLOW(Y) = {(}

Tabela de Análise Preditiva:

Tabela de análise preditiva da gramática G
 ae();$
SS → A)     
AA → CB     
B   B → εB → ;XB 
CC → Y(X     
X X → e    
YY → a     

Analisador Preditivo Tabular:

Movimentos do analisador preditivo tabular para a(e;e)
PilhaEntradaDerivação
$ Sa(e;e) $S → A)
$ ) Aa(e;e) $A → CB
$ ) B Ca(e;e) $C → Y(X
$ ) B X ( Ya(e;e) $Y → a
$ ) B X ( aa(e;e) $ 
$ ) B X ((e;e) $ 
$ ) B Xe;e) $X → e
$ ) B ee;e) $ 
$ ) B;e) $B → ;XB
$ ) B X ;;e) $ 
$ ) B Xe) $X → e
$ ) B ee) $ 
$ ) B) $B → ε
$ )) $ 
$$aceita

Ybadoo   •   Copyright 2009/2024   •   GFDL