BrauSoft

El analizador sintáctico recibe los tokens o palabras generadas por el analizador léxico y determina si la secuencia u orden que presentan es correcta y permitida por el lenguaje. La salida que generará será el árbol sintáctico.

Lo primero que tenemos que hacer es determinar la sintaxis del lenguaje y expresarla formalmente en notación BNF. Esta tarea es bastante sencilla.

Script ::= <Sentencias> FinFichero
<Sentencias> ::= <Sentencia> . <Sentencias>
		| <Sentencia>
<Sentencia> ::= <DeclaracionVariable>
		| <DeclaracionConstante>
		| <Asignacion>
		| <Condicional>
		| <Bucle>
		| <LlamadaAMetodo>
<DeclaracionVariable> ::= Variable <Tipo> Identificador
<Tipo> ::= Numerica
		| Cadena
		| Logica
<DeclaracionConstante> ::= Constante Numerica Identificador = Cte_Numerica
		| Constante Cadena Identificador = Cte_Cadena
		| Constante Logica Identificador = Cte_Logica
<Asignacion> ::= Identificador = <Expresion>
<Condicional> ::= Si <Expresion> Entonces <Sentencias>	<RestoCondicional>
<RestoCondicional> ::= Sino <Sentencias> Fin Si
		| Fin Si
<Bucle> ::= Mientras <Expresion> Hacer <Sentencias> Fin Mientras
<LlamadaAMetodo> :: = Identificador <Parametros>
<Parametros> ::= < UnoOMasParametros >
		| ε
<UnoOMasParametros>::=  <Expresion> , <UnoOMasParametros>
		| < Expresion >
<Expresion> ::= <ExpresionSimple> <OperadorRelacional> <ExpresionSimple>
		| <ExpresionSimple>
<OperadorRelacional> ::= < | > | <= | >= | = | !=
<ExpresionSimple> ::= < ExpresionSimple > <OperadorAditivo> < Termino>
		| <Termino>
<OperadorAditivo> ::= + | - | O
<Termino> ::= <Termino> <OperdoraMultiplicacion> <Operando>
		| <Operando>
<OperadorMultiplicacion> ::= * | / | Y
<Operando> ::= Identificador
		| Cte_Numerica
		| Cte_Cadena
		| Cte_Logica
		| ( <Expresion> )

Vamos a imponer que nuestra definición del lenguaje cumpla la condición LL(1), lo cual implica que a partir de un determinado símbolo no terminal solo existe una producción que se puede aplicar. Para lo cual hay que eliminar las ambigüedades, la recursividad inmediata por la izquierda y los prefijos comunes. Esto es algo más complicado y nos puede dar algún quebradero de cabeza.

1. <Sentencia> ::= <Asignacion>
2. <Sentencia> ::= <LLamadaAMetodo>
3. <Asignacion> ::= Identificador = <Expresion>
4. <LLamadaAMetodo> ::= Identificador <Parametros>

En este ejemplo el lenguaje no cumpliría la condición LL(1) ya que si el símbolo que leemos es un identificador se podrían aplicar tanto la producción uno como la dos.

Para comprobar que cumple la condición LL(1) hemos de calcular los símbolos directores, es decir aquellos símbolos terminales que nos guiarán para elegir una determinada producción entre todas aquellas que tengan la misma parte izquierda. De tal forma que cuando tengamos un determinado no terminal y leamos un símbolo por adelantado solo exista una producción que tenga el no terminal por parte izquierda y el símbolo por adelantado como símbolo director. En el ejemplo anterior tendríamos como símbolo director de todas las producciones el no terminal “Identificador”, por lo tanto si tenemos el no terminal <Sentencia> y leemos el símbolo “Identificador” no podríamos decantarnos por ninguna de las dos producciones (la uno o la dos).

El calculo de los directores es una tarea sumamente tediosa y es fácil cometer algún error. Numeramos las producciones para poder identificarlas más fácilmente.

