lexer

AsYacc – first alpha release

Alessandro Crugnola actionscript , , , , , ,

Before going further with discussing how to add runtime scripting support to a Flash applications, I’d like to share with you the source code of a porting of Yacc I did a while ago. I did some simple modification to make Yacc able to generate ActionScript 3.0 source code instead of C. It works quite well and supports a lot standard Yacc features. There might be some issues – report them to me and I’ll try to fix them 🙂

You can easilly find documentation about Yacc searching Google (you can start here for example).

Usually Yacc is used in conjunction with a Scanner generator (like Lex/Flex), but I didn’t to any porting of commonly used Scanner generators yet.

Here you can download the sources. The source code should be portable and compilable on all the most common platform, but I didn’t tested it on Windows yet. To compile the source code on Mac or Linux, cd to the source code directory and type use:

gcc *.c -o AsYacc

Once you have the compiled binary file, you can run the Parser generator using:

./AsYacc -Hpackage=it.sephiroth.test grammar.y

Where grammar.y is a text file that contains the grammar of a language defined using the proper syntax (see the docs online for all the detailed information you may need).

Here you can download a simple calculator example that uses the RegexLexer described previously to implement the Scanner. For the ones who might be interested, here is the grammar used:
/* Infix notation calculator. */
%{
%}
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG
%right '^' /* exponentiation */
%%
input:
exp { trace( $1 ); }
;
exp:
NUM { $$ = $1; }
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { $$ = $1 / $3; }
| '-' exp %prec NEG { $$ = -$2; }
| exp '^' exp { $$ = Math.pow( $1, $3 ); }
| '(' exp ')' { $$ = $2; }
;
%%

Scripting Flash apps: scanning the input file

Alessandro Crugnola scripting languages , , , , , , , ,

Here we go. I know that probably I should have started this new topic talking about the grammar of the language we are going to implement, but as long as I see grammar strictly related to parsing, I’ve preferred to talk about scanning first.

We will go back to the grammar the next time, when talking about how to parse an input file.

I wrote about scanning (or lexing if you prefer) a while ago, when blogging about expression evalution in ActionScript. Scanning an input file is quite always the same (although some languages might require unusual features), and what I wrote about expressions works also for a general language.

The goal of the scanning process is to group some characters together, skipping the ones that have no meaning for the language like spaces. Each group of characters is usually called token. So a Scanner converts a textual input into a stream of tokens, each one rappresenting a possible valid word for our language. While scanning you don’t take care about the meaning of what you are grouping or about the fact that a sequence of tokens is meaningful. This is a task for the Parser as we will see.

When talking about expressions, I showed a manual implementation for a Lexer. Now I want to take a different approach and show you a possible implementation for a simple dynamic scanner. This scanner will be based on regular expressions: each regular expression will rappresent a given token, and we will be able to assign callbacks to the scanner that will be executed each time a given token is extracted from the input.
Writing a general and reusable scanner is usually a good practice. A common approach is to use some scanner generators, that are usually regular expression based too but are able to generate the code for a scanner at compile time. Our approach is different (and generates slower scanners) because regular expressions are evaluated at runtime; but it is fine for a test project.

You can download the source code for the regular expression based lexer (RegexLexer) here, as long as a simple usage example. Let’s see this example together so we can briefly discuss it (PBLexer.as):

Continue reading →

Runtime expression evaluation in ActionScript

Alessandro Crugnola actionscript, scripting languages , , , , , , ,

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.

Continue reading →