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