Due: December 18
In this assignment you will writing a complete interpreter for HL except that
it will not handle errors in programs.
This should familiarize you with symbol table manipulation,
semantic analysis, and evaluation.
Step 1 - Parser preparation
A parser solution will not be provided for this assignment, but you will need a functional parser to proceed.
You may now collabrate with your classmates to make sure that your parser in functional.
This assignment can be done in teams of 2 people at no penalty.
If you are going to work in a team you should decide which parser you are going to work from.
You can combine your parsers if you wish. You can now also copy parser code from classmates if you wish.
Once you have a functional parser, here are some additional changes/decisions you will need to make about your parsing:
- Add the println function as defined in the
to the HL grammar and to your parser.
- Decide whether you want to define the other three
built-in functions in the grammar as was done for
the printing functions, or as special cases of function calls.
If you decide to integrate them in the grammar, then you should allow expressions as parameters.
- You may also want to rework the HL grammar a little
to implement some of the semantics of HL. In particular, you
can probably remove stop and return statements from the top level
statements. However, this is not absolutely necessary, and you can deal with this issue later on
in your error handler instead.
Step 2 - Preparation
Before you start writing your evaluator code, you need to set up your project
to facilitate this process with jjtree. The facilities offered by jjtree are explained in
Handout 5-5 Visitors
- Make a new copy of your second assignment and replace TestHL.java and SimpleNode.java by the ones
- Add the option
- Compile your project and use the
createEval script to create a file Eval.java
from the interface HLVisitor.java.
The instructions on how to use this script can be found in the
of the Scripts directory.
The file Eval.java is the main file for this assignment. It will now contain one
evaluator visitor for each type of syntax tree.
Step 3 - Assignment
Write an interpreter for the language HL,
which is a special-purpose language for the manipulation of polynomials.
Here are detailed semantic specifications for HL:
- Start by building parts of the evaluator, just to wrap your head around
the concepts of visitors and evaluation. Here is a good order:
- Integer, boolean, and string constants.
- Arithmetic expressions with integers.
- Print statement, body, and clause.
- if and while statements and conditions.
- Then you will need to work on polynomials, and indexing (polynomial evaluation).
- At first, keep polynomial ASTs as originally defined, just to figure out what it means to
evaluate a polynomial.
- Then you should work on evaluating arithmetic expressions when some of the terms are polynomials.
- Once this is done, you can rework the polynomial structure are defined in the requirements,
- Then you can implement the two built-in functions: coeff and exp.
- Then you will need to start dealing with identifiers, function
calls, assignments and symbol tables.
It is easier to implement these in the order in which they are needed:
You will probably need to define your own class for symbol table records.
There are Java Symbol classes available in various places, but you
will probably end up doing as much work adapting them to your needs
as you would writing them from scratch.
- the identifier table for scanning,
- the scope stack for parsing
- and finally the activation stack for the evaluation of indentifiers and function calls.
- Once you have done this, you'll have a very good sense of how your
entire interpreter is working and the rest should fall into place
fairly naturally. Your biggest decision will be whether to make semantic
analysis a separate phase or how to distribute its work to the other
components of your interpreter.
- Java files.
In addition to TestHL and SimpleNode, you will notice
- IndexedPair.java and PairedTable.java which work together.
I have found these two classes very useful for implementing the class HLpolyn and
the symbol table functionality.
You can use this class for 2 purposes:
- You do not have to do any type checking in evaluations in this assignment since error
management is handled in assignment4. You may, however, find it practical to do some type checking
anyway. If that is the case, you can use this class to throw evaluation exceptions whenever Eval
encounters a problem.
- You will need to throw exceptions to implement the return and stop statements.
You will need 2 different types of evaluation exceptions for this, one for each type of statement.
The cleanest way to do this is with 2 subclasses of EvaluationException.
- Miscellaneous scripts
- Test files
Here are the steps we will take to test and grade your assignment:
- We will provide 3 default files in case you did not:
- We will download and open your A3.zip submission and run either
your makefile on it or ours if you did not provide a replacement.
- We will then run all the tests specified in the marking sheet in
the order in the marking sheet and compare them with the results files.
- scoping.hl determines whether you implemented static or dynamic
scoping. We have an alterate test file to do this in case your program
crash with scoping.hl: scopetype.hl.
How to submit the assignment
- Zip up together all your source files and makefile into A3.zip.
Be sure to preserve the correct hierarchical structure of files when you
zip everything up. Our makefile uses the default: everything in one directory
except that all jjtree-generated files are in the AST subdirectory.
- Submit electronically using submit-cps710 A3.zip
- Fill out and submit the marking sheet: (
in the D2L submission folder called "Assignment 3 marking sheets".
This page is maintained by
Saturday, 17-Dec-2016 00:39:21 EST