Finally I have a bit of free time to write down this post.
Some days ago a guy on the forum asked about how to evaluate at runtime simple mathematical expressions with support for symbols and function calls.

Now that the eval function have been removed from the language for reasons I’ve not enought time to talk about, we need to parse and execute those expressions manually.

I built a simple Actionscript library that can be used to parse mathematical expressions: it has support for function calls, for variables and it is able to convert the expression into a postfix rappresentation if you may need it. The expression parser is quite simple and have been built manually following some concepts related to programming language compilers; it includes a Scanner (or lexer – however you want to call it) to tokenize the expression, a Parser that convert the expression into an Abstract Syntax Tree and a simple routine that evaluates that AST using a Symbol Table as evaluation context.

There are no comments inside the code right now; I hope to find a little bit of time to write an in depth discussion about this topic. In the mean time you can continue reading the entry for a general explanation about how does the code works and for some examples that may be useful.

Here is a simple example that shows how does the code works:

import it.sephiroth.expr.CompiledExpression;
import it.sephiroth.expr.Parser;
import it.sephiroth.expr.Scanner;
public class Example
{
public static function run(): void
{
var expression: String = "sin( x / ( 8 / 2 + (-0.12 + 2.3) * x / x ) ) * 100";
var scanner: Scanner = new Scanner( expression );
var parser: Parser = new Parser( scanner );
var compiled: CompiledExpression = parser.parse();
var context: Object = {
x: 100,
sin: Math.sin,
cos: Math.cos
};
trace( 'Postfix:', compiled.toString() );
trace( 'Result:', compiled.execute( context ) );
}
}

Before I forgot, you can download the source code here with a simple example included.

Building an expression parser and evaluator is quite a simple task if you don’t plan to write a superfast library or a superpowerful engine. The steps are something like predefined and can be subdivided into tree groups:

• Lexical analysis
• Parsing
• Evaluation

My code simply follow those steps to make you able to evaluate an expression. Before starting with the code anyways it is really important to define a set of rules and functionalities our expression evaluator will include. This is foundamental because based on the features the operations performed during the tree steps above may vary.

In my code I simply want to accept integer and float numbers (float numbers defined using the simple dot syntax), negative numbers, variables, function calls, basic operations (subtract, add, multiply, divide and negate) and parethesis for grouping.

Lexical Analysis

During Lexical analysis the input string is analyzed to provide the parser a set of chunks, called tokens, that can be interpreted easilly by our code. The main goal of the lexical analysis is just to group togheter some characters and give them a meaning (for instance: 1 is a number, / the divide operation and so on), discarding the unuseful ones (like spaces). At this stage there is no validation of the input, because the lexical analyzer (Scanner.as) doesn’t know anything about how does the input will be interpreted.
The lexical analyzer generates a stream of tokens (Token.as) of different type (TokenType.as) which are then feeded to the Parser.

Parsing

The Parsing phase is one of the most important and is when the program starts to take a streams of token and give a meaning to a set of them. During this step the Parser (Parser.as) reads from the Scanner the tokens as needed and, given a defined Grammar, is able to group them togheter and understand if the input is grammatically correct or not.
In our sitatuation the grammar is implicit: the expression must be formatted correctly, every open parenthesis must match a closed one and function calls allows one or more arguments. When working on more complex parsers, the grammar may became much more complex (think about a whatever language parser for instance), and so the technique I used (called Recursive Descent Parsing) risk to become too difficult to use, too time and memory consuming. At this stage may be helpful to use parser generators, but I’ll talk about that the next time because I’ve something interestingto show you.
During this phase the input is validated but also other two really important tasks are performed: the first one is that all the identifiers found inside the input are recorded inside a Symbol Table (SymbolTable.as), than later will be filled at runtime with valid values for the indetifiers to execute the expression correctly. The second one is that the input is translated into an intermediate form that is easier for a computer language to deal with: the Abstract Syntax Tree (it.sephiroth.expr.ast.* package). The AST is a tree structure where each node rappresents a portion of code that then can be analyzed easilly using a tree walker or other means. When evaluating expressions an AST is not always useful because expressions evaluation may be performed using a stack based direct execution.

Evaluation

When the AST is ready, we are sure that the expression is syntactically valid and can be executed providing the right context. A context is simply the variables and functions that are needed by the expression to return a value, and are assigned to the identified included inside the Symbol Table. When the expression is executing, it requests from the symbol table the values needed. In my code the evaluation is performed by each AST node itself, but we may use also a tree walker to walk each node and execute it based on its type.

This is a super general introduction about how does the code works, hope to have a bit of free time to go more in depth about this. Just to show you something working, here is a simple Flex examples that plots an expression. The potting is not accurate, but the example can be used to give you an idea about how does the code may be used. With the separation provided, we will be able to replace the single parts of the code with improved versions, obtaining anyway a correct result.

Share with...