Como hacer un analizador de expresiones, implementación (II)
En el anterior artículo de la serie comencé a mostrar cómo implementar un analizador de expresiones aritméticas o parser a partir de las reglas de la gramática en notación BNF, con las clases encargadas de extraer los números, variables y constantes. En este artículo voy a terminar la serie con la clase encargada de analizar la regla principal, que analiza las expresiones en sí. También mostraré una pequeña aplicación de ejemplo que dibuja la gráfica correspondiente a la expresión a partir del objeto generado por el compilador.
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 código fuente del proyecto con el parser que utilizaré como ejemplo en este artículo, escrito en CSharp con Visual Studio 2013.
La clase Expression
La clase Expression es la de más alto nivel del parser. El compilador generará como resultado un objeto de este tipo, cuyas variables y constantes se podrán obtener para darles valores usando las propiedades Variables y Constants, y que se podrá evaluar leyendo su propiedad Value. Estas son las reglas BNF a partir de las cuales he construido la clase:
<expr>::=<expr2>+<expr>|<expr2>-<expr>|<expr2>
<expr2>::=<expr1>*<expr2>|<expr1>/<expr2>|<expr1>
<expr1>::=<expr0>^<expr1>|<expr0>
<expr0>::=-<element>|<element>
<element>::=(<expr>)|<number>|<const>|<var>
La clase representa la regla <expr>, el resto de reglas, <element>, <expr0>, <expr1> y <expr2>, se implementan como funciones dentro de la clase. Recordemos que he dividido las reglas que implican a los distintos operadores según su nivel de precedencia.
Los operandos de la expresión se guardan en las variables _operand1 y _operand2, y el operador en la variable _operator. Con la propiedad Value realizamos la operación correspondiente entre estos dos operandos:
public override double Value
{
get
{
if (_operand2 == null)
{
if (_operator == '-')
{
return -_operand1.Value;
}
return _operand1.Value;
}
switch (_operator)
{
case '+':
return Math.Round(_operand1.Value + _operand2.Value,
ExpressionBase._precision);
case '-':
return Math.Round(_operand1.Value - _operand2.Value,
ExpressionBase._precision);
case '*':
return Math.Round(_operand1.Value * _operand2.Value,
ExpressionBase._precision);
case '/':
return Math.Round(_operand1.Value / _operand2.Value,
ExpressionBase._precision);
case '^':
return Math.Round(Math.Pow(_operand1.Value, _operand2.Value),
ExpressionBase._precision);
default:
return double.NaN;
}
}
set
{
throw new NotSupportedException();
}
}
Con el método Parse comienza el análisis de la cadena de entrada y se procesan las operaciones de suma y diferencia:
public override string Parse(string expr)
{
string sexpr = base.Parse(expr);
if (!string.IsNullOrEmpty(sexpr))
{
_operand1 = Expression2(ref sexpr);
sexpr = base.Parse(sexpr);
while (!string.IsNullOrEmpty(sexpr))
{
if (sexpr[0] == ')')
{
return sexpr;
}
else if ((sexpr[0] == '+') || (sexpr[0] == '-'))
{
if (_operand2 != null)
{
_operand1 = new Expression(_operand1, _operand2,
_operator);
}
_operator = sexpr[0];
if (sexpr.Length > 1)
{
sexpr = base.Parse(sexpr.Substring(1));
_operand2 = Expression2(ref sexpr);
sexpr = base.Parse(sexpr);
}
else
{
throw new BadSyntaxException(sexpr);
}
}
else
{
throw new BadSyntaxException(sexpr);
}
}
if ((_operand2 == null) && (_operator != '-'))
{
Expression exp = _operand1 as Expression;
if (exp != null)
{
_operand1 = exp._operand1;
_operand2 = exp._operand2;
_operator = exp._operator;
}
}
return sexpr;
}
throw new NotRecognizedException();
}
En este método debemos detectar el final de una expresión entre paréntesis para que no se produzca un error de sintaxis. Este método puede devolver tanto una nueva expresión como un elemento simple, como un número, variable o constante, de manera que la expresión queda optimizada en los casos en los que el resto sea uno de estos elementos en lugar de una nueva expresión.
Con el método Expression2 se genera una expresión cuya operación es un producto o una división:
private ExpressionBase Expression2(ref string expr)
{
ExpressionBase operand1 = Expression1(ref expr);
ExpressionBase operand2 = null;
char op = '\0';
expr = base.Parse(expr);
while (!string.IsNullOrEmpty(expr))
{
if ((expr[0] == '*') || (expr[0] == '/'))
{
if (operand2 != null)
{
operand1 = new Expression(operand1, operand2, op);
}
op = expr[0];
if (expr.Length > 1)
{
expr = base.Parse(expr.Substring(1));
operand2 = Expression2(ref expr);
expr = base.Parse(expr);
}
else
{
throw new BadSyntaxException(expr);
}
}
else
{
break;
}
}
if (operand2 != null)
{
return new Expression(operand1, operand2, op);
}
return operand1;
}
Lo mismo para la exponenciación, en el método Expression1, y el menos unario, en el método Expression0. En el método de más bajo nivel, Element, empezamos intentando construir un número:
try
{
Number exnum = new Number();
expr = exnum.Parse(expr);
return exnum;
}
catch (NotRecognizedException ex) {}
Debemos capturar la excepción NotRecognizedException, para que no se produzca un falso error de sintaxis. También debemos comprobar del mismo modo si el siguiente elemento es una variable o una constante:
try
{
Variable exvar = new Variable();
expr = exvar.Parse(expr);
return ExpressionBase._variables[ExpressionBase._variables.IndexOf(exvar)];
}
catch (NotRecognizedException ex) {}
try
{
Constant excon = new Constant();
expr = excon.Parse(expr);
return ExpressionBase._constants[ExpressionBase._constants.IndexOf(excon)];
}
catch (NotRecognizedException ex) {}
Y, por último, comprobamos si se trata de una nueva expresión entre paréntesis:
if (expr[0] == '(')
{
if (expr.Length > 1)
{
expr = base.Parse(expr.Substring(1));
ExpressionBase expar = new Expression();
expr = expar.Parse(expr);
expr = base.Parse(expr);
if (!string.IsNullOrEmpty(expr))
{
if (expr[0] == ')')
{
if (expr.Length > 1)
{
expr = expr.Substring(1);
}
else
{
expr = "";
}
return expar;
}
}
}
}
Y con esto, ya tenemos completo el parser y podemos generar objetos ejecutables de la clase Expression. A continuación, mostraré como utilizar estos objetos con una sencilla aplicación que dibuja la gráfica correspondiente a la expresión y permite asignar valores a las constantes y variables de la misma.
La aplicación ExpressionPlayer
Esta aplicación de ejemplo se limita a compilar una expresión y representar la gráfica en dos dimensiones, con la variable principal en el eje de abcisas y uno o dos controles TrackBar para modificar el valor del resto de variables, en caso de que existan:
Una vez escrita la expresión, solo hay que pulsar el botón Parse para que el programa la intente compilar. En caso de que no esté incorrectamente escrita, obtendremos un objeto de tipo Expression:
Expression _expr = new Expression();
_expr.Parse(txtExpression.Text);
El programa creará controles en la barra de herramientas que nos permitirán asignar valores a las constantes y establecer un rango de valores para las variables, así como el paso entre dos valores sucesivos de la variable. Una vez establecidos estos valores, solo hay que pulsar el botón Play para que se dibuje la gráfica, y podemos modificar el valor de las variables secundarias utilizando los controles TrackBar, para comprobar cómo se modifica la forma de la gráfica.
Y esto es todo respecto a la implementación de un parser para trabajar con expresiones aritméticas. El código se puede extender para trabajar con expresiones más sofisticadas sin más que añadir nuevas reglas a la gramática e implementarlas en las clases apropiadas.
Como en los artículos anteriores, os dejo una lista de libros que os pueden ayudar a profundizar más en el tema:
