Just a little bit freak

sábado, 13 de junio de 2015

La generación de resultados y el código fuente 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 la generación de resultados y al final se proporciona el código fuente.

Generación de resultados

El árbol de sintaxis abstracta construido durante la fase de análisis semántico no solo es útil para realizar las comprobaciones semánticas. Este árbol resulta especialmente cómodo para realizar la interpretación. Para ello, cada nodo del AST cuenta con un método interpret que realiza la interpretación de ese nodo y a su vez dispara las interpretaciones oportunas sobre sus nodos hijos. Todo el proceso de interpretación comienza en el programa principal con la llamada:

    AST.interpret()

Obviamente, el AST se interpreta solo cuando la relación de comprobaciones semánticas finaliza con éxito. Se enumera a continuación la interpretación de cada uno de los distintos nodos del AST.

    node_Declaracion.interpret( )

La interpretación de este nodo tiene como efecto lateral la declaración como variables de los lexemas que aparecen en la lista de identificadores.

    node_Asignacion.interpret( )

La interpretación de este nodo calcula el valor que devuelve la interpretación de la expresión y como efecto lateral asigna ese valor al identificador que actúa como receptor de la asignación. En caso de ser necesario, realiza el typecasting.

    node_Expresion.interpret( )

La interpretación de este nodo calcula el valor que devuelve la interpretación de la expresión y imprime ese valor por el stdout.

    node_MasBinario.interpret( )

La interpretación de este nodo devuelve el resultado de sumar la interpretación de sus dos términos.

    node_MenosBinario.interpret( )

La interpretación de este nodo devuelve el resultado de restar la interpretación de sus dos términos.

    node_O.interpret( )

La interpretación de este nodo devuelve el resultado de aplicar el operador O lógico a la interpretación de sus dos términos. La interpretación del nodo se realiza por cortocircuito, lo cual quiere decir que si el primer térmito se evalúa como "true", ya no se interpreta el segundo término. Esto tiene como consecuencia que una expresión como esta:

    >>> 1 | (1/0)
    1

no provoca error de ejecución por división por cero.

    node_Mul.interpret( )

La interpretación de este nodo devuelve el resultado de multiplicar la interpretación de sus dos factores.

    node_Div.interpret( )

La interpretación de este nodo devuelve el resultado de dividir la interpretación de sus dos factores.

    node_Y.interpret( )

La interpretación de este nodo devuelve el resultado de aplicar el operador Y lógico a la interpretación de sus dos factores. La interpretación del nodo se realiza por cortocircuito, lo cual quiere decir que si la interpretación el primer factor devuelve falso como resultado, el segundo factor ya no se evalúa, con lo que una línea como esta,

    >>> 0 & (1/0)
    1

se evalúa sin que se produzca el error de ejecución.

    node_PorCien.interpret( )

La interpretación de este nodo devuelve el resultado de calcular el resto a la interpretación de sus dos factores.

    node_Cmp.interpret( )

La interpretación de este nodo devuelve el resultado de comparar la interpretación de sus dos factores.

    node_Ident.interpret( )

La interpretación de este nodo devuelve el valor que el identificador tiene almacenado en la tabla de símbolos.

    node_NrEnter.interpret( )

La interpretación de este nodo devuelve el valor de la constante entera.

    node_NrReal.interpret( )

La interpretación de este nodo devuelve el valor de la constante real.

    node_MasUnario.interpret( )

La interpretación de este nodo devuelve el resultado de la interpretación del factor, manteniendo su signo.

    node_MenosUnario.interpret( )

La interpretación de este nodo devuelve el resultado de la interpretación del factor, cambiando su signo.

    node_No.interpret( )

La interpretación de este nodo devuelve el resultado de la interpretación del factor con la lógica invertida.

    node_OpTorio.interpret( )

La interpretación de este nodo calcula en primer lugar el resultado de la interpretación de las expresiones 1 y 2 del operatorio. Después de ésto, asigna a la variable muda del operatorio el valor devuelto por la interpretación de la expresión 1 y comienza a iterar sobre la variable muda del operatorio desde el valor devuelto por la interpretación de la expresión 1 mas uno hasta el valor devuelto por la interpretación de la expresión 2, acumulando las interpretaciones parciales del operatorio en una variable temporal res. Al terminar las iteraciones, el operatorio devuelve res como resultado de interpretar el operatorio.

    >>> (+) (i, 1..3, i)
    >>> 6

