Ybadoo - Soluções em Software Livre
Tutoriais
Compiladores

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

Exercício 03.75

Apresente a Análise Preditiva Tabular da entrada ((x + y) ^ (z * y)) / (x - y) sobre a gramática a seguir.

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

 

Solução do Exercício

Eliminação de Recursividade à Esquerda:

G = ({A, A₁, B, B₁, C, B₁, D, E}, {+, -, *, /, ^, (, ), x, y, z}, P, A)
P = {A  → BA₁
     A₁ → +BA₁ | -BA₁ | ε
     B  → CB₁
     B₁ → *CB₁ | /CB₁ | ε
     C  → DC₁
     C₁ → ^DC₁ | ε
     D  → (A) | E
     E  → x | y | z}

Fatoração à Esquerda:

G = ({A, A₁, B, B₁, C, B₁, D, E}, {+, -, *, /, ^, (, ), x, y, z}, P, A)
P = {A  → BA₁
     A₁ → +BA₁ | -BA₁ | ε
     B  → CB₁
     B₁ → *CB₁ | /CB₁ | ε
     C  → DC₁
     C₁ → ^DC₁ | ε
     D  → (A) | E
     E  → x | y | z}

Conjuntos FIRST(α) e FOLLOW(A):

FIRST(A)  = {(, x, y, z}
FIRST(A₁) = {+, -, ε}
FIRST(B)  = {(, x, y, z}
FIRST(B₁) = {*, /, ε}
FIRST(C)  = {(, x, y, z}
FIRST(C₁) = {^, ε}
FIRST(D)  = {(, x, y, z}
FIRST(E)  = {x, y, z}
FOLLOW(A)  = {), $}
FOLLOW(A₁) = {), $}
FOLLOW(B)  = {+, -, ), $}
FOLLOW(B₁) = {+, -, ), $}
FOLLOW(C)  = {+, -, *, /, ), $}
FOLLOW(C₁) = {+, -, *, /, ), $}
FOLLOW(D)  = {+, -, *, /, ^, ), $}
FOLLOW(E)  = {+, -, *, /, ^, ), $}

Tabela de Análise Preditiva:

Tabela de análise preditiva da gramática G
 xyz+-*/^()$
AA → BA₁A → BA₁A → BA₁     A → BA₁  
A₁   A₁ → +BA₁A₁ → -BA₁    A₁ → εA₁ → ε
BB → CB₁B → CB₁B → CB₁     B → CB₁  
B₁   B₁ → εB₁ → εB₁ → *CB₁B₁ → /CB₁  B₁ → εB₁ → ε
CC → DC₁C → DC₁C → DC₁     C → DC₁  
C₁   C₁ → εC₁ → εC₁ → εC₁ → εC₁ → ^DC₁ C₁ → εC₁ → ε
DD → ED → ED → E     D → (A)  
EE → xE → yE → z        

Analisador Preditivo Tabular:

