Exercício 08.30

Converta para a Forma Normal de Chomsky a Gramática Livre do Contexto (GLC) da linguagem de programação SIMPLE (Deitel, 2003).

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 >
     < 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  }

Resposta

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₅ >       ->  =  }

Recomendamos

cert.br Revista Segurança Digital Revista Digital