Tutoriais - Compiladores
Tutoriais
Compiladores

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

Exercício 03.48

Apresente a Análise Recursiva com Retrocesso da palavra (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 A_r → A_sα, 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 A_r → A_rα:

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. Análise Recursiva com Retrocesso da palavra (a; (a; a); a):