Homework 1
Interpreter of Straight-line Program  

powered by FreeFind

Modified: 

Overview

The text describes a simple language (not iterators, functions, data structures, just assignment, print and compound statements) and suggests an implementation for an interpreter. A complier for languages such as C++ and Java generally:

  1. constructs an Abstract Syntax Tree (AST) from a program's text that represents the program's semantics (meaning)
  2. generates corresponding machine code,
  3. the code can then be executed

Our simple language will be represented not in text form but in the intermediate AST representation, delaying the need to transform text to the AST. For some examples of program text and equivalent program AST:

Text AST  
37 new NumExp(37) NumExp(37)
a = 37 new AssignStm("a", new NumExp(37))

   AssignStm
      /  \
   "a"  NumExp(37)

a := 5 + 3 ;
print ( a ) ;

new CompoundStm(
       new AssignStm( "a",
           new OpExp(
              new NumExp(5),
              OpExp.Plus,
              new NumExp(3)
           )
        ),
        new PrintStm(
             new LastExpList(
                   new IdExp("b")
             )
         )
);

                CompoundStm
                   /                 \
            AssignStm             PrintStm
               /       \                 /          \
          "a"    OpExp         LastExpList  IdExp("b")
                 /      |       \
NumExp(5) OpExp.Plus NumExp(3)

The program can be interpreted (executed) by traversing the AST and performing the operations at each node of the AST.

Assignment

  1. complete the given skeleton of the Interpreter
  2. interpret the 3 given straight-line programs. The skeleton will interpret only Program 1 given below.   
  3. write as an AST and interpret a straight-line Program 4 defined as: a := 5+3; b = 10*a; print( a, b);

Files

Download the following files:

  1. StraightLine.java - Java definitions from text p. 10.
  2. Interpreter.java - Interpreter skelton.
  3. Program 1, 2, 3 - test programs.

Getting Started

  1. Download the files listed above, preferably to a separate directory.
  2. Copy Program1.java to Program.java (i.e. the interpreter program uses the classes defined in the file named Program.java).
  3. At home:

    At IUS enter in the DOS Command window:

  4. The Interpreter can be executed by (note that Java is case-sensitive everywhere, including the DOS command window):
     
    1. To compile a Java program named StraightLine.java enter:

        javac -classpath . StraightLine.java
         

    2. Delete Program.class after any changes to Program.java, otherwise the old program version will be interpreted.

      del Program.class

    3. To compile a Java program named Interpreter.java enter:

        javac -classpath . Interpreter.java
         

    4. To execute the compiled Interpreter program:

        java -cp . Interpreter
         

Turn In

  1. Cover sheet with your name, C431, date, and Homework 1.
  2. Print out of Interpreter.
  3. Print out of Program 4 (i.e. Assignment Part 3).
  4. Print out of test results for Programs 2, 3 and 4.