« Estado del proyecto a 25/09/2006
Aplicación de gestión »

Creando un analizador semántico

Entre las funciones de un analizador semántico están las siguientes:

  • Detectar si las variables, constantes y funciones han sido declaradas antes de ser utilizadas.
  • Verificar que las variables, constantes y funciones sean accesibles (visibilidad) desde el ámbito en que son utilizadas.
  • Comprobar que los diferentes identificadores solo hayan sido declarados una vez.
  • Comprobaciones de tipos al evaluar las expresiones. Por ejemplo que no se multiplique un número por una cadena o que la expresión a evaluar en un IF sea del tipo booleano.
  • Verificar que no se intente modificar el valor de una constante.
  • Generar la tabla de símbolos.

El lenguaje de script que estoy desarrollando de momento solo tendrá un ámbito, por lo que no será necesaria la comprobación del ámbito.

Para realizar el análisis semántico utilizaremos una gramática de atributos. Dichos atributos se asociaran tanto a los símbolos terminales como a los no terminales y se propagarán por el árbol sintáctico desde abajo hacia arriba, dando lugar al árbol semántico.
Lo primero que haremos será definir las reglas semánticas, para ello utilizaremos de nuevo la notición BNF a la que añadiremos en pseudocódigo las reglas semánticas.

A continuación se detallan aquellas producciones que constan de reglas semánticas:

 MAXIMIZAR

10 <DeclaracionVariable> ::= Variable <Tipo> Identificador
	InsertarSimbolo (Variable, Identificador, <Tipo>.Tipo)
11 <Tipo> ::= Numerica
	<Tipo>.Tipo  = Numerica
12 <Tipo> ::= Cadena
	<Tipo>.Tipo  = Cadena
13 <Tipo> ::= Logica
	<Tipo>.Tipo  = Logica
14 <DeclaracionConstante> ::= Constante <Resto_Constante>
	InsertarSimbolo (Constante, Identificador, < Resto_Constante >.Tipo)
18 <Condicional> ::= Si <Expresion> Entonces <Sentencias>  <Resto_Condicional>
	Si <Expresion>.Tipo <> Logica
		Error
21 <Bucle> ::= Mientras <Expresion> Hacer <Sentencias> Fin Mientras
	Si <Expresion>.Tipo <> Logica
		Error
22 <Asignacion_O_LlamadaAMetodo> ::= Identificador <Resto_Asignacion_O_LlamadaAMetodo> 

	Si No Existe (Identificador)
		Error
	Si hijo(1).produccion = 23
		Si es una variable
			Si tipo(identificado) <> hijo(1).tipo
				error
		sino
			Error
	Si hijo(1).produccion = 24
		Recorrer parametros y comprobar que el numero y el tipo de parámetros coincide
23 <Resto_Asignacion_O_LlamadaAMetodo> ::= = <Expresion>
	<Resto_Asignacion_O_LlamadaAMetodo>.Tipo = <Expresion>.Tipo
24 <Resto_Asignacion_O_LlamadaAMetodo> ::= <Parametros>
30 <Expresion> ::= <ExpresionSimple> <Resto_Expresion>
	Si <Resto_Expresion> SeAnula
		<Expresion>.Tipo = <ExpresionSimple>.Tipo
	Sino
		Si <ExpresionSimple>  = <Resto_Expresion>.Tipo
			<Expresion>.Tipo = Logica
		Sino
			Error
31 <Resto_Expresion> ::= <OperadorRelacional> <ExpresionSimple>
	<Resto_Expresion>.Tipo = <ExpresionSimple>.Tipo
32 <Resto_Expresion> ::= ε
39 <ExpresionSimple> ::= <Termino> <Resto_ExpresionSimple>
	Si <Resto_ExpresionSimple>  se anula
		<ExpresionSimple>.Tipo = <Termino>.Tipo
	Sino
		Si <Termino>.Tipo = <Resto_ExpresionSimple>.Tipo
			<ExpresionSimple>.Tipo = <Termino>.Tipo
		Si no
			Error