Al finalizar las iteraciones, la variable muda del operatorio contiene el valor devuelto por la interpretación de la expresión 2 del operatorio si este valor es mayor o igual que el valor devuelto por la interpretación de la expresión 1.

    >>> i
    >>> 3

Si el valor devuelto por la interpretación de la expresión 2 es menor que el valor devuelto por la interpretación de la expresión 1, la variable muda contiene el valor devuelto por la interpretación de la expresión 1.

    >>> (+) (i, 1..0, i)
    >>> 1
    >>> i
    >>> 1

Al igual que ocurre con los nodos relacionados con operaciones lógicas, los operatorios lógicos tambien se interpretan por cortocircuito. En ese caso, al finalizar la interpretación del nodo, la variable muda no contiene el valor máximo del rango sino el valor del rango que ha causado el cortocircuito de la interpretación del operatorio. Por ejemplo:

    >>> (&) (i, -2..2, i)
    >>> 0
    >>> i
    >>> 0

Vemos en el ejemplo anterior como la variable "i" usada como indice del operatorio se ha incrementado desde -2 hasta alcanzar el valor 0. Ese valor 0 ha hecho falsa la expresión (&). Y ahi ha finalizado la evaluación del operatorio, ya no se han evaluado los valores 1 y 2.

Errores de ejecución

La gestión de los errores de ejecución se hace con la misma filosofía con la que se gestionan los errores léxicos, sintácticos y semánticos: en el programa principal se capturan todas las posibles excepciones que se pueden lanzar durante la ejecución de alguna acción dentro del código del intérprete. En concreto se capturan estas tres excepciones:

  1. OverflowError
  2. ZeroDivisionError
  3. ValueError

La excepción "OverflowError" se dispara cuando se desborda un rango al calcular una operación aritmética. Por ejemplo:

    >>> 100000 * 100000
    Execution Error: overflow error

La excepción "ZeroDivisionError" se dispara cuando se produce una división por cero. Por ejemplo:

    >>> 1/(2-2)
    Execution Error: zero division error

La excepción "ValueError" se dispara cuando se utiliza la función atoi o la función atof sobre una cadena de dígitos que excede el rango de representación de los enteros o los reales respectivamente. Por ejemplo:

    >>> 9999999999999999999999
    Execution Error: value error

Con cualquiera de las 3 excepciones anteriores, el programa principal actúa capturando la excepción y mostrando por el stderr el mensaje informativo que corresponda a la excepción capturada, tal como se observa en los ejemplos anteriores. Una vez atendido el error de ejecución, se atiende la siguiente línea del stdin.

El código fuente

Directamente descargable desde github, en este repositorio:

https://github.com/aicastell/m2k2.git

Espero que lo disfrutéis! :)

sábado, 6 de junio de 2015

El analizador semántico 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 semántico. En el siguiente post hablaremos de la generación de resultados.

Analisis semántico

Determinadas características del lenguaje de programación de entrada no se pueden modelar mediante la gramática con partes derechas regulares (GDPR) del analizador sintáctico, por lo que es necesario que se comprueben en una fase posterior al análisis sintáctico que se conoce como análisis semántico. Un ejemplo de una de estas reglas semánticas que no se pueden modelar mediante la gramática con partes derechas regulares es que en m2k2 los identificadores tienen que estar declarados antes de poder utilizarse.

La tabla de simbolos

La tabla de símbolos se emplea, entre otras cosas, para revisar si un identificador ya ha sido declarado. Así, el uso de la tabla de símbolos puede considerarse como parte del proceso de análisis semántico. En el módulo semantico.py se implementa la clase SymbolTable.

    class SymbolTable:
        def __init__( )

        # gestión de buffer
        def declare( type, id )
        def isdeclared( id)
        def gettype( id )
        def getvalue( id )
        def putvalue( id, v )

        # gestión de silent
        def setsilent( id )
        def setnotsilent( id )
        def issilent( id )
        def clearallsilent( )

La tabla de simbolos es un objeto instanciado de la clase anterior, declarado como global dentro del módulo semantico.py

    symTable = SymbolTable( )

El constructor de esta clase no recibe ningun parámetro de entrada pero internamente crea dos atributos importantes:

    self.buffer={}
    self.silent=[]

