Exercício 07.59

Desenvolva uma Gramática Livre do Contexto (GLC) que reconheça expressões matemáticas na notação pós-fixada (notação polonesa inversa), considerando os operadores aritméticos de adição, subtração, multiplicação e divisão sobre operandos numéricos inteiros, reais e variáveis. Uma variável é uma palavra composta por dígitos e letras, cujo primeiro símbolo deve ser obrigatoriamente uma letra. A seguir, alguns exemplos de entradas válidas:

1 count +
a 2.5 * 3 +
1 x1 / -6 *
xpto -20.0 30.5 * +

Resposta com recursividade à esquerda

G = ({EXPRESSAO, OPERADOR, OPERANDO, NOME, PALAVRA, LETRA, REAL, INTEIRO, SINAL, NUMERO, DIGITO},
     {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, 0, 1, 2, 3,
      4, 5, 6, 7, 8, 9, -, +, *, /, .}, P, EXPRESSAO)
P = {< EXPRESSAO >  ->  < OPERANDO > < OPERANDO > < OPERADOR >
     < OPERADOR >   ->  +
                    |   -
                    |   *
                    |   /
     < OPERANDO >   ->  < EXPRESSAO >
                    |   < REAL >
                    |   < NOME >
     < NOME >       ->  < LETRA > < PALAVRA >
     < PALAVRA >    ->  < PALAVRA > < LETRA >
                    |	< PALAVRA > < DIGITO >
                    |   ε
     < 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
     < REAL >       ->  < SINAL > . < NUMERO >
                    |   < INTEIRO > . < NUMERO > 
                    |   < INTEIRO >
     < INTEIRO >    ->  < SINAL > < NUMERO >
     < SINAL >      ->  +
                    |   -
                    |   ε
     < NUMERO >     ->  < NUMERO > < DIGITO >
                    |   < DIGITO >
     < DIGITO >     ->  0
                    |   1
                    |   2
                    |   3
                    |   4
                    |   5
                    |   6
                    |   7
                    |   8
                    |   9  }

Resposta com recursividade à direita

G = ({EXPRESSAO, OPERADOR, OPERANDO, NOME, PALAVRA, LETRA, REAL, INTEIRO, SINAL, NUMERO, DIGITO},
     {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, 0, 1, 2, 3,
      4, 5, 6, 7, 8, 9, -, +, *, /, .}, P, EXPRESSAO)
P = {< EXPRESSAO >  ->  < OPERANDO > < OPERANDO > < OPERADOR >
     < OPERADOR >   ->  +
                    |   -
                    |   *
                    |   /
     < OPERANDO >   ->  < EXPRESSAO >
                    |   < REAL >
                    |   < NOME >
     < NOME >       ->  < LETRA > < PALAVRA >
     < PALAVRA >    ->  < LETRA > < PALAVRA >
                    |	< DIGITO > < PALAVRA >
                    |   ε
     < 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
     < REAL >       ->  < SINAL > . < NUMERO >
                    |   < INTEIRO > . < NUMERO > 
                    |   < INTEIRO >
     < INTEIRO >    ->  < SINAL > < NUMERO >
     < SINAL >      ->  +
                    |   -
                    |   ε
     < NUMERO >     ->  < DIGITO > < NUMERO >
                    |   < DIGITO >
     < DIGITO >     ->  0
                    |   1
                    |   2
                    |   3
                    |   4
                    |   5
                    |   6
                    |   7
                    |   8
                    |   9  }

Recomendamos

Revista LibreOffice Magazine cert.br Revista Tema