Evaluador de expresiones matemáticas complejas

Operadores binarios. Operadores unitarios. Concatenación de expresiones. Variables. Asignación. Símbolo. Alfabeto. Léxico. Sintáctico. Semántica. Herencia

  • Enviado por: El remitente no desea revelar su nombre
  • Idioma: castellano
  • País: México México
  • 13 páginas
publicidad
publicidad

Introducción

El objetivo de esta práctica es la realización de un evaluador de expresiones matemáticas complejas:

(4.5^-2+3.1*8+3!)/(3^2)

permitiendo también la concatenación de expresiones, declaración de variables, promoción de tipos, etc.

entero x;

x= 2 * 4;

5 + x!

En este tipo de problemas (reconocedores de expresiones, compiladores e intérpretes de lenguajes, etc.), siempre se siguen los siguientes pasos:

  • ANÁLISIS LÉXICO
    Trocea la entrada
        parser o scanner

  • ANÁLISIS SINTÁCTICO
    Construir un árbol de sintaxis (AS)
        mediante pilas

  • ANÁLISIS SEMÁNTICO
    Semántica Estática, Semántica Dinámica, Semántica Temporal,...
        o como efecto lateral de la evaluación en los intérpretes

  • EVALUACIÓN
    Recorrido en preorden

Según el tipo de gramática que tengamos, algunos o todos estos pasos pueden ser automatizados.

Especificación del Problema

  • Operadores binarios
    + - * / % ^

  • Operadores unitarios
    - !

  • Concatenación de expresiones
    expr1 ; expr2

  • Declaración de variables
    entero x;
    real y

  • Asignación
    x = expr

Formalmente

A continuación se especifica formalmente el alfabeto, el léxico y la sintaxis de las expresiones.
La semántica se especifica informalmente. Para las especificaciones formales, se utiliza la
notación EBNF (BNF -Backus-Naur Form- extendida).

Símbolo

Significado

|

Definición alternativa

"entero", "real", …

Simbolos terminales y no terminales

::=

Definición

*

Repetición de la unidad sintáctica precedente
0 o más veces (separado por un <separador>)

+

Repetición de la unidad sintáctica precedente
1 o más veces (separado por un <separador>)

( )

Agrupación de unidad sintáctica

[ ]

Opcional (puede ocurrir o no)

Alfabeto

letra ::= 'a', ... , 'z', 'A',..., 'Z'

dígito ::= '0',...,'9'

especiales ::= '(', ')', '+', '-', '*', '/', '%', '^', '!', '=', '.'

separador_expresion ::= ';'

separador ::= '\n', '\r', ' ', '\t'

Nota: se consideran distintas las mayúsculas y minúsculas.

Nota: para simplificar las especificaciones del léxico y de la sintaxis, algunos caracteres aparecerán en dichas especificaciones de forma explícita, como el ';',  '.', etc.

Léxico

entero ::= (digito) +

real ::= (digito)+ '.' (digito) +

identificador ::= letra [ ( letra | digito ) + ]

Nota: los tipos "entero" y "real" pueden considerarse como identificadores predefinidos o como palabras reservadas. Se sugiere considerarlos como palabras reservadas. En este caso, hay que añadir la siguiente regla:

tipo ::= "entero" | "real"

en cuyo caso, dichas cadenas NO GENERARÁN un token identificador

Sintáxis

lista_expr ::= lista_expr ';' expr

expr

expr ::= term '+' expr

| term '-' expr

| term '*' expr

| term '/' expr

| term '%' expr

| term '^' expr

| '-' term

| term '!'

| declaración

| asignación

term ::= identificador

| entero

| real

| '(' expr ')'

declaración ::= tipo identificador

asignación ::= identificador '=' expr

NOTA: Si queremos que los nombres de los tipos sea identificadores predefinidos y no palabras reservadas, aquí habría que incluir la siguiente regla:

tipo ::= "entero" | "real"

Semántica

  • Los operadores binarios se agrupan por defecto por la izquierda.
    Así, 2^3^4 se interpreta como (2^3)^4.

  • La prioridad de los operadores, de mayor a menor, es:
    ! (factorial)
    ^ (exponenciación)
    - (menos unario)
    * / % (operadores multiplicativos)
    + - (operadores aditivos)
    = (asignación)

  • Los operadores binarios aceptan y devuelven los siguientes tipos
    + - * / % :entero, entero -> entero
    + - * / ^: real, real -> real

  • Los operadores unarios aceptan y devuelven los siguientes tipos
    - ! : entero -> entero
    - :  real -> real

  • Las expresiones enteras se pueden promocionar a reales si el contexto lo requiere.

  • Se considera un error usar siempre tipos reales "para simplificar"

  • Se considera un error declarar una variable ya declarada

  • Se considera un error utilizar una variable no inicializada.

