Expression Parser

`loop.compiler.Expression`

Class of objects that parse simple expressions composed by values and operands with precedence. The operands are always parsed from left to right. Many restrictions are imposed to the expression grammar, however this class is useful to implement simple expressions evaluators when Lua expressions are too expressive (i.e. control structures or first-class functions may lead to undesirable situations) or to create compilers of simple expressions. All operators are parsed accordingly to their precedence that may be overhidden by the use of round brackets.

Each object is created with lists defining the format of each valid value, format of operators (i.e. operator symbol and relative position of operands) and evaluation precedence. The object also must provide an operation for each operator that will be called whenever the operator is parsed. The same is true for values that are parsed by specific operations defined in the object instance.

Behavior

Initialization

Expression([object])

Creates an expression parser that parses expression of a given grammar. The grammar is specified by field of the table object that will become the Expression instance. These fields define operator format and precedence and format of values. The resulted grammar is very restricted. For further information see section Remarks. Below, there is a description of the informations that should be provided as fields of table parser. These informations should be provided at creation time only and should not change later.

values

Field that contains a table that maps the name of each value valid in the expression to a Lua pattern that matches the strings that represent these values. The pattern must define a capture of the substring necessary for the evaluation of the value.
Example:

values = {
 number = "(%d*%.?%d+)",
 string = "'([^']*)'",
 name = "([%a_][%w_]*)",
}

operators

Field that contains a table that maps the name of each operator to a string that contains the format of the operator. All non-space characters of the format are considered as operator delimiters and each space caracter is considered as the positions of operand values. For example, the following strings specifies the binary operator '+' in prefixed, infixed and posfixed forms respectively: '+ ', ' + ', ' +'.
Example:

operators = {
 invert = "- ",
 sum = " + ",
 subtract = " - ",
 multiply = " * ",
 divide = " / ",
}

precedence

Field that contains an array of lists containing the names of each valid operator. The lists should be arranged in the array in increasing order of precedence, therefore higher the index of a list in the array the first those operators will be parsed in each expression. All the operators in a list of a particular position in the array are evaluated in order of occourence in the expression from left to right.
Example:

precedence = {
 {"sum","subtract"},
 {"multiply","divide"},
 {"invert"},
}

Methods

evaluate(expression [, start])

Parses the expression in string expression stating at index start. If not value is provided for start the parsing starts from first character. Whenever a value or operand is parsed a particular method of the objet is invoked to properly evaluate the value or operator construction. The name of the called method is the same name of the value or operator, i.e. names previously provided by fields values and operators of the table provided at object creation. Below, there is a description of the methods called and the values they should return. All these methods are not defined by class Expression and must be provided by the object instance.

Value methods: Each value of the expression is evaluated by a method which name matches the name of the value. This method is called with the string captured by the pattern defined for that value and should return some Lua value that represents the parsed value.
Operator methods: Whenever an operator and all its operands are parsed the method which name matches the name of the operator is called. The arguments of this call are the values of all the operands that were previously returned by other calls of value methods or operator methods. The operand values are provided as arguments of the call in the same order of occurence in the expression, i.e. from left to right.

Remarks

The symbols '(' and ')' are reserved for precedence overhidding and should not be used in value or operand representations.
The patterns of values should not match any operator delimiter, otherwise the parsing behavior is not defined.
If patterns of values present intersections there is no garantee which kind of value will be matched.
Operands of a given operator cannot be expressions with operators of lower or same precedence, except if the first operand occurs before any operator delimiter, in such case the first operand may be an expression with operators of the same precedence. To allow such construction, the operand expressions must be delimited by round brackets, i.e. '(' and ')'.
The parsing process is slow, therefore should not be used for very long expressions.

Examples

Meta-circular expression solver

local Expression = require "loop.compiler.Expression"
local solver = Expression{
 values = {
 number = "(%d*%.?%d+)",
 variable = "([%a_][%w_]*)",
 },
 operators = {
 invert = "- ",
 absolute = "| |",
 sum = " + ",
 subtract = " - ",
 multiply = " * ",
 divide = " / ",
 power = " ^ ",
 apply = " ",
 },
 precedence = {
 {"sum","subtract"},
 {"multiply","divide"},
 {"power"},
 {"invert"},
 {"absolute"},
 {"apply"},
 },
}
function solver:number (value) return tonumber(value) end function solver:variable(name) return self.vars[name] or math[name] end function solver:invert (op) return -op end function solver:absolute(op) return math.abs(op) end function solver:sum (op1, op2) return op1 + op2 end function solver:subtract(op1, op2) return op1 - op2 end function solver:multiply(op1, op2) return op1 * op2 end function solver:divide (op1, op2) return op1 / op2 end function solver:power (op1, op2) return op1 ^ op2 end function solver:apply (f,arg) return f(arg) end function calculate(expr, vars)
 solver.vars = vars
 return solver:evaluate(expr)
end
-- calculate and show the roots of a quadratic equation local vars = { a = 3, b = -6, c = 6 }
vars.d = calculate("b^2 - 4*a*c", vars)
local r1, r2
if vars.d >= 0 then
 r1 = calculate("(-b + sqrt d) / (2*a)", vars)
 r2 = calculate("(-b - sqrt d) / (2*a)", vars)
else
 local r = calculate("-b/(2*a)", vars)
 local i = calculate("|( sqrt(-d)/(2*a) )|", vars)
 if i == 1
 then r1, r2 = "i", "-i"
 else r1, r2 = i.."i", (-i).."i"
 end
 if r ~= 0 then r1, r2 = r.."+"..r1, r..r2 end end local msg = "The roots of (%d*x^2 + %d*x + %d) are"
print(msg:format(vars.a, vars.b, vars.c), r1, r2)