Tutoriais - Compiladores
Tutoriais
Compiladores

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

Exercício 03.80

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

G = ({A, B, D}, {x, y}, P, A)
P = {A → DxD
     B → y | Ax
     D → yB | Bx}

Solução do Exercício

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

A gramática livre de contexto está simplificada.

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

G = ({A, B, C}, {x, y}, P, A)
P = {A → CxC
     B → y | Ax
     C → yB | Bx}

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

G = ({A, B, C}, {x, y}, P, A)
P = {A → CxC
     B → y | CxCx
     C → yB | yx | CxCxx}

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

G = ({A, B, C, D}, {x, y}, P, A)
P = {A → CxC
     B → y | CxCx
     C → yB | yx | yBD | yxD
     D → xCxx | xCxxD}