Diseño de la solución

Análisis léxico

El analizador léxico debe leer la entrada y generar los símbolos léxicos del lenguaje, llamados tokens. Por ello, estos tokens serán aquellos definidos por el léxico del lenguaje. En este caso, tenemos los siguientes tipos de tokens:

  • Palabras reservadas del lenguaje:

    • TK_TIPO_ENTERO

    • TK_TIPO_REAL

  • TK_IDENTIFICADOR

  • números: TK_REAL, TK_ENTERO

  • operadores: TK_SUMA, TK_RESTA, TK_MENOS_UNARIO, TK_ASIGNACION, TK_FACTORIAL, TK_MULTIPLICACION, TK_DIVISION, TK_MODULO, TK_EXPONENCIACION, TK_PUNTO_Y_COMA

  • elementos sintácticos: TK_ABRE_PARENTESIS, TK_CIERRA_PARENTESIS.
    Nota: el caso del punto y coma es especial. En muchos lenguajes, el punto y coma es un terminador de sentencia, y es considerado un elemento sintáctico como los parentesis, corchetes, etc. En otros lenguajes, es considerado un separador de sentencias. En este caso, el punto y coma puede ser un elemento sintáctico o, como en nuestro caso, un operador.

  • todos los operadores y caracteres especiales. Se suelen tratar de forma literal en la especificación de la sintáxis (aparece ";" en vez del token TK_PUNTO_Y_COMA, "+" en vez de TK_OPERADOR_SUMA) por simplicidad. En cualquier caso, el analizador léxico devuelve un token con el tipo adecuado.

  • y los tokens especiales:

    • TK_ERROR, cuando se encuentra un error léxico

    • TK_FIN_DE_ENTRADA, cuando se termina la entrada

Análisis sintáctico

El análisis sintáctico consiste en la generación de un árbol sintáctico, que representa la expresión matemática. Para ello, se construyen las reglas sintácticas según se leen tokens léxicos. Si se puede construir el árbol sintáctico, es que la expresión es sintácticamente correcta. Si no se puede, es que había algún error sintáctico.

A continuación, se presentan un par de ejemplos de árboles.

2 * ( 3 + 8 )

se representa como

entero x;

x = 7

se representa como

Nota: estos árboles se denominan AST (Abstract Syntax Tree- Árbol de Sintáxis Abstracta) cuando la reglas irrelevantes se eliminan, por ejemplo, los paréntesis podrían no aparecer en el primer ejemplo, quedando el siguiente árbol:

2 * ( 3 + 8 )

el AST se representa como

Puedes ver una animación del algoritmo.

Evaluador (con análisis semántico al vuelo)

El evaluador (o generador de código, o transformador, según se desee) consiste en recorrer el árbol (en preorden) para realizar los cálculos intermedios.

Evalúa las expresiones

  • 2+3
    devuelve 5

  • entero x
    devuelve “entero x”

  • expr1 ; expr2
    evalúa expr1, evalúa expr2,
    devuelve el resultado de expr2

  • x= expr1
    evalúa expr1, guarda en x, devuelve el valor de x

Implementación

Análisis léxico

Para realizar el análisis léxico, se suele usar el siguiente algoritmo, escrito en seudocódigo:

leo un carácter
    si es dígito:
        // es un número
        leer caracteres hasta que no sea dígito
        // me sobra el último, lo devuelvo
    si es `+':
        es una suma
    si es `-'
        es una resta
    ...
    si es letra:
        // en un identificador
        leer caracteres válidos (letras o dígitos) hasta que no sea letra ni dígito
        // me sobra el último, lo devuelvo
    else
        carácter no válido: ERROR LÉXICO

Para implementar los tokens, podemos pensar en un par de esquemas sencillos:

Primer método: HERENCIA

public abstract class MToken {

public abstract String toString();

}

class TkAbreParentesis extends MToken {

}

class TkNumeroEntero extends MToken {

private int valor;

}

class TkSuma extends MToken {

}

...

O también

public abstract class OperadorBinarioTk extends MToken {

// uno para cada tipo de prioridad

final static int PRIO_OP_MULTIPLICACION= 8;

final static int PRIO_OP_SUMA= 7;

public abstract int prioridad ();

public String toString();

}

