Tutoriais - Compiladores
Tutoriais
Compiladores

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

Exercício 03.61

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

G = ({S, X, K, Y}, {x, y, z}, P, S)
P = {S → KY | XK
     X → XK | x
     K → YK | XX | x
     Y → y | z}

Solução do Exercício

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

G = ({S, X, K, Y}, {x, y, z}, P, S)
P = {S → KY | XK
     X → XK | x
     K → YK | XX | x
     Y → y | z}

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

G = ({A, B, C, D}, {x, y, z}, P, A)
P = {A → CD | BC
     B → BC | x
     C → DC | BB | x
     D → y | z}

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

G = ({A, B, B1, C, D}, {x, y, z}, P, A)
P = {A  → CD | BC
     B  → xB1 | x
     B1 → CB1 | C
     C  → DC | BB | x
     D  → y | z}

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

G = ({A, B, B1, C, D}, {x, y, z}, P, A)
P = {A  → CD | BC
     B  → xB1 | x
     B1 → CB1 | C
     C  → DC | xB1B | xB | x
     D  → y | z}