Computer Systems Organization I - Prof. Grishman

Assignment #6

Write a program in C which will interpret the statements of a simple programming language, SIMPL.  SIMPL has four statements, an assignment statement, while and endwhile statements, and a print statement.  The interpreter should print whatever is specified by the print statements.  For example, the program

    num = 1
    while num < 4
       square = num * num
       print num
       print square
       num = num + 1
    endwhile

should output

    num = 1
    square = 1
    num = 2
    square = 4
    num = 3
    square = 9

SIMPL Specifications (minimum requirements)

Tokens

There are five types of SIMPL tokens:  variables, reserved words, constants, operators, and punctuation.
A variable consists of 1 to 31 letters (upper or lower case).
Reserved words:  the words "while", "endwhile", and "print" are reserved and may not be used as variable names.
A (decimal) constant consists of 1 to 9 decimal digits.
There are six operators:  +, -, *, /, < and >
There is only one punctuation token, =

Statement format

Each SIMPL statement is on a separate line.
Tokens are separated by at least one whitespace character. 
Statements may begin and end with zero or more whitespace characters.

Expressions

An expression element is a variable or constant.
An expression is either an expression element or two expression elements separated by an operator.
The operators < and > return 1 if the relation is true, and 0 if the relation is false.
A reference in an expression or a print statement to a variable which has not been assigned a value is an error.

Statements

The assignment statement has the form 'variable = expression' and assigns to variable the value of expression.
The while statement has the form 'while expression' and executes the statements up to the following 'endwhile' statement as long as expression is non-zero (true).  while statements cannot be nested.
The print statement has the form 'print variable' and prints the name and value of variable to standard output.
After the last statement in the SIMPL program has been executed, the interpreter terminates.

Optional features

This assignment offers substantial opportunity for adding optional features for extra credit.  Some possibilities are listed here:

Suggestions for organizing the program

You may write the program any way you like, so long as the final program meets the specifications just described.  However, we offer the following suggestions for data structures and program organization to help you get started.

Global data structures

Note that, because we do not have something like a Java ArrayList in C, we need global variables to keep track of the number of currently filled elements in each array (program, variable, token).

High-level program structure

The general strategy is to have the structure of the interpreter reflect the structure of the language being interpreted, and to have lots of relatively small functions, one to handle each language construct.  This makes it easier to debug the program, and to understand the program once it is written.

Stages of implementation

Altogether, this system, with minimal comments, should take about 300 lines of code.  We will do this in three stages, each of which (very roughly) requires 100 lines of new code and will be due in (roughly) one week increments.

Stage 1:  due Nov. 22 -- tokenization and token classification

Stage 1 will be the most straightforward because it builds on the getline function we did in class and the gettoken function you did for homework.  It should read in the program and then print it, with each line followed by a list of the tokens in the line and whether the token is an integer, variable (or reserved word), or other.  Reserved words will be considered variables for this stage.  In terms of the functions listed above, it involves writing loadProgram, listProgram, tokenize, isVariable, and isConstant.  A sample output would be

Line 0:  a = 3
    Token 0:  a (variable)
    Token 1:  = (other)
    Token 2:  3 (constant)
Line 1:  while a < 60
    Token 0:  while (variable)
    Token 1:  a (variable)
    Token 2:  < (other)
    Token 3:  60 (constant)

Stage 2:  due Dec. 2 -- assignment statements

The focus in stage 2 is on keeping track of variables and their values.  This version of the program should accept a SIMPL program consisting only of assignment statements where the right-hand side is a simple variable or constant.  After each statement is executed, it should print the name and value of the variable.  This involves writing executeProgram, a simple version of executeStatement (which always calls) executeAssignment, evaluateExpressionElement, intValue and getVariableValue.  A sample input would be

quack = 3
moo = quack
moo = woof

and output would be (in addition to a listing of the program)

Assign quack = 3
Assign moo = 3
Error:  undefined variable woof
Assign moo = 0  [default value for undefined variables]

Stage 3 (final version):  due Dec. 8 -- complete system

The main things to be added in this stage are the code for expressions, and the code for the other statements (print and while).

Grading

This project will be worth 16 points.  Successful completion of stage 1 on time gets 4 points;  successful completion of stage 2 on time gets 5 points;  and successful completion of the final system gets 7 points.  A final system without a getwhile will be worth 5 points (2 point penalty).  Credit will be based primarily on correct execution of correct programs, but some credit will also be given for comments (we expect at least a line before each function explaining what it does) and error checks (if we can get your program to crash with an invalid input, it won't get full credit;  make sure you don't overrun any arrays).

Extra credit will depend on features added, starting with 0.5 points for 'easy' additions;  we anticipate awarding up to 4 points of extra credit for interesting combinations of features, but stand ready to be wow-ed.

Label your program files for the three stages lastname6a.c, lastname6b.c, and lastname6.c.  Submit your program (.c file) by email, as an attachment, to the e-tutor, Ian Lau <itl204@nyu.edu>, by one minute before midnight on the specified date. (Late assignments will be penalized 1/2 point for each weekday late.) Label your email "CSO Asgn 6a", "CSO Asgn6b", and "CSO Asgn 6".  For the final version
It is important to keep up with the stages of the project.  If you are having trouble, contact me or Ian by email.