Runtime expression evaluation in ActionScript

http://albaghdadipenang.com/?p=building-network-security-dissertation 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 do risk assessment business plan evaluate at runtime simple mathematical expressions with support for symbols and function calls.

http://myvespagroup.com/?p=sql-online-training 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.

http://www.oalth.gr/bibliography-dissertation/ bibliography dissertation 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.

get 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.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 ) );
}
}

http://www.tempus-help.uns.ac.rs/?get-a-term-paper Before I forgot, you can download the source code here with a simple example included.

Pro Essay Writing Service Reviews

http://www.atelierfotografico.eu/chemistry-help-ionic-bonds/ 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:

check writing services 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.

go here 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

enter During Lexical analysis the http://www.ciplimemeprotezi.net/business-plan-writer-raleigh-nc/ business plan writer raleigh nc input string is analyzed to provide the parser a set of chunks, called online vs traditional education essays tokens, that can be do my research paper cheap 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 less expensive cialis tablets 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

http://bsqmgroup.com/?p=csulb-thesis-and-dissertation-office 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) phd thesis methodology reads from the Scanner the tokens as needed and, given a defined Grammar, is able to group them togheter and essay corrector online 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 marcarian masters thesis 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 http://fecom.es/creative-writing-assignments-for-college-students/ creative writing assignments for college students 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 personal statement writing the input is translated into an intermediate form that is buy tok essay online easier for a computer language to deal with: the Abstract Syntax Tree (it.sephiroth.expr.ast.* package). The microsoft windows vista home premium with sp2 (64 bit) 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 get expressions evaluation may be performed using a stack based direct execution.

Evaluation

http://kaya-izolasyon.com/?kinds-of-creative-writing kinds of creative writing When the AST is ready, we are sure that the expression is syntactically valid and can be executed providing the right http://impulsegcc.com/?p=biology-coursework-osmosis-help 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.

enter 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.

  • http://www.3solarbids.com/a-homework-helper/ a homework helper 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.

  • This is writing an essay for college application joke 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 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 😉

  • Erik

    Interesting post. Are you aware of this project:
    http://eval.hurlant.com/
    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!

  • Erik

    No it is not my project, hehe.
    Greetz Erik

  • 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.

  • 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 🙂

  • zwetan

    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 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.

  • 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.)

  • 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

  • Anonymous

    I cannot seem to find your grammar definition. Is it hardcoded ?

  • Torique

    ” given a defined Grammar ”
    where is the defined grammar here ?

  • 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.

  • rooney

    How did u make the graph? its great! can you please post the code for generating this graph ?

  • 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

  • Rojas

    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

  • 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.

  • Anonymous

    excelent lib, exactlly what i was looking. thanks

  • http://www.sharon-zarabi.com/web/best-college-application-essay-service/ Expressions evaluation at (almost) native speed

    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…

  • dissertation online rwth aachen Top Down or Bottom Up for Expression Evaluation ?

    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….

  • Sheehan

    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.

  • Antrol

    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

  • Hi, actually you can just pass one argument to a function call, but you can easily modify the parser to accept multiple parameters.