Ybadoo - Soluções em Software Livre
Tutoriais
Compiladores

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

Exercício 03.35

Apresente a Análise Preditiva Tabular, com recuperação local de erros, da entrada * x * * - x y z sobre a gramática a seguir.

G = ({A, B, C}, {+, -, *, /, x, y, z}, P, A)
P = {A → BAA | C
     B → + | - | * | /
     C → x | y | z}

 

Solução do Exercício

Eliminação de Recursividade à Esquerda:

G = ({A, B, C}, {+, -, *, /, x, y, z}, P, A)
P = {A → BAA | C
     B → + | - | * | /
     C → x | y | z}

Fatoração à Esquerda:

G = ({A, B, C}, {+, -, *, /, x, y, z}, P, A)
P = {A → BAA | C
     B → + | - | * | /
     C → x | y | z}

Conjuntos FIRST(α) e FOLLOW(A):

FIRST(A) = {+, -, *, /, x, y, z}
FIRST(B) = {+, -, *, /}
FIRST(C) = {x, y, z}
FOLLOW(A) = {+, -, *, /, x, y, z, $}
FOLLOW(B) = {+, -, *, /, x, y, z}
FOLLOW(C) = {+, -, *, /, x, y, z, $}

Tabela de Análise Preditiva:

Tabela de análise preditiva da gramática G
 +-*/xyz$
AA → BAAA → BAAA → BAAA → BAAA → CA → CA → Cerro 1
BB → +B → -B → *B → /    
C    C → xC → yC → z 
+desempilha       
- desempilha      
*  desempilha     
/   desempilha    
x    desempilha   
y     desempilha  
z      desempilha 
$erro 2erro 2erro 2erro 2erro 2erro 2erro 2aceita

erro 1 - insere o token x na entrada e emite a mensagem: operando esperado.

erro 2 - retira o token da entrada e emite a mensagem: fim de arquivo encontrado.

Analisador Preditivo Tabular:

Movimentos do analisador preditivo tabular para * x * * - x y z
PilhaEntradaDerivação
$ A* x * * - x y z $A → BAA
$ A A B* x * * - x y z $B → *
$ A A ** x * * - x y z $ 
$ A Ax * * - x y z $A → C
$ A Cx * * - x y z $C → x
$ A xx * * - x y z $ 
$ A* * - x y z $A → BAA
$ A A B* * - x y z $B → *
$ A A ** * - x y z $ 
$ A A* - x y z $A → BAA
$ A A A B* - x y z $B → *
$ A A A ** - x y z $ 
$ A A A- x y z $A → BAA
$ A A A A B- x y z $B → -
$ A A A A -- x y z $ 
$ A A A Ax y z $A → C
$ A A A Cx y z $C → x
$ A A A xx y z $ 
$ A A Ay z $A → C
$ A A Cy z $C → y
$ A A yy z $ 
$ A Az $A → C
$ A Cz $C → z
$ A zz $ 
$ A$erro 1
$ Ax $A → C
$ Cx $C → x
$ xx $ 
$$aceita

Ybadoo   •   Copyright 2009/2024   •   GFDL