1. Simplificação da gramática livre do contexto
1.1. Exclusão de Produções Vazias
1.1.1. Identificação das variáveis que constituem produções vazias
Conjunto de variáveis que constituem produções vazias
| Iteração |
Variáveis |
| 0 |
∅ |
| 1 |
{D} |
| 2 |
{D, F} |
| 3 |
{D, F, B} |
| 4 |
{D, F, B} |
1.1.2. Exclusão das produções vazias da gramática
G = ({A, B, C, D, E, F}, {x, y, z}, P, A)
P = {< A > -> < E > x y
| z < D >
| z
< B > -> < D > < F >
| < D >
| < F >
| x < C > y
< C > -> x < E > < B >
| x < E >
| < F > < C > z
| < C > z
< D > -> y < C > < A >
| < A > < F > < A >
| < A > < A >
< E > -> < A > z < C >
| < B > < E > y z
| < E > y z
< F > -> z < A > y
| < D >
| < A > < C > < B >
| < A > < C > }
1.1.3. Inclusão da palavra vazia, caso pertença a linguagem gerada pela gramática
G = ({A, B, C, D, E, F}, {x, y, z}, P, A)
P = {< A > -> < E > x y
| z < D >
| z
< B > -> < D > < F >
| < D >
| < F >
| x < C > y
< C > -> x < E > < B >
| x < E >
| < F > < C > z
| < C > z
< D > -> y < C > < A >
| < A > < F > < A >
| < A > < A >
< E > -> < A > z < C >
| < B > < E > y z
| < E > y z
< F > -> z < A > y
| < D >
| < A > < C > < B >
| < A > < C > }
1.2. Exclusão de Produções da Forma < A > -> < B >
1.2.1. Construção dos fechos das variáveis
Fecho(A) = ∅
Fecho(B) = {D, F}
Fecho(C) = ∅
Fecho(D) = ∅
Fecho(E) = ∅
Fecho(F) = {D}
1.2.2. Exclusão das produções da forma < A > -> < B >
G = ({A, B, C, D, E, F}, {x, y, z}, P, A)
P = {< A > -> < E > x y
| z < D >
| z
< B > -> < D > < F >
| z < A > y
| y < C > < A >
| < A > < F > < A >
| < A > < A >
| < A > < C > < B >
| < A > < C >
| x < C > y
< C > -> x < E > < B >
| x < E >
| < F > < C > z
| < C > z
< D > -> y < C > < A >
| < A > < F > < A >
| < A > < A >
< E > -> < A > z < C >
| < B > < E > y z
| < E > y z
< F > -> z < A > y
| y < C > < A >
| < A > < F > < A >
| < A > < A >
| < A > < C > < B >
| < A > < C > }
1.3. Exclusão de Símbolos Inúteis
1.3.1. Identificação das variáveis que constituem terminais
Conjunto de variáveis que constituem terminais
| Iteração |
Variáveis |
| 0 |
∅ |
| 1 |
{A} |
| 2 |
{A, B, D, F} |
| 3 |
{A, B, D, F} |
G = ({A, B, D, F}, {x, y, z}, P, A)
P = {< A > -> z < D >
| z
< B > -> < D > < F >
| z < A > y
| < A > < F > < A >
| < A > < A >
< D > -> < A > < F > < A >
| < A > < A >
< F > -> z < A > y
| < A > < F > < A >
| < A > < A > }
1.3.2. Identificação dos símbolos alcançáveis a partir do símbolo inicial
Conjunto de símbolos alcançáveis a partir do símbolo inicial
| Iteração |
Variáveis |
Terminais |
| 0 |
{A} |
∅ |
| 1 |
{A, D} |
{z} |
| 2 |
{A, D, F} |
{z} |
| 3 |
{A, D, F} |
{z, y} |
G = ({A, D, F}, {y, z}, P, A)
P = {< A > -> z < D >
| z
< D > -> < A > < F > < A >
| < A > < A >
< F > -> z < A > y
| < A > < F > < A >
| < A > < A > }
2. Conversão das produções contendo terminais para a forma < A > -> a
G = ({A, D, F, Y₀, Z₀, Z₁}, {y, z}, P, A)
P = {< A > -> < Z₀ > < D >
| z
< D > -> < A > < F > < A >
| < A > < A >
< F > -> < Z₁ > < A > < Y₀ >
| < A > < F > < A >
| < A > < A >
< Y₀ > -> y
< Z₀ > -> z
< Z₁ > -> z }
3. Conversão das produções contendo variáveis para a forma < A > -> < B > < C >
G = ({A, D, D₀, F, F₀, F₁, Y₀, Z₀, Z₁}, {y, z}, P, A)
P = {< A > -> < Z₀ > < D >
| z
< D > -> < A > < D₀ >
| < A > < A >
< F > -> < Z₁ > < F₀ >
| < A > < F₁ >
| < A > < A >
< D₀ > -> < F > < A >
< F₀ > -> < A > < Y₀ >
< F₁ > -> < F > < A >
< Y₀ > -> y
< Z₀ > -> z
< Z₁ > -> z }
