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 |
{SINAL} |
| 2 |
{SINAL} |
1.1.2. Exclusão das produções vazias da gramática
G = ({PROGRAMA, COMANDO, INPUT, PRINT, REM, IF, LET, GOTO, END, EXPR, TERMO, FATOR, CONDICAO,
ITEM, RELACAO, INTEIRO, SINAL, PALAVRA, LABEL, VARIAVEL, DIGITO, LETRA}, {0, 1, 2, 3, 4,
5, 6, 7, 8, 9, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y,
z, (, ), =, !, <, >, +, -, *, /}, P, PROGRAMA)
P = {< PROGRAMA > -> < PROGRAMA > < LABEL > < COMANDO > | < LABEL > < COMANDO >
< COMANDO > -> < INPUT > | < PRINT > | < REM > | < IF > | < LET > | < GOTO >
| < END >
< INPUT > -> input < VARIAVEL >
< PRINT > -> print < VARIAVEL >
< REM > -> rem < PALAVRA >
< IF > -> if < CONDICAO > goto < LABEL >
< LET > -> let < VARIAVEL > = < EXPR >
< GOTO > -> goto < LABEL >
< END > -> end
< EXPR > -> < EXPR > + < TERMO > | < EXPR > - < TERMO > | < TERMO >
< TERMO > -> < TERMO > * < FATOR > | < TERMO > / < FATOR > | < FATOR >
< FATOR > -> ( < EXPR > ) | < ITEM >
< CONDICAO > -> < ITEM > < RELACAO > < ITEM >
< ITEM > -> < VARIAVEL > | < INTEIRO >
< RELACAO > -> == | != | > | >= | < | <=
< INTEIRO > -> < SINAL > < LABEL > | < LABEL >
< SINAL > -> - | +
< PALAVRA > -> < PALAVRA > < DIGITO > | < PALAVRA > < LETRA > | < DIGITO > | < LETRA >
< LABEL > -> < LABEL > < DIGITO > | < DIGITO >
< VARIAVEL > -> < LETRA >
< DIGITO > -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< LETRA > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z }
1.1.3. Inclusão da palavra vazia, caso pertença a linguagem gerada pela gramática
G = ({PROGRAMA, COMANDO, INPUT, PRINT, REM, IF, LET, GOTO, END, EXPR, TERMO, FATOR, CONDICAO,
ITEM, RELACAO, INTEIRO, SINAL, PALAVRA, LABEL, VARIAVEL, DIGITO, LETRA}, {0, 1, 2, 3, 4,
5, 6, 7, 8, 9, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y,
z, (, ), =, !, <, >, +, -, *, /}, P, PROGRAMA)
P = {< PROGRAMA > -> < PROGRAMA > < LABEL > < COMANDO > | < LABEL > < COMANDO >
< COMANDO > -> < INPUT > | < PRINT > | < REM > | < IF > | < LET > | < GOTO >
| < END >
< INPUT > -> input < VARIAVEL >
< PRINT > -> print < VARIAVEL >
< REM > -> rem < PALAVRA >
< IF > -> if < CONDICAO > goto < LABEL >
< LET > -> let < VARIAVEL > = < EXPR >
< GOTO > -> goto < LABEL >
< END > -> end
< EXPR > -> < EXPR > + < TERMO > | < EXPR > - < TERMO > | < TERMO >
< TERMO > -> < TERMO > * < FATOR > | < TERMO > / < FATOR > | < FATOR >
< FATOR > -> ( < EXPR > ) | < ITEM >
< CONDICAO > -> < ITEM > < RELACAO > < ITEM >
< ITEM > -> < VARIAVEL > | < INTEIRO >
< RELACAO > -> == | != | > | >= | < | <=
< INTEIRO > -> < SINAL > < LABEL > | < LABEL >
< SINAL > -> - | +
< PALAVRA > -> < PALAVRA > < DIGITO > | < PALAVRA > < LETRA > | < DIGITO > | < LETRA >
< LABEL > -> < LABEL > < DIGITO > | < DIGITO >
< VARIAVEL > -> < LETRA >
< DIGITO > -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< LETRA > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | 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(PROGRAMA) = ∅
Fecho(COMANDO) = {INPUT, PRINT, REM, IF, LET, GOTO, END}
Fecho(INPUT) = ∅
Fecho(PRINT) = ∅
Fecho(REM) = ∅
Fecho(IF) = ∅
Fecho(LET) = ∅
Fecho(GOTO) = ∅
Fecho(END) = ∅
Fecho(EXPR) = {TERMO, FATOR, ITEM, VARIAVEL, LETRA, INTEIRO, LABEL, DIGITO}
Fecho(TERMO) = {FATOR, ITEM, VARIAVEL, LETRA, INTEIRO, LABEL, DIGITO}
Fecho(FATOR) = {ITEM, VARIAVEL, LETRA, INTEIRO, LABEL, DIGITO}
Fecho(CONDICAO) = ∅
Fecho(ITEM) = {VARIAVEL, LETRA, INTEIRO, LABEL, DIGITO}
Fecho(RELACAO) = ∅
Fecho(INTEIRO) = {LABEL, DIGITO}
Fecho(SINAL) = ∅
Fecho(PALAVRA) = {DIGITO, LETRA}
Fecho(LABEL) = {DIGITO}
Fecho(VARIAVEL) = {LETRA}
Fecho(DIGITO) = ∅
Fecho(LETRA) = ∅
1.2.2. Exclusão das produções da forma < A > -> < B >
G = ({PROGRAMA, COMANDO, INPUT, PRINT, REM, IF, LET, GOTO, END, EXPR, TERMO, FATOR, CONDICAO,
ITEM, RELACAO, INTEIRO, SINAL, PALAVRA, LABEL, VARIAVEL, DIGITO, LETRA}, {0, 1, 2, 3, 4,
5, 6, 7, 8, 9, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y,
z, (, ), =, !, <, >, +, -, *, /}, P, PROGRAMA)
P = {< PROGRAMA > -> < PROGRAMA > < LABEL > < COMANDO > | < LABEL > < COMANDO >
< COMANDO > -> input < VARIAVEL > | print < VARIAVEL > | rem < PALAVRA >
| if < CONDICAO > goto < LABEL > | let < VARIAVEL > = < EXPR >
| goto < LABEL > | end
< INPUT > -> input < VARIAVEL >
< PRINT > -> print < VARIAVEL >
< REM > -> rem < PALAVRA >
< IF > -> if < CONDICAO > goto < LABEL >
< LET > -> let < VARIAVEL > = < EXPR >
< GOTO > -> goto < LABEL >
< END > -> end
< EXPR > -> < EXPR > + < TERMO > | < EXPR > - < TERMO >
| < TERMO > * < FATOR > | < TERMO > / < FATOR >
| ( < EXPR > )
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< TERMO > -> < TERMO > * < FATOR > | < TERMO > / < FATOR >
| ( < EXPR > )
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< FATOR > -> ( < EXPR > )
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< CONDICAO > -> < ITEM > < RELACAO > < ITEM >
< ITEM > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< RELACAO > -> == | != | > | >= | < | <=
< INTEIRO > -> < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< SINAL > -> - | +
< PALAVRA > -> < PALAVRA > < DIGITO > | < PALAVRA > < LETRA >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< LABEL > -> < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< VARIAVEL > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< DIGITO > -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< LETRA > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | 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 |
{COMANDO, END, EXPR, TERMO, FATOR, ITEM, RELACAO, INTEIRO, SINAL, PALAVRA, LABEL, VARIAVEL, DIGITO, LETRA} |
| 2 |
{COMANDO, END, EXPR, TERMO, FATOR, ITEM, RELACAO, INTEIRO, SINAL, PALAVRA, LABEL, VARIAVEL, DIGITO, LETRA, PROGRAMA, INPUT, PRINT, REM, LET, GOTO, CONDICAO} |
| 3 |
{COMANDO, END, EXPR, TERMO, FATOR, ITEM, RELACAO, INTEIRO, SINAL, PALAVRA, LABEL, VARIAVEL, DIGITO, LETRA, PROGRAMA, INPUT, PRINT, REM, LET, GOTO, CONDICAO, IF} |
| 4 |
{COMANDO, END, EXPR, TERMO, FATOR, ITEM, RELACAO, INTEIRO, SINAL, PALAVRA, LABEL, VARIAVEL, DIGITO, LETRA, PROGRAMA, INPUT, PRINT, REM, LET, GOTO, CONDICAO, IF} |
G = ({PROGRAMA, COMANDO, INPUT, PRINT, REM, IF, LET, GOTO, END, EXPR, TERMO, FATOR, CONDICAO,
ITEM, RELACAO, INTEIRO, SINAL, PALAVRA, LABEL, VARIAVEL, DIGITO, LETRA}, {0, 1, 2, 3, 4,
5, 6, 7, 8, 9, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y,
z, (, ), =, !, <, >, +, -, *, /}, P, PROGRAMA)
P = {< PROGRAMA > -> < PROGRAMA > < LABEL > < COMANDO > | < LABEL > < COMANDO >
< COMANDO > -> input < VARIAVEL > | print < VARIAVEL > | rem < PALAVRA >
| if < CONDICAO > goto < LABEL > | let < VARIAVEL > = < EXPR >
| goto < LABEL > | end
< INPUT > -> input < VARIAVEL >
< PRINT > -> print < VARIAVEL >
< REM > -> rem < PALAVRA >
< IF > -> if < CONDICAO > goto < LABEL >
< LET > -> let < VARIAVEL > = < EXPR >
< GOTO > -> goto < LABEL >
< END > -> end
< EXPR > -> < EXPR > + < TERMO > | < EXPR > - < TERMO >
| < TERMO > * < FATOR > | < TERMO > / < FATOR >
| ( < EXPR > )
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< TERMO > -> < TERMO > * < FATOR > | < TERMO > / < FATOR >
| ( < EXPR > )
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< FATOR > -> ( < EXPR > )
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< CONDICAO > -> < ITEM > < RELACAO > < ITEM >
< ITEM > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< RELACAO > -> == | != | > | >= | < | <=
< INTEIRO > -> < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< SINAL > -> - | +
< PALAVRA > -> < PALAVRA > < DIGITO > | < PALAVRA > < LETRA >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< LABEL > -> < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< VARIAVEL > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< DIGITO > -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< LETRA > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | 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 |
{PROGRAMA} |
∅ |
| 1 |
{PROGRAMA, LABEL, COMANDO} |
∅ |
| 2 |
{PROGRAMA, LABEL, COMANDO, DIGITO, VARIAVEL, PALAVRA, CONDICAO, EXPR} |
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, i, n, p, u, t, r, e, m, f, g, o, l, d, =} |
| 3 |
{PROGRAMA, LABEL, COMANDO, DIGITO, VARIAVEL, PALAVRA, CONDICAO, EXPR, LETRA, ITEM, RELACAO, TERMO, FATOR, SINAL} |
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, =, +, -, *, /, (, )} |
| 4 |
{PROGRAMA, LABEL, COMANDO, DIGITO, VARIAVEL, PALAVRA, CONDICAO, EXPR, LETRA, ITEM, RELACAO, TERMO, FATOR, SINAL} |
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, =, +, -, *, /, (, ), !, <, >} |
G = ({PROGRAMA, COMANDO, EXPR, TERMO, FATOR, CONDICAO, ITEM, RELACAO, SINAL, PALAVRA, LABEL, VARIAVEL,
DIGITO, LETRA}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q,
r, s, t, u, v, w, x, y, z, (, ), =, !, <, >, +, -, *, /}, P, PROGRAMA)
P = {< PROGRAMA > -> < PROGRAMA > < LABEL > < COMANDO > | < LABEL > < COMANDO >
< COMANDO > -> input < VARIAVEL > | print < VARIAVEL > | rem < PALAVRA >
| if < CONDICAO > goto < LABEL > | let < VARIAVEL > = < EXPR >
| goto < LABEL > | end
< EXPR > -> < EXPR > + < TERMO > | < EXPR > - < TERMO >
| < TERMO > * < FATOR > | < TERMO > / < FATOR >
| ( < EXPR > )
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< TERMO > -> < TERMO > * < FATOR > | < TERMO > / < FATOR >
| ( < EXPR > )
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< FATOR > -> ( < EXPR > )
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< CONDICAO > -> < ITEM > < RELACAO > < ITEM >
< ITEM > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< RELACAO > -> == | != | > | >= | < | <=
< SINAL > -> - | +
< PALAVRA > -> < PALAVRA > < DIGITO > | < PALAVRA > < LETRA >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< LABEL > -> < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< VARIAVEL > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< DIGITO > -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< LETRA > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z }
2. Conversão das produções contendo terminais para a forma < A > -> a
G = ({PROGRAMA, COMANDO, EXPR, TERMO, FATOR, CONDICAO, ITEM, RELACAO, SINAL, PALAVRA, LABEL, VARIAVEL,
DIGITO, LETRA, I₀, N₀, P₀, U₀, T₀, P₁, R₀, I₁, N₁, T₁, R₁, E₀, M₀, I₂, F₀, G₀, O₀, T₂, O₁, L₀,
E₁, T₃, EQ₀, G₁, O₂, T₄, O₃, E₂, N₂, D₀, PL₀, MI₀, TI₀, FR₀, AP₀, FP₀, TI₁, FR₁, AP₁, FP₁, AP₂,
FP₂, EQ₁, EQ₂, EX₀, EQ₃, GT₀, EQ₄, LT₀, EQ₅}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, g,
h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, (, ), =, !, <, >, +, -, *, /}, P, PROGRAMA)
P = {< PROGRAMA > -> < PROGRAMA > < LABEL > < COMANDO > | < LABEL > < COMANDO >
< COMANDO > -> < I₀ > < N₀ > < P₀ > < U₀ > < T₀ > < VARIAVEL >
| < P₁ > < R₀ > < I₁ > < N₁ > < T₁ > < VARIAVEL >
| < R₁ > < E₀ > < M₀ > < PALAVRA >
| < I₂ > < F₀ > < CONDICAO > < G₀ > < O₀ > < T₂ > < O₁ > < LABEL >
| < L₀ > < E₁ > < T₃ > < VARIAVEL > < EQ₀ > < EXPR >
| < G₁ > < O₂ > < T₄ > < O₃ > < LABEL >
| < E₂ > < N₂ > < D₀ >
< EXPR > -> < EXPR > < PL₀ > < TERMO > | < EXPR > < MI₀ > < TERMO >
| < TERMO > < TI₀ > < FATOR > | < TERMO > < FR₀ > < FATOR >
| < AP₀ > < EXPR > < FP₀ >
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< TERMO > -> < TERMO > < TI₁ > < FATOR > | < TERMO > < FR₁ > < FATOR >
| < AP₁ > < EXPR > < FP₁ >
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< FATOR > -> < AP₂ > < EXPR > < FP₂ >
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< CONDICAO > -> < ITEM > < RELACAO > < ITEM >
< ITEM > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< RELACAO > -> < EQ₁ > < EQ₂ > | < EX₀ > < EQ₃ > | > | < GT₀ > < EQ₄ > | < | < LT₀ > < EQ₅ >
< SINAL > -> - | +
< PALAVRA > -> < PALAVRA > < DIGITO > | < PALAVRA > < LETRA >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< LABEL > -> < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< VARIAVEL > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< DIGITO > -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< LETRA > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< I₀ > -> i
< N₀ > -> n
< P₀ > -> p
< U₀ > -> u
< T₀ > -> t
< P₁ > -> p
< R₀ > -> r
< I₁ > -> i
< N₁ > -> n
< T₁ > -> t
< R₁ > -> r
< E₀ > -> e
< M₀ > -> m
< I₂ > -> i
< F₀ > -> f
< G₀ > -> g
< O₀ > -> o
< T₂ > -> t
< O₁ > -> o
< L₀ > -> l
< E₁ > -> e
< T₃ > -> t
< EQ₀ > -> =
< G₁ > -> g
< O₂ > -> o
< T₄ > -> t
< O₃ > -> o
< E₂ > -> e
< N₂ > -> n
< D₀ > -> d
< PL₀ > -> +
< MI₀ > -> -
< TI₀ > -> *
< FR₀ > -> /
< AP₀ > -> (
< FP₀ > -> )
< TI₁ > -> *
< FR₁ > -> /
< AP₁ > -> (
< FP₁ > -> )
< AP₂ > -> (
< FP₂ > -> )
< EQ₁ > -> =
< EQ₂ > -> =
< EX₀ > -> !
< EQ₃ > -> =
< GT₀ > -> >
< EQ₄ > -> =
< LT₀ > -> <
< EQ₅ > -> = }
3. Conversão das produções contendo variáveis para a forma < A > -> < B > < C >
G = ({PROGRAMA, PROGRAMA₀, COMANDO, INPUT₀, INPUT₁, INPUT₂, INPUT₃, PRINT₀, PRINT₁, PRINT₂, PRINT₃,
REM₀, REM₁, IF₀, IF₁, IF₂, IF₃, IF₄, IF₅, LET₀, LET₁, LET₂, LET₃, GOTO₀, GOTO₁, GOTO₂, END₀,
EXPR, EXPR₀, EXPR₁, EXPR₂, EXPR₃, EXPR₄, TERMO, TERMO₀, TERMO₁, TERMO₂, FATOR, FATOR₀, CONDICAO,
CONDICAO₀, ITEM, RELACAO, SINAL, PALAVRA, LABEL, VARIAVEL, DIGITO, LETRA, I₀, N₀, P₀, U₀, T₀, P₁,
R₀, I₁, N₁, T₁, R₁, E₀, M₀, I₂, F₀, G₀, O₀, T₂, O₁, L₀, E₁, T₃, EQ₀, G₁, O₂, T₄, O₃, E₂, N₂, D₀,
PL₀, MI₀, TI₀, FR₀, AP₀, FP₀, TI₁, FR₁, AP₁, FP₁, AP₂, FP₂, EQ₁, EQ₂, EX₀, EQ₃, GT₀, EQ₄, LT₀, EQ₅},
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w,
x, y, z, (, ), =, !, <, >, +, -, *, /}, P, PROGRAMA)
P = {< PROGRAMA > -> < PROGRAMA > < PROGRAMA₀ > | < LABEL > < COMANDO >
< PROGRAMA₀ > -> < LABEL > < COMANDO >
< COMANDO > -> < I₀ > < INPUT₃ >
| < P₁ > < PRINT₃ >
| < R₁ > < REM₁ >
| < I₂ > < IF₅ >
| < L₀ > < LET₃ >
| < G₁ > < GOTO₂ >
| < E₂ > < END₀ >
< INPUT₀ > -> < T₀ > < VARIAVEL >
< INPUT₁ > -> < U₀ > < INPUT₀ >
< INPUT₂ > -> < P₀ > < INPUT₁ >
< INPUT₃ > -> < N₀ > < INPUT₂ >
< PRINT₀ > -> < T₀ > < VARIAVEL >
< PRINT₁ > -> < N₁ > < PRINT₀ >
< PRINT₂ > -> < I₁ > < PRINT₁ >
< PRINT₃ > -> < R₀ > < PRINT₂ >
< REM₀ > -> < M₀ > < PALAVRA >
< REM₁ > -> < E₀ > < REM₀ >
< IF₀ > -> < O₁ > < LABEL >
< IF₁ > -> < T₂ > < IF₀ >
< IF₂ > -> < O₀ > < IF₁ >
< IF₃ > -> < G₀ > < IF₂ >
< IF₄ > -> < CONDICAO > < IF₃ >
< IF₅ > -> < F₀ > < IF₄ >
< LET₀ > -> < EQ₀ > < EXPR >
< LET₁ > -> < VARIAVEL > < LET₀ >
< LET₂ > -> < T₃ > < LET₁ >
< LET₃ > -> < E₁ > < LET₂ >
< GOTO₀ > -> < O₃ > < LABEL >
< GOTO₁ > -> < T₄ > < GOTO₀ >
< GOTO₂ > -> < O₂ > < GOTO₁ >
< END₀ > -> < N₂ > < D₀ >
< EXPR > -> < EXPR > < EXPR₀ > | < EXPR > < EXPR₁ >
| < TERMO > < EXPR₂ > | < TERMO > < EXPR₃ >
| < AP₀ > < EXPR₄ >
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< EXPR₀ > -> < PL₀ > < TERMO >
< EXPR₁ > -> < MI₀ > < TERMO >
< EXPR₂ > -> < TI₀ > < FATOR >
< EXPR₃ > -> < FR₀ > < FATOR >
< EXPR₄ > -> < EXPR > < FP₀ >
< TERMO > -> < TERMO > < TERMO₀ > | < TERMO > < TERMO₁ >
| < AP₁ > < TERMO₂ >
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< TERMO₀ > -> < TI₁ > < FATOR >
< TERMO₁ > -> < FR₁ > < FATOR >
< TERMO₂ > -> < EXPR > < FP₁ >
< FATOR > -> < AP₂ > < FATOR₀ >
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< FATOR₀ > -> < EXPR > < FP₂ >
< CONDICAO > -> < ITEM > < CONDICAO₀ >
< CONDICAO₀ > -> < RELACAO > < ITEM >
< ITEM > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
| < SINAL > < LABEL > | < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< RELACAO > -> < EQ₁ > < EQ₂ > | < EX₀ > < EQ₃ > | > | < GT₀ > < EQ₄ > | < | < LT₀ > < EQ₅ >
< SINAL > -> - | +
< PALAVRA > -> < PALAVRA > < DIGITO > | < PALAVRA > < LETRA >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< LABEL > -> < LABEL > < DIGITO >
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< VARIAVEL > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< DIGITO > -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< LETRA > -> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
< I₀ > -> i
< N₀ > -> n
< P₀ > -> p
< U₀ > -> u
< T₀ > -> t
< P₁ > -> p
< R₀ > -> r
< I₁ > -> i
< N₁ > -> n
< T₁ > -> t
< R₁ > -> r
< E₀ > -> e
< M₀ > -> m
< I₂ > -> i
< F₀ > -> f
< G₀ > -> g
< O₀ > -> o
< T₂ > -> t
< O₁ > -> o
< L₀ > -> l
< E₁ > -> e
< T₃ > -> t
< EQ₀ > -> =
< G₁ > -> g
< O₂ > -> o
< T₄ > -> t
< O₃ > -> o
< E₂ > -> e
< N₂ > -> n
< D₀ > -> d
< PL₀ > -> +
< MI₀ > -> -
< TI₀ > -> *
< FR₀ > -> /
< AP₀ > -> (
< FP₀ > -> )
< TI₁ > -> *
< FR₁ > -> /
< AP₁ > -> (
< FP₁ > -> )
< AP₂ > -> (
< FP₂ > -> )
< EQ₁ > -> =
< EQ₂ > -> =
< EX₀ > -> !
< EQ₃ > -> =
< GT₀ > -> >
< EQ₄ > -> =
< LT₀ > -> <
< EQ₅ > -> = }
