Como construir un analizador de expresiones, la gramática

Cuando estamos trabajando con funciones matemáticas, resulta muy conveniente disponer de un parser, o analizador de expresiones, que nos permita escribir e interpretar diferentes versiones de las ecuaciones que deben ser procesadas por el programa, en lugar de tener que modificar y recompilar el código para adaptarlo a dichos cambios cada vez. En esta serie de artículos voy a mostrar cómo construir un sencillo pero potente analizador, que puede ser extendido fácilmente para tratar con expresiones más sofisticadas, empezando por definir en este artículo la teoría básica necesaria para encarar con éxito este tipo de desarrollos.

En primer lugar, debemos hacer una distinción entre compiladores e intérpretes. Un intérprete procesa la expresión y la ejecuta al terminar, devolviéndonos el resultado, mientras que un compilador la procesa y la transforma en algo que podemos ejecutar después todas las veces que queramos, existiendo la posibilidad de modificar los valores de los parámetros que pudiera tener la expresión.

Normalmente un compilador produce código ejecutable, pero esta no es la única posibilidad para transformar la expresión o expresiones tratadas. El programa que voy a ofrecer en esta serie transforma la expresión en una serie de objetos que después pueden ser utilizados para trabajar con la fórmula en un formato parametrizable y ejecutable.

En cualquier caso, el primer paso necesario para construir un analizador sintáctico es definir una gramática apropiada para el lenguaje que vamos a utilizar. Esta gramática debe estar diseñada de manera que presente unas propiedades básicas que nos faciliten escribir el programa de la forma más sencilla posible.

Empecemos por definir una notación para las reglas gramaticales. Para ello usaremos la conocida notación BNF (Backus-Naur Form), que nos permite diseñar una serie de reglas para pasar de un objeto genérico (por ejemplo, una expresión), a un objeto concreto bien construido (por ejemplo, la expresión 10*x +y).

Supongamos que todas nuestras expresiones van a ser siempre de la forma n*v1+v2, donde n es un número cualquiera entre 0 y 9, y v1 y v2 son dos posibles variables diferentes, que pueden o no aparecer en la expresión. De esta forma, las expresiones posibles serán n*v1+v2, n*v1, n*v2, v1 y v2.

Los componentes de la gramática que necesitan ser definidos descomponiéndolos en otros más simples se denominan símbolos no terminales, y se representan escribiéndolos entre los caracteres < y >, por ejemplo:

<expresión>

Para formar una regla de descomposición de un símbolo no terminal, usamos el símbolo ::=, y a su derecha indicamos los elementos en los que se descompone el elemento de la izquierda. Si existen varias posibilidades, las indicamos todas, separándolas con el carácter |. En nuestro ejemplo:

<expresión>::=<número>*<variable><restoexpresión>|<variable>

El símbolo * se denomina terminal, ya que queda definido directamente y forma parte de la expresión real, por lo que no es necesario crear una regla de derivación para descomponerlo. Un símbolo terminal también se llama token, y puede estar compuesto por más de un carácter.

Para los símbolos no terminales de la parte izquierda, debemos crear nuevas reglas hasta que todas ellas finalicen en símbolos terminales, por ejemplo, para <número>:

<número>::={1,2,3,4,5,6,7,8,9}

Que nos podría dar problemas con la expresión 5*x, que es correcta, si elegimos la primera de las reglas de la parte derecha para analizar, en lugar de la segunda. Esto lo hemos evitado añadiendo otra regla, <restoexpresión>, que cubre las dos posibilidades, que después del símbolo x venga un signo +, o bien que se acabe ahí la expresión.

Por último, otra propiedad a evitar en el diseño de la gramática, es lo que se conoce como recursividad a la izquierda. Esto consiste simplemente en no utilizar reglas de la forma:

<S>::=<S>+<X>

La forma de evitarlo es sencilla, pero no trivial, así que, para no alargar mucho el artículo y pasar directamente a la gramática que voy a usar en el analizador, os dejo este enlace sobre eliminación de la recursividad a la izquierda.

Diseño de una gramática para expresiones simples