public class SumaTk extends OperadorBinarioTk {

public int prioridad() { return PRIO_OP_SUMA; }

public String toString() { return "+"; }

}

Segundo método: TIPADO EXPLÍCITO

public class MToken {

final static int TOKEN_TIPO_A 1

final static int TOKEN_TIPO_B 2

final static int TOKEN_TIPO_C 3

// un valor para cada tipo de token

char op;

public int tipoToken ()

public int prioridad () // OJO! con los que no son operadores

public String toString()

}

Elección

El primer método es tedioso en Java, pues obliga a que cada clase token esté declarada en un fichero, pues todos los tokens han de ser públicos (una sola clase pública por fichero). Además, aunque parece natural la herencia, a la hora de usar los tokens, hay que preguntar constantemente por el instanceof de los tokens.

El segundo método podíamos denominarlo "a la antigua": el tipo está implícito y hay que preguntar a cada token de qué tipo es. Por otro lado, seleccionar entre tokens es un switch muy clarito y estructurado, lo que siempre es deseable.

En nuestra implementación, optaremos por la segunda solución. Por lo tanto, el prototipo a rellenar será el siguiente:

package evaluador.Lexico;

public class MToken {

public final static int TK_ENTERO = 1; // numero entero

public final static int TK_REAL = 2; // numero real

public final static int TK_TIPO_ENTERO = 3; // declaración "entero"

public final static int TK_TIPO_REAL = 4; // declaración "real"

public final static int TK_IDENTIFICADOR = 5;

public final static int TK_PUNTO_Y_COMA = 6;

public final static int TK_ASIGNACION = 7;

public final static int TK_SUMA = 8;

public final static int TK_RESTA = 9;

public final static int TK_MULTIPLICACION = 10;

public final static int TK_DIVISION = 11;

public final static int TK_MODULO = 12;

public final static int TK_MENOS_UNARIO = 14;

public final static int TK_EXPONENCIACION = 15;

public final static int TK_FACTORIAL = 16;

public final static int TK_ABRE_PARENTESIS = 17;

public final static int TK_CIERRA_PARENTESIS= 18;

public final static int TK_FIN_DE_ENTRADA = 19;

public final static int TK_ERROR = 20;

public MToken (int tipo, Object valor, int linea, int posLinea) {

...

}

public int tipo() { ... }

public Object valor() { ... }

public int linea() { ... }

public int posLinea() { ... }

public boolean esOperador() { ... }

public int prioridad() { ... }

public String toString() { ... }

}

