Course Project Deliverable #3: BaM Interpreter (Applying Semantics)

Course Project Deliverable #3: BaM Interpreter (Applying Semantics) COSC 252, Fall 2015
Jeremy Bolton
Total Points: 160

Due Date: 12/1/2015

Over the course of the term you will design and build a programming language. Specifically you will build an interpreter for the programming language specified below. The third deliverable is a fully functioning interpreter for BaM.

Instructions:

Apply semantics to BaM – the result is a fully functional interpreter. The interpreter should evaluate any input sentence and, by default, should print out the last value computed. If the input is multiple statements, only print out the last evaluated statement. For function definitions, you can simply print out the name of the function. For Example:

Input: 3+4 Ouput: 7

Input: x = 2+5/1 Output: xis7

Input: x = 1; y= 10 z = y+10
Output: z is 20

Input: if( x ) // lets say x is 9 z= z +1
x = x -1;
endif

Output: x is 8

Details:

Semantics:

 If statements:
o The condition will be semantically true if the value is > 0, else the condition is false. o If statements blocks will not have a separate scope/environment.

 Function invocations
o Each time a function is invoked, a new (blank) scope is entered. Upon completion of

the functions execution, the scope is destroyed.
 Scope: BaM will adhere to a lexical (static) scoping system.

Requirements:

•   expression evaluation
•   variable assignment
•   variable evaluation
•   if statement evaluation
•   function definitions (assignment)
•   function invocation / evaluation

  Major notes:

•   Must maintain appropriate environments with scope information.
•   Must maintain activation records to track callers return location.
•   When a function is invoked be sure that formal parameters are assigned argument values in new

  scope

•   When a function returns, be sure the return value (indicated in fundef) is indeed returned.
•   Scoping, Environment, and activation records should be able to facilitate recursion.

  Notes: Feel free to remove the waitEndIf and waitFunction helper methods if you prefer to copy and paste input. (You may also need to make other updates to allow for copy/paste.) Please feel free to use the Project Discussion board in BB as a means to communicate/note considerations and bugs.

  Tips:

  Grading Notes, approx. scoring guide:

  •   The program must compile, otherwise a grade of zero will be assigned.
  •   Evaluates simple expressions: 0 – 50%
  •   Assigns and retrieves variables: ~ 70%
  •   Correctly evaluates conditional statements: ~ 80%
  •   Correctly defines functions and evaluates functions: ~ 90%
  •   Correctly maintains appropriate activation records and scope: ~ 100%

•   You will need to insert semantics directly into your top-down parsing functions.
•   As a result your parsing functions will likely have return values, structures, or objects
•   You will need to implement a structure(s) or object(s) to represent a variable list, function

  list, activation record (dynamic link), lexical scope (static link). This may be done with a few complex structures or many simple structures.

Previous Deliverables:

Given the following basic grammar, build a recursive decent, top-down parser for BaM in c++. Please name the parsing functions intuitively – corresponding to the names of the abstractions. A coding template has been provided, and I encourage you to use it. Feel free to deviate from the template (and/or the grammar) as you see fit, but be sure that the resulting parser will at a minimum parse the grammar listed here.

Requirements:

1. Top down parser based on grammar below, which parses grammar below.
2. Functions named intuitively.
3. Trace out the parse tree: INCLUDE print statements indicating when the parser “enters” a

   function and “leaves” a function. See examples below.

4. Post the .cpp file in BB.
5. The program must identify syntax errors and output an insightful message.

Grading Notes, approx. scoring guide:

•   The program must compile, otherwise a grade of zero will be assigned.
•   Partially parses up to <fact>: 0 – 50%
•   Correctly parses up to <fact>: ~ 50%
•   Correctly parses up to <term> ~ 60%
•   Correctly parses up to <expr> ~ 70%
•   Correctly parses up to <stmt> ~ 80%
•   Correctly parses up to <stmt_L> ~ 90%
•   Correctly parses up to <fundef> ~ 100%

  Examples: Parse Tree Trace.

Previous examples of syntax …

BaM has a simple and intuitive syntax, and will perform some simple operations focused on mathematical calculation. There is essentially one data type which is numeric and implied. The syntax is similar to a hybrid subset of small Basic and Matlab and is described below. Many of the standard tokens are shown below when describing the syntax of the language. Other tokens include numeric literals which will be integers and variables which will be alpha-numeric strings (starting with an alpha).

The language will allow sentences in the following forms:  Variables and numeric literals: e.g.

12 totalSum

•   Mathematical expressions: Simple arithmetic operations: *, -, +, / . e.g. 2+4*x
•   Variable assignment(s): (semicolon is used to separate assignments on the same line) e.g. x = 2+4

  y= 4-2+sum

  x = 3; y=3+9

•   Simple if statement(s) whose blocks will execute based on a mathematical expression, e.g.

  if( 3+1/x ) x=5

  y= 2 endif

•   Function definitions: a function will return one value, e.g.

  fundef z = f( b,c,d ) y = 3+4

  x = b+c*d-y; z = y+x endfun

•   Function invocation , e.g.

e.g.

f(a)

fun(x,y,z)

Please note that the language should support intuitive and standard combinations of the aforementioned abstractions: e.g.

e.g.

x = x+y-f(x+z, fun(z+y)) * f(2,3)

fundef z = f( b,c,d )

y = 3+4
x = b+c*d-y; z = y+x

endfun

if( 3+1/x + fun(a) ) x=5

y = g(2) endif