Sonoma State University
Department of Computer Science
CS-460: Programming Languages
Programming Assignment 6: Interpreter

Objective:

Hints:

  • You will need to maintain a stack data structure and a program counter to keep track of the flow-of-control as your program interprets and executes an input program.
  • The symbol table you created in Programming Assignment 4 can be used to maintain variable values during program interpretation and execution.
  • Your program will traverse the Abstract Syntax Tree you created in Programming Assignment 5 when executing statements. You should start at the first statement in the main procedure.
  • The Abstract Syntax Tree contains Boolean and numerical expressions in postfix notation to make it easy to evaluate the expressions during program interpretation and execution.
  • The Abstract Syntax Tree contains Boolean and numerical expressions in postfix notation to make it easy to evaluate the expressions during program interpretation and execution. Use a stack data structure to evaluate the postfix notation expression.

Please note:

Input test files to determine the effectiveness of your programming assignment six solution:

The output from your programming assignment six solution should look like the following files:

Uploading your programming project files

  • Please upload your source code and a Makefile as a zip or gzipped-tar file.

Programming Assignment 6 Rubric

CRITERIA RATINGS POINTS
Compilation:
Will the program compile with GNU compiler?		 Proficient
10 points
Makefile provided. Student's assignment six program is written in C or C++ and compiles with gcc (GNU C compiler) or g++ (GNU C++ compiler) without syntax errors on GNU/Linux. No external libraries (besides standard built-in C/C++ libraries) are required to build the project.		 Satisfactory
6 points
Student's assignment six program is written in C or C++ and compiles on GNU/Linux with gcc or g++. A Makefile is not included. Extra external library dependencies may be required to compile and run student's assignment six program besides standard built-in C/C++ libraries.		 Below Expectation
0 points
Makefile not included. Student's assignment six program fails to compile with gcc or g++ on GNU/Linux.		 10 points
Parsing Implementation:
How was the parsing technique implemented?		 Proficient
5 points
Student's assignment six program features a procedurally-driven deterministic finite-state automaton (DFA) to identify and parse comments.		 Below Expectation
0 points
Student's assignment six program implements a table-driven DFA; OR student's assignment six program implements a combination of procedurally-driven and table-driven DFA; OR student's assignment sux program fails to use a DFA (table or procedural).		 5 points
Recursive Descent technique:
How was the Concrete Syntax Tree created?		 Proficient
5 points
Student's assignment six program utilizes a recursive descent technique to build a Concrete Syntax Tree from the top-down.		 Below Expectation
0 points
Student's assignment six program does not use the recursive descent technique; OR there may be flaws in how the recursive descent technique is implemented; OR another technique is utilized instead.		 5 points
Abstract Syntax Tree:
How was the the Abstract Syntax Tree implemented?		 Proficient
5 points
Student's assignment six program utilizes a Left-Child, Right-Sibling binary tree representation to store an Abstract Syntax Tree (AST).		 Below Expectation
0 points
Student's assignment six program fails to properly create a Abstract Syntax Tree (AST) using a binary tree. There may be structural flaws with the AST.		 5 points
Symbol Table Implementation:
What does the symbol table include?		 Proficient
5 points
Student's assignment six program utilizes a linear linked list to hold a symbol table. Entries in the symbol table denote a variable's datatype (e.g. char, int, string, or boolean), a variable's name, and a variable's scope. The symbol table also holds the names of functions and procedures. If a symbol name is a function or procedure, that symbol table entry also includes a parameter list to denote the proper ordering of parameters passed-in to the function or procedure. Variable names, function names, and procedure names are are case-sensitive. Lastly, functions denoted in the symbol table contain a return-value datatype.		 Satisfactory
3 points
Student's assignment six program utilizes a symbol table; however, one attribute from the symbol table is missing: a variable's name, a variable's datatypes, a variable's scope, a function's name, a procedure's name, a function's return datatype, or the parameter list of each function or procedure.		 Below Expectation
0 points
Student's assignment six program implements a symbol table; however, two or more attributes from the symbol table are missing: a variable's name, a variable's datatypes, a variable's scope, a function's name, a procedure's name, a function's return datatype, or the parameter list of each function or procedure; OR the symbol table contains structural errors.		 5 points
Test program 1:
The first benchmark test.		 Proficient
10 points
Student's assignment six program interprets and executes test program one. The output when test program one is executed matches the output for test program one in the assignment guidelines.		 Satisfactory
6 points
Student's assignment six program interprets and executes test program one. The output from interpreting test program one does not identically match the expected output as defined in the assignment guidelines for test program one. There are between one and three mismatches in the output.		 Below Expectation
0 points
Student's assignment six program fails to interpret and execute test program one; OR student's assignment six program interprets and executes test program one but generates four or more mismatches with the expected output for test program one as defined in the assignment guidelines.		 10 points
Test program 2:
The second benchmark test.		 Proficient
10 points
Student's assignment six program interprets and executes test program two. The output when test program two is executed matches the output for test program two in the assignment guidelines.		 Satisfactory
6 points
Student's assignment six program interprets and executes test program two. The output from interpreting test program two does not identically match the expected output as defined in the assignment guidelines for test program one. There are between one and three mismatches in the output.		 Below Expectation
0 points
Student's assignment six program fails to interpret and execute test program two; OR student's assignment six program interprets and executes test program two but generates four or more mismatches with the expected output for test program two as defined in the assignment guidelines.		 10 points
Test program 3:
The third benchmark test.		 Proficient
10 points
Student's assignment six program interprets and executes test program three. The output when test program three is executed matches the output for test program three in the assignment guidelines.		 Satisfactory
6 points
Student's assignment six program interprets and executes test program three. The output from interpreting test program three does not identically match the expected output as defined in the assignment guidelines for test program three. There are between one and three mismatches in the output.		 Below Expectation
0 points
Student's assignment six program fails to interpret and execute test program three; OR student's assignment six program interprets and executes test program three but generates four or more mismatches with the expected output for test program three as defined in the assignment guidelines.		 10 points
Total points: 60