domingo, 31 de mayo de 2015

El analizador sintáctico del lenguaje m2k2

Introducción

En este post vamos a seguir todos los pasos necesarios para diseñar e implementar un intérprete. Un intérprete es un programa que recibe como entrada un programa en un lenguaje determinado y que produce como salida el resultado de su ejecución. El lenguaje aceptado como entrada por el intérprete es el denominado m2k2, definido formalmente en el primer post.

El diseño del intérprete se estructura en cuatro partes claramente diferenciadas que a su vez configuran la estructura principal de este documento:

  • Análisis léxico
  • Análisis sintáctico
  • Análisis semántico
  • Generación de resultados

En este post se expone el diseño y la implementación del analizador sintáctico. En los siguientes post hablaremos de los analizadores semántico y de la generación de resultados.

Analisis sintáctico

El analizador léxico pone el interfaz getNextToken() a disposición del analizador sintáctico. El analizador sintáctico constituye el esqueleto principal del intérprete: recibe como entrada los tokens que le pasa el analizador léxico a través de su interfaz y comprueba si esa sucesión de tokens llega en el orden correcto, lo que indica que la sucesión de símbolos que representan dichos tokens puede ser generada por la gramática correspondiente al lenguaje analizado.

Especificación sintáctica del lenguaje de entrada

El proceso a seguir para diseñar una gramática que reconozca un lenguaje de programación no es inmediato. Menos aún cuando uno empieza en esto de los analizadores sintácticos. Se profundiza en este proceso. Para empezar, se hacen explícitas las reglas de precedencia y asociatividad de los operadores del lenguaje m2k2.

Operación Operador Aridad Asociatividad Precedencia
Cambio de signo - Unario 1
Identidad + Unario 1
Negación ! Unario 1
Operatorios (+) (-) (*) (/) (&) (|) Unario 1
Multiplicación * Binario Por la izquierda 2
División / Binario Por la izquierda 2
Modulo (o resto) % Binario Por la izquierda 2
Conjunción & Binario Por la izquierda 2
Igual que = Binario Por la izquierda 2
Distinto que != <> Binario Por la izquierda 2
Menor que < Binario Por la izquierda 2
Mayor que > Binario Por la izquierda 2
Menor o igual que <= Binario Por la izquierda 2
Suma + Binario Por la izquierda 3
Resta - Binario Por la izquierda 3
Disyunción | Binario Por la izquierda 3

De no existir estas reglas, una expresión aparentemente tan inofensiva como esta,

    1/2*3

se convertiría en una terrible pesadilla para el analizador sintáctico, al tratarse de una linea ambigua con una doble interpretación:

    (1/2)*3
    1/(2*3)

Siguiendo las reglas de precedencia y asociatividad que acabamos de exponer, la ambiguedad desaparece, y queda claro que la interpretación es esta:

(1/2)*3

ya que los operadores / y * tienen la misma prioridad pero son asociativos por la izquierda. Desaparece por tanto la ambigüedad. La gramática correspondiente al lenguaje m2k2 debe hacer explícitas las reglas anteriores. La siguiente gramática incontextual reconoce el lenguaje m2k2 y hace explícitas las reglas de precedencia y asociatividad antes presentadas.

<Linea> <DeclVar> tkEOL
<Linea> <Sentencia> tkEOL
 
<DeclVar> <Tipo> <ListaIds>
 
<Tipo> tkTipoEnter
<Tipo> tkTipoReal
 
<ListaIds> tkIdent tkComa <ListaIdent>
<ListaIds> tkIdent
 
<Sentencia> <Expresion> <Asignacion>
 
<Asignacion> tkAsign <Expresion>
<Asignacion> λ
 
<Expresion> <Expresion> tkMas <Termino>
<Expresion> <Expresion> tkMenos <Termino>
<Expresion> <Expresion> tkO <Termino>
<Expresion> <Termino>
 
<Termino> <Termino> tkMul <Factor>
<Termino> <Termino> tkDiv <Factor>
<Termino> <Termino> tkY <Factor>
<Termino> <Termino> tkPorCien <Factor>
<Termino> <Termino> tkCmp <Factor>
<Termino> <Factor>
 
<Factor> tkIdent
<Factor> tkNrEnter
<Factor> tkNrReal
<Factor> tkOpTorio tkAbrPar tkIdent tkComa <Rango> tkComa <Expresion> tkCiePar
<Factor> tkAbrPar <Expresion> tkCiePar
<Factor> tkMenos <Factor>
<Factor> tkMas <Factor>
<Factor> tkNo <Factor>
 
<Rango> <Expresion> tkPtoPto <Expresion>

Como se observa, la cadena vacia no pertenece al lenguaje generado por esta gramática.

Transformaciones sobre la gramática original

La gramática incontextual anterior es recursiva por la izquierda. Para eliminar esta recursividad se reescribe como una gramática con partes derechas regulares (GPDR).

<Linea> <DeclVar> tkEOL
<Linea> <Sentencia> tkEOL
 
<DeclVar> <Tipo> <ListaIds>
 
<Tipo> tkTipoEnter
<Tipo> tkTipoReal
 
<ListaIds> tkIdent ( tkComa tkIdent )*
 
<Sentencia> <Expresion> <Asignacion>
 
<Asignacion> tkAsign <Expresion>
<Asignacion> λ
 
<Expresion> <Termino> ( ( tkMas | tkMenos | tkO ) <Termino> )*
 
<Termino> <Factor> ( ( tkMul | tkDiv | tkY | tkPorCien | tkCmp ) <Factor> )*
 
<Factor> tkIdent
<Factor> tkNrEnter
<Factor> tkNrReal
<Factor> tkOpTorio tkAbrPar tkIdent tkComa <Rango> tkComa <Expresion> tkCiePar
<Factor> tkAbrPar <Expresion> tkCiePar
<Factor> (tkMenos | tkMas | tkNo ) <Factor>
 
<Rango> <Expresion> tkPtoPto <Expresion>

Sin ninguna modificación adicional, estas 18 reglas forman la gramática que implementa el analizador sintáctico. El lector con experiencia en esto de los analizadores sintácticos ya habrá notado que la gramática anterior no reconoce exactamente el lenguaje m2k2, puesto que la gramática permite que cualquier expresión pueda actuar como receptora de una asignación (recuerde que solo los identificadores pueden ser receptores en una asignación). Sin embargo, es muy sencillo resolver este pequeño problema en el nivel semántico con ayuda de la gramática atribuida. Veremos como resolvemos esto mas adelante.

