Como construir un analizador de expresiones, implementación (I)
En el artículo anterior de esta serie hice un repaso de las principales cuestiones acerca del diseño de la gramática para construir un analizador o parser para expresiones aritméticas. En este artículo voy a mostrar la primera parte de su implementación a partir de las reglas BNF de la gramática, convirtiendo la expresión de entrada, en forma de cadena de texto, en una serie de objetos que podremos utilizar para evaluarla, pudiendo dar diferentes valores a las constantes y variables que la componen.
Si prefieres comenzar por el principio, este es el enlace al artículo sobre el diseño de la gramática para un analizador de expresiones.
En este enlace puedes descargar el descargar el código fuente del proyecto con el parser que utilizaré como ejemplo en este artículo, escrito en CSharp con Visual Studio 2013.
El parser que voy a implementar funcionará como un compilador que generará como resultado un objeto ejecutable y parametrizable que nos permitirá evaluar la expresión modificando el valor de sus parámetros, las constantes y las variables. El código se encuentra en el proyecto Expressions, que genera una librería de clases que se puede enlazar como referencia para ser utilizado desde cualquier aplicación.
Definición de una clase base para el analizador
En primer lugar, defino una clase base abstracta de la que derivarán todos los restantes elementos, de manera que se pueda acceder a todos ellos usando el mismo interfaz, la clase ExpressionBase:
public abstract class ExpressionBase
{
protected static int _precision = 10;
protected static List<Variable> _variables = new List<Variable>();
protected static List<Constant> _constants = new List<Constant>();
public ExpressionBase(){}
public static int Precision
{
get { return ExpressionBase._precision; }
set { ExpressionBase._precision = Math.Min(20, Math.Max(1, value)); }
}
public IEnumerable<Variable> Variables
{
get { foreach (Variable v in ExpressionBase._variables)
{ yield return v; } }
}
public IEnumerable<Constant> Constants
{
get { foreach (Constant c in ExpressionBase._constants)
{ yield return c; } }
}
public static void Clear()
{
_variables.Clear();
_constants.Clear();
}
public abstract double Value { get; set; }
public virtual string Parse(string expr)
{
return expr.TrimStart(new char[] { ' ', '\n', '\r', '\t' });
}
}
Declaro una colección estática de variables y otra de constantes, de manera que todas las expresiones compartan las mismas, lo que nos permitirá trabajar con sistemas de ecuaciones. A estas colecciones se accede a través de las propiedades de instancia Variables y Constants, mediante las cuales podremos enumerarlas usando una instrucción foreach. Estas colecciones se pueden vaciar utilizando el método Clear.
Puesto que todos los valores serán de tipo double, también defino una precisión para evitar errores de redondeo utilizando la función Math.Round al devolver los resultados de las operaciones.
Todas las clases derivadas deberán implementar la propiedad abstracta Value, mediante la cual asignaremos valores a las constantes y variables y obtendremos el valor de todos los objetos que compone la expresión para realizar las operaciones aritméticas.
Por último, el método Parse se encargará de ir analizando la expresión. En la clase base lo único que hace es eliminar los espacios en blanco y los saltos de línea hasta llegar al siguiente caracter evaluable. Este método deberá devolver el resto de la cadena de entrada una vez que la clase haya extraído el elemento en el que está especializada.
Ahora queda decidir, de entre todas las reglas de la gramática, cuales vamos a elegir para definir las clases de elementos. Cada elemento deberá trabajar con una regla principal y todas las reglas derivadas. En este caso, he dividido las reglas en cuatro grupos, números, constantes, variables y expresiones, que dan lugar a otras tantas clases.
Las clases que componen el parser utilizarán dos excepciones, definidas en el módulo Exceptions, para indicar un error de sintaxis (BadSyntaxException) y para rechazar una cadena de entrada si no cumple con las reglas de la clase para que se pueda intentar otra alternativa (NotRecognizedException).
La clase Number
Esta clase será la que se encargue de analizar los números. Como recordatorio, estas son las reglas BNF de la gramática mediante las que se define la sintaxis:
<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>::={“,”,.}
La regla <number> es la que da lugar a la clase, mientras que <rnumber>, <rdecimal> y <fdecimal> se implementarán como funciones dentro de la clase.
En el método Parse comenzamos a analizar desde la regla <number>, comprobando si el primer caracter es un número o un separador decimal:
public override string Parse(string expr)
{
string snum = base.Parse(expr);
if (string.IsNullOrEmpty(snum)) { throw new NotRecognizedException(); }
if (char.IsNumber(snum, 0))
{
_value = Convert.ToDouble(snum[0].ToString());
if (snum.Length > 1)
{
return RNumber(snum.Substring(1));
}
return "";
}
else if ((snum[0] == ',') || (snum[0] == '.'))
{
if (snum.Length > 1)
{
_value = 0;
_decimalpos = 1;
return RDecimal(snum.Substring(1));
}
throw new BadSyntaxException(snum);
}
throw new NotRecognizedException();
}
En función de que el primer caracter sea un número o un separador decimal, tomaremos la decisión de continuar por la regla <rnumber> o <rdecimal>. El valor del número lo iremos calculando en la variable _value, ayudados por la variable _decimalpos para calcular la parte decimal.
En el método RNumber iremos añadiendo las cifras al valor del número de forma recursiva hasta encontrar el final o bien un separador decimal, para continuar con la regla <rdecimal>:
private string RNumber(string expr)
{
if (char.IsNumber(expr, 0))
{
_value = (10 * _value) + Convert.ToDouble(expr[0].ToString());
if (expr.Length > 1)
{
return RNumber(expr.Substring(1));
}
return "";
}
else if ((expr[0] == ',') || (expr[0] == '.'))
{
if (expr.Length > 1)
{
_decimalpos = 1;
return RDecimal(expr.Substring(1));
}
throw new BadSyntaxException(expr);
}
return expr;
}
En el método Rdecimal, simplemente comprobaremos que el siguiente caracter sea un número, para pasar a analizar el resto de las posiciones decimales a partir de la regla <fdecimal>:
private string RDecimal(string expr)
{
if (char.IsNumber(expr, 0))
{
_value += Math.Round(Convert.ToDouble(expr[0].ToString()) /
(10 * _decimalpos), ExpressionBase._precision);
_decimalpos++;
if (expr.Length > 1)
{
return FDecimal(expr.Substring(1));
}
return "";
}
throw new BadSyntaxException(expr);
}
Por último, en el método FDecimal terminaremos de calcular el valor de la parte decimal del número recursivamente:
private string FDecimal(string expr)
{
if (char.IsNumber(expr, 0))
{
_value += Math.Round(Convert.ToDouble(expr[0].ToString()) /
(10 * _decimalpos), Precision);
_decimalpos++;
if (expr.Length > 1)
{
return FDecimal(expr.Substring(1));
}
return "";
}
return expr;
}
La clase Variable
Con esta clase implementaremos las variables de la expresión, según la regla de la gramática:
<var>::={x,y,z}
Como las variables se almacenan en una colección de la clase, he implementado los interfaces IComparable e IEquatable para poder comprobar si la colección ya contiene la variable que hemos encontrado, y, en caso contrario, añadirla. Dos variables serán iguales si tienen el mismo nombre, el cual se almacena en la variable _name. El interfaz IComparable nos permite además ordenar la colección.
Este elemento es muy fácil de identificar, simplemente se compone de una de las letras x, y o z, no distinguiremos entre mayúsculas y minúsculas:
public override string Parse(string expr)
{
string svar = base.Parse(expr);
if (!string.IsNullOrEmpty(svar))
{
if ((char.ToLower(svar[0]) >= 'x') && (char.ToLower(svar[0]) <= 'z'))
{
_name = svar.Substring(0, 1).ToLower();
if (!ExpressionBase._variables.Contains<Variable>(this))
{
ExpressionBase._variables.Add(this);
}
if (svar.Length > 1)
{
return svar.Substring(1);
}
return "";
}
}
throw new NotRecognizedException();
}
La clase Constant
Para terminar este artículo, vamos a ver cómo construir la clase Constant para analizar las constantes, basadas en este conjunto de reglas:
<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}
De nuevo, la clase implementará la regla principal, <const>, y la secundaria, <rconst> la implementaré en forma de función. Esta clase también implementará los interfaces IEquatable e IComparable, al igual que en las variables, por las mismas razones.
El método Parse comprueba en primer lugar si el siguiente caracter es una letra válida, y, en caso de haber más caracteres, llamará a la función RConst para construir el resto del nombre de la constante:
public override string Parse(string expr)
{
string scon = base.Parse(expr);
if (!string.IsNullOrEmpty(scon))
{
if ((char.ToLower(scon[0]) >= 'a') && (char.ToLower(scon[0]) <= 'w'))
{
_name = scon.Substring(0, 1).ToLower();
if (scon.Length > 1)
{
return RConst(scon.Substring(1));
}
if (!ExpressionBase._constants.Contains(this))
{
ExpressionBase._constants.Add(this);
}
return "";
}
}
throw new NotRecognizedException();
}
Y la función RConst seguirá añadiendo caracteres mientras encuentre letras o números:
private string RConst(string expr)
{
if (char.IsLetterOrDigit(expr, 0))
{
_name += expr.Substring(0, 1).ToLower();
if (expr.Length > 1)
{
return RConst(expr.Substring(1));
}
expr = "";
}
if (!ExpressionBase._constants.Contains(this))
{
ExpressionBase._constants.Add(this);
}
return expr;
}
En el siguiente artículo mostraré como implementar las expresiones propiamente dichas. Mientras tanto, como en el artículo anterior, os dejo una lista de libros que os pueden ayudar a profundizar más en el tema:
