Creando un analizador semántico
Viernes 29 dAmerica/Chicago Septiembre dAmerica/Chicago 2006 a las 0:52Entre 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:
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:
VB.NET:
-
''' <summary>
-
''' Es un simbolo de la tabla de simbolos. Se utiliza en el analizador léxico
-
''' </summary>
-
''' <remarks></remarks>
-
Public Class Simbolo
-
-
Public Enum ClaseSimbolo
-
Variable
-
Constante
-
Funcion
-
End Enum
-
-
Private _nombre As String
-
-
''' <summary>
-
''' El nombre del simbolo. Por ejemplo el nombre de una variable tal y como se declara
-
''' </summary>
-
''' <value></value>
-
''' <returns></returns>
-
''' <remarks></remarks>
-
Public Property Nombre() As String
-
Get
-
Return _nombre
-
End Get
-
Set(ByVal value As String)
-
_nombre = value
-
End Set
-
End Property
-
-
Private _clase As ClaseSimbolo
-
-
''' <summary>
-
''' Indica que clase de simbolo es: variable, constante o función
-
''' </summary>
-
''' <value></value>
-
''' <returns></returns>
-
''' <remarks></remarks>
-
Public Property Clase() As ClaseSimbolo
-
Get
-
Return _clase
-
End Get
-
Set(ByVal value As ClaseSimbolo)
-
_clase = value
-
End Set
-
End Property
-
-
Private _tipo As String
-
-
''' <summary>
-
''' Representa el tipo del simbolo: numerica, cadena o logica
-
''' </summary>
-
''' <value></value>
-
''' <returns></returns>
-
''' <remarks></remarks>
-
Public Property Tipo() As String
-
Get
-
Return _tipo
-
End Get
-
Set(ByVal value As String)
-
_tipo = value
-
End Set
-
End Property
-
-
Private _valor As String
-
-
''' <summary>
-
''' Valor del simbolo. Unicamente utilizado por las constantes
-
''' </summary>
-
''' <value></value>
-
''' <returns></returns>
-
''' <remarks></remarks>
-
Public Property Valor() As String
-
Get
-
Return _valor
-
End Get
-
Set(ByVal value As String)
-
_valor = value
-
End Set
-
End Property
-
-
Private _tiposDeLosArgumentos As New List(Of String)
-
-
''' <summary>
-
''' Solo utilizada por los simbolos de tipo función. Es una lista con los tipos de los
-
''' argumentos de la función.
-
''' </summary>
-
''' <value></value>
-
''' <returns></returns>
-
''' <remarks></remarks>
-
Public ReadOnly Property TiposDeLosArgumentos() As List(Of String)
-
Get
-
Return _tiposDeLosArgumentos
-
End Get
-
End Property
-
-
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 .
<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