Calculo de primeros y siguientes

Las clausuras son incómodas para calcular primeros y siguientes. Sin embargo, la GPDR se puede traducir a una gramática incontextual y calcular primeros y siguientes sobre la gramática incontextual. Para eliminar las clausuras de la GPDR y transformar la gramática en una gramática incontextual, se emplea la siguiente transformación:

<E> <T> (+T)*
Es equivalente a:
<E> <T> <C>
<E> + <T> <C> | λ

De esta forma, los primeros y los siguientes de (+T)* son los primeros y los siguientes de C. Aplicando esta transformación sobre la GPDR presentada antes como solución, se obtiene esta gramática:

<Linea> <DeclVar> tkEOL
<Linea> <Sentencia> tkEOL
 
<DeclVar> <Tipo> <ListaIds>
 
<Tipo> tkTipoEnter
<Tipo> tkTipoReal
 
<ListaIds> tkIdent <C1>
<C1> tkComa tkIdent <C1>
<C1> λ
 
<Sentencia> <Expresion> <Asignacion>
 
<Asignacion> tkAsign <Expresion>
<Asignacion> λ
 
<Expresion> <Termino> <C2>
<C2> ( tkMas | tkMenos | tkO ) <Termino> <C2>
<C2> λ
 
<Termino> <Factor> <C3>
<C3> ( tkMul | tkDiv | tkY | tkPorCien | tkCmp ) <Factor> <C3>
<C3> λ
 
<Factor> tkIdent
<Factor> tkNrEnter
<Factor> tkNrReal
<Factor> tkOpTorio tkAbrPar tkIdent tkComa <Rango> tkComa <Expresion> tkCiePar
<Factor> tkAbrPar <Expresion> tkCiePar
<Factor> (tkMenos | tkMas | tkNo ) <Factor>
 
<Rango> <Expresion> tkPtoPto <Expresion>

En la siguiente tabla aparecen los primeros y siguientes de la gramática incontextual anterior. El lector no debe perder de vista que los no terminales <C1>, <C2> y <C3> se corresponden con las tres clausuras de la gramática GPDR presentada como solución.

Anulable Primeros Siguientes
<Linea> No tkTpoEnter, tkTpoReal, tkIdent, tkNrEnter,
tkNrReal, tkOpTorio, tkAbrPar, tkMas,
tkMenos, tkNo
tkEOL
<DeclVar> No tkTpoEnter, tkTpoReal tkEOL
<Tipo> No tkTpoEnter, tkTpoReal tkIdent
<ListaIds> No tkIdent tkEOL
<C1> Si tkComa tkEOL
<Sentencia> No tkIdent, tkNrEnter, tkNrReal, tkOpTorio,
tkAbrPar, tkMas, tkMenos, tkNo
tkEOL
<Asignacion> Si tkAsign tkEOL
<Expresion> No tkIdent, tkNrEnter, tkNrReal, tkOpTorio,
tkAbrPar, tkMas, tkMenos, tkNo
tkAsign, tkEOL, tkCiePar, tkPtoPto, tkComa
<C2> Si tkMas, tkMenos, tkO tkAsign, tkEOL, tkCiePar, tkPtoPto, tkComa
<Termino> No tkIdent, tkNrEnter, tkNrReal, tkOpTorio,
tkAbrPar, tkMas, tkMenos, tkNo
tkMas, tkMenos, tkO, tkAsign, tkEOL, tkCiePar, tkPtoPto, tkComa
<C3> Si tkMul, tkDiv, tkY, tkPorCien, tkCmp tkMas, tkMenos, tkO, tkAsign, tkEOL, tkCiePar, tkPtoPto, tkComa
<Factor> No tkIdent, tkNrEnter, tkNrReal, tkOpTorio,
tkAbrPar, tkMenos, tkMas, tkNo
tkMul, tkDiv, tkY, tkPorCien, tkCmp, tkMas,
tkMenos, tkO, tkAsign, tkEOL, tkCiePar,
tkPtoPto, tkComa
<Rango> No tkIdent, tkNrEnter, tkNrReal,
tkAbrPar, tkMenos, tkMas, tkNo tkOpTorio,
tkComa

Tabla de análisis predictivo

Estamos en condiciones de rellenar la tabla de análisis predictivo para la gramática GDPR propuesta. La tabla de análisis predictivo es enorme, por lo que, por falta de espacio, se va a partir en varias tablas para que quepa toda entera.

<Linea>
tkAbrPar <Sentencia>tkEOL
tkAsign error
tkCiePar error
tkCmp error
tkComa error
tkDiv error
tkEOL error
tkIdent <Sentencia>tkEOL
tkMas <Sentencia>tkEOL
tkMenos <Sentencia>tkEOL
tkMul error
tkNo <Sentencia>tkEOL
tkNrEnter <Sentencia>tkEOL
tkNrReal <Sentencia>tkEOL
tkO error
tkOpTorio <Sentencia>tkEOL
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter <DeclVar>tkEOL
tkTpoReal <DeclVar>tkEOL
tkY error

<DeclVal>
tkAbrPar error
tkAsign error
tkCiePar error
tkCmp error
tkComa error
tkDiv error
tkEOL error
tkIdent error
tkMas error
tkMenos error
tkMul error
tkNo error
tkNrEnter error
tkNrReal error
tkO error
tkOpTorio error
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter <Tipo><ListaIds>
tkTpoReal <Tipo><ListaIds>
tkY error

<Tipo>
tkAbrPar error
tkAsign error
tkCiePar error
tkCmp error
tkComa error
tkDiv error
tkEOL error
tkIdent error
tkMas error
tkMenos error
tkMul error
tkNo error
tkNrEnter error
tkNrReal error
tkO error
tkOpTorio error
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter tkTpoEnter
tkTpoReal tkTpoReal
tkY error

<ListaIds>
tkAbrPar error
tkAsign error
tkCiePar error
tkCmp error
tkComa error
tkDiv error
tkEOL error
tkIdent tkIdent ( tkComa tkIdent )*
tkMas error
tkMenos error
tkMul error
tkNo error
tkNrEnter error
tkNrReal error
tkO error
tkOpTorio error
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter error
tkTpoReal error
tkY error

