COMP1721 - Higher Computing 1B

Higher Computing 1B - Week 10 Laboratory Exercises

This lab involves:

Create a separate directory (lab10 is a good name) using mkdir for this week's lab exercises.

The Language

Your task is to produce an interpreter for a simple language. This language allows simple arithmetic expressions to be printed or assigned to a variable. For example: 

% a.out
> put_i 42;
42
> put_i 6 + 12 * 2 + 4 + 3 * 2 + 2;
42
> put_i 3 * (2 + 3 + 3) / 4;
6
> answer = 42;
> put_i answer;
42
> put_i answer-6*7;
0
> x = answer/6*3;
> put_i x;
21

Notice, the major difference to assignment 2. In assignment 2, you given statements like these output equivalent AVR assembler. In this lab exercise you will evaluate the statements immediately and out put the result.

A grammar for this language is:

Statement --> Identifier = Expression ;
--> put_i Expression ;
Expression --> Expression Op Expression
--> ( Expression )
--> Identifier
--> Constant
Op --> +
--> -
--> *
--> /

Getting Started

The file interpreter.c contains a starting point for the lab exercise. Save it in your current directory. You also need two files from assignment 2, cavy_syntax.h and cavy_syntax.c, save these in your current directory too.

The code in interpreter.c is a working implementation for a subset of the language described above. Read it carefully. A grammar for the subset that has been implemented by the code you have been given is:

Statement --> Identifier = Term ;
--> put_i Term ;
Term --> Identifier
--> Constant

Here is how you compile and run the code you have been given: 

% dcc interpreter.c cavy_syntax.c
% a.out
> put_i 42;
42
> answer = 42;
> put_i answer;
42
> x = 15;
> put_i x;
15

Your task is to add to the code you have been given so that it interprets the full language specified. Effectively have to add code which evaluates expressions to interpreter.c. The tricky part in doing is getting the precedence of operators correct.

You will notice interpreter.c already contains code (similar to a tute question) which implements the language's variables. You don't need to change this code. You just need to add expression handling.

Hints

The grammar for expressions can be re-written like this:

Expression --> Factor Expression1
Expression1 --> + Factor Expression1
--> - Factor Expression1
-->
Factor --> Term Factor1
Factor1 --> * Term Factor1
--> / Term Factor1
-->
Term --> Identifier
--> Constant
--> ( Expression )

Although the above grammar is more complex, it encapsulated how expressions have to be parsed to correctly implement the precedence of operators.

You should implement functions corresponding to some of the non-terminal symbols in this grammar. The non-terminals are the symbols in italics.

Implement functions with these signatures: 

int expression(void);
int factor(void);
int term(void);

corresponding to the non-terminals Expression, Factor and Term. respectively.

These functions should read the tokens corresponding to, respectively, a Expression, Factor and Term, evaluate it and return its value.

One tricky part is getting the expression and factor functions not to consume one too many tokens. The function view_token is helpful here.

Your expression, factor and term functions should be mutually recursive - i.e they should call each other.

You will notice interpreter.c already contains much (not all) of the implementation of a term function.

Finished?

When you have interpreter.c After your tutor has checked that you answers are correct and given you the lab mark, you must also submit your answers using give. Here is the command to use: 

% /home/cs1721/bin/classrun -give lab10 interpreter.c

Andrew Taylor (andrewt@cse.unsw.edu.au)
Higher Computing 1B, Computer Science & Engineering, UNSW