Respecto de cómo realizar la división en tokens, existen dos posibilidades:

  • Leer caracter a caracter. Según el caracter leido, en un switch se decide qué tipo de token se va a devolver. Hay dos detalles a tener en cuenta:

    • Algunos tokens quedan determinado por la letra que se lee (por ejemplo, el caracter '+' es el token TK_SUMA). Otros tokens requieren leer el caracter siguiente y se determinar si se necesita o no (por ejemplo, una sequencia de dígitos para formar un entero). El problema es que después de formar el token se ha leido un caracter de más. Hay que "devolverlo" o "desleerlo", cosa que no admiten ciertos lectores. Para resolverlo podemos hacer dos cosas:

      • Me implemento un mecanismo para devolver un caracter (almacenarlo para la siguiente vez que quiera leer).

      • Uso algún lector que me permita "devolver" un caracter ya leido, por ejemplo PushbackReader.

    • El fin de flujo se determina cuando el método read devuelve un -1. Esto ha de comprobarse antes de convertir el valor a un char, pues de otra forma, el -1 se convierte a una letra.

    • Usar el StringTokenizer. Para ello, necesitamos generar una String a partir de un Reader.

    • NOTA: Se desaconseja el uso de la clase StreamTokenizer, pues no es capaz de distinguir entre números reales y enteros. (Bueno, en realidad si se puede, pero hay que tener cuidado para reconocer los enteros...)

      Análisis sintáctico

      Según se leen tokens se implementan las reglas sintácticas definidas. Para ello, usaremos la siguiente declaración de tipos:

      abstract class NodoAS {

      abstract Object Eval() throws Exception;

      }

      class nodoFactorialAS extends NodoAS {

      NodoAS expr;

      }

      class NodoSumaAS extends NodoAS {

      NodoAS expr1, expr2;

      }

      ...

      // también vale

      class NodoOpBinarioAS extends NodoAS {

      NodoAS expr1, expr2;

      char operador;

      }

      ...

      Y la clase pública será:

      public class ArbolSintactico {

      public ArbolSintactico (Parser analizador) throws Exception {

      ...

      }

      // devuelve la expresión almacenada

      // con cuidado con los paréntesis

      // Los paréntesis son los mínimos necesarios

      public String toString() { ... }

      }

      El constructor lanza una excepción si hay un error sintáctico en la entrada (analizador) indicando la causa.

      Evaluador (con análisis semántico al vuelo)

      Se añaden a la clase ArbolSintactico los métodos para evaluar y realizar el análisis semántico.

      public class ArbolSintactico {

      // además de lo necesario para el análisis sintáctico,

      // añadimos las siguientes funciones

      // devuelve el resultado de evaluar la última expresión

      // puede ser una String si es una declaración, un Integer

      // si es un valor entero o un Double si es un valor real

      public Object Eval() throws Exception { ... }

      // devuelve true si al árbol no tiene errores semánticos

      // false en caso contrario

      public boolean chequeoSemantico() { ... }

      }

      Hay que tener en cuenta que la misma expresión puede evaluarse varias veces, mucho cuidado con los efectos laterales y las variables globales.

      Pruebas

      Para realizar pruebas, se recomienda tener un programa que monta el árbol sintáctico a partir de una cadena de caracteres y luego lo evalúa. Un posible esquema sería:

      import java.io.*;

      import evaluador.*;

      class test {

      public static void main(String args[]) {

      String expr= "3+4*5";

      try {

      System.out.println("Test: " + expr);

      StringReader sr= new StringReader(expr);

      Parser p= new Parser(fis);

      ArbolSintactico AS= new ArbolSintactico(p);

      System.out.println(AS.Eval());

      } catch (Exception e) {

      System.out.println("Falló la prueba " + expr);

      System.out.println("Razón " + e);

      }

      }

      }

      Se recomienda poner varias expresiones, hasta estar seguros de que funciona la práctica.

      ' PROGRAMA PARA EVALUAR UNA EXPRESION

      Dim igual, error_tipo, no_texto, abierto, cerrado As Integer

      Dim cadena, aux As String

      Dim vector(1 To 40) As String

      Private Sub Command1_Click()

      Command2.Visible = True

      Command1.Visible = False

      abierto = 0

      cerrado = 0

      error_tipo = 0

      igual = 0

      no_texto = 2

      ya1 = 0

      ya2 = 0

      ya3 = 0

      If (Text1.Text = Null) Then

      long_cad = 0

      no_texto = 1

      Else

      long_cad = Len(cadena)

      End If

      For i = 1 To long_cad

      vector(i) = Mid(cadena, i, 1)

      Next i

      ' I N I C I A E V A L U A C I O N

      ' calculando posición del signo igual

      For i = 1 To long_cad

      If vector(i) = "=" Then

      igual = i

      Exit For

      End If

      Next i

      ' error tipo 1

      If (vector(1) = "=") Then

      error_tipo = 1

      MsgBox "ERROR 1 Ausencia de identificador", vbExclamation, "Mensaje de error"

      End If

      ' error tipo 2

      For i = 2 To igual - 1

      If (vector(i) = ".") Then

      error_tipo = 2

      MsgBox "ERROR 2 No es correcto incluir un punto en el identificador", vbExclamation, "Mensaje de error"

      End If

      Next i

      ' error tipo 3

      For i = 0 To 9

      If (vector(1) = i) Then

      error_tipo = 3

      MsgBox "ERROR 3 No es correcto iniciar un identificador con un numero", vbExclamation, "Mensaje de error"

      Exit For

      End If

      Next i

      ' error tipo 4

      If (igual <> 0) Then

      If (vector(1) = "*" Or vector(1) = "/" Or vector(1) = "+" Or vector(1) = "-" Or vector(1) = "(" Or vector(1) = ")" Or vector(1) = ".") Then

      error_tipo = 4

      MsgBox "ERROR 4 No es correcto iniciar un identificador con un operador o un punto", vbExclamation, "Mensaje de error"

      End If

      End If

      ' error tipo 5

      If (vector(igual + 1) = "=") Then

      error_tipo = 5

      MsgBox "ERROR 5 No es correcto colocar más de un signo de igual consecutivo", vbExclamation, "Mensaje de error"

      End If

      ' error tipo 6

      If (igual <> 0) Then

      If (vector(igual + 1) = "*" Or vector(igual + 1) = "/" Or vector(igual + 1) = "+" Or vector(igual + 1) = ")") Then

      error_tipo = 6

      MsgBox "ERROR 6 No es correcto colocar un parentesis derecho o un operador diferente de -, despues del signo =.", vbExclamation, "Mensaje de error"

      End If

      End If

      ' error tipo 7

      If (no_texto = 2) Then

      For i = igual + 1 To long_cad

      If (vector(i) = "(") Then

      abierto = abierto + 1

      If (ya3 = 0) Then

      If (vector(i + 1) = ")") Then

      error_tipo = 7

      MsgBox "ERROR 7 Es incorrecto no colocar nada entre los parentesis ().", vbExclamation, "Mensaje de error"

      ya3 = 1

      End If

      End If

      If (ya1 = 0) Then

      If (vector(i + 1) = "*") Or vector(i + 1) = "/" Or vector(i + 1) = "+" Then

      error_tipo = 7

      MsgBox "ERROR 7.1 No es correcto colocar un operador diferente de -, despues de ""("", vbExclamation, ", "Mensaje de error"

      ya1 = 1

      End If

      End If

      End If

      If (vector(i) = ")") Then

      cerrado = cerrado + 1

      If (vector(i - 1) = "*" Or vector(i - 1) = "/" Or vector(i - 1) = "+" Or vector(i - 1) = "-") Then

      error_tipo = 7

      MsgBox "ERROR 7.2 No es correcto colocar un operador antes de "")"", vbExclamation", "Mensaje de error"

      End If

      If (ya2 = 0) Then

      If (cerrado > abierto) Then

      error_tipo = 7

      MsgBox "ERROR 7.3 No es correcto colocar un "")"" sin un ""("" previo.", vbExclamation, "Mensaje de error"

      ya2 = 1

      End If

      End If

      End If

      Next i

      If (abierto <> cerrado) Then

      error_tipo = 7

      MsgBox "ERROR 7.4 El número de parentesis que se abre es diferente a los cerrados.", vbExclamation, "Mensaje de error"

      End If

      End If

      ' error tipo 8

      For i = igual + 1 To long_cad

      If (vector(i) = "*" Or vector(i) = "/" Or vector(i) = "+" Or vector(i) = "-") Then

      If (vector(i + 1) = "*" Or vector(i + 1) = "/" Or vector(i + 1) = "+" Or vector(i + 1) = "-") Then

      error_tipo = 8

      MsgBox "ERROR 8 No es correcto colocar más de un operador consecutivo.", vbExclamation, "Mensaje de error"

      Exit For

      End If

      End If

      Next i

      ' error tipo 9

      If (igual <> 0) Then

      If (long_cad <> 0) Then

      If (vector(long_cad) = "*" Or vector(long_cad) = "/" Or vector(long_cad) = "+" Or vector(long_cad) = "-") Or vector(long_cad) = "=" Then

      error_tipo = 9

      MsgBox "ERROR 9 No es correcto colocar un operador al final de la expresion", vbExclamation, "Mensaje de error"

      End If

      End If

      End If

      ' error tipo 10

      If (no_texto = 2) Then

      If (igual = 0) Then

      error_tipo = 10

      MsgBox "ERROR 10 No se escribio una ecuacion. Ausencia de signo igual.", vbExclamation, "Mensaje de error"

      End If

      End If

      ' EN ESTA SECCION SE EVALUA SI EXISTE UNA CADENA Y SI ES CORRECTA

      ' DE SER CORRECTA, SE VISUALIZA LA SEGUNDA IMAGEN

      If (error_tipo = 0) Then

      If (no_texto = 2) Then

      Label3.Visible = True

      'image1.Visible = True

      End If

      End If

      End Sub

      Private Sub Command2_Click()

      Text1.Text = ""

      error_tipo = 0

      Command1.Visible = True

      Command2.Visible = False

      Label3.Visible = True

      'image1.Visible = True

      End Sub

      Private Sub text1_change()

      cadena = Text1.Text

      End Sub

      Private Sub Text1_keyPress(keyAscii As Integer)

      If (keyAscii = vbKeyReturn) Then

      Call Command1_Click

      End If

      If keyAscii = Asc(";") Or keyAscii = Asc(",") Or keyAscii = Asc(":") Or keyAscii > Asc("Z") Or keyAscii < Asc("(") Or keyAscii = Asc("_") Or keyAscii = Asc("<") Or keyAscii = Asc(">") Or keyAscii = Asc("?") Then

      keyAscii = 0

      Beep

      End If

      End Sub