El atributo buffer es un diccionario Python que almacena en cada posición buffer[id] una lista con dos valores: el tipo del identificador id y su valor. El diccionario se inicializa a vacio. Los métodos que gestionan el atributo buffer tienen el comportamiento esperado según el nombre de su prototipo. La declaración de un nuevo identificador asigna un valor por defecto 0 a ese identificador si es de tipo entero y 0.0 si es de tipo real. El resto de métodos sirven para comprobar si un identificador esta o no declarado, para obtener el tipo base correspondiente a un identificador, para asignar un valor a un identificador, y para obtener el valor que un identificador tiene asignado. El atributo silent esta relacionado con las comprobaciones semánticas que se hacen sobre el operatorio. Hablaremos mas sobre el atributo "silent" y sobre los métodos que lo gestionan en una sección posterior.

Representación semántica elegida

Como representación semántica se utiliza un árbol de sintaxis abstracta o AST, aprovechando que la GPDR implementada en el analizador sintáctico tiene una cómoda representación como AST. El AST tiene 3 raices posibles:

  • node_Declaracion
  • node_Asignacion
  • node_Expresion
La interpretación de cada raíz en realidad supone realizar una de las tres acciones posibles con el intérprete:

  • La declaración de una lista de variables
  • La asignación del resultado devuelto por una expresión a un identificador
  • La escritura por stdout del resultado devuelto por una expresión

A continuación se muestra la representación gráfica de cada uno de los 3 posibles nodos del AST:

Los nodos node_Asignacio y node_Expresio tienen un campo expr que apunta a una expresión. Esta expresión puede tener una representación tan compleja como la del AST mostrado en este ejemplo:

Esquema de traducción

El análisis semántico no se realiza de forma independiente al análisis sintáctico, sino que ambos se realizan de forma simultánea. El analizador semántico empieza por construir los AST introducidos en la sección anterior. Para ello usa la gramática atribuida que se construye progresivamente en esta sección a medida que se explica la razón de los pasos seguidos.

<Linea> <DeclVar> tkEOL {RETURN <DeclVar>.ast}
<Linea> <Sentencia> tkEOL {RETURN <Sentencia>.ast}

Si la <Linea> se parsea correctamente, se devuelve el AST resultante.

