FLAMEScript

Introduction

An example of a FLAMEScript program is as follows:

fun fact(n) {
    r := 1
    while n > 0 {
         r := r * n
         n := n - 1
    }
    return r
}

n := 1
while n < 10 {
    print n, "factorial is", fact(n)
    n := n + 1
}

Your task is to implement a simple scripting language interpreter for FLAMEScript. Your interpreter should read an entire program from standard input and execute it.

FLAMEScript overview

program       :  statements

statements    :  statements statement
              |  empty
              ;
                 
statement     :  ID := expr          
              |  ID ( exprlist )
              |  print exprlist
              |  while relop statement
              |  if relop statement
              |  if relop statement else statement
              |  return expr
              |  break
              |  { statements }
              |  fun ID ( idlist ) { statements }
              ;

expr          :  expr + expr
              |  expr - expr
              |  expr * expr
              |  expr / expr
              |  ( expr )
              |  -expr
              |  +expr
              |  ID
              |  ID ( exprlist )
              |  INTEGER
              |  FLOAT
              |  STRING
              ;

relop         : expr < expr
              | expr <= expr
              | expr > expr
              | expr >= expr
              | expr == expr
              | expr != expr
              | relop and relop
              | relop or relop
              | not relop
              | ( relop )
              ;

exprlist      : exprlist1
              | empty
              ;

exprlist1     : exprlist1 COMMA expr
              | expr
              ;
        
idlist        : idlist1
              | empty
              ;

idlist1       : idlist1 COMMA ID
              | ID
              ;

• FLAMEScript is dynamically typed. Variables are never declared in advance nor are datatypes explicitly stated. This is exactly the same type of programming model used by Python.

• Instead of using begin/end to start or stop a group of statements, curly braces { } are used.

• Each statement is terminated by a newline or a semicolon. This makes the statement termination rules incompatible with FLAME---an extra feature.

• Nested functions are not supported. If a function definition appears inside another function, FLAMEScript should print an insulting error message to the user.

• Strings are supported as a datatype and can be used in arithmetic operations. For example, "Hello" + "World" is "HelloWorld".

• Function definitions are simply a new kind of statement.

Scoping rules

When a variable assignment "x := expr" is made, two rules are applied:

• If the variable "x" is undefined in any scope, it is created in the local scope (effectively becoming a local variable of a function).

• If the variable "x" is already defined, its value is modified in whatever scope in which it was defined.

Writing your interpreter

• Using plex.py, write a lexer for FLAMEScript. To do this, simply take your FLAME lexer and tweak it a little bit. You'll need to add tokens for { } and remove some reserved words not used by FLAMEScript (begin, end, read, write, do, etc.).

• Using pyson.py, write a parser for FLAMEScript. Your parser should construct a parse tree and manage a symbol table almost exactly the same way as you did for FLAME. However, unlike FLAME, you don't need to do nearly as much work for type checking or symbol table management. This is because types are going to be checked at runtime.

• Write an execution module that simply takes the parse tree from the parser and runs the script by walking through the tree. Your tree walking code will be very similar to that used in FLAME code generation except that it should be much easier (see implementation hints below).

Implementation Hints

1. Because FLAMEScript is dynamically typed, you can get away with essentially no symbol table management or type checking during compilation (especially if you don't care about error messages). Instead, we'll deal with this at run time.

2. When executing a FLAMEScript program, simply use a Python dictionary to store information about the defined variables and other aspects of the program. For example, if you have the following FLAMEScript program:

   a = 4
   b = a * 10
   print a, b
   

   This can be emulated in Python as follows:

   symbols = { }             # Symbol table
   symbols['a'] = 4
   symbols['b'] = symbols['a'] * 10
   print symbols['a'], symbols['b']
   

3. Let Python do all of the expression evaluation and type checking for you. Use Python exceptions to catch type errors and print an appropriate error message.

4. Evaluation of functions is the most tricky part of the assignment. You will need to store the parse tree for each function in the symbol table someplace. To execute a function, create a new local scope and walk the corresponding function parse tree using this local scope to hold local variables.

5. At no point during execution should your parser print a Python error message. However, if a runtime error occurs, you should produce some kind of sensible error message. For example:

   a := 4 - "Hello"      /* Type error in - operator */
   

   When a runtime error occurs, your interpreter should print a message and immediately stop execution.

What to turn in

• fslex.py
• fsparse.py
• flamescript.py

% python flamescript.py <program.fs

To hand in your program, create a tar file:

tar -cf yourloginname.tar flamescript

Extra credit will be awarded in proportion to the completeness of your solution. Partial solutions are accepted, but to receive any extra credit points, your solution must minimally be able to parse any syntactically correct FLAMEScript program. More extra credit points will be awarded depending on your interpreter's ability to actually run these programs.

Note: The implementation of this project should not be nearly as involved as FLAME. If you allow Python to do a lot of your work and you have a reasonable grasp of everything we have done this quarter, you should be able to bang this out in a day or so.