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! :)

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