<DeclVar> <Tipo> <ListaIds> { <DeclVar>.ast = node_Declaracion( <Tipo>.t, <ListaIds>.l }
<Tipo> tkTpoEnter { <Tipo>.t = "enter" }
<Tipo> tkTpoReal { <Tipo>.t = "real" }
<ListaIds> {l = [] } tkIdent {l=l+tkIdent.lex} ( tkComa tkIdent {l=l+tkIdent.lex} )*

El método que parsea a <DeclVar> comienza por parsear a <Tipo>. Si el método que parsea a <Tipo> finaliza con éxito, devuelve en la variable sintetizada t el tipo de las variables que se deben declarar. El método que parsea a <DeclVar> continua parseando a <ListaIds>. A medida que se parsea a <ListaIds> se construye una lista l con los lexemas de todos los identificadores que hay que declarar. Si el método que parsea a <ListaIds> finaliza con éxito, el método que parsea a <DeclVar> ya puede construir un node_Declaracion con los atributos sintetizados t y l.

<Sentencia> {IF self.a.cat == "tkIdent" THEN leftIdent = self.a.lex}
<Expresion> {<Asignacion>.isident = <Expresion>.isident }
<Asignacion>
{IF <Asignacion>.isnotempty
THEN Sentencia.ast = node_Asignacion( leftIdent, Asignacion.ast )
ELSE Sentencia.ast = node_Expresion( Expresion.ast ) ENDIF}
<Asignacion> tkAsign { IF <Asignacion>.isident = 0 THEN "Error" ENDIF}
{Asignacion.isnotempty = 1} <Expresion>
<Asignacion> λ {Asignacion.isnotempty = 0}

El método que parsea a <Sentencia> empieza guardando en leftIdent el lexema del token actualmente analizado si este token es un identificador. Después se llama al método que parsea a <Expresion>. Si el parseo de <Expresion> finaliza con éxito, <Expresion> retorna un atributo sintetizado isident que indica si la expresión parseada es o no un identificador. El valor de isident se copia en <Asignacion> mediante su atributo heredado isident, y a continuación se llama al método que parsea a <Asignacion>.

Dentro del método que parsea a <Asignacion> se utiliza el atributo heredado isident para saber si la parte izquierda de la asignación es o no un identificador. En caso de encontrar un tkAsign en la entrada, se genera un error si la parte izquierda de la asignación no es un identificador. El método devuelve cierto en el atributo sintetizado isnotempty si la asignación tiene parte derecha, y falso en caso contrario.

De vuelta en el método que parsea <Sentencia> si el método que parsea <Asignacion> finaliza correctamente, se evalúa el atributo sintetizado isnotempty que ha devuelto la llamada al método que parsea . Si la asignación tiene parte derecha, se construye un node_Asignacion, y si no tiene parte derecha, se trata de una sentencia expresión, por lo que se construye un node_Expresion.

<Expresion> <Termino>
{<Expresion>.isident = <Termino>.isident}
{<Expresion>.ast = <Termino>.ast}
(( tkMas | tkMenos | tkO ) <Termino>
{<Expresion>.isident=0}
{IF tkMas THEN node_MasBinario( <Expresion>.ast, <Termino>.ast ) ELSE
IF tkMenos THEN node_Menos( <Expresion>.ast, <Termino>.ast ) ELSE
IF tkO THEN node_O( <Expresion>.ast, <Termino>.ast ) ENDIF} )*

Lo primero que hace el método que parsea a <Expresion> es llamar al método que parsea a <Termino>. Si el método que parsea a <Termino> retorna con éxito, <Termino> vuelve con dos atributos sintetizados: el atributo isident, que indica si <Termino> es un identificador o no lo es, y el atributo ast, que contiene el AST de ese <Termino>. Esos dos valores promocionan hacia arriba copiandose en la <Expresion>. Si en este punto se lee de la entrada un token tkMas, tkMenos o tkO, entonces se afirma que <Expresion> no es un identificador, y se construye un node_MasBinario, node_Menos o un node_O con lo que hay en <Expresion>.ast hasta ese momento y con el <Termino>.ast recien calculado. Las sucesivas iteraciones de la clausura irán construyendo correctamente las ramas del AST.

<Termino> <Factor>
{<Termino>.isident = <Factor>.isident}
{<Termino>.ast = <Factor>.ast}
( ( tkMul | tkDiv | tkY | tkPorCien | tkCmp ) <Factor>
{<Termino>.isident=0}
{IF tkMul THEN node_Mul( <Termino>.ast, <Factor>.ast ) ELSE
IF tkDiv THEN node_Div( <Termino>.ast, <Factor>.ast ) ELSE
IF tkY THEN node_Y( <Termino>.ast, <Factor>.ast ) ELSE
IF tkPorCien THEN node_PorCien( <Termino>.ast, <Factor>.ast ) ELSE
IF tkCmp THEN node_Cmp( <Termino>.ast, <Factor>.ast ) ENDIF} )*

El método que parsea a <Termino> empieza llamando al método que parsea a <Factor>. Si el método que parsea a <Factor> retorna con éxito, <Factor> vuelve con dos atributos sintetizados: el atributo isident, que indica si <Factor> es un identificador o no lo es y el atributo ast, que contiene el AST de ese <Factor>. Esos dos valores promocionan hacia arriba copiandose en el <Termino>. Si en este punto se lee de la entrada un token tkMul, tkDiv, tkY, tkPorCien o tkCmp, entonces se afirma que <Termino> no es un identificador, y se construye un node_Mul, node_Div, node_Y, node_PorCien o un node_Cmp con lo que hay en <Termino>.ast hasta ese momento y con el <Factor>.ast recién calculado. Las sucesivas iteraciones de la clausura irán construyendo correctamente las ramas del AST.

<Factor> tkIdent {<Factor>.isident = 1} {Factor.ast = node_Ident( tkIdent.lex )}
<Factor> tkNrEnter {<Factor>.isident = 0} {Factor.ast = node_NrEnter( tkNrEnter.val )}
<Factor> tkNrReal {<Factor>.isident = 0} {Factor.ast = node_NrReal( tkNrReal.val )}
<Factor> tkOpTorio {optor = tkOpTorio.lex}
tkAbrPar tkIdent {id = tkIdent.lex}
tkComa <Rango> tkComa <Expresion>
{<Factor>.ast=node_OpTorio(optor, id, Rango.ast1, Rango.ast2, <Expresion>.ast )
tkCiePar {<Factor>.isident = 0}
<Factor> tkAbrPar <Expresion> {<Factor>.ast = <Expresion>.ast}
<Factor> tkCiePar {<Factor>.isident = 0}
<Factor> (tkMenos | tkMas | tkNo )<Factor>
{IF tkMenos THEN <Factor>.ast = node_MenosUnario(<Factor>.ast) ELSE
{IF tkMas THEN <Factor>.ast = node_MasUnario(<Factor>.ast) ELSE
{IF tkNo THEN <Factor>.ast = node_No(<Factor>.ast) ENDIF}

El método que parsea a <Factor> es el punto de la gramática atribuida donde aparecen las condiciones de parada de la recursion. Si desde se deriva un tkIdent, entonces isident es cierto. En cualquier otro caso isident es falso. El resto de las acciones semanticas son para construir los distintos nodos hoja del árbol: node_Ident, node_NrEnter, node_NrReal, node_OpTorio, node_MenosUnario, node_MasUnario o node_No.

<Rango> <Expresion> {<Rango>.ast1 = <Expresion>.ast}
<Factor> tkPtoPto
<Factor> <Expresion> {<Rango>.ast2 = <Expresion>.ast}

Si el <Rango> se parsea correctamente, retorna con dos atributos sintetizados ast1 y ast2 correspondientes a los AST de las expresiones 1 y 2 de los operatorios.

Relación de comprobaciones semánticas

El análisis semántico debe comprobar que la semántica de lo que se va leyendo por la entrada es valida. Entre otras cosas determina si el tipo de los resultados intermedios es correcto, comprueba que los argumentos de un operador pertenecen al conjunto de operadores posibles, comprueba si los operadores son compatibles entre si, etc. Si suponemos que i es una variable declarada de tipo entero y x de tipo real, para el siguiente fragmento de código en m2k2,

    i <- x * x

el analizador léxico devuelve la secuencia de tokens:

    tkIdent('i')
    tkAsign
    tkIdent('x')
    tkMul
    tkIdent('x')

Los errores que puede detectar el analizador sintáctico son aquellos que violan la gramática GDPR, aunque en este caso el analizador sintáctico dice que los tokens llegan en el orden correcto. Sin embargo, el analizador semántico debe mostrar un error semántico que diga que el tipo del identificador que actúa como receptor de la asignación es menos general que el tipo de la expresión que se pretende asignar.

El método parse_Linea devuelve sobre AST el árbol de sintaxis abstracta de la línea analizada.

    AST = SynAna.parse_Linea()

El analizador semántico realiza las comprobaciones semánticas sobre ese AST. Para ello, cada nodo del AST cuenta con un método check que comprueba la semántica de ese nodo y a su vez dispara las comprobaciones semánticas oportunas sobre sus nodos hijos. Todo el proceso de comprobaciones semánticas comienza en el programa principal con la llamada:

    AST.check()

Se enumeran a continuación las comprobaciones semánticas realizadas en cada uno de los nodos del árbol de sintaxis abstracta.

    node_Declaracion.check( )

Comprueba si en la lista de identificadores que se pretende declarar hay algún identificador que ya ha sido previamente declarado. También comprueba si en esa lista hay dos identificadores que tengan el mismo lexema.

    node_Asignacion.check( )

Comprueba si el identificador que actúa como receptor de la asignación ha sido previamente declarado. También comprueba que el tipo del receptor de la asignación no sea menos general que el tipo de la expresión que se asigna. El conflicto con el no-identificador como receptor de una asignación lo resuelve la gramática atribuida tal y como se explica en un apartado anterior que habla sobre el esquema de traducción.

    node_Expresion.check( )

Comprueba la semántica de la expresión que cuelga de este nodo y se devuelve su tipo.

    node_MasBinario.check( )

Comprueba la semántica de los dos términos que hacen de operandos de este nodo y devuelve el tipo que genera la suma binaria después de realizar el typecasting oportuno.

    node_MenosBinario.check( )

Comprueba la semántica de los dos términos que hacen de operandos de este nodo y devuelve el tipo que genera la resta binaria después de realizar el typecasting oportuno.

    node_O.check( )

Comprueba que los dos términos que hacen de operandos de este nodo sean de tipo entero y devuelve el tipo "enter".

    node_Mul.check( )

Comprueba la semántica de los dos términos que hacen de operandos de este nodo y devuelve el tipo que genera la multiplicación después de realizar el typecasting oportuno.

    node_Div.check( )

Comprueba la semántica de los dos términos que hacen de operandos de este nodo y devuelve el tipo que genera la división después de realizar el typecasting correspondiente.

    node_Y.check( )

Comprueba que los dos factores que hacen de operandos de este nodo sean de tipo entero y devuelve el tipo "enter".

    node_PorCien.check( )

Comprueba que los dos factores que hacen de operandos de este nodo sean de tipo entero y devuelve el tipo "enter"

    node_Cmp.check( )

Comprueba la semántica de los dos factores que hacen de operandos de este nodo y devuelve el tipo enter.

    node_Ident.check( )

Actúa como condición de parada de la recursividad. Comprueba si el identificador de este nodo ha sido previamente declarado en la tabla de símbolos y en caso afirmativo devuelve el tipo de ese identificador.

    node_NrEnter.check( )

Actúa como condición de parada de la recursividad. Devuelve el tipo "enter".

    node_NrReal.check( )

Actúa como condición de parada de la recursividad. Devuelve el tipo real.

    node_MasUnario.check( )

Comprueba la semántica del factor que acompaña a este nodo y devuelve su tipo.

    node_Menos.check( )

Comprueba la semántica del factor que acompaña a este nodo y devuelve su tipo.

    node_No.check( )

Comprueba que el factor que hace de operando de este nodo sea de tipo entero y devuelve el tipo "enter".

    node_OpTorio.check( )

Comprueba si el identificador que actúa como variable muda esta declarado y es de tipo "enter". Si esto se cumple, comprueba si las expresiones 1 y 2 del operatorio (rango mínimo y rango máximo) son de tipo "enter". Si esto también se cumple, comprueba con el método issilent() si la variable muda de este operatorio aparece en la lista "silent". Cuando se empieza a evaluar la semántica de la expresión 3 del operatorio, la lista silent contiene los identificadores de las variables que se estan utilizando como mudas en operatorios de nivel superior. Si la variable no se esta usando como variable muda en ningun operatorio de nivel superior, se inserta en la lista silent usando el método setsilent antes de evaluar la semántica de la expresión 3 de ese operatorio. Cuando se terminan las comprobaciones semánticas sobre la expresión 3, se usa el método setnotsilent() para eliminar de la lista silent la variable muda anteriormente insertada en ella. Si todo va bien, al terminar las comprobaciones semánticas del operatorio de nivel mas alto, la lista "silent" debe estar vacia. En caso de que se produzca algun error semántico durante las comprobaciones semánticas del operatorio, la lista "silent" se vacia explícitamente con el método clearallsilent() para que las variables que fueron insertadas en esa lista no sigan ahí al comenzo del análisis de la nueva línea. Todo está perfectamente sincronizado para cumplir la restricción semántica que dice que en el interior de la expresión 3 de un operatorio no puede aparecer otro operatorio que utilice como variable muda una variable que se este usando como muda de otro operatorio de nivel superior en esa misma línea.

Errores semánticos

Para gestionar los errores semánticos se implementa la clase SemError en el módulo semantico.py.

    class SemError:
        def __init__( message )
        def __str__( )

El constructor de esta clase recibe como parámetro una cadena de texto que contiene el mensaje informativo del error. El método __str__ construye el mensaje de error que se imprime por el stderr al imprimir un objeto de esta clase.

Cuando se incumple alguna de las comprobaciones semánticas expuestas en la sección anterior se produce un error semántico. El analizador semántico lanza una excepción SemError junto con el mensaje de error que construye la clase SemError

    raise SemError, SemError( message )

El programa principal captura la excepción y la muestra por el stderr. Sirvan las siguientes situaciones como ejemplos:

    >>> enter i
    >>> real x
    >>> i <- x
    Semantic Error: incorrect typecast in assignment, real i expected
    >>> 1&1.0
    Semantic Error: expected enter operands in binary '&' operator
    >>> (+)(i, 1..2, (*)(i, 1..2, i))
    Semantic Error: silent identifier 'i' inside '(*)' operatory is already in use

Los errores semánticos contienen menos información que los errores léxicos o sintácticos. Existe una razón de limpieza de código para defender esta forma de tratar los errores semanticos. Recuerde que tanto el analizador léxico como el sintáctico hacen uso de información contenida en el propio analizador léxico y en los tokens que el analizador léxico proporciona al analizador sintáctico para construir los mensajes de error que se muestran por el stderr. Parece razonable que los analizadores léxico y sintáctico tengan acceso a estas informaciones.

El analizador semántico tambien podría trabajar con tokens y recibir del analizador sintáctico un parámetro con el analizador léxico para seguir dando a los errores el mismo tratamiento que se les daba en los analizadores léxico y sintáctico. Sin embargo, para mantener el código lo mas limpio posible, parece razonable que el analizador semántico deje de trabajar con tokens y se concentre en su cometido, tratando únicamente el tipo y lexema de los identificadores, y en el tipo y valor de las constantes. Por no tener acceso a los tokens se pierde la información sobre la categoría léxica de los tokens o el puntero al primer carácter de la línea donde empieza el token. Por no tener acceso al analizador léxico, se pierde la información sobre la cadena de caracteres de la línea actualmente analizada, el número de la línea actualmente analizada y el nombre del fichero de entrada.

Una vez se atiende el error semántico 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 semántico

Las acciones semánticas que aparecen en la gramática atribuida construída durante la sección del "Esquema de traducción" se traducen al lenguaje de programación Python y se intercalan entre las acciones del analizador sintáctico. Se ejecutan cuando el analizador sintáctico pasa por ellas. Para ello se modifica en el módulo sintactico.py la implementación del analizador sintáctico correspondiente a la gramática original de la siguiente manera:

  • Los atributos heredados del no terminal <E> se interpretan como parámetros de entrada del método parse_E.
  • Los atributos sintetizados del no terminal <E> se interpretan como parámetros de salida del método parse_E.

Se comienza por definir la clase "Attributes" en el módulo semantico.py como la clase vacía:

    class Attributes:
        pass

El analizador sintáctico, antes de llamar a un método de parsing de un no terminal, crea un objeto de la clase vacía con el nombre del no terminal al que va a llamar, y añade en ese objeto los atributos heredados del no terminal. Este objeto es el único parámetro que se pasa al método de parsing en su llamada. El correspondiente método de parsing crea sobre su parámetro de entrada los atributos sintetizados. Así, la traducción de la regla:

<E> <T> {<R>.h = <T>.s} <R> {<E>.s = <R>.s}

es la siguiente:

    def parse_E(E):
        T = Attributes()
        R = Attributes()
        parse_T(T)
        R.h = T.s
        parse_R(R)
        E.s = R.s

El siguiente es un extracto del código fuente correspondiente al módulo sintáctico.py. En concreto, el código corresponde al método de parsing del no terminal <Sentencia> con su control de errores correspondiente. El lector debe observar el atributo heredado leftisident del no terminal <Asignacion> y el atributo sintetizado isident del no terminal <Expresion>:

    def parse_Sentencia(self, Sentencia):

        Expresion  = Attributes()
        Asignacion = Attributes()

        # <Sentencia> -> <Expresion> <Asignacion>
        if self.a.cat in ["tkIdent", "tkNrEnter", "tkNrReal", "tkOpTorio", "tkAbrPar", "tkMenos", "tkMas", "tkNo"]:
            if self.a.cat == "tkIdent":
                leftIdent = self.a.lex
            if self.parse_Expresion(Expresion) == 0:
                raise SynError, SynError(self.LA, self.a, "expected <Expresion>")
            Asignacion.leftisident = Expresion.isident
            if self.parse_Asignacion(Asignacion) == 0:
                raise SynError, SynError(self.LA, self.a, "expected <Asignacion>")

        # otro
        else:
            raise SynError, SynError(self.LA, self.a, "expected <Expresion>")

        # se construye un nodo de asignacion o un nodo de expresion
        if Asignacion.isnotempty:
            Sentencia.ast = node_Asignacion( leftIdent, Asignacion.ast )
        else:
            Sentencia.ast = node_Expresion( Expresion.ast )

        return 1

El uso de una gramática GPDR para resolver el analizador sintáctico implica la existencia de clausuras y por tanto la existencia de un número potencialmente infinito de atributos en la gramática. Sin embargo, al interpretarlos dentro de un esquema de traducción, este problema desaparece. Los trataremos como parámetros en las correspondientes llamadas. De esta manera, la traducción de,

<E> <T> {<E>.s = <T>.s} (+<T> {<E>.s = <E>.s+<T>.s})*

es simplemente esta:

    def parse_E(E):
        T = Attributes()
        parse_T(T)
        E.s = T.s
        while token.cat == "suma":
            token = LA.getNextToken()
            parse_T(T)
            E.s = E.s + T.s

El siguiente es otro fragmento el código fuente extraído del módulo sintáctico.py. En concreto, el extracto es una versión reducida del código correspondiente al método de parsing del no terminal con el control de errores necesario. Preste especial atención al trato dado a la clausura:

    def parse_Termino(self, Termino):

        Factor = Attributes()

        # <Termino> -> <Factor> ( (tkMul|tkDiv|tkY|tkPorCien|tkCmp) <Factor> )*
        if self.a.cat in ["tkIdent", "tkNrEnter", "tkNrReal", "tkOpTorio", "tkAbrPar", "tkMenos", "tkMas", "tkNo"]:
            if self.parse_Factor(Factor) == 0:
                raise SynError, SynError(self.LA, self.a, "expected <Factor>")
            Termino.isident = Factor.isident
            Termino.ast = Factor.ast
            while self.a.cat in ["tkMul","tkDiv","tkY","tkPorCien","tkCmp"]:
                Termino.isident = 0
                tk = self.a
                self.a = self.LA.getNextToken()
                if self.parse_Factor(Factor) == 0:
                    raise SynError, SynError(self.LA, self.a, "expected <Factor>")
                if tk.cat == "tkMul":
                    Termino.ast = node_Mul( Termino.ast, Factor.ast )
                if tk.cat == "tkDiv":
                    Termino.ast = node_Div( Termino.ast, Factor.ast )
                if tk.cat == "tkY":
                    Termino.ast = node_Y( Termino.ast, Factor.ast )
                if tk.cat == "tkPorCien":
                    Termino.ast = node_PorCien( Termino.ast, Factor.ast )
                if tk.cat == "tkCmp":
                    Termino.ast = node_Cmp( Termino.ast, tk.lex, Factor.ast )

            # si a no pertenece a siguientes de p*
            if self.a.cat not in ["tkMas", "tkMenos", "tkO", "tkAsign", "tkEOL", "tkCiePar", "tkPtoPto", "tkComa"]:
                raise SynError, SynError(self.LA, self.a, "expected tkMas, tkMenos, tkO, tkAsign, tkEOL, tkCiePar, tkPtoPto or tkComa")

            # otro
            else:
                raise SynError, SynError(self.LA, self.a, "expected <Termino>")

        return 1

Respecto de la implementación del AST, todos los nodos del AST estan implementados como clases dentro del módulo semantico.py. A continuación se muestra el listado de los prototipos de estas clases:

    class node_Declaracion
        def __init__
        def check( )
        def interpret( )
    class node_Expresion
        def __init__
        def check( )
        def interpret( )
    class node_Asignacion
        def __init__
        def check( )
        def interpret( )
    class node_MasBinario
        def __init__
        def check( )
        def interpret( )
    class node_MenosBinario
        def __init__
        def check( )
        def interpret( )
    class node_O
        def __init__
        def check( )
        def interpret( )
    class node_Mul
        def __init__
        def check( )
        def interpret( )
    class node_Div
        def __init__
        def check( )
        def interpret( )
    class node_Y
        def __init__
        def check( )
        def interpret( )
    class node_PorCien
        def __init__
        def check( )
        def interpret( )
    class node_Cmp
        def __init__
        def check( )
        def interpret( )
    class node_Ident
        def __init__
        def check( )
        def interpret( )
    class node_NrEnter
        def __init__
        def check( )
        def interpret( )
    class node_NrReal
        def __init__
        def check( )
        def interpret( )
    class node_MasUnario
        def __init__
        def check( )
        def interpret( )
    class node_MenosUnario
        def __init__
        def check( )
        def interpret( )
    class node_No
        def __init__
        def check( )
        def interpret( )
    class node_OpTorio
        def __init__
        def check( )
        def interpret( )

Continuar leyendo el generación de resultados y código fuente

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

Seguidores