40 <Resto_ExpresionSimple> ::= <OperadorAditivo> <ExpresionSimple>
	Si <OperadorAditivo> = +
		Si <ExpresionSimple>.Tipo  = Numerica Or <ExpresionSimple>.Tipo = Cadena
			<Resto_ExpresionSimple>.Tipo = <ExpresionSimple>.Tipo
		Sino
			Error
	Si <OperadorAditivo> = -
		Si <ExpresionSimple>.Tipo  = Numerica
			<Resto_ExpresionSimple>.Tipo = <ExpresionSimple>.Tipo
		Sino
			Error
	Si <OperadorAditivo> = O
		Si <ExpresionSimple>.Tipo  = Logica
			<Resto_ExpresionSimple>.Tipo = Logica
		Sino
			Error
41 <Resto_ExpresionSimple> ::= ε
45 <Termino> ::= <Operando> <Resto_Termino>
	Si <Resto_Termino> se anula
		<Termino>.Tipo = <Operando>.Tipo
	Sino
		Si <Operando>.Tipo = <Resto_Termino>.Tipo
			<Termino>.Tipo = <Operando>.Tipo
		Si no
			Error
46 <Resto_Termino> ::= <OperadorMultiplicacion> <Termino>
	Si <OperadorMultiplicacion> = *  Or <OperadorMultiplicacion> = /
		Si <Termino>.Tipo  = Numerica
			<Resto_Termino>.Tipo = Numerica
		Sino
			Error
	Si <OperadorMultiplicacion> = Y
		Si <Termino>.Tipo  = Logica
			<Resto_Termino>.Tipo = Logica
		Sino
			Error
47 <Resto_Termino> ::= ε
51 <Operando> ::= Identificador
	Si Existe(Identificado)
		<Operando>.Tipo = Tipo (Identificador)
	Sino
		Error
52 <Operando> ::= Cte_Numerica
	<Operando>.Tipo = Numerico
53 <Operando> ::= Cte_Cadena
	<Operando>.Tipo = Cadena
54 <Operando> ::= Cte_Logica
	<Operando>.Tipo = Logica
55 <Operando> ::= ( <Expresion> )
	<Operando>.Tipo = Tipo(<Expresion>)

Recorreremos recursivamente el árbol sintáctico en postorden (para cada nodo procesamos recursivamente todos los descendientes primero y luego el nodo). Iremos añadiendo atributos con información al árbol a medida que procesemos nodos. Como el recorrido se realiza en postorden cuando procesemos un nodo ya habremos procesado previamente todos sus descendientes por lo que dispondremos de la información de que nos provean sus atributos.

Añadiremos a la tabla de símbolos todas las constantes y variables que se vayan reconociendo, junto con la información del tipo y el valor (en el caso des la constantes)

La tabla de símbolos será una lista de elementos del tipo símbolo:

