CS403: Programming Languages

The Designer Programming Language

Version 1

Printable Version

Preliminary information

Your task is to build an interpreter for a general purpose programming language of your own design. Your language must support the following features:
The only basic types you need to provide are integer and string and you do not need to provide methods for coercing one type to another (although you may find it convenient to do so). The efficiency of your interpreter is not particularly important, as long as you can solve the test problem in a reasonable amount of time. Your language also does not need to support reclamation of memory that is no longer needed. You are to write your program in a statically-typed, imperative language such as C, C++, or Java. Check with me first if you wish to use some other host language.

Test Problem

You must implement an AVL tree in your language, with the implementation based upon the pseudocode found at http://beastie.cs.ua.edu/avl/. The AVL tree will store integers. You must also implement an interpreter that reads commands from a file. The commands are:
0 display the tree 1 NNN insert the number @NNN@ into the tree 2 NNN delete the number @NNN@ from the tree
To make it easy to test with randomly generated commands, you should ignore attempts to delete non-existent numbers.

Place your program in a file named iAVL. Your main should look something like:
    function main()
        var fp = open(getCommandLineArgument(1));
        return 0;
Suppose these commands are found in the file commands:
    1 3
    1 2
    1 6
    1 5
    1 1
Then the output of:
    run iAVL commands
would be an in-order traversal of the tree:
    1(2) 2+(3) [3] 5(6) 6+(3) 
A plus sign is used if the balance factor of the node is +1, while a minus sign is used if the balance factor is -1. Parent values are enclosed in parenthesis and the root value is enclosed in square brackets. There are no spaces or tabs before the first value and no spaces or tabs after the last (only a newline). There is exactly one space separating values. The UNIX command diff will be used to compare outputs, so these rules must be strictly followed.


Failure to correctly implement the test program will result in a 10 point deduction. Each feature not correctly implemented will result in a 10 point deduction. You will receive a 10 point deduction if any rule in your makefile causes a pause for input (see the makefile rules below).

For Undergraduates: if you do not, at least, implement a recognizer for your language, you will fail the course.

For Graduates: if you do not, at least, implement an pretty printer, you will fail the course.

Testing your implementations

Your makefile should respond the command
which builds your processor and to the following commands, each of which illustrates a feature of your language:
    make error1
    make error1x
    make error2
    make error2x
    make error3
    make error3x
    make error4
    make error4x
    make error5
    make error5x
    make arrays
    make arraysx
    make conditionals
    make conditionalsx
    make recursion
    make recursionx
    make iteration
    make iterationx
    make functions
    make functionsx      # shows you can pass functions and return nested functions
    make lambda      
    make lambdax      
The first rule in a pair of rules should print out the appropriate input program, while the x rules should execute that program. In particular, the first three error rules should show off your parser detecting three different kinds of syntax errors, while the last to error rules should demonstrate the detection of two different kinds of semantic errors.

Your makefile should also respond to the commands:
    make problem
    make problemx
These commands display the test problem of your implementation and run the test problem, respectively.

Finally, provide an executable shellscript named run that runs one of your programs like so:
    run testprogram1.mylang [commandLineArgs...]
Test programs can be named anything.

Note: in the case of recognizing only, only the error rules need be present in your makefile. In the case of pretty printing only, the run rules should run the input program through the pretty printer.

Finally, your makefile should respond to the command:
    make clean
This command should remove all compilation artifacts (such as .o or .class files) so that a clean compile can be performed.

Makefiles for graduate students should additionally respond to the commands:
    make grad
    make gradx
These rules should thoroughly demonstrate the additional requirements for graduate students.

Submitting your assignment

To submit assignments, you need to install the submit system:
For preliminary testing, send me all the files in your directory by running the command:
    submit proglan lusth test1
For your final submission, use the command:
    submit proglan lusth assign1
The submit program will bundle up all the files in your current directory and ship them to me. Thus it is very important that only the files related to the assignment are in your directory (you may submit test cases and test scripts). This includes subdirectories as well since all the files in any subdirectories will also be shipped to me, so be careful. You may submit as many times as you want before the deadline; new submissions replace old submissions.
To prepare for submission, place all your source code, sample programs, a README detailing how to run and write programs in your language, and a makefile for building your system into one directory. Name the README file README.