<Sentencia>
tkAbrPar <Expresion><Asignacion>
tkAsign error
tkCiePar error
tkCmp error
tkComa error
tkDiv error
tkEOL error
tkIdent <Expresion><Asignacion>
tkMas <Expresion><Asignacion>
tkMenos <Expresion><Asignacion>
tkMul error
tkNo <Expresion><Asignacion>
tkNrEnter <Expresion><Asignacion>
tkNrReal <Expresion><Asignacion>
tkO error
tkOpTorio <Expresion><Asignacion>
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter error
tkTpoReal error
tkY error

<Asignacion>
tkAbrPar error
tkAsign tkAsign<Expresion>
tkCiePar error
tkCmp error
tkComa error
tkDiv error
tkEOL λ
tkIdent error
tkMas error
tkMenos error
tkMul error
tkNo error
tkNrEnter error
tkNrReal error
tkO error
tkOpTorio error
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter error
tkTpoReal error
tkY error

<Expresion>
tkAbrPar <Termino>((tkMas|tkMenos|tkO)<Termino>)*
tkAsign error
tkCiePar error
tkCmp error
tkComa error
tkDiv error
tkEOL error
tkIdent <Termino>((tkMas|tkMenos|tkO)<Termino>)*
tkMas <Termino>((tkMas|tkMenos|tkO)<Termino>)*
tkMenos <Termino>((tkMas|tkMenos|tkO)<Termino>)*
tkMul error
tkNo <Termino>((tkMas|tkMenos|tkO)<Termino>)*
tkNrEnter <Termino>((tkMas|tkMenos|tkO)<Termino>)*
tkNrReal <Termino>((tkMas|tkMenos|tkO)<Termino>)*
tkO error
tkOpTorio <Termino>((tkMas|tkMenos|tkO)<Termino>)*
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter error
tkTpoReal error
tkY error

<Termino>
tkAbrPar <Factor>((tkMul|tkDiv|tkY| tkPorCien|tkCmp)<Factor>)*
tkAsign error
tkCiePar error
tkCmp error
tkComa error
tkDiv error
tkEOL error
tkIdent <Factor>((tkMul|tkDiv|tkY| tkPorCien|tkCmp)<Factor>)*
tkMas <Factor>((tkMul|tkDiv|tkY| tkPorCien|tkCmp)<Factor>)*
tkMenos <Factor>((tkMul|tkDiv|tkY| tkPorCien|tkCmp)<Factor>)*
tkMul error
tkNo <Factor>((tkMul|tkDiv|tkY| tkPorCien|tkCmp)<Factor>)*
tkNrEnter <Factor>((tkMul|tkDiv|tkY| tkPorCien|tkCmp)<Factor>)*
tkNrReal <Factor>((tkMul|tkDiv|tkY| tkPorCien|tkCmp)<Factor>)*
tkO error
tkOpTorio <Factor>((tkMul|tkDiv|tkY| tkPorCien|tkCmp)<Factor>)*
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter error
tkTpoReal error
tkY error

<Factor>
tkAbrPar tkAbrPar <Expresion> tkCiePar
tkAsign error
tkCiePar error
tkCmp error
tkComa error
tkDiv error
tkEOL error
tkIdent tkIdent
tkMas (tkMenos|tkMas|tkNo)<Factor>
tkMenos (tkMenos|tkMas|tkNo)<Factor>
tkMul error
tkNo (tkMenos|tkMas|tkNo)<Factor>
tkNrEnter tkNrEnter
tkNrReal tkNrReal
tkO error
tkOpTorio tkOpTorio tkAbrPar tkIdent tkComa <Rango> tkComa <Expresion> tkCiePar
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter error
tkTpoReal error
tkY error

<Rango>
tkAbrPar <Expresion> tkPtoPto <Expresion>
tkAsign error
tkCiePar error
tkCmp error
tkComa error
tkDiv error
tkEOL error
tkIdent <Expresion> tkPtoPto <Expresion>
tkMas <Expresion> tkPtoPto <Expresion>
tkMenos <Expresion> tkPtoPto <Expresion>
tkMul error
tkNo <Expresion> tkPtoPto <Expresion>
tkNrEnter <Expresion> tkPtoPto <Expresion>
tkNrReal <Expresion> tkPtoPto <Expresion>
tkO error
tkOpTorio <Expresion> tkPtoPto <Expresion>
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter error
tkTpoReal error
tkY error

(tkComa tkIdent)*
tkAbrPar error
tkAsign error
tkCiePar error
tkCmp error
tkComa tkComa tkIdent (tkComa tkIdent)*
tkDiv error
tkEOL λ
tkIdent error
tkMas error
tkMenos error
tkMul error
tkNo error
tkNrEnter error
tkNrReal error
tkO error
tkOpTorio error
tkPorCien error
tkPtoPto error
tkSpc error
tkTpoEnter error
tkTpoReal error
tkY error

((tkMas|tkMenos|tkO)<Termino>)*
tkAbrPar error
tkAsign λ
tkCiePar λ
tkCmp error
tkComa λ
tkDiv error
tkEOL λ
tkIdent error
tkMas ((tkMas|tkMenos|tkO)<Termino>)((tkMas|tkMenos|tkO)<Termino>)*
tkMenos ((tkMas|tkMenos|tkO)<Termino>)((tkMas|tkMenos|tkO)<Termino>)*
tkMul error
tkNo error
tkNrEnter error
tkNrReal error
tkO ((tkMas|tkMenos|tkO)<Termino>)((tkMas|tkMenos|tkO)<Termino>)*
tkOpTorio error
tkPorCien error
tkPtoPto λ
tkSpc error
tkTpoEnter error
tkTpoReal error
tkY error