1 <Script> ::= <Sentencias> FinFichero
	Dir = Inic(Sentencias) = Inic(Sentencia) = Inic(DeclaracionVariable) U Inic(DeclaracionConstante) U Inic(Asignacion_O_LlamadaAMetodo) U Inic(Condicional) U Inic(Bucle) = Variable Constante Identificador Si Mientras
2 <Sentencias> ::= <Sentencia> . <Resto_Sentencias>
	Dir = Inic(Sentencia) = Inic(DeclaracionVariable) U Inic(DeclaracionConstante) U Inic(Asignacion_O_LlamadaAMetodo) U Inic(Condicional) U Inic(Bucle) = Variable Constante Identificador Si Mientras
3 <Resto_Sentencias> ::= <Sentencias>
	Dir = Inic (sentencias) = Variable Constante Identificador Si Mientras
4 <Resto_Sentencias> ::= ε
	Dir = Seg(Resto_Sentencias) = Seg(Sentencias) = FinFichero U Fin U Sino U Seg(Resto_Sentencias) = FinFichero Fin Sino
5 <Sentencia> ::= <DeclaracionVariable>
	Dir = Variable
6 <Sentencia> ::= <DeclaracionConstante>
	Dir = Constante
7 <Sentencia> ::= <Asignacion_O_LlamadaAMetodo>
	Dir = Identificador
8 <Sentencia> ::= <Condicional>
	Dir = Si
9 <Sentencia> ::= <Bucle>
	Dir = Mientras
10 <DeclaracionVariable> ::= Variable <Tipo> Identificador
	Dir = Variable
11 <Tipo> ::= Numerica
	Dir = Numerica
12 <Tipo> ::= Cadena
	Dir = Cadena
13 <Tipo> ::= Logica
	Dir = Logica
14 <DeclaracionConstante> ::= Constante <Resto_Constante>
	Dir = Constante
15 <Resto_Constante> ::= Numerica Identificador = Cte_Numerica
	Dir = Numerica
16 <Resto_Constante> ::= Cadena Identificador = Cte_Cadena
	Dir = Cadena
17 <Resto_Constante> ::= Logica Identificador = Cte_Logica
	Dir = Logica
18 <Condicional> ::= Si <Expresion> Entonces <Sentencias>  <Resto_Condicional>
	Dir = Si
19 <Resto_Condicional> ::= Sino <Sentencias> Fin Si
	Dir = Sino
20 <Resto_Condicional> ::= Fin Si
	Dir = Fin
21 <Bucle> ::= Mientras <Expresion> Hacer <Sentencias> Fin Mientras
	Dir = Mientras
22 <Asignacion_O_LlamadaAMetodo> ::= Identificador						<Resto_Asignacion_O_LlamadaAMetodo>
	Dir = Identificador
23 <Resto_Asignacion_O_LlamadaAMetodo> ::= = <Expresion>
	Dir = =
24 <Resto_Asignacion_O_LlamadaAMetodo> ::= <Parametros>
	Dir = Inic(UnoOMasParametros) U Seg(Parametros) = Inic (Expresion) U Seg(Resto_Asignacion_O_LlamadaAMetodo) = Inic(ExpresionSimple) U Seg(Asignacion_O_LlamadaAMetodo) = Inic(Termino) U Seg(Sentencia) = Inic(Operando)  U . = Identificador Cte_Numerica Cte_Cadena Cte_Logica ( .
25 <Parametros> ::= <UnoOMasParametros>
	Dir = Inic (UnoOMasParametros) = Inic(Expresion) = Inic(ExpresionSimple) = Inic(Termino) = Inic(Operando)  = Identificador Cte_Numerica Cte_Cadena Cte_Logica (
26 <Parametros> ::= ε
	Dir = Seg(Parametros) = Seg(Resto_Asignacion_O_LlamadaAMetodo) = Seg(Asignacion_O_LlamadaAMetodo) = Seg(Sentencia) = .
27 <UnoOMasParametros>::=  <Expresion> <Resto_UnoOMasParametros>
	Dir = Inic(Expresion) = Inic(ExpresionSimple) = Inic(Termino) = Inic(Operando)  = Identificador Cte_Numerica Cte_Cadena Cte_Logica (
28 <Resto_UnoOMasParametros>::=  , <UnoOMasParametros>
	Dir = ,
29 <Resto_UnoOMasParametros>::= ε
	Dir = Seg(Resto_UnoOMasParametros) = Seg(UnoOMasParametros) = Seg(Parametros) = Seg (Resto_Asignacion_O_LlamadaAMetodo) = Seg(Asignacion_O_LlamadaAMetodo) = Seg(Sentencia) = .
30 <Expresion> ::= <ExpresionSimple> <Resto_Expresion>
	Dir = Inic(ExpresionSimple) = Inic(Termino) = Inic(Operando)  = Identificador Cte_Numerica Cte_Cadena Cte_Logica (
31 <Resto_Expresion> ::= <OperadorRelacional> <ExpresionSimple>
	Dir = Inic(OperadorRelacional) = <  >  <=  >=  =  !=
32 <Resto_Expresion> ::= ε
	Dir = Seg(Expresion) = Entonces U Hacer U ) U , U Seg(Resto_Asignacion_O_LlamadaAMetodo) = Entonces U Hacer U ) U Seg(Asignacion_O_LlamadaAMetodo) = Entonces U Hacer U ) U Seg(Sentencia) = Entonces Hacer  )  ,  .
33 <OperadorRelacional> ::= <
	Dir = <
34 <OperadorRelacional> ::= >
	Dir = >
35 <OperadorRelacional> ::= <=
	Dir = <=
36 <OperadorRelacional> ::= >=
	Dir = >=
37 <OperadorRelacional> ::= =
	Dir = =
38 <OperadorRelacional> ::=!=
	Dir = !=
39 <ExpresionSimple> ::= <Termino> <Resto_ExpresionSimple>
	Dir = Inic(Termino) = Inic(Operando)  = Identificador Cte_Numerica Cte_Cadena Cte_Logica (
40 <Resto_ExpresionSimple> ::= <OperadorAditivo> <ExpresionSimple>
	Dir = + - O
41 <Resto_ExpresionSimple> ::= ε
	Dir = Seg(Resto_ExpresionSimple) = Seg(ExpresionSimple) = Inic(Resto_Expresion) U Seg(Expresion) U Seg(Resto_Expresion) U Seg(Resto_ExpresionSimple) = Inic(OperadorRelacional) U Entonces U Hacer U ) U , U . U Seg(Resto_Asignacion_O_LlamadaAMetodo) U Seg(Expresion) =
<  >  <=  >=  =  != U Entonces U Hacer . U )
42 <OperadorAditivo> ::= +
	Dir =  +
43 <OperadorAditivo> ::=  -
	Dir =  -
44 <OperadorAditivo> ::=  O
	Dir = O
45 <Termino> ::= <Operando> <Resto_Termino>
	Dir = Inic(Operando)  = Identificador Cte_Numerica Cte_Cadena Cte_Logica (
46 <Resto_Termino> ::= <OperadorMultiplicacion> <Termino>
	Dir = * / Y
47 <Resto_Termino> ::= ε
	Dir = Seg(Resto_Termino) = Seg(Termino) = Inic (Resto_ExpresionSimple) U Seg(ExpresionSimple) = Inic(OperadorAditivo) U Inic(Resto_Expresion) U Seg(Expresion) U Seg(Resto_Expresion) U Seg(Resto_ExpresionSimple) = + - O U Inic(OperadorRelacional) U Entonces U Hacer U . U , U Seg(Resto_Asignacion_O_LlamadaAMetodo) U Seg(Expresion) = + - O U
<  >  <=  >=  =  != U Entonces U Hacer U . U , U  ) U Seg(Sentencia) = + - O U
<  >  <=  >=  =  != U Entonces U Hacer U . U ,U ) U Inic(Resto_Sentencias) = + - O U <  >  <=  >=  =  != U Entonces U Hacer U . U , U )
48 <OperadorMultiplicacion> ::= *
	Dir = *
