Ybadoo - Soluções em Software Livre
Tutoriais
Compiladores

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

Exercício 03.71

Apresente a Análise Preditiva Tabular, com recuperação de erros em modo pânico, da entrada (a++b)*ab* sobre a gramática a seguir.

G = ({A, B, C, D, E}, {a, b, +, *, (, )}, P, A)
P = {A → A+B | B
     B → BC | C
     C → D* | D
     D → (A) | E
     E → a | b | ε}

 

Solução do Exercício

Eliminação de Recursividade à Esquerda:

G = ({A, A₁, B, B₁, C, D, E}, {a, b, +, *, (, )}, P, A)
P = {A  → BA₁
     A₁ → +BA₁ | ε
     B  → CB₁
     B₁ → CB₁ | ε
     C  → D* | D
     D  → (A) | E
     E  → a | b | ε}

Fatoração à Esquerda:

G = ({A, A₁, B, B₁, C, C₁, D, E}, {a, b, +, *, (, )}, P, A)
P = {A  → BA₁
     A₁ → +BA₁ | ε
     B  → CB₁
     B₁ → CB₁ | ε
     C  → DC₁
     C₁ → * | ε
     D  → (A) | E
     E  → a | b | ε}

Conjuntos FIRST(α) e FOLLOW(A):

FIRST(A)  = {a, b, +, *, (, ε}
FIRST(A₁) = {+, ε}
FIRST(B)  = {a, b, *, (, ε}
FIRST(B₁) = {a, b, *, (, ε}
FIRST(C)  = {a, b, *, (, ε}
FIRST(C₁) = {*, ε}
FIRST(D)  = {a, b, (, ε}
FIRST(E)  = {a, b, ε}
FOLLOW(A)  = {), $}
FOLLOW(A₁) = {), $}
FOLLOW(B)  = {+, ), $}
FOLLOW(B₁) = {+, ), $}
FOLLOW(C)  = {a, b, +, *, (, ), $}
FOLLOW(C₁) = {a, b, +, *, (, ), $}
FOLLOW(D)  = {a, b, +, *, (, ), $}
FOLLOW(E)  = {a, b, +, *, (, ), $}

Tabela de Análise Preditiva:

Tabela de análise preditiva da gramática G
 ab+*()$
AA → BA₁A → BA₁A → BA₁A → BA₁A → BA₁sincsinc
A₁  A₁ → +BA₁  A₁ → εA₁ → ε
BB → CB₁B → CB₁sincB → CB₁B → CB₁sincsinc
B₁B₁ → CB₁B₁ → CB₁B₁ → εB₁ → CB₁B₁ → CB₁B₁ → εB₁ → ε
CC → DC₁C → DC₁sincC → DC₁C → DC₁sincsinc
C₁C₁ → εC₁ → εC₁ → εC₁ → *C₁ → εC₁ → εC₁ → ε
DD → ED → EsincsincD → (A)sincsinc
EE → aE → bE → εE → εE → εE → εE → ε

Analisador Preditivo Tabular:

Movimentos do analisador preditivo tabular para (a++b)*ab*
PilhaEntradaDerivação
$ A(a + + b) * a b * $A → BA₁
$ A₁ B(a + + b) * a b * $B → CB₁
$ A₁ B₁ C(a + + b) * a b * $C → DC₁
$ A₁ B₁ C₁ D(a + + b) * a b * $D → (A)
$ A₁ B₁ C₁ ) A ((a + + b) * a b * $ 
$ A₁ B₁ C₁ ) Aa + + b) * a b * $A → BA₁
$ A₁ B₁ C₁ ) A₁ Ba + + b) * a b * $B → CB₁
$ A₁ B₁ C₁ ) A₁ B₁ Ca + + b) * a b * $C → DC₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ Da + + b) * a b * $D → E
$ A₁ B₁ C₁ ) A₁ B₁ C₁ Ea + + b) * a b * $E → a
$ A₁ B₁ C₁ ) A₁ B₁ C₁ aa + + b) * a b * $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁+ + b) * a b * $C₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁+ + b) * a b * $B₁ → ε
$ A₁ B₁ C₁ ) A₁+ + b) * a b * $A₁ → +BA₁
$ A₁ B₁ C₁ ) A₁ B ++ + b) * a b * $ 
$ A₁ B₁ C₁ ) A₁ B+ b ) * a b * $sinc
$ A₁ B₁ C₁ ) A₁+ b ) * a b * $A₁ → +BA₁
$ A₁ B₁ C₁ ) A₁ B ++ b ) * a b * $ 
$ A₁ B₁ C₁ ) A₁ Bb ) * a b * $B → CB₁
$ A₁ B₁ C₁ ) A₁ B₁ Cb) * a b * $C → DC₁
$ A₁ B₁ C₁ ) A₁ B₁ C₁ Db) * a b * $D → E
$ A₁ B₁ C₁ ) A₁ B₁ C₁ Eb) * a b * $E → b
$ A₁ B₁ C₁ ) A₁ B₁ C₁ bb) * a b * $ 
$ A₁ B₁ C₁ ) A₁ B₁ C₁) * a b * $C₁ → ε
$ A₁ B₁ C₁ ) A₁ B₁) * a b * $B₁ → ε
$ A₁ B₁ C₁ ) A₁) * a b * $A₁ → ε
$ A₁ B₁ C₁ )) * a b * $ 
$ A₁ B₁ C₁* a b * $C₁ → *
$ A₁ B₁ ** a b * $ 
$ A₁ B₁a b * $B₁ → CB₁
$ A₁ B₁ Ca b * $C₁ → DC₁
$ A₁ B₁ C₁ Da b * $D → E
$ A₁ B₁ C₁ Ea b * $E → a
$ A₁ B₁ C₁ aa b * $ 
$ A₁ B₁ C₁b * $C₁ → DC₁
$ A₁ B₁ C₁ Db * $D → E
$ A₁ B₁ C₁ Eb * $E → b
$ A₁ B₁ C₁ bb * $ 
$ A₁ B₁ C₁* $C₁ → *
$ A₁ B₁ ** $ 
$ A₁ B₁$B₁ → ε
$ A₁$A₁ → ε
$$aceita

Ybadoo   •   Copyright 2009/2024   •   GFDL