((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)*
tkAbrPar error
tkAsign λ
tkCiePar λ
tkCmp ((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)*
tkComa λ
tkDiv ((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)*
tkEOL λ
tkIdent error
tkMas λ
tkMenos λ
tkMul ((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)*
tkNo error
tkNrEnter error
tkNrReal error
tkO λ
tkOpTorio error
tkPorCien ((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)*
tkPtoPto λ
tkSpc error
tkTpoEnter error
tkTpoReal error
tkY ((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)((tkMul|tkDiv|tkY|tkPorCien|tkCmp)<Factor>)*

En la tabla anterior no hay ninguna celda con mas de una opción posible, por lo que podemos afirmar que la gramática es RLL(1), y por tanto sobre ella podremos aplicar el algoritmo de análisis.

Errores sintácticos

Para gestionar los errores sintácticos, se implementa la clase SynError en el módulo sintactico.py.

    class SynError:
        def __init__( LA, token, message )
        def __str__( )

El constructor de esta clase recibe como parámetros el analizador léxico construido para la línea analizada (LA), el token en el que se produce el error (token), y un mensaje informativo del error (message). El método __str__ se encarga de combinar los parámetros anteriores para construir el mensaje de error que se imprime por el stderr al imprimir un objeto de esta clase. Para ello extrae del parámetro LA el nombre del fichero de entrada, la línea analizada y el número de la línea analizada dentro del fichero de entrada. Del parámetro token se extrae su categoría léxica y el puntero al primer carácter del token dentro de la línea analizada.

El analizador sintáctico detecta un error cuando recibe del analizador léxico un token que no concuerda con ninguna cadena del lenguaje generado por la gramática del analizador sintáctico. Son típicos los errores por paréntesis omitidos o por omisión de operandos u operadores. En cualquier caso, el analizador sintáctico lanza una excepción SynError junto con el mensaje de error que construye la clase SynError.

    raise SynError, SynError( LA, a, message )

La excepción es capturada en el programa principal, donde el mensaje de error es mostrado por el stderr. Sirvan las dos situaciones siguientes a modo de ejemplo:

    >>> x*(1+y
    File “”, line 13
    x*(1+y
          ^
    Syntax Error: tkEOL unexpected; expected tkCiePar
    >>> x(1+y)
    File “”, line 17
    x(1+y)
     ^
    Syntax Error: tkAbrPar unexpected; expected tkMas, tkMenos, tkO, tkAsign, tkEOL, tkCiePar, tkPtoPto or tkComa

Como se observa, el mensaje de error contiene el nombre del fichero de entrada, la línea donde se ha detectado el error, el número de dicha línea dentro del fichero de entrada, un puntero '^' señalando el primer carácter del token dentro de la línea analizada y un mensaje indicando el error cometido. Una vez se atiende el error sintáctico y se muestra por el stderr el mensaje informativo del error, se omite todo el procesamiento posterior sobre la línea actual y se continua atendiendo la siguiente línea del stdin.

Implementación del analizador sintáctico

En la implementación del analizador sintáctico se utiliza la clase SynAnalyser incluida en el módulo sintactico.py.

    SynAnalyser:
        def __init__( LexAnalyser )
        def parse_Linea( )
        def parse_DeclVar( )
        def parse_Tipo( )
        def parse_ListaIds( )
        def parse_Sentencia( )
        def parse_Asignacion( )
        def parse_Expresion( )
        def parse_Termino( )
        def parse_Factor( )
        def parse_Rango( )

La idea básica llevada a cabo para implementar el analizador sintáctico es tener un método por cada uno de los no terminales de la gramática GDPR. El resultado de la llamada a cada uno de los métodos es cierto si se ha encontrado en la entrada una secuencia de tokens que se pueda derivar a partir de ese no terminal y falso en caso contrario. El análisis comienza con una llamada al método parse_Linea: si devuelve cierto, se ha llegado al final de la entrada con éxito. En caso contrario, se ha detectado un error sintáctico

La clase SynAnalyser utiliza el atributo a para guardar el token analizado en cada momento y el atributo LA para guardar el analizador léxico construido para la línea actual. El constructor de esta clase comienza haciendo una llamada al interfaz del analizador léxico,

    self.a = self.LA.getNextToken()

En lo que resta de esta sección se exponen los esquemas usados para implementar el analizador sintáctico. Se utiliza la abreviatura aceptables(α) para hacer referencia al conjunto primeros(α) si α no es anulable, o bien primeros(α) ∪ siguientes(α) si α es anulable.

Si un símbolo no terminal <Termino> tiene las reglas:

<Termino> α1
<Termino> α2
<Termino> α3

entonces la estructura del método parse_Termino es:

    def parse_Termino(self):
        if   self.a.cat in aceptables(α1): # acciones de α1
        elif self.a.cat in aceptables(α2): # acciones de α2
        ...
        elif self.a.cat in aceptables(αn): # acciones de αn
        else raise SynError, SynError(self.LA, self.a, "expected <Termino>")
        return(1)

Las acciones de las partes derechas dependen de la forma que tienen esas partes derechas. Las opciones posibles son varias. Todas ellas se detallan a continuación.

  • 1. Si α = λ, la acción asociada es la acción nula (pass en Python)
  • 2. Si α es un símbolo no terminal (como por ejemplo <Termino>), hay que llamar al método de parsing correspondiente.
        if self.parse_Termino( ) == 0:
            raise SynError, SynError(self.LA, self.a, "expected <Termino>")
    
  • 3. Si α es un terminal (como por ejemplo tkIdent), hay que comprobar que es el token actual. Si lo es, se debe llamar al interfaz getNextToken para que proporcione el siguiente token de la entrada. Si no lo es, se ha encontrado un error.
        if self.a.cat in [“tkIdent”]:
            self.a = self.LA.getNextToken()
        else:
            raise SynError, SynError(self.LA, self.a, "expected tkIdent")
    
  • 4. Si α = (β)*, hay que entrar en un bucle y mantenerse en el mientras se este en uno de los primeros de β. Al salir del bucle hay que comprobar que se ha encontrado uno de los siguientes de β.
        # <ListaIds> -> tkIdent (tkComa tkIdent)*
        ...
        while self.a.cat in ["tkComa"]:
            self.a = self.LA.getNextToken()
            if self.a.cat not in ["tkIdent"]:
                raise SynError, SynError(self.LA, self.a, "expected tkIdent" )
            self.a = self.LA.getNextToken()
        # si a no pertenece a siguientes de p*
        if self.a.cat not in ["tkEOL"]:
            raise SynError, SynError(self.LA, self.a, "expected tkEOL")
    
  • 5. Si α=β1β2...βn, hay que aplicar secuencialmente las reglas anteriores según sea el caso:
        # ... tkComa  tkComa ...
        ...
        if self.a.cat not in ["tkComa"]:
            raise SynError, SynError(self.LA, self.a, "expected tkComa")
        self.a = self.LA.getNextToken()
        if self.parse_Rango(Rango) == 0:
            raise SynError, SynError(self.LA, self.a, "expected <Rango>")
        if self.a.cat not in ["tkComa"]:
            raise SynError, SynError(self.LA, self.a, "expected tkComa")
        ...
    

Todo esto es lo necesario para implementar el analizador sintáctico. Los fragmentos de código anteriores han sido directamente extraídos del código fuente del analizador sintáctico, aunque parece razonable no detallar aquí todos los métodos de parsing del analizador sintáctico, ya que al finalizar esta serie de articulos, el lector tendrá a su disposición el código fuente para profundizar en los detalles de la implementación que considere necesarios para su total comprensión.

Continuar leyendo el analizador semántico

domingo, 17 de mayo de 2015

El analizador léxico del lenguaje m2k2

Introducción

En este post vamos a seguir todos los pasos necesarios para diseñar e implementar un intérprete. Un intérprete es un programa que recibe como entrada un programa en un lenguaje determinado y que produce como salida el resultado de su ejecución. El lenguaje aceptado como entrada por el intérprete es el denominado m2k2, definido formalmente en el primer post.

El intérprete de m2k2 se implementará íntegramente con el lenguaje de programación Python. Python es un lenguaje de programación fácil de aprender y potente. Tiene eficaces estructuras de datos de alto nivel (listas, tuplas, cadenas y diccionarios) y una solución de programación orientada a objetos simple pero eficaz. La elegante sintaxis de Python, su gestión de tipos dinámica y su naturaleza interpretada hacen de él el lenguaje ideal para la implementación del intérprete para el lenguaje micro2k2 especificado en el post anterior.

Cuando se leen ordenes desde una tty, se dice que el intérprete está en modo interactivo. El intérprete de m2k2 se presenta al usuario de forma interactiva como una orden directamente ejecutable desde el intérprete de comandos de cualquier sistema Unix/Linux.

    $ m2k2

En este modo, el intérprete espera la siguiente orden con el indicador principal, que suele ser tres signos mayor ('>>>'). El intérprete muestra un mensaje de bienvenida con su número de versión, antes de mostrar el primer indicador, algo similar a esto:

    m2k2 1.4.2 (Mar 5 2002, 15:17:54) on devnull
    Wittylabs, 2015. Castellón, Spain
    >>>

El intérprete de m2k2 no solo puede utilizarse de forma interativa. A su entrada también puede redireccionarse un fichero, o incluso la salida de otro programa, como se muestra en estos ejemplos:

    $ cat programa.2k2 | m2k2
    $ m2k2 < programa.2k2

Entrando ya en materia, el diseño del intérprete se estructura en cuatro partes claramente diferenciadas que a su vez configuran la estructura principal de este documento:

  • Análisis léxico
  • Análisis sintáctico
  • Análisis semántico
  • Generación de resultados

En este post se expone el diseño y la implementación del analizador léxico. En los siguientes post hablaremos de los analizadores sintáctico, semántico y de la generación de resultados.

Analisis léxico

Al iniciarse el proceso de interpretación, el código fuente de un programa no es mas que un flujo de caracteres. El analizador léxico lee caracteres del programa de entrada y produce secuencias de simbolos elementales del lenguaje de programación de entrada, conocidos como tokens. Los tokens son posteriormente analizados sintácticamente por el analizador sintáctico. Por consiguiente, el proceso de analisis léxico puede entenderse como la transformación de un flujo de caracteres de entrada en un flujo de tokens de salida. La entrada es filtrada para eliminar aquellos elementos del programa de entrada que son superfluos para realizar el analisis sintáctico. En concreto se eliminan espacios y tabuladores.

Especificación léxica del lenguaje de entrada

La especificación del analizador léxico incluye por cada categoría léxica del lenguaje, su patron, sus atributos y las acciones asociadas. El formalismo de las expresiones regulares tiene la capacidad suficiente para especificar el patron de las categorías léxicas.

Categoría Expresión regular Acciones Atributos
Ident [a-zA-Z][a-zA-Z0-9_]* Copiar lexema
Comprobar reservada
emitir (( tkIdent, | tkTpoEnter | tkTpoReal)
caracter1
lexema
TpoReal [rR][eE][aA][lL] caracter1
TpoEnter [eE][nN][tT][eE][rR] caracter1
NrEnter [0-9][0-9]* | #[0-9a-fA-F][0-9a-fA-F]* Calcular valor
Comprobar rango
emitir tkNrEnter
caracter1
valor
NrReal [0-9][0-9]*\.[0-9][0-9]* | [0-9][0-9]*\.[0-9][0-9]*[eE][+-]?[0-9][0-9]* Calcular valor
Comprobar rango
emitir tkNrReal
caracter1
valor
AbrPar \( emitir tkAbrPar caracter1
CiePar \) emitir tkCiePar caracter1
PtoPto \.\. emitir tkPtoPto caracter1
Space [ \t][ \t]* omitir caracter1
Coma , emitir tkComa caracter1
EOL \n emitir tkEOL caracter1
Asign <\- emitir tkAsign carácter1
Mas \+ emitir tkMas carácter1
Menos \- emitir tkMenos carácter1
Mul \* emitir tkMul carácter1
Div / emitir tkDiv carácter1
PorCien % emitir tkPorCien carácter1
Y & emitir tkY carácter1
O \| emitir tkO carácter1
No ! emitir tkNo carácter1
Cmp =|!=|<>|<|>|<=|>= copiar lexema
emitir tkCmp
carácter1
lexema
OpTorio \([\+ \- \* / % & \| ]\) copiar lexema
emitir tkOpTorio
carácter1
lexema

Para diferenciar los identificadores de las palabras reservadas enter y real (con todas sus variantes en mayúsculas y en minúsculas), las acciones de la categoría léxica Ident comprueban si el lexema del identificador es una palabra reservada o no lo es. En caso de ser una palabra reservada, se emite el tkTpo adecuado. En caso de no serlo, se emite un tkIdent.

El salto de línea cumple en m2k2 la función de terminador, por lo que no se incluye en la categoría léxica Spc (los blancos). Se le asigna la categoría léxica EOL.

Los operadores de comparación se agrupan en la categoría léxica Cmp. Esto se hace así porque todos los operadores de comparación tienen el mismo nivel de precedencia y la misma aridad (número de argumentos). Por la misma razón, los operadores de operatorio se agrupan en la categoría léxica OpTorio.

Los operadores aritméticos no se agrupan en una sola categoría léxica porque los operadores + y - tienen dos aridades posibles (unaria o binaria), mientras que los operadores * / y % solo tienen una única aridad posible (binaria). En caso de agrupar los cinco operadores en una sola categoría léxica, es imposible diferenciar en el nivel sintáctico los operadores binarios de los operadores unarios. En este supuesto, el analizador sintáctico parsea como correctos los operadores * / y % cuando actúan como operadores unarios. Para evitar este problema, lo mejor es tener categorías léxicas distintas para los operadores aritméticos, y así poder diferenciar en las reglas de la gramática del analizador sintáctico los operadores unarios de los operadores binarios.

Nótese que los operadores aritméticos * / y % si se pueden agrupar en una sola categoría léxica, ya que los tres son operadores binarios. Sin embargo, la categoría léxica resultante de agrupar estos tres operadores aritméticos es poco representativa a nivel conceptual. Por ello finalmente se opta por crear una categoría léxica distinta para cada operador aritmético.

Con los operadores lógicos ocurre algo parecido a los operadores aritméticos. El operador ! es unario, mientras que los operadores & y | son binarios. Por ello no se agrupan los operadores lógicos en una sola categoría léxica. Los operadores & y | si puede agruparse en una sola categoría léxica, ya que los dos son operadores binarios. Sin embargo, la categoría léxica resultante de agrupar estos dos operadores lógicos es poco representativa a nivel conceptual. Por ello finalmente se opta por crear una categoría léxica distinta para cada operador lógico.

Diagrama de la máquina discriminadora determinista

Para dividir la entrada en una serie de tokens se utiliza una maquina discriminadora determinista o MDD en adelante. Se trata de un tipo de automata muy similar a los automatas finitos deterministas, con dos diferencias básicas. Por un lado no reconoce la entrada completa, sino prefijos de la entrada. Por otro lado tiene acciones asociadas a cada uno de los estados finales. El diagrama de la MDD se muestra en la siguiente imagen. En las siguientes secciones veremos los detalles del funcionamiento y de la implementación de esta MDD.

Errores léxicos

Para gestionar los errores léxicos, se implementa la clase LexError en el módulo lexico.py.

    class LexError:
      def __init__( fis, sentence, sentenceNr, chr1, message )
      def __str__( )

El constructor de esta clase recibe como parámetros el nombre del fichero de entrada (fis, file input stream), la línea actual (sentence), el número de la línea actual (sentenceNr), el puntero al carácter de la línea actual que ha provocado el error léxico (chr1) y finalmente un mensaje informativo del error (message). El método __str__ se encarga de combinar los parámetros anteriores para construir el mensaje de error que se imprime por el stderr al imprimir un objeto de esta clase.

El analizador léxico detecta un error cuando lee de la entrada algun carácter que no pertenece al alfabeto del lenguaje (ñ $ ;) o cuando lee una secuencia de caracteres pertenecientes al alfabeto del lenguaje con los cuales no se puede formar ningún token válido en el orden en el que aparecen. En cualquier caso, el analizador léxico lanza una excepción LexError junto con un mensaje de error construido por la clase LexError

    raise LexError, LexError( fis, s, sNr, cPtr, message )

La excepción es capturada en el programa principal, donde el mensaje de error es mostrado por el stderr. Sirvan las dos situaciones siguientes a modo de ejemplo:

    >>> i + 1;
    File “”, line 34
    i + 1;
    ^
    Lexic Error: invalid syntax
    >>> enter _i
    File “”, line 57
    enter _i
    ^
    Lexic Error: invalid syntax

Como se observa, el mensaje de error contiene el nombre del fichero donde se ha detectado el error, la línea donde se ha detectado el error, el número de línea dentro del fichero de entrada, un puntero '^' señalando el carácter inesperado, y un mensaje indicando el error cometido. Después de atender el error léxico y mostrar por el stderr el mensaje informativo del error, se omite todo el procesamiento posterior sobre la línea actual y se continua atendiendo la siguiente línea del stdin.

Un error que también se podría detectar a nivel léxico es el de los desbordamientos de rango, ya que en principio es posible escribir una expresión regular para (por ejemplo) los enteros. En la práctica no es una solución aceptable: la expresión regular resulta demasiado complicada e incluso puede ser dependiente de la arquitectura sobre la que se ejecute el intérprete. La solución adoptada para tratar con este tipo de errores consiste en capturar la excepción ValueError en el programa principal. Trataremos esto mas adelante en una sección dedicada al tratamiento de los errores de ejecución.

Implementación del analizador léxico

En la implementación del analizador léxico se utiliza la clase LexAnalyser y la clase Token. Ambas estan implementadas en el módulo lexico.py.

    class LexAnalyser:
      def __init__( fis, sentence, sentenceNr )
      def getCurrentChar( )
      def pointNextChar( )
      def pointPreviousChar( )
      def getNextToken( )

    class Token:
      def __init__( cat, lex, chr1 )

El analizador léxico debe dividir la entrada en una serie de tokens. Para este fin se utiliza la MDD que hemos introducido antes. La implementación de la MDD se puede hacer mediante tablas o mediante control de flujo. Se opta por la implementación mediante tablas. Para implementar la MDD con tablas, son necesarias las cuatro tablas siguientes, implementadas en el módulo léxico.py como diccionarios globales al módulo:

    movement [ (state, char) ]
    final[ state ]
    action[ state ]
    category[ state ]

La tabla "movement" contiene, por cada estado y cada posible carácter de la entrada, el estado siguiente de la maquina determinista al que se transita. Es una tabla realmente grande, pero al estar implementada con diccionarios proporciona un acceso rapidísimo. La tabla "final" indica, por cada estado de la MDD, si es final o no. La tabla "action" contiene, por cada estado de la MDD, la acción asociada (emitir u omitir). Por último, se usa la tabla "category" para conocer la categoría léxica asociada a cada estado final de la MDD.

La MDD se implementa en la clase LexAnalyser con ayuda de los métodos getNextToken(), getCurrentChar(), pointNextChar() y pointPreviousChar(). El método getNextToken() parte del estado inicial y del primer carácter a analizar y actúa repetidamente sobre la cadena de entrada, empezando en cada caso en un punto distinto de la misma pero siempre desde su estado inicial. El método getNextToken() utiliza pointNextChar() para transitar entre estados avanzando sobre la cadena de caracteres mientras el carácter obtenido con getCurrentChar tenga algún movimiento posible en la tabla movement. A medida que getNextToken() avanza, va tomando nota del último estado final por el que ha pasado. Cuando no puede avanzar, detiene el avance.

Si ha pasado por algún estado final, pointPreviousChar() devuelve los caracteres sobrantes a la entrada y getNextToken() ejecuta las acciones asociadas al último estado final por el que ha transitado. Si la acción asociada al último estado final es emitir, la clase Token construye el token adecuado en función de los parámetros enviados a su constructor, y getNextToken() envía ese token recién construido al analizador sintáctico. El método getNextToken() actúa por tanto de interfaz entre el analizador léxico y el analizador sintáctico, permitiendo a éste último obtener el token actual de la entrada. Si la acción asociada al último estado final es omitir, se continua analizando la cadena en busca del siguiente token.

Si no ha pasado por ningún estado final, getNextToken() ha detectado un error léxico. En ese caso lanza una excepción LexError y el programa principal la captura y la muestra por stderr.

Continuar leyendo el analizador sintáctico

sábado, 16 de mayo de 2015

Especificación formal del lenguaje m2k2

Introducción

En este post vamos a seguir todos los pasos necesarios para diseñar e implementar un intérprete. Un intérprete es un programa que recibe como entrada un programa en un lenguaje determinado y que produce como salida el resultado de su ejecución. El lenguaje aceptado como entrada por el intérprete que vamos a implementar se denomina m2k2. En este primer post vamos a describir la especificación formal del lenguaje.

Tipos de datos

Las variables que pueden definirse en m2k2 siempre llevan definido un tipo. Los tipos que pueden definirse son dos: el entero y el real. El lenguaje no asume convenios ni rangos de representación concretos, que dependerán de la arquitectura sobre la que se ejecute el interprete. En cuanto a los valores logicos, m2k2 no dispone de un tipo lógico explicito, sino que utiliza variables de tipo entero para representarlos: el cero se asocia al valor falso, y otros enteros, no nulos, se consideran asociados al cierto. El lenguaje no acepta cadenas de caracteres ni vectores.

Nivel léxico

Los programas en m2k15 utilizan el juego de caracteres ASCII de 7 bits. A la hora de identificar los diferentes componentes léxicos de un programa m2k15 se sigue siempre una "estrategia avariciosa": procedimiento de izquierda a derecha, el siguiente componente será de la porción de programa pendiente de analizar, el prefijo mas largo que pertenezca al conjunto de componentes léxicos básicos del lenguaje.

Blancos

Los componentes lexicos pueden separarse por cualquier secuencia de espacios en blanco, tabuladores, y saltos de linea. El salto de linea cumple en m2k2 la función de terminador. El lenguaje no admite comentarios.

Identificadores

Los identificadores serán secuencias de caracteres donde pueden intervenir letras, digitos y el caracter subrayado, y que comienzan siempre por letra. Los identificadores harán referencia a las variables. Las letras mayusculas y minusculas no son equivalentes: así por ejemplo "abc", "AbC" y "ABC" hacen referencia a 3 variables diferentes.

Literales

A continuación se presentan los literales que dentro de un programa m2k2 permite especificar valores constantes.

Literales enteros

Los literales enteros pueden ser en notación decimal o en notación hexadecimal. En notación decimal se utilizan secuencias de digitos en base 10 (por ejemplo 123). En notación hexadecimal se emplea el caracter '#' para cambiar a base hexadecimal (por ejemplo #12ac).

Literales reales

Los literales reales han de expresarse en notación cientifica, en formato: entero.decimal[eE][+-]digitos. Observa que aunque la parte "entero.decimal" es obligatoria (y va separada por un punto), la parte del exponente es opcional. La letra 'e' puede ser indistintamente mayuscula o minuscula. Por ejemplo, 2.37, 0.1e-1 o 100.0e+10 son ejemplos validos de literales reales.

Operadores

El lenguaje dispone del siguiente conjunto de operadores:

    + - * / % & | ! = != <> < > <= >=
Ademas algunos de ellos pueden intervenir como parte de unos componentes léxicos mas complejos llamados operatorios, donde aparecen entre parentesis:
    (+) (-) (*) (/) (%) (&) (|)

Palabras clave

Las palabras clave que define el lenguaje son:

    ENTER REAL

Las palabras clave pueden escribirse en mayusculas y en minusculas, indistintamente, o utilizando cualquier combinación de ambas. Son palabras reservadas que por tanto no pueden utilizarse como identificadores.

Otros componentes léxicos

El nucleo básico del lenguaje también admite los siguientes componentes léxicos:

    (   )   <-   ,   ..   :

Expresiones

Las expresiones mas simples validas en el nucleo básico del lenguaje son los literales y las variables de los tipos numéricos elementales. También son validas aquellas expresiones que pueden construirse a partir de otras utilizando operadores. El lenguaje posee operadores aritmeticos, de comparación y lógicos. Ademas, también posee una construcción especial para expresar la aplicación reiterada de un mismo operador binario, construcción a la que denominaremos expresión "operatorio", por tratarse de una generalización de la notación matemática de sumatorios y productorios.

Operadores aritméticos

Los operadores aritméticos aplicables a operandos de tipos numericos son los siguientes:

    + suma (binario) o sin efecto (unario)
    - resta (binario) o cambio de signo (unario)
    * multiplicación (binario)
    / división (binario)
    % resto (binario)

La operación de dos valores del mismo tipo siempre devuelve un valor de ese tipo. En particular, cabe señalar que la división de dos valores enteros devuelve el entero resultante de realizar la división entera del primer valor entre el segundo (por ejemplo, 7/3 devuelve 2).

Si se realiza una operación aritmetica entre dos valores numericos de tipos distintos, se somete al operando de tipo menos general, antes de realizar los calculos propios de la operación, a una conversión implicita al tipo mas general (el tipo real es mas general que el tipo entero). Se dice que el operando "promociona", y como consecuencia de ello, el resultado de la operación acaba siendo del tipo mas general.

El caso del operador % es especial, ya que requiere obligatoriamente que sus dos operandos sean de tipo entero. El resultado de una operación como a%b, el resto de la división entera de a entre b, puede expresarse entonces como a-b*(a/b).

Operadores de comparación

Los operadores de comparación son los siguientes:

    =  igual
    != distinto
    <> distinto
    < menor
    > mayor
    <= menor o igual
    >= mayor o igual

Son todos operadores binarios, y en principio, los valores comparados han de ser del mismo tipo numérico elemental, si bien también se pueden realizar comparaciones en las que intervengan un valor real y uno entero, en cuyo caso se produce una previa conversión implicita del operando entero al tipo real.

El resultado devuelto es siempre de tipo entero: un 0 para representar el valor falso y un 1 para representar el valor cierto.

Operadores logicos

Los operadores lógicos son:

    & conjunción (binario)
    | disyunción (binario)
    ! negación (unario)

Los operadores lógicos solo pueden operar sobre operandos de tipo entero (el cero se interpreta como falso y cualquier otro valor, como cierto), y el resultado que devuelven es, también, de tipo entero: 0 para representar falso y 1 para representar cierto.

Cabe señalar que, en el caso de los operadores lógicos binarios, el lenguaje no garantiza que, cuando baste el valor del primer operando para determinar el valor del resultado, no intente evaluarse el segundo. Será responsabilidad del interprete del lenguaje optimizar la evaluación de este tipo de expresiones.

Reglas de precedencia y asociatividad

En el lenguaje m2k2 los operadores unarios son prefijos y los binarios son infijos y asociativos por la izquierda. Respecto a los niveles de precedencia, estos son solo tres:

  • MAXIMA: La de los operadors unarios
  • INTERMEDIA: La de los operadores de multiplicación, división, resto, conjunción y comparación.
  • MINIMA: La de los operadores de suma, resta y disyunción.

Se permite el uso de parentesis para especificar la aplicación de operadores en uno orden distinto del que se seguirá de sus reglas de precedencia y asociatividad.

La expresión operatorio

El lenguaje m2k2 ofrece una expresión "operatorio" con la sintaxis:

    idop(ident, expr1..expr2,expr3)

donde "idop" puede ser cualquier identificador de los definidos en la sección que hablamos de los operatorios, "ident" debe ser el identificador de una variable (la variable muda del operatorio), adecuadamente declarada de tipo entero, las expresiones "expr1" y "expr2" han de ser de tipo entero, y expr3 puede ser de cualquier tipo numérico, con la restricción de que en el interior de expr3 no puede aparecer otro "operatorio" que utilice a "ident" también como variable muda.

En lo que respecta a la semantica de la expresión, se puede decir, informalmente, que se trata de aplicar reiteradamente el operador binario (aritmetico o logico) que aparece entre parentesis en "idop" a una lista de operandos de la forma expr3, donde la variable "ident" va tomando, sucesivamente y en orden creciente, todos los valores comprendidos entre un limite inferior (el resultado de evaluar expr1) y uno superior (el resultado de evaluar expr2), ambos inclusive. Es responsabilidad del usuario del lenguaje que el limite superior sea mayor o igual que el inferior.

Así por ejemplo, el sumatorio de j desde 1 hasta 1000 de j^2 se podría expresar en m2k2 como (+)(j,1..1000,j*j). Mientras que el resultado de evaluar (/)(k,1..3,k+0.5) sería el mismo que el de evaluar 1.5/2.5/3.5

Estructura de los programas

Los programas en m2k2 son secuencias de cero o mas declaraciones de las siguientes clases: declaraciones de variables y sentencias (simples o compuestas).

Declaraciones de variables

Declarar una variable consiste en asociar un identificador con un determinado tipo de variable (entera o real).

En m2k2 pueden declararse simultáneamente variables de un mismo tipo mediante lo que se denomina una declaración homogenea de variables, consistente en una especificación del tipo de las variables, y una lista de uno o mas identificadores separados por comas.

Todas las variables a las que se haga referencia en el programa deben haber sido explicitamente declaradas previamente. Por otra parte esta prohibido usar el mismo identificador mas de una vez para declarar variables.

Variables de tipos elementales

Para los tipos elementales, la especificación de tipo consiste, simplemente, en la palabra clave que lo identifica: ENTER para el tipo entero y REAL para el tipo real. Asi, por ejemplo, podrían declararse las variables enteras a y esPar y la real X1, de la siguiente manera:

    ENTER a, esPar
    REAL X1

Sentencias simples

Las sentencias simples que ofrece el lenguaje son las de asignación y las de expresión.

Sentencias de asignación

Las sentencias de asignación en m2k2 permiten asignar el valor de una expresión al objeto receptor referenciado por su parte izquierda. Su sintaxis puede expresarse como:

    receptor <- expresion

donde receptor puede ser únicamente un identificador de una variable de tipo elemental previamente declarada. El tipo de receptor ha de ser el mismo que el de expresión, o bien un tipo mas general, en cuyo caso el valor de la expresión se convierte implicitamente al tipo del receptor antes de realizar la asignación.

Sentencias expresión

Cualquier expresión correcta constituye una sentencia válida en el lenguaje, cuya ejecución consiste, simplemente, en evaluar la expresión. El interprete del lenguaje m2k2 actuará mostrando por la salida estandar el resultado de evaluar las expresiones.

Ejemplo

Para finalizar con la definición del lenguaje se ofrece a modo de ejemplo un programa en el lenguaje m2k2:

    >>> enter inicio, final
    >>> inicio<-0
    >>> final<-3
    >>>
    >>> real x
    >>> x<-3.5
    >>>
    >>> enter i
    >>> x <- (*)(i,inicio..final,x) + (+)(i,1..10,i)
    >>> x
    205.0625

Continuar leyendo el analizador léxico

Visitas:

Seguidores