Voy a diseñar una gramática que permitirá analizar expresiones con las siguientes características:

Se pueden usar números con decimales.
Se pueden definir constantes utilizando un determinado conjunto de caracteres.
Las constantes no pueden empezar por un número o por las letras x, y o z.
Se pueden utilizar tres posibles variables, X, Y y Z.
Se admiten los operadores binarios suma (+), diferencia (-), producto (*), división (/) y exponenciación (^).
Se admite el operador menos unario (-).
Se pueden construir subexpresiones encerrándolas entre paréntesis.

Además, el analizador deberá tener en cuenta las siguientes condiciones:

Las expresiones encerradas entre paréntesis y el menos unario tienen la mayor precedencia (es decir, se ejecutan antes que cualquier otro operador en caso de duda).
El siguiente nivel de precedencia lo tiene la exponenciación.
A continuación, el producto y la división.
Por último, la suma y la diferencia son los operadores de menor precedencia.

Para empezar, vemos que la regla de mayor rango será la que defina las expresiones, y que, por debajo de esta, debemos tener reglas para definir números, constantes y variables. Vamos a diseñar la gramática siguiendo este enfoque.

Definición de los números

Las reglas gramaticales con las que defino los números son las siguientes:

<number>::=<digit><rnumber>|<decimalsep><rdecimal> <rnumber>::=<digit><rnumber>|<decimalsep><rdecimal>|<void> <rdecimal>::=<number><fdecimal> <fdecimal>::=<number><fdecimal>|<void> <digit>::={0,1,2,3,4,5,6,7,8,9} <decimalsep>::={“,”,.}

Por la primera regla vemos que un número debe comenzar por un dígito o por un separador decimal, lo que nos permite decidir solo examinando el primer carácter de la cadena si estamos o no ante un número. Con la regla <rnumber> definimos el resto del número, que pueden ser más cifras, un separador de decimales seguido de más números o terminar con la primera cifra.

La regla <rdecimal> fuerza a que después de un separador de decimales exista al menos un número, y <fdecimal> impide que pongamos otro separador decimal adicional. En esta gramática permito usar como separador decimal el punto (.) o la coma (,) indistintamente.

Definición de las variables y las constantes

La definición de las variables es más sencilla. Como solo consisten en una letra, nos basta con una sola regla:

<var>::={x,y,z}

Las constantes, sin embargo, pueden consistir en más de una letra o número, por lo que necesitamos más de una regla para definirlas:

<const>::=<letter><rconst> <rconst>::=<allchar><rconst>|<void> <letter>::={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w} <allchar>::={0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,g,h,i,j, k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}

He definido dos conjuntos de caracteres, <letter> para la letra inicial, y <allchar> para el resto del nombre de la constante, que puede contener números o las letras x, y y z.

El símbolo <void> no debe interpretarse como que la cadena de entrada se deba terminar al final de la constante, sino que significa que, si no encontramos un carácter válido, podemos considerar que ya hemos terminado con la constante. Alguna regla de mayor nivel que esta se ocupará de decidir si es un carácter valido.

Definición de las expresiones

Por último, queda definir la entidad de mayor nivel, la expresión. Puesto que existen unas reglas de precedencia de operadores, es una buena idea reflejarlas en la gramática, ya que esto facilitará la implementación del programa, pues la expresión se compilará de forma natural siguiendo estas reglas y no tendremos que implementar ninguna lógica adicional.

Esto lo vamos a conseguir dividiendo las reglas que implican los distintos operadores en varios niveles, el más inferior de los cuales definirá los elementos de mayor precedencia:

Vemos que el nivel de mayor precedencia es <element>, el que define las expresiones entre paréntesis y los números, constantes y variables de la expresión.

De esta manera, vamos descendiendo desde el nivel más alto, <expr> hasta llegar al nivel más bajo que podamos encontrar y le damos preferencia a esta regla sobre los niveles superiores.

En el próximo artículo, explicaré la implementación de un analizador de expresiones utilizando esta gramática.

Si quieres profundizar más en el tema del análisis sintáctico y definición de gramáticas, te puedo recomendar estos libros: