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 añadido en la sección de descargas el código fuente completo del Visor XML así como el ejecutable del mismo.

Esta herramienta me ha sido de gran utilidad para la depuración del árbol sintáctico y semántico generados por los respectivos analizadores.

Hace tiempo desarrollé un addin para el Visual Studio 2003 que incorporaba una nueva ventana de inspección al IDE que permitía explorar variables que tuvieran XML (tanto en una variable de tipo string como XMLDocument) y ver su contenido con esta herramienta y realizar búsquedas en el XML.

Este artículo es la continuación de:

Creando un visor de XML (Parte I)

POBLANDO EL TREEVIEW:

El proceso es muy similar al descrito anteriormente, salvo que ahora en vez de transformar el árbol en una cadena de texto formateada, se irán incluyendo sus nodos jerárquicamente en un TreeView.

Para poblar el TreeView también nos basaremos en dos funciones, una para inicializar las variables y cargar el documento xml, y otra que será llamada de forma recursiva.

COMPLETANDO LA HERRAMIENTA:

Con esto se habrá terminado el núcleo de nuestra aplicación, habiéndola dotado de la funcionalidad básica para la que se ideó, es decir, el mostrar el xml formateado para que resulte más legible, mostrarlo mediante un árbol y permitir seleccionar nodos mediante XPath visualizando aquellos que respondan a la expresión de búsqueda resaltados.

Vayamos ahora a dotarla de ciertos elementos adicionales para completar la aplicación.

En primer lugar le añadiremos la funcionalidad de permitir ajustar las líneas para que todo el texto de una línea se muestre en pantalla, ocupando las líneas que sean necesarias para mostrarse. Esto es tan sencillo como añadir un checkBox, y establecer la propiedad WordWrap de los RichTextBox al valor de la propiedad Checked del checkBox

Le añadiremos también la funcionalidad de cargar y guardar ficheros. Con este fin se crearán dos elementos de menú y se les asociarán teclas de acceso rápido, CTRL+C y CTRL+G respectivamente. El documento que guardaremos será el xml ya formateado, no el original.

Según vayamos cargando ficheros, éstos se irán incluyendo en la lista de recientes hasta un máximo de cinco. De igual forma incluimos en la lista de ficheros recientes aquéllos documentos que guardemos. El código que realiza esta inserción es el siguiente:

Cuando se cierre el formulario, se guardará la lista de ficheros recientes en un fichero XML, para que dicha listas persista entre ejecuciones de la aplicación.

Primera parte de este artículo:

Creando un visor de XML (Parte I)

En este artículo se describe el proceso de desarrollo de una pequeña herramienta que permitirá formatear un documento XML haciendo que resulte más legible, mostrarlo mediante un árbol, y seleccionar nodos mediante XPath visualizando aquéllos que respondan a la expresión de búsqueda resaltados. Adicionalmente se le añadirán otras características secundarias como el guardar y cargar ficheros, una lista de archivos recientes, ajuste de línea y expansión y contracción de todos los nodos del árbol. Es una herramienta sencilla pero que puede ser bastante útil para trabajar con XML.

Debido a sus dimensiones, este artículo ha sido dividido en dos partes. Se puede consultar la segunda parte en la siguiente dirección.

El resultado final de la aplicación mostrando sus tres vistas será el siguiente:

FORMATEANDO EL DOCUMENTO XML:

El código para formatear el texto se basa en dos funciones. La primera de ellas se llama FormatearTexto y se encargará de inicializar las variables, cargar el texto introducido en el primer RichTextBox en una variable del tipo XmlDocument. Esta primera función llamará a la segunda (IndentarXML), la cual es una función recursiva que se llamará así misma por cada nodo que tenga el arbol XML.

La función "FormatearTexto" recibe un parámetro que indica si se está realizando una consulta o no. Si es así, se obtendrán todos los nodos seleccionados por la consulta y se crearán dos arrayList para almacenar las posiciones iniciales y finales de los nodos seleccionados, para poder posteriormente resaltarlos en el RichTextBox.

La función "IndentarXML" se encarga de transformar el nodo en cadena formateada y de llamarse a si misma recursivamente por cada hijo que tuviera el nodo. El parámetro profundidad se va incrementando en uno en cada nivel del árbol, y sirve para tabular correctamente el texto de cada nodo. Si se esta consultando y el nodo actual pertenece a los nodos seleccionados por la consulta XPath, entonces se marcará su posición inicial y final añadiéndolas a los arrayList.

Continuación
Creando un visor de XML (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.

El clásico Arkanoid. Está desarrollado con Visual Basic.NET utilizando el framework 1.1. Este sencillo juego lo implementé a finales del 2004, después de finalizar el Tetris y me llevó muy poco tiempo. Consta únicamente de 727 líneas.

La nave puede ser manejada tanto con el teclado como con el ratón. Según destruyes ladrillos se va descubriendo una imagen tapada inicialmente por un telón negro y se van adquiriendo puntos. El jugador comienza con tres vidas que irá perdiendo cuando no consiga alcanzar la pelota con la nave. No consta más que de un nivel, aunque sería muy sencillo agregarle nuevos niveles.

Usa un único sonido que se reproduce al impactar la pelota contra los ladrillos y solo consta de tres imágenes: la pelota, la nave y el ladrillo (además de la imagen que se descubre a la derecha). Los gráficos se dibujan utilizando GDI+ con la técnica del doble buffer para evitar los molestos parpadeos. Soy conciente de las deficiencias de los gráficos, pero mis habilidades con el paint no dan para más.

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.

Para mostrar el código coloreado en el blog utilizo un plugin para el wordpress llamado iG:Syntax Hiliter. Este plugin es muy útil e interesante ya que permite colorear el código de múltiples lenguajes de programación. Sin embargo presenta una serie de deficiencias que he intentado solucionar.

Por un lado, es un poco incómodo leer el código en la ventana que se muestra ya que no suele caber todo y se necesita una barra de scroll horizontal lo que dificulta su lectura. Para solucionarlo le he realizado unas modificaciones para permitir abrir una nueva ventana del navegador con el código coloreado. En la parte superior izquierda del recuadro que muestra el código ahora aparece la opción "Maximizar", que abre una ventana de las mismas dimensiones que la pantalla con el código

Por otro lado, en el código en VB.Net, que es el que yo utilizo, no coloreaba correctamente muchas palabras. Así que también le hice unos cambios en el fichero que colorea el código en VB.Net.

Lo he probado en el Firefox y en el Internet Explorer y funciona correctamente, de todas formas si encontráis algún bug por favor comunicádmelo.

Lo podéis ver por ejemplo en los siguientes post:

Autómata finito determinista para reconocer constantes numéricas
Coloreando el código en el editor

Si alguien esta interesado en el plugin modificado que me lo pida y se lo envío. El plugin original se distribuye bajo la licencia GNU GPL, espero no infringirla. Si no es así por favor comunicádmelo.

El original se pueden encontrar en la siguiente dirección: iG:Syntax Hiliter

Se agradecen recomendaciones de otros plugins interesantes para el wordpress.

Este juego es considerado por muchos el mejor juego desarrollado en España. Fue toda una revolución cuando se publicó en el año 1988.

Esta basado en la novela "El nombre de la rosa" de Umberto Eco, de la que también se hizo una película. Inicialmente el juego iba a tener el mismo nombre que la novela, pero no pudo ser así por no llegarse a un acuerdo.

El juego se desarrolla en una abadía, donde nos meteremos en la piel de Guillermo de Occam y Adso. Con los cuales tendremos que participar en los distintos actos rutinarios que desarrollan los monjes en la abadía a la vez que investigamos una serie de crímenes a lo largo de los siete días en que se desarrolla la aventura.

Fue desarrollado por Paco Menéndez, todo un referente en el mundo de la programación de videojuegos y que lamentablemente ya no está entre nosotros. Los gráficos son obra de Juan Delcán.

Fué distribuido por Opera Soft y se publicaron versiones para MSX, Spectrum, Amstrad y posteriormente salieron versiones para PC, MSX 2 e incluso para la Game Boy Advance.

La dificultad es muy elevada y es muy complicado terminárselo sin hacer uso de las guías que se publicaron en su época.

Esta es la apariencia que tenía el juego en el MSX:

Hace poco tiempo ha salido al mercado una nueva versión, extremadamente fiel al original, para móviles. Esta versión esta desarrollada en J2ME.

De esta obra de arte se han hecho diferentes remakes y nuevas versiones debido al éxito que tuvo y el impacto que causó.

Unos links interesantes:

Visor java del mapa Applet de java que muestra el mapa de la abadía por pantallas.

Remake para PC

Proyecto en 3D basado en el juego original

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: