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 |
{E} |
| 2 |
{E, C} |
| 3 |
{E, C, B} |
| 4 |
{E, C, B, G} |
| 5 |
{E, C, B, G} |
1.1.2. Exclusão das produções vazias da gramática
G = ({A, B, C, D, E, F, G}, {w, x, y, z}, P, A)
P = {< A > -> x < C > < D > z
| x < D > z
| < D >
| < F > < B > x < G >
| < F > < B > x
| < F > x < G >
| < F > x
< B > -> < F > x < G >
| < F > x
| < D > x < F >
| < C > < E >
| < C >
| < E >
< C > -> x < A > z
| < E >
| < D > z
< D > -> x < E >
| x
| w < F > z
< E > -> < E > < F > < D >
| < F > < D >
| < D > < F >
| < F > x
< F > -> y < F > x
| x < F > < F > w
| w z < F >
< G > -> < B > < C >
| < B >
| < C >
| < A > < B > < C >
| < A > < B >
| < A > < C >
| < A >
| w < A > y }
1.1.3. Inclusão da palavra vazia, caso pertença a linguagem gerada pela gramática
G = ({A, B, C, D, E, F, G}, {w, x, y, z}, P, A)
P = {< A > -> x < C > < D > z
| x < D > z
| < D >
| < F > < B > x < G >
| < F > < B > x
| < F > x < G >
| < F > x
< B > -> < F > x < G >
| < F > x
| < D > x < F >
| < C > < E >
| < C >
| < E >
< C > -> x < A > z
| < E >
| < D > z
< D > -> x < E >
| x
| w < F > z
< E > -> < E > < F > < D >
| < F > < D >
| < D > < F >
| < F > x
< F > -> y < F > x
| x < F > < F > w
| w z < F >
< G > -> < B > < C >
| < B >
| < C >
| < A > < B > < C >
| < A > < B >
| < A > < C >
| < A >
| w < A > y }
1.2. Exclusão de Produções da Forma < A > -> < B >
1.2.1. Construção dos fechos das variáveis
Fecho(A) = {D}
Fecho(B) = {C, E}
Fecho(C) = {E}
Fecho(D) = ∅
Fecho(E) = ∅
Fecho(F) = ∅
Fecho(G) = {A, B, C, D, E}
1.2.2. Exclusão das produções da forma < A > -> < B >
G = ({A, B, C, D, E, F, G}, {w, x, y, z}, P, A)
P = {< A > -> x < C > < D > z
| x < D > z
| x < E >
| x
| w < F > z
| < F > < B > x < G >
| < F > < B > x
| < F > x < G >
| < F > x
< B > -> < F > x < G >
| < F > x
| < D > x < F >
| < C > < E >
| x < A > z
| < E > < F > < D >
| < F > < D >
| < D > < F >
| < F > x
| < D > z
< C > -> x < A > z
| < E > < F > < D >
| < F > < D >
| < D > < F >
| < F > x
| < D > z
< D > -> x < E >
| x
| w < F > z
< E > -> < E > < F > < D >
| < F > < D >
| < D > < F >
| < F > x
< F > -> y < F > x
| x < F > < F > w
| w z < F >
< G > -> < B > < C >
| < F > x < G >
| < F > x
| < D > x < F >
| < C > < E >
| x < A > z
| < E > < F > < D >
| < F > < D >
| < D > < F >
| < F > x
| < D > z
| < A > < B > < C >
| < A > < B >
| < A > < C >
| x < C > < D > z
| x < D > z
| x < E >
| x
| w < F > z
| < F > < B > x < G >
| < F > < B > x
| < F > x < G >
| < F > x
| w < A > y }
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, D, G} |
| 2 |
{A, D, G, B, C} |
| 3 |
{A, D, G, B, C} |
G = ({A, B, C, D, G}, {w, x, y, z}, P, A)
P = {< A > -> x < C > < D > z
| x < D > z
| x
< B > -> x < A > z
| < D > z
< C > -> x < A > z
| < D > z
< D > -> x
< G > -> < B > < C >
| x < A > z
| < D > z
| < A > < B > < C >
| < A > < B >
| < A > < C >
| x < C > < D > z
| x < D > z
| x
| w < A > y }
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, C, D} |
{x, z} |
| 2 |
{A, C, D} |
{x, z} |
G = ({A, C, D}, {x, z}, P, A)
P = {< A > -> x < C > < D > z
| x < D > z
| x
< C > -> x < A > z
| < D > z
< D > -> x }
2. Conversão das produções contendo terminais para a forma < A > -> a
G = ({A, C, D, X₀, X₁, X₂, Z₀, Z₁, Z₂, Z₃}, {x, z}, P, A)
P = {< A > -> < X₀ > < C > < D > < Z₀ >
| < X₁ > < D > < Z₁ >
| x
< C > -> < X₂ > < A > < Z₂ >
| < D > < Z₃ >
< D > -> x
< X₀ > -> x
< X₁ > -> x
< X₂ > -> x
< Z₀ > -> z
< Z₁ > -> z
< Z₂ > -> z
< Z₃ > -> z }
3. Conversão das produções contendo variáveis para a forma < A > -> < B > < C >
G = ({A, A₀, A₁, A₂, C, C₀, D, X₀, X₁, X₂, Z₀, Z₁, Z₂, Z₃}, {x, z}, P, A)
P = {< A > -> < X₀ > < A₁ >
| < X₁ > < A₂ >
| x
< A₀ > -> < D > < Z₀ >
< A₁ > -> < C > < A₀ >
< A₂ > -> < D > < Z₁ >
< C > -> < X₂ > < C₀ >
| < D > < Z₃ >
< C₀ > -> < A > < Z₂ >
< D > -> x
< X₀ > -> x
< X₁ > -> x
< X₂ > -> x
< Z₀ > -> z
< Z₁ > -> z
< Z₂ > -> z
< Z₃ > -> z }