Movimentos do analisador preditivo tabular para ((x + y) ^ (z * y)) / (x - y)
PilhaEntradaDerivação
$ A((x + y) ^ (z * y)) / (x - y) $A → BA₁
$ A₁ B((x + y) ^ (z * y)) / (x - y) $B → CB₁
$ A₁ B₁ C((x + y) ^ (z * y)) / (x - y) $C → DC₁
$ A₁ B₁ C₁ D((x + y) ^ (z * y)) / (x - y) $D → (A)
$ A₁ B₁ C₁ ) A (((x + y) ^ (z * y)) / (x - y) $ 
$ A₁ B₁ C₁ ) A(x + y) ^ (z * y)) / (x - y) $A → BA₁
$ A₁ B₁ C₁ ) A₁ B(x + y) ^ (z * y)) / (x - y) $B → CB₁
$ A₁ B₁ C₁ ) A₁ B₁ C(x + y) ^ (z * y)) / (x - y) $C → DC₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ D(x + y) ^ (z * y)) / (x - y) $D → (A)
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A ((x + y) ^ (z * y)) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) Ax + y) ^ (z * y)) / (x - y) $A → BA₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ Bx + y) ^ (z * y)) / (x - y) $B → CB₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ Cx + y) ^ (z * y)) / (x - y) $C → DC₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ Dx + y) ^ (z * y)) / (x - y) $D → E
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ Ex + y) ^ (z * y)) / (x - y) $E → x
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ xx + y) ^ (z * y)) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁+ y) ^ (z * y)) / (x - y) $C₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁+ y) ^ (z * y)) / (x - y) $B₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁+ y) ^ (z * y)) / (x - y) $A₁ → +BA₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B ++ y) ^ (z * y)) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ By) ^ (z * y)) / (x - y) $B → CB₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ Cy) ^ (z * y)) / (x - y) $C → DC₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ Dy) ^ (z * y)) / (x - y) $D → E
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ Ey) ^ (z * y)) / (x - y) $E → y
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ yy) ^ (z * y)) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁) ^ (z * y)) / (x - y) $C₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁) ^ (z * y)) / (x - y) $B₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁) ^ (z * y)) / (x - y) $A₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁ C₁ )) ^ (z * y)) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁^ (z * y)) / (x - y) $C₁ → ^DC₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ D ^^ (z * y)) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁ D(z * y)) / (x - y) $D → (A)
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A ((z * y)) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) Az * y)) / (x - y) $A → BA₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ Bz * y)) / (x - y) $B → CB₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ Cz * y)) / (x - y) $C → DC₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ Dz * y)) / (x - y) $D → E
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ Ez * y)) / (x - y) $E → z
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ zz * y)) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁* y)) / (x - y) $C₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁* y)) / (x - y) $B₁ → *CB₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C ** y)) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ Cy)) / (x - y) $C → DC₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ Dy)) / (x - y) $D → E
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ Ey)) / (x - y) $E → y
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁ yy)) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁ C₁)) / (x - y) $C₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁ B₁)) / (x - y) $B₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ) A₁)) / (x - y) $A₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁ C₁ ))) / (x - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁) / (x - y) $C₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁) / (x - y) $B₁ → ε
$ A₁ B₁ C₁ ) A₁) / (x - y) $A₁ → ε
$ A₁ B₁ C₁ )) / (x - y) $ 
$ A₁ B₁ C₁/ (x - y) $C₁ → ε
$ A₁ B₁/ (x - y) $B₁ → /CB₁
$ A₁ B₁ C // (x - y) $ 
$ A₁ B₁ C(x - y) $C → DC₁
$ A₁ B₁ C₁ D(x - y) $D → (A)
$ A₁ B₁ C₁ ) A ((x - y) $ 
$ A₁ B₁ C₁ ) Ax - y) $A → BA₁
$ A₁ B₁ C₁ ) A₁ Bx - y) $B → CB₁
$ A₁ B₁ C₁ ) A₁ B₁ Cx - y) $C → DC₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ Dx - y) $D → E
$ A₁ B₁ C₁ ) A₁ B₁ C₁ Ex - y) $E → x
$ A₁ B₁ C₁ ) A₁ B₁ C₁ xx - y) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁- y) $C₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁- y) $B₁ → ε
$ A₁ B₁ C₁ ) A₁- y) $A₁ → -BA₁
$ A₁ B₁ C₁ ) A₁ B -- y) $ 
$ A₁ B₁ C₁ ) A₁ By) $B → CB₁
$ A₁ B₁ C₁ ) A₁ B₁ Cy) $C → DC₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ Dy) $D → E
$ A₁ B₁ C₁ ) A₁ B₁ C₁ Ey) $E → y
$ A₁ B₁ C₁ ) A₁ B₁ C₁ yy) $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁) $C₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁) $B₁ → ε
$ A₁ B₁ C₁ ) A₁) $A₁ → ε
$ A₁ B₁ C₁ )) $ 
$ A₁ B₁ C₁$C₁ → ε
$ A₁ B₁$B₁ → ε
$ A₁$A₁ → ε
$$aceita

Ybadoo   •   Copyright 2009/2025   •   GFDL