Ybadoo - Soluções em Software Livre
Tutoriais
Compiladores

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

Exercício 03.50

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

G = ({S, L}, {a, ;, (, )}, P, S)
P = {S → (L) | a
     L → L;S | S}

 

Solução do Exercício

1. Eliminação da recursividade à esquerda:

1.1. Simplificação da gramática livre de contexto:

G = ({S, L}, {a, ;, (, )}, P, S)
P = {S → (L) | a
     L → L;S | (L) | a}

1.2. Renomeação das variáveis em uma ordem crescente qualquer:

G = ({A, B}, {a, ;, (, )}, P, A)
P = {A → (B) | a
     B → B;A | (B) | a}

1.3. Transformação das produções da forma Ar → Asα, onde r ≤ s:

G = ({A, B}, {a, ;, (, )}, P, A)
P = {A → (B) | a
     B → B;A | (B) | a}

1.4. Exclusão das recursões da forma Ar → Arα:

G = ({A, B, C}, {a, ;, (, )}, P, A)
P = {A → (B) | a
     B → (B)C | aC | (B) | a
     C → ;AC | ;A}

2. Fatoração a esquerda da gramática livre de contexto:

G = ({A, B, C, D}, {a, ;, (, )}, P, A)
P = {A → (B) | a
     B → (B)D | aD
     C → ;AD
     D → C | ε}

3. Conjuntos FIRST(α) e FOLLOW(A):

FIRST(A) = {a, (}
FIRST(B) = {a, (}
FIRST(C) = {;}
FIRST(D) = {;, ε}
FOLLOW(A) = {;, ), $}
FOLLOW(B) = {)}
FOLLOW(C) = {)}
FOLLOW(D) = {)}

4. Tabela de Análise Preditiva:

Tabela de análise preditiva da gramática G
 a;()$
AA → asincA → (B)sincsinc
BB → aD B → (B)Dsinc 
C C → ;AD sinc 
D D → C D → ε 

5. Analisador Preditivo Tabular:

Movimentos do analisador preditivo tabular para (a (a; ); a)
PilhaEntradaDerivação
$ A(a (a; ); a)$A → (B)
$ ) B ((a (a; ); a)$ 
$ ) Ba (a; ); a)$B → aD
$ ) D aa (a; ); a)$ 
$ ) D(a; ); a)$erro - descartar entrada
$ ) Da; ); a)$erro - descartar entrada
$ ) D; ); a)$D → C
$ ) C; ); a)$C → ;AD
$ ) D A ;; ); a)$ 
$ ) D A); a)$erro - descartar pilha
$ ) D); a)$D → ε
$ )); a)$ 
$; a)$erro - descartar entrada
$a)$erro - descartar entrada
$)$erro - descartar entrada
$$aceita

Ybadoo   •   Copyright 2009/2024   •   GFDL