Menu:

Sponsor

Discover Master of Alchemy, our first iPad/iPhone and iPod touch game!

Follow Me

 

Forum's topics

Latest Files

Archives

Top Rated

Categories

Photo Gallery


Gabriele Farina on April 19, 2008 in actionscript

Runtime expression evaluation in ActionScript

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.

You can download the example here

 

Bookmark and Share

 

 

23 comments
Hi, actually you can just pass one argument to a function call, but you can easily modify the parser to accept multiple parameters.
Hi dear. Nice work, but i have one doubt: how can I use 2 arguments in a function? Each time that a try to use 2 parameters with a function, the following message show: Error: Unexpected token COMMA. What is wrong? Thanks
I don't suppose you previously had this library done in AS2...? If so, could you please provide a link. Awesome library by the way.
excelent lib, exactlly what i was looking. thanks
Hi, the easiest way to create a parser from the grammar you gave is to use a parser generator. Actually there are only 2 parser generators I know for AS: one is Antlr 3.1, and the other one is the porting of Yacc I made to create the code you can see in this post:
http://www.sephiroth.it/weblog/archives/2008/05/top_down_or_bottom_up_for_expression.php
I'm going to release the tool, even if it is not complete and it is based on a quite old version of Yacc.
However it generates quite fast parsers; I used it for some projects at alittleb.it, and it works well.
This is very good! However I have one question. I have a sample grammar, for example: "expression: Number,Operand,Number \r" + "Number : '-'? [0-9]+\r" + "Operand : MUL | DIV | ADD | SUB\r" + "MUL : '*'\r" + "DIV : '/'\r" + "ADD : '+'\r" + "SUB : '-'\r" I want to parse this make a table driver parser that I can use during runtime. Can you please comment on this ? I just need a direction to start in
The source code to generate the graph is already included in the sources you can download from here: http://www.sephiroth.it/weblog/archives/files/actionscript/ExpressionParser.tgz
How did u make the graph? its great! can you please post the code for generating this graph ?
In this example the grammar is hardcoded inside the code because the parser is manually implemented used a recursive descent parser. If you want to look at the grammar of the expression, you can read this post: http://www.sephiroth.it/weblog/archives/2008/05/top_down_or_bottom_up_for_expression.php I'm going to release the custom Yacc version I used to generate the code used in the second example, if you want to wait.
" given a defined Grammar " where is the defined grammar here ?
I cannot seem to find your grammar definition. Is it hardcoded ?
It seems that antlr 3.1 will support actionscript too as a compiler target, this is really interesting news :) http://www.antlr.org/wiki/display/ANTLR3/Code+Generation+Targets
Nice description of parsing, I'll check out the lib since I love parsing algorithms. I wrote an excel like parser for ActionScript using ANTLR here: http://arcanearcade.blogspot.com/2008/04/using-antlr-to-create-excel-like.html I also wrote a parser that used the shunting yard algorithm and RPN, but can't share that one (someday I'll rewrite it since the algorithms are public knowledge but I do link a paper on it.)
Hi Zwetan,

I'll give a look at that code, but later today or tomorrow I'll publish an alternative library that should work faster (bottom up parsing with direct expression evaluation), and may be also used in production.
Hi Gabriele, nice lib :) the topic is very interesting, if you want to see another way of doing it (top-bottom parsing and reverse polish notation) check this out http://code.google.com/p/maashaack/source/browse/trunk/ES4a/src/system/evaluators/MathEvaluator.as and some tests http://code.google.com/p/maashaack/source/browse/trunk/ES4a/tests/ES4a_core/system/evaluators/MathEvaluatorTest.as RPN (or postfix) for math expression save a lot of time in the parsing, even if it look a little bit more crude ;)
Hi Tyler, I'm not discouraged at all ;). I'm working on other posts about this topic that will hopefully improve the library to a version that will be usable for production. Right now my goal is not to have a small scripting language interpreter (or compiler) that can be used to script Flash websites, but this may be a task I should add to my list. First of all, anyways, let's focus on expressions evaluation. There is much more to say about that :)
Don't get discouraged, this project has been around for a long while with no activity. The big difference between it and yours is that yours is light weight and less likely to crash everything. The other project is wicked cool but your is far more practical to be added to running websites. It will be great for script tags in my project htmlwrapper and many other things that need something a little more dynamic.
No it is not my project, hehe. Greetz Erik
Oh well, the library seems interesting, but my goal is to start discussing about this topic from a teorical point of view, not creating a fully functional expression evaluator. I'll give a look at your code anyway (I guess it's yours - maybe not), thanks for telling me about this library!
Interesting post. Are you aware of this project: http://eval.hurlant.com/ Greetz Erik
Hi Tyles, the code can be improved a lot. My first goal was to start talking about this topic form a simple point of view, but I'm working on many interesting improvments that will be discussed in the future. The topic has a lot of implications and I've quite a lot of interesting stuff to show you guys :) I'm happy you found the post interesting ;)
This is amazing and a much better way of dealing with these issues then the alternatives that I have seen. Thanks for putting the time into this, it is really great.

The great thing about this is how you are securing what can be called by giving a context look up table but this isn't perfect for things that want to be open to call anything. Not sure how I feel about it.

Similarly Have you thought about instantiating new classes? There are some tricky things about this but getDefinition works really well.
Hi Gabriele, nice Library, exactlly what i was looking for 2 month ago ... :-( but i m very interested in you lib. for all readers which need more than just math expressions i have two hints: http://eval.hurlant.com/ and http://www.riaone.com/deval/ two nice mighty libs for evaluating expressions. bye and have a nice day.


Post a comment

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)


Type the characters you see in the picture above.





 

TrackBacks

TrackBack URL for this entry: http://www.sephiroth.it/cgi-bin/mt/mt-tb.cgi/240

Listed below are links to weblogs that reference Runtime expression evaluation in ActionScript:

» Expressions evaluation at (almost) native speed from sephiroth.it - flash & php
Finally I found a bit of time this weekend to do some other tests with expressions evaluation. The results are pretty interesting, even if obvious from some point of view. I took the ExpressionEvaluator I wrote as example for the... [Read More]

» Top Down or Bottom Up for Expression Evaluation ? from sephiroth.it - flash & php
Last time I wrote about Top Down parsing, a technique for parsing that can be easilly implemented manually using function recursion. Today it is time to talk about one of the other ways of parsing, called Bottom Up parsing.... [Read More]