Tutoriais - Compiladores
Tutoriais
Compiladores

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

Exercício 03.45

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

G = ({S, A, B, C}, {a, b, c,}, P, S)
P = {S → ABc
     A → BA | CcB | a
     B → ABb | b
     C → CA | c}

Solução do Exercício

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

G = ({S, A, B, C}, {a, b, c,}, P, S)
P = {S → ABc
     A → BA | CcB | a
     B → ABb | b
     C → CA | c}

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

G = ({A, B, C, D}, {a, b, c,}, P, A)
P = {A → BCc
     B → CB | DcC | a
     C → BCb | b
     D → DB | c}

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

G = ({A, B, C, D}, {a, b, c,}, P, A)
P = {A → BCc
     B → CB | DcC | a
     C → CBCb | DcCCb | aCb | b
     D → DB | c}

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

G = ({A, B, C, C₀, D, D₀}, {a, b, c,}, P, A)
P = {A  → BCc
     B  → CB | DcC | a
     C  → DcCCbC₀ | aCbC₀ | bC₀
     C₀ → BCbC₀ | ε
     D  → cD₀
     D₀ → BD₀ | ε}