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 |
{B, D, F} |
| 2 |
{B, D, F} |
1.1.2. Exclusão das produções vazias da gramática
G = ({A, B, C, D, E, F, G, H}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A > -> < C > < B >
| < C >
< B > -> + < C > < B >
| + < C >
| - < C > < B >
| - < C >
< C > -> < E > < D >
| < E >
< D > -> * < E > < D >
| * < E >
| / < E > < D >
| / < E >
| % < E > < D >
| % < E >
< E > -> < G > < F >
| < G >
< F > -> ^ < G > < F >
| ^ < G >
< G > -> ( < A > )
| < H >
< H > -> w
| x
| y
| z }
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, H}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A > -> < C > < B >
| < C >
< B > -> + < C > < B >
| + < C >
| - < C > < B >
| - < C >
< C > -> < E > < D >
| < E >
< D > -> * < E > < D >
| * < E >
| / < E > < D >
| / < E >
| % < E > < D >
| % < E >
< E > -> < G > < F >
| < G >
< F > -> ^ < G > < F >
| ^ < G >
< G > -> ( < A > )
| < H >
< H > -> w
| x
| y
| z }
1.2. Exclusão de Produções da Forma < A > -> < B >
1.2.1. Construção dos fechos das variáveis
Fecho(A) = {C, E, G, H}
Fecho(B) = ∅
Fecho(C) = {E, G, H}
Fecho(D) = ∅
Fecho(E) = {G, H}
Fecho(F) = ∅
Fecho(G) = {H}
Fecho(H) = ∅
1.2.2. Exclusão das produções da forma < A > -> < B >
G = ({A, B, C, D, E, F, G, H}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A > -> < C > < B >
| < E > < D >
| < G > < F >
| ( < A > )
| w
| x
| y
| z
< B > -> + < C > < B >
| + < C >
| - < C > < B >
| - < C >
< C > -> < E > < D >
| < G > < F >
| ( < A > )
| w
| x
| y
| z
< D > -> * < E > < D >
| * < E >
| / < E > < D >
| / < E >
| % < E > < D >
| % < E >
< E > -> < G > < F >
| ( < A > )
| w
| x
| y
| z
< F > -> ^ < G > < F >
| ^ < G >
< G > -> ( < A > )
| w
| x
| y
| z
< H > -> w
| x
| y
| z }
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, C, E, G, H} |
| 2 |
{A, C, E, G, H, B, D, F} |
| 3 |
{A, C, E, G, H, B, D, F} |
G = ({A, B, C, D, E, F, G, H}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A > -> < C > < B >
| < E > < D >
| < G > < F >
| ( < A > )
| w
| x
| y
| z
< B > -> + < C > < B >
| + < C >
| - < C > < B >
| - < C >
< C > -> < E > < D >
| < G > < F >
| ( < A > )
| w
| x
| y
| z
< D > -> * < E > < D >
| * < E >
| / < E > < D >
| / < E >
| % < E > < D >
| % < E >
< E > -> < G > < F >
| ( < A > )
| w
| x
| y
| z
< F > -> ^ < G > < F >
| ^ < G >
< G > -> ( < A > )
| w
| x
| y
| z
< H > -> w
| x
| y
| z }
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, B, E, D, G, F} |
{(, ), w, x, y, z} |
| 2 |
{A, C, B, E, D, G, F} |
{(, ), w, x, y, z, +, -, *, /, %, ^} |
G = ({A, B, C, D, E, F, G}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A > -> < C > < B >
| < E > < D >
| < G > < F >
| ( < A > )
| w
| x
| y
| z
< B > -> + < C > < B >
| + < C >
| - < C > < B >
| - < C >
< C > -> < E > < D >
| < G > < F >
| ( < A > )
| w
| x
| y
| z
< D > -> * < E > < D >
| * < E >
| / < E > < D >
| / < E >
| % < E > < D >
| % < E >
< E > -> < G > < F >
| ( < A > )
| w
| x
| y
| z
< F > -> ^ < G > < F >
| ^ < G >
< G > -> ( < A > )
| w
| x
| y
| z }
2. Conversão das produções contendo terminais para a forma < A > -> a
G = ({A, B, C, D, E, F, G, (₀, (₁, (₂, (₃, )₀, )₁, )₂, )₃, +₀, +₁, -₀, -₁, *₀, *₁, /₀, /₁, %₀, %₁, ^₀, ^₁}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A > -> < C > < B >
| < E > < D >
| < G > < F >
| < (₀ > < A > < )₀ >
| w
| x
| y
| z
< B > -> < +₀ > < C > < B >
| < +₁ > < C >
| < -₀ > < C > < B >
| < -₁ > < C >
< C > -> < E > < D >
| < G > < F >
| < (₁ > < A > < )₁ >
| w
| x
| y
| z
< D > -> < *₀ > < E > < D >
| < *₁ > < E >
| < /₀ > < E > < D >
| < /₁ > < E >
| < %₀ > < E > < D >
| < %₁ > < E >
< E > -> < G > < F >
| < (₂ > < A > < )₂ >
| w
| x
| y
| z
< F > -> < ^₀ > < G > < F >
| < ^₁ > < G >
< G > -> < (₃ > < A > < )₃ >
| w
| x
| y
| z
< (₀ > -> (
< (₁ > -> (
< (₂ > -> (
< (₃ > -> (
< )₀ > -> )
< )₁ > -> )
< )₂ > -> )
< )₃ > -> )
< +₀ > -> +
< +₁ > -> +
< -₀ > -> -
< -₁ > -> -
< *₀ > -> *
< *₁ > -> *
< /₀ > -> /
< /₁ > -> /
< %₀ > -> %
< %₁ > -> %
< ^₀ > -> ^
< ^₁ > -> ^ }
3. Conversão das produções contendo variáveis para a forma < A > -> < B > < C >
G = ({A, A₀, B, B₀, B₁, C, C₀, D, D₀, D₁, D₂, E, E₀, F, F₀, G, G₀, (₀, (₁, (₂, (₃, )₀, )₁, )₂, )₃, +₀, +₁, -₀, -₁, *₀, *₁, /₀, /₁, %₀, %₁, ^₀, ^₁}, {w, x, y, z, +, -, *, /, %, ^, (, )}, P, A)
P = {< A > -> < C > < B >
| < E > < D >
| < G > < F >
| < (₀ > < A₀ >
| w
| x
| y
| z
< A₀ > -> < A > < )₀ >
< B > -> < +₀ > < B₀ >
| < +₁ > < C >
| < -₀ > < B₁ >
| < -₁ > < C >
< B₀ > -> < C > < B >
< B₁ > -> < C > < B >
< C > -> < E > < D >
| < G > < F >
| < (₁ > < C₀ >
| w
| x
| y
| z
< C₀ > -> < A > < )₁ >
< D > -> < *₀ > < D₀ >
| < *₁ > < E >
| < /₀ > < D₁ >
| < /₁ > < E >
| < %₀ > < D₂ >
| < %₁ > < E >
< D₀ > -> < E > < D >
< D₁ > -> < E > < D >
< D₂ > -> < E > < D >
< E > -> < G > < F >
| < (₂ > < E₀ >
| w
| x
| y
| z
< E₀ > -> < A > < )₂ >
< F > -> < ^₀ > < F₀ >
| < ^₁ > < G >
< F₀ > -> < G > < F >
< G > -> < (₃ > < G₀ >
| w
| x
| y
| z
< G₀ > -> < A > < )₃ >
< (₀ > -> (
< (₁ > -> (
< (₂ > -> (
< (₃ > -> (
< )₀ > -> )
< )₁ > -> )
< )₂ > -> )
< )₃ > -> )
< +₀ > -> +
< +₁ > -> +
< -₀ > -> -
< -₁ > -> -
< *₀ > -> *
< *₁ > -> *
< /₀ > -> /
< /₁ > -> /
< %₀ > -> %
< %₁ > -> %
< ^₀ > -> ^
< ^₁ > -> ^ }
