Ybadoo - Soluções em Software Livre
Tutoriais
Compiladores

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

Exercício 03.49

Apresente a Análise Preditiva Tabular da entrada (a; (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 | ε}

Conjuntos FIRST(α) e FOLLOW(A):

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

Tabela de Análise Preditiva:

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

Analisador Preditivo Tabular:

Movimentos do analisador preditivo tabular para (a; (a; a); a)
PilhaEntradaDerivação
$ A(a; (a; a); a)$A → (B)
$ ) B ((a; (a; a); a)$ 
$ ) Ba; (a; a); a)$B → aD
$ ) D aa; (a; a); a)$ 
$ ) D; (a; a); a)$D → C
$ ) C; (a; a); a)$C → ;AD
$ ) D A ;; (a; a); a)$ 
$ ) D A(a; a); a)$A → (B)
$ ) D ) B ((a; a); a)$ 
$ ) D ) Ba; a); a)$B → aD
$ ) D ) D aa; a); a)$ 
$ ) D ) D; a); a)$D → C
$ ) D ) C; a); a)$C → ;AD
$ ) D ) D A ;; a); a)$ 
$ ) D ) D Aa); a)$A → a
$ ) D ) D aa); a)$ 
$ ) D ) D); a)$D → ε
$ ) D )); a)$ 
$ ) D; a)$D → C
$ ) C; a)$C → ;AD
$ ) D A ;; a)$ 
$ ) D Aa)$A → a
$ ) D aa)$ 
$ ) D)$D → ε
$ ))$ 
$$aceita

Ybadoo   •   Copyright 2009/2024   •   GFDL