Tutoriais - Compiladores
Tutoriais
Compiladores

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

Exercício 03.54

Elimine a recursividade à esquerda, considerando a palavra vazia, das produções da gramática a seguir.

G = ({S, A, B, C}, {a, b}, P, S)
P = {S → SC | AA | a
     A → CA | AB | a
     B → AC | b
     C → CA | AS | b}

Solução do Exercício

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

G = ({S, A, B, C}, {a, b}, P, S)
P = {S → SC | AA | a
     A → CA | AB | a
     B → AC | b
     C → CA | AS | b}

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

G = ({A, B, C, D}, {a, b}, P, A)
P = {A → AD | BB | a
     B → DB | BC | a
     C → BD | b
     D → DB | BA | b}

4. Exclusão das recursões da forma A_r → A_rα:

G = ({A, A₀, B, B₀, C, D, D₀}, {a, b}, P, A)
P = {A  → BBA₀ | aA₀
     A₀ → DA₀ | ε
     B  → DBB₀ | aB₀
     B₀ → CB₀ | ε
     C  → BD | b
     D  → BAD₀ | bD₀
     D₀ → BD₀ | ε}

3. Transformação das produções da forma A_r → A_sα, onde r ≤ s:

G = ({A, A₀, B, B₀, C, D, D₀}, {a, b}, P, A)
P = {A  → BBA₀ | aA₀
     A₀ → DA₀ | ε
     B  → DBB₀ | aB₀
     B₀ → CB₀ | ε
     C  → DBB₀D | aB₀D | b
     D  → DBB₀AD₀ | aB₀AD₀ | bD₀
     D₀ → BD₀ | ε}

4. Exclusão das recursões da forma A_r → A_rα:

G = ({A, A₀, B, B₀, C, D, D₀, D₁}, {a, b}, P, A)
P = {A  → BBA₀ | aA₀
     A₀ → DA₀ | ε
     B  → DBB₀ | aB₀
     B₀ → CB₀ | ε
     C  → DBB₀D | aB₀D | b
     D  → aB₀AD₀D₁ | bD₀D₁
     D₀ → BD₀ | ε
     D₁ → BB₀AD₀D₁ | ε