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