49 <OperadorMultiplicacion> ::= /
	Dir = /
50 <OperadorMultiplicacion> ::= Y
	Dir = Y
51 <Operando> ::= Identificador
	Dir = Identificador
52 <Operando> ::= Cte_Numerica
	Dir = Cte_Numerica
53 <Operando> ::= Cte_Cadena
	Dir = Cte_Cadena
54 <Operando> ::= Cte_Logica
	Dir = Cte_Logica
55 <Operando> ::= ( <Expresion> )
	Dir = (

Continuación
Analizador sintáctico (Parte II)

He dotado al editor de código con intellisense. Esta funcionalidad resulta muy útil a la hora de escribir código ya que aumenta considerablemente la productividad del desarrollador. No es demasiado compleja de implementar. Hoy en día la inmensa mayoría de entornos de desarrollo incorporan esta característica.

El Intellisense se activa al presionar la combinación de teclas + J, con lo que se mostrará una lista con todas las palabras, posicionándose el foco en aquella palabra que encaje con lo que hay escrito en el editor o en la primera de ellas si hubiera varias que encajaran. Se podrá seleccionar mediante los cursores la palabra deseada y al pulsar la barra espaciadora o la tecla ENTER se escribirá dicha palabra en el editor, desapareciendo la lista de palabras. Si pulsáramos la tecla ESC una vez se esta mostrando la lista de palabras, esta desaparecería.

Actualmente la lista de palabras únicamente muestra las palabras del lenguaje, pero no muestra variables o constantes que se hayan declarado previamente en el código. Cuando finalice la implantación de los analizadores incluirá las variables y las constantes en la lista.

Aparte de lo comentado en un post anterior hace unos días este es el estado del motor de aventuras gráficas a día de hoy.

He terminado el analizador sintáctico, aunque probablemente tenga que hacerle alguna modificación posteriormente para adaptarlo al analizador semántico. Todavía no he diseñado el analizador semántico, por lo que los datos de entrada que recibirá del sintáctico aun no están definidos por lo que tendré que hacer modificaciones al sintáctico para adaptarlo a lo esperado por el semántico.

A la hora de desarrollarlo he tenido algún contratiempo, ya que después de definir el lenguaje, expresarlo en notación BNF, calcular los símbolos directores e implementarlo, me he dado cuenta de que había dos producciones en las que a partir de un mismo no terminal compartían el mismo símbolo director, por lo que el analizador no era capaz de elegir la producción correcta de las dos posibles.

Finalmente me decidí por hacer una pequeña modificación al lenguaje para evitar dicho problema. Inicialmente el salto de línea era el separador de sentencias como en el lenguaje Visual Basic. Ahora es el punto, al igual que en las frases del lenguaje natural.

Cuando tenga una versión mas o menos definitiva del analizador sintáctico escribiré un par de posts sobre el proceso de desarrollo, incluyendo algunas capturas y fragmentos de código.

Una funcionalidad muy fácil de implementar y que resulta interesante es la de colorear en el editor de código que estoy creando las palabras del script dependiendo del tipo de palabra del que se trate.

Teniendo implementado el analizador léxico desarrollar esta funcionalidad es trivial. Para empezar lanzamos el analizador léxico y recibimos la colección de palabras que componen el script. Para cada una de ellas tendremos el tipo de palabra de que se trata y su posición en el script, indicada por su línea y columna. Con esta información simplemente seleccionaremos en el control RichTextBox que contiene el código las palabras que queramos resaltar y establecemos el color deseado según el tipo de palabra.

Se ha decidido colorear las palabras reservadas y las constantes lógicas (verdadero y falso) de azul, las cadenas de caracteres de color morado y los errores de color rojo. El resto de palabras permanecerán de color negro.

Esta es la apariencia que muestra el código una vez coloreado:

La palabra entera no la colorea de azul porque no es un tipo valido, el tipo es "numerica".

El código empleado en VB.NET es el siguiente:

A día de hoy (03/09/2006) esta es la funcionalidad que esta finalizada en motor de aventuras gráficas:

• Funciones matemáticas para tratar con puntos, ángulos, polígonos.
• Editor de áreas.
• Analizador léxico. Ver el primer artículo y el segundo artículo y este otro artículo
• Funcionalidad de colorear las palabras del editor de código basándose en el analizador léxico.
• Intellisense en el editor de texto.

Y poco más. Todavía me queda un largo camino hasta finalizar el proyecto.

Ahora mismo estoy terminando de desarrollar el analizador sintáctico y posteriormente me pondré con el semántico. Mi prioridad es finalizar cuanto antes el lenguaje de script.

Este artículo es la continuación de:

Creando un analizador léxico (Parte I)

Trás definir todos los posibles tokens procederemos a la implementación del analizador léxico que los reconocerá.

El analizador antes de poder reconocer los tokens debe fraccionar el código fuente en las palabras que lo componen, teniendo en cuenta para ello los separadores (salto de línea y espacio en blanco). Además se debe tener en cuenta que los espacios en blanco dentro de una cadena no deben ser tenidos en cuenta.

Una vez separadas todas las palabras existentes en el código fuente se deben intentar reconocer cada una de ellas. Para ello nos serviremos de autómatas finitos deterministas, que desarrollaremos según lo expuesto en un artículo anterior, para los componentes léxicos más complejos. Para aquellas palabras cuyo reconocimiento es trivial, como los operadores o las palabras reservadas, simplemente compararemos con dichas elementos. Como se muestra en el siguiente fragmento de código que es utilizado para reconocer si una palabra es una constante lógica o no.

El analizador recibe como parámetros la ruta de un fichero que contiene el script, una cadena con el script o un array de cadenas conteniendo cada una línea del script. Como salida genera una colección de palabras o componentes léxicos. Para cada uno de ellos se proporciona la siguiente información:

• Palabra en si tal y como aparece en el script
• Tipo de componente léxico
• Componente sintáctico con que se corresponde y que será utilizado posteriormente por el analizador sintáctico
• Linea y columna del script en la que aparece la palabra. Utilizado para mostrar los errores resaltándolos en el código del script y notificar en que punto se ha producido el posible error.

El analizador reconoce los siguientes componentes léxicos:

• Identificador
• CTE_Cadena
• CTE_Numerica
• CTE_Logica
• Palabra_Reservada
• Simbolo_Especial ",", "(" y ")"
• Operador
• Salto_Linea
• Fin_Fichero
• Erronea

La siguiente entrada del analizador léxico:

n1 "hola" "hño l!'a" "\\as" "ac\\as\"11\"22\"dd fas" c2
fin
variable 3 * a verdadero Y
fas"dfas "as"asf"
"a\aas" 1234.34
c3 c3 "AAAA BB
CC"
"fasdfs\"
numerica 3 / 456 <> != 3 O
fadvariable c3
si
falso
cadena
( , 3 )


produce la siguiente salida:

Creando un analizador léxico (Parte I)

Este artículo versa acerca del desarrollo de un analizador léxico. Debido a su tamaño ha sido dividido en dos partes, siendo este la primera parte y esta la segunda.

La función de un analizador léxico es examinar el código fuente y reconocer las palabras o tokens que formen parte del lenguaje así como determinar si hay elementos que no pertenecen al lenguaje. Como resultado del análisis léxico se devolverá la lista de tokens que forman el código fuente.

Lo primero que debemos hacer es definir los tipos de palabras que compondrán el lenguaje así como las reglas para formar palabras

En el lenguaje que estoy creando he identificado los siguientes tipos de palabras:

• Identificadores
• Cadenas
• Valores o constantes numéricas
• Valores o constantes lógicas
• Palabras reservadas
• Símbolos especiales como ",", "(" y ")"
• Operadores
• Saltos de línea
• Fin de fichero

Dicho lenguaje pretende ser bastante sencillo y fácil de utilizar. Por ello se utilizan palabras en castellano en vez de en ingles como la mayoría de lenguajes de programación.

Ahora pasaremos a definir las reglas de formación de cada uno de esos tipos de palabras. Hay tipos de palabras que se definen por enumeración como son los operadores, los símbolos especiales, las palabras reservadas, etc. Para definir otros tipos de tokens utilizaremos autómatas finitos deterministas como ya se explico en el artículo Autómata finito determinista para reconocer constantes numéricas.

Definiciones

• Operadores:
• + , -, *, /, =, !=, <, >, >=, <=, Y, O
• Palabras reservadas:
Variable: para declarar variables
Constante: para declarar constantes
Logica: tipo de dato
Cadena: tipo de dato
Numerica: tipo de dato
Si: Forma parte de la estructura condicional
Entonces: Forma parte de la estructura Condicional
Fin: Forma parte de la estructura Condicional e Iterativa
Mientras: Forma parte de la estructura Iterativa
• Símbolos especiales:
(, ) y ,
• Constantes lógicas:
Verdadero, Falso
• Constante cadena:
Secuencia de caracteres delimitados por las comillas (“) Si la cadena contiene el carácter “ o \ debe ir precedido del carácter de escape \

A.F.D. Reconocedor de cadenas.
• Constante numérica:
Una constante numérica debe estar formada por al menos un dígito, puede ir precedida o no por el signo y puede tener o no decimales. Si contiene el punto decimal debe tener al menos un dígito en la parte de los decimales.

A.F.D. Reconocedor de ctes numéricas.
• Identificadores:
Una letra seguida una secuencia de 0 o más letras o dígitos o el signo _

A.F.D. Reconocedor de identificadores.

Continuación
Creando un analizador léxico (Parte II)

En este breve artículo voy a explicar el proceso de creación de un sencillo autómata finito determinista para reconocer constantes numéricas. Este autómata forma parte del analizador léxico que estoy implementando para el lenguaje de script, que utilizaré en el motor de aventuras gráficas que estoy desarrollando.

Al final del artículo incluiré el código del autómata en su totalidad.

Lo primero que debemos hacer es definir lo que será una constante numérica valida. Una constante numérica debe estar formada por al menos un dígito, puede ir precedida o no por el signo y puede tener o no decimales. Si contiene el punto decimal debe tener al menos un dígito en la parte de los decimales.

Se trata de un autómata conexo ya que todos los estados son accesibles desde el inicial. Es un autómata determinista, ya que desde un estado y para una determinada entrada solo existe transición a un estado, nunca a varios estados.

Una vez definida la constante numérica formalmente mediante el diagrama de estados anterior, la implementación del autómata es muy sencilla. Debemos definir cuales serán los estados finales (aquellos marcados con un doble circulo en la imagen) y que transiciones son válidas para cada estado según las entradas que reciba y cuales no. Una vez procesados todos los caracteres que forman la palabra, la habremos reconocido como una constante numérica correcta, si no se ha producido ninguna transición no válida y si estamos en uno de los estados finales.

Para el motor de aventuras gráficas que estoy desarrollando he creado un pequeño editor de áreas que hace uso de las funciones de una librería matemática que estoy creando para manejar polígonos, puntos, ángulos, vectores, etc.

Este editor de momento permite crear fácilmente áreas con lados comunes, simplemente haciendo click en el formulario sucesivamente para definir cada uno de los puntos que forman el polígono. Muestra todas las áreas adyacentes a una de ellas, lo cual me es útil para probar la librería matemática. Los polígonos podrán tener cualquier número de lados y ser cóncavos o convexos.