MAXIMIZAR PLAIN TEXT
VB.NET:
  1. ''' <summary>
  2. ''' Es un simbolo de la tabla de simbolos. Se utiliza en el analizador léxico
  3. ''' </summary>
  4. ''' <remarks></remarks>
  5. Public Class Simbolo
  6.  
  7.     Public Enum ClaseSimbolo
  8.         Variable
  9.         Constante
  10.         Funcion
  11.     End Enum
  12.  
  13.     Private _nombre As String
  14.  
  15.     ''' <summary>
  16.     ''' El nombre del simbolo. Por ejemplo el nombre de una variable tal y como se declara
  17.     ''' </summary>
  18.     ''' <value></value>
  19.     ''' <returns></returns>
  20.     ''' <remarks></remarks>
  21.     Public Property Nombre() As String
  22.         Get
  23.             Return _nombre
  24.         End Get
  25.         Set(ByVal value As String)
  26.             _nombre = value
  27.         End Set
  28.     End Property
  29.  
  30.     Private _clase As ClaseSimbolo
  31.  
  32.     ''' <summary>
  33.     ''' Indica que clase de simbolo es: variable, constante o función
  34.     ''' </summary>
  35.     ''' <value></value>
  36.     ''' <returns></returns>
  37.     ''' <remarks></remarks>
  38.     Public Property Clase() As ClaseSimbolo
  39.         Get
  40.             Return _clase
  41.         End Get
  42.         Set(ByVal value As ClaseSimbolo)
  43.             _clase = value
  44.         End Set
  45.     End Property
  46.  
  47.     Private _tipo As String
  48.  
  49.     ''' <summary>
  50.     ''' Representa el tipo del simbolo: numerica, cadena o logica
  51.     ''' </summary>
  52.     ''' <value></value>
  53.     ''' <returns></returns>
  54.     ''' <remarks></remarks>
  55.     Public Property Tipo() As String
  56.         Get
  57.             Return _tipo
  58.         End Get
  59.         Set(ByVal value As String)
  60.             _tipo = value
  61.         End Set
  62.     End Property
  63.  
  64.     Private _valor As String
  65.  
  66.     ''' <summary>
  67.     ''' Valor del simbolo. Unicamente utilizado por las constantes
  68.     ''' </summary>
  69.     ''' <value></value>
  70.     ''' <returns></returns>
  71.     ''' <remarks></remarks>
  72.     Public Property Valor() As String
  73.         Get
  74.             Return _valor
  75.         End Get
  76.         Set(ByVal value As String)
  77.             _valor = value
  78.         End Set
  79.     End Property
  80.  
  81.     Private _tiposDeLosArgumentos As New List(Of String)
  82.  
  83.     ''' <summary>
  84.     ''' Solo utilizada por los simbolos de tipo función. Es una lista con los tipos de los
  85.     ''' argumentos de la función.
  86.     ''' </summary>
  87.     ''' <value></value>
  88.     ''' <returns></returns>
  89.     ''' <remarks></remarks>
  90.     Public ReadOnly Property TiposDeLosArgumentos() As List(Of String)
  91.         Get
  92.             Return _tiposDeLosArgumentos
  93.         End Get
  94.     End Property
  95.  
  96. End Class

El siguiente script tras pasar por el analizador semántico genera este árbol semántico:

variable numerica j .
j = 1 + 2 * j + 4 .

 

 MAXIMIZAR

<Elemento Nombre="<SCRIPT>" Produccion="1">
    <Elemento Nombre="<SENTENCIAS>" Produccion="2">
        <Elemento Nombre="<SENTENCIA>" Produccion="5">
            <Elemento Nombre="<DECLARACIONVARIABLE>" Produccion="10">
                <Elemento Nombre="VARIABLE" Palabra="variable" Linea="1" Col="1"></Elemento>
                <Elemento Nombre="<TIPO>" Produccion="11" Tipo="NUMERICA">
                    <Elemento Nombre="NUMERICA" Palabra="numerica" Linea="1" Col="10"></Elemento>
                </Elemento>
                <Elemento Nombre="IDENTIFICADOR" Palabra="j" Linea="1" Col="19"></Elemento>
            </Elemento>
        </Elemento>
        <Elemento Nombre="." Palabra="." Linea="1" Col="21"></Elemento>
        <Elemento Nombre="<RESTO_SENTENCIAS>" Produccion="3">
            <Elemento Nombre="<SENTENCIAS>" Produccion="2">
                <Elemento Nombre="<SENTENCIA>" Produccion="7">
                    <Elemento Nombre="<ASIGNACION_O_LLAMADAAMETODO>" Produccion="22">
                        <Elemento Nombre="IDENTIFICADOR" Palabra="j" Linea="2" Col="1"></Elemento>
                        <Elemento Nombre="<RESTO_ASIGNACION_O_LLAMADAAMETODO>" Produccion="23" Tipo="NUMERICA">
                            <Elemento Nombre="=" Palabra="=" Linea="2" Col="3"></Elemento>
                            <Elemento Nombre="<EXPRESION>" Produccion="30" Tipo="NUMERICA">
                                <Elemento Nombre="<EXPRESIONSIMPLE>" Produccion="39" Tipo="NUMERICA">
                                    <Elemento Nombre="<TERMINO>" Produccion="45" Tipo="NUMERICA">
                                        <Elemento Nombre="<OPERANDO>" Produccion="52" Tipo="NUMERICA">
                                            <Elemento Nombre="CTE_NUMERICA" Palabra="1" Linea="2" Col="5"></Elemento>
                                        </Elemento>
                                        <Elemento Nombre="<RESTO_TERMINO>" Produccion="47"></Elemento>
                                    </Elemento>
                                    <Elemento Nombre="<RESTO_EXPRESIONSIMPLE>" Produccion="40" Tipo="NUMERICA">
                                        <Elemento Nombre="<OPERADORADITIVO>" Produccion="42">
                                            <Elemento Nombre="+" Palabra="+" Linea="2" Col="7"></Elemento>
                                        </Elemento>
                                        <Elemento Nombre="<EXPRESIONSIMPLE>" Produccion="39" Tipo="NUMERICA">
                                            <Elemento Nombre="<TERMINO>" Produccion="45" Tipo="NUMERICA">
                                                <Elemento Nombre="<OPERANDO>" Produccion="52" Tipo="NUMERICA">
                                                    <Elemento Nombre="CTE_NUMERICA" Palabra="2" Linea="2" Col="9"></Elemento>
                                                </Elemento>
                                                <Elemento Nombre="<RESTO_TERMINO>" Produccion="46" Tipo="NUMERICA">
                                                    <Elemento Nombre="<OPERADORMULTIPLICACION>" Produccion="48">
                                                        <Elemento Nombre="*" Palabra="*" Linea="2" Col="11"></Elemento>
                                                    </Elemento>
                                                    <Elemento Nombre="<TERMINO>" Produccion="45" Tipo="NUMERICA">
                                                        <Elemento Nombre="<OPERANDO>" Produccion="51" Tipo="NUMERICA">
                                                            <Elemento Nombre="IDENTIFICADOR" Palabra="j" Linea="2" Col="13"></Elemento>
                                                        </Elemento>
                                                        <Elemento Nombre="<RESTO_TERMINO>" Produccion="47"></Elemento>
                                                    </Elemento>
                                                </Elemento>
                                            </Elemento>
                                            <Elemento Nombre="<RESTO_EXPRESIONSIMPLE>" Produccion="40" Tipo="NUMERICA">
                                                <Elemento Nombre="<OPERADORADITIVO>" Produccion="42">
                                                    <Elemento Nombre="+" Palabra="+" Linea="2" Col="15"></Elemento>
                                                </Elemento>
                                                <Elemento Nombre="<EXPRESIONSIMPLE>" Produccion="39" Tipo="NUMERICA">
                                                    <Elemento Nombre="<TERMINO>" Produccion="45" Tipo="NUMERICA">
                                                        <Elemento Nombre="<OPERANDO>" Produccion="52" Tipo="NUMERICA">
                                                            <Elemento Nombre="CTE_NUMERICA" Palabra="4" Linea="2" Col="17"></Elemento>
                                                        </Elemento>
                                                        <Elemento Nombre="<RESTO_TERMINO>" Produccion="47"></Elemento>
                                                    </Elemento>
                                                    <Elemento Nombre="<RESTO_EXPRESIONSIMPLE>" Produccion="41"></Elemento>
                                                </Elemento>
                                            </Elemento>
                                        </Elemento>
                                    </Elemento>
                                </Elemento>
                                <Elemento Nombre="<RESTO_EXPRESION>" Produccion="32"></Elemento>
                            </Elemento>
                        </Elemento>
                    </Elemento>
                </Elemento>
                <Elemento Nombre="." Palabra="." Linea="2" Col="19"></Elemento>
                <Elemento Nombre="<RESTO_SENTENCIAS>" Produccion="4"></Elemento>
            </Elemento>
        </Elemento>
    </Elemento>
    <Elemento Nombre="FIN_FICHERO" Palabra="FIN_SCRIPT" Linea="3" Col="1"></Elemento>
</Elemento

Ejemplos de errores detectados por el analizador semántico, mostrandose primero el script y a continuación el error detectado:

j = 1 + 2 * j + 4 .
ERROR: Identificador no declarado: j en línea 1 Columna 13

variable numerica j .
j = 1 + verdadero .
ERROR: Se esperaba un valor de tipo numérico o cadena tras el operador: + en la línea 2 Columna 7

si "a" = 3 entonces
   j = 4 .
fin si .
ERROR: No es posible realizar la comparación ya que los dos operandos son de tipos distintos. Línea 1 Columna 8

This entry was posted on Viernes, Septiembre 29th, 2006 at 0:52 and is filed under Motor Aventura Gráfica, Artículos. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

Antispam. Escriba la palabra 'hola' (sin comillas)