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