An Interpreter for a Simple Postscript­like Language

Assigned: Thursday September 15, 2016

Due: Monday September 26, 2016

Weight: The entire interpreter project (Part A and Part B together) will count for 10% of your course grade. This first part is worth 2% and second part is 8% ­ the inten make sure that you are on the right track and have a chance for mid­course correction before completing Part 2. However, note that the work and amount of code invo 1 is a large fraction of the total project, so you need to get going on this part right away.

This assignment is to be your own work. Refer to the course academic integrity statement in the syllabus.

Turning in your assignment

All the problem solutions should be placed in a single file named HW2_partA.py. When you are done and certain that everything is working correctly, turn in your file on the Assignment2(Interpreter­PartA) DROPBOX on Blackboard (under AssignmentSubmisions menu).

The file that you upload must be named HW2_partA.py . Be sure to include your name as a comment at the top of the file. Also in a comment, indicating whether y intended for Unix/Linux or Windows. You may turn in your assignment up to 5 times. Only the last one submitted will be graded. Please let the instructor know if you n resubmit it a 6th time.

Implement your code for Python 3. The TA will run all assignments using Python3 interpreter. You will lose points if your code is incompatible with Python

The work you turn in is to be your own personal work. You may not copy another student’s code or work together on writing code. You may not copy code from the anything else that lets you avoid solving the problems for yourself.


The assignment will be marked for good programming style (appropriate algorithms, good indentation and appropriate comments ­­ refer to the Python style guide) ­­ as thoroughness of testing and clean and correct execution. You will lose points if you don’t (1) provide test functions, (2) explain your code with appropriate comments, a a good programming style.

The Problem

In this assignment you will write an interpreter in Python for a simplified PostScript­like language, concentrating on key computational features of the abstract machin all PS features related to graphics, and using a somewhat­simplified syntax. The simplified language, SPS, has the following features of PS:

integer constants, e.g. 123: in python3 there is no practical limit on the size of integers

string constants, e.g. (CptS355): string delimited in paranthesis

name constants, e.g. /fact: start with a / and letter followed by an arbitrary sequence of letters and numbers

names to be looked up in the dictionary stack, e.g. fact: as for name constants, without the /

code constants: code between matched curly braces { … }

built­in operators on numbers: add, sub, mul, div, mod

built­in operators on string values: length, get, put, getinterval. Check Appendix for more information on string functions.

built­in loop operator: for; make sure that you understand the order of the operands on the stack. Play with ghostscript if necessary to help understand what is h

stack operators: dup, exch, pop, roll,copy, clear

dictionary creation operator: dict; takes one operand from the operand stack, ignores it, and creates a new, empty dictionary on the operand stack

dictionary stack manipulation operators: begin, end. begin requires one dictionary operand on the operand stack; end has no operands.

name definition operator: def. This requires two operands, a name and a value

defining (using def) and calling functions

stack printing operator (prints contents of stack without changing it): stack

Part A ­ Requirements

In Part A you will build some essential pieces of the interpreter but not yet the full interpreter. The pieces you build will be driven by Python test code rather than actua programs. The pieces you are going to build first are:

    1. The operand stack

    1. The dictionary stack

    2. Defining varibles with def

    3. Looking up names

    4. The operators that don’t involve code arrays: all of the operators except for loop and calling functions (In Part B, you will add the implementations for for loo functions, as well as interpreting input strings in the Postscript language.

  1. The Operand Stack

The operand stack should be implemented as a Python list. The list will contain Python integers, strings, and later in Part 2 code arrays. Python integer and strings the represent Postscript integers and string constants. Python strings which start with a slash / on the stack represent names of Postscript variables. When using a list as of the decisions you have to make is where the hot end of the stack is located. (The hot end is where pushing and popping happens). Will the hot end be at position 0, the list, or at position ­1, the end of the list? It’s your choice.

2. The Dictionary Stack



12/11/2016 CptS 355 – Assignment 2 – Part A

The dictionary stack is also implemented as a Python list. It will contain Python dictionaries which will be the implementation for Postscript dictionaries. The dictionary to support adding and removing dictionaries at the hot end, as well as defining and looking up names.

3. Operators

Operators will be implemented as zero­argument Python functions that manipulate the operand and dictionary stacks. For example, the div operator could be implem Python function (with comments instead of actual implementations)

def div():

op1 = # pop the top value off the operand stack

op2 = # pop the top value off the operand stack

# push (op1 / op2) onto the operand stack

The begin and end operators are a little different in that they manipulate the dictionary stack in addition to or instead of the operand stack. Remember that the dict op affects only the operand stack.

The def operator takes two operands from the operand stack: a string (recall that strings that start with / in the operand stack represent names of postscript variables) It changes the dictionary at the hot end of the dictionary stack so that the string is mapped to the value by that dictionary. Notice that def does not change the number dictionaries on the dictionary stack!

4. Name Lookup

Name lookup is implemented by a Python function:

def lookup(name):

  • search the dictionaries on the dictionary stack starting at the hot end to find one that contains name

  • return the value associated with name

Note that name lookup is not a Postscript operator, but it is implemented by a Python function.

You may start your implementation using the below skeleton code:

­­­­­­­­­­­­­­­­­­­­­­­­­­­ 10% ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­

  • The operand stack: define the operand stack and its operations opstack = []

  • now define functions to push and pop values on the opstack according to your decision about which

  • end should be the hot end. Recall that `pass` in python is a no­op: replace it with your code.

def opPop():


def opPush(value):


# Remember that there is a Postscript operator called “pop” so we choose different names for these functions.

­­­­­­­­­­­­­­­­­­­­­­­­­­­ 20% ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­

# The dictionary stack: define the dictionary stack and its operations

dictstack = []

# now define functions to push and pop dictionaries on the dictstack, to define name, and to lookup a name

def dictPop():


def dictPush():


def define(name, value):


def lookup(name):


    • return the value associated with name

  • what is your design decision about what to do when there is no definition for name

­­­­­­­­­­­­­­­­­­­­­­­­­­­ 10% ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­

# Arithmetic operators: define all the arithmetic operators here ­­ add, sub, mul, div, mod

­­­­­­­­­­­­­­­­­­­­­­­­­­­ 15% ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­

# String operators: define all the string operators ­­ length, get, put, getinterval

­­­­­­­­­­­­­­­­­­­­­­­­­­­ 25% ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­

# Define the stack manipulation and print operators: dup, exch, pop, roll, copy, clear, stack

­­­­­­­­­­­­­­­­­­­­­­­­­­­ 20% ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­

  • Define the dictionary manipulation operators: dict, begin, end, def

  • name the function for the def operator psDef because def is reserved in Python


http://www.eecs.wsu.edu/~arslanay/CptS355/assignments/interpreterPartA-2016.html 2/4

12/11/2016 CptS 355 – Assignment 2 – Part A

Test your code:

def testAdd():




if opPop() != 3: return False

return True

def testLookup():




if lookup(“n1”) != 3: return False

return True


  • go on writing test code for ALL of your code here; think about edge cases, and

  • other points where you are likely to make a mistake.

Main Program

To run all the tests, so your main should look like:

#now an easy way to run all the test cases and make sure that they all return true is

itestCases = [testAdd, testLookup] # add the names of your test functions to this list

for test in testCases:

if not test(): return False

return True

  • but wouldn’t it be nice to run all the tests, instead of stopping on the first failure,

  • and see which ones failed

  • How about something like:

testCases = [(‘add’, testAdd), (‘lookup’, testLookup)] # add you test functions to this list along with suitable names

failedTests = [testName for (testName, testProc) in testCases if not testProc()] if failedTests:

return (‘Some tests failed’, failedTests)

else: return (‘All tests OK’)

­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ APPENDIX ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­


length : gets a string (from the stack) and pushes the length of the string on the stack

string length : int

For example:

(CptS355) length

After running the above, the operand stack will be:


get : gets a string and an index (integer) value (from the stack) and pushes the ASCII value of the character at position index onto the stack

string index get : int

For example:

(CptS355) 0 get

After running the above, the operand stack will be:


the ASCII value 67 corresponds to character C.

put : gets a string, an index (integer) value, and an ASCII(integer) value (from the stack), replaces the character at position index in the string with the given AS character. The resulting string, however,is not stored in the operand stack. Hence, for explicit use of put operator, we can define a string variable and apply the put op the value of this variable.


12/11/2016 CptS 355 – Assignment 2 – Part A

string index int put : ­

For example:

/s1 (CptS355) def

s1 0 99 put


After running the above, the operand stack will be:


Ascii value 99 corresponds to lowercase c. Please note that when you execute put for a string variable, you should update the value of the variable in the stack dictio

getinterval : gets a string, an index (integer) value, and a count (integer) value (from the stack), and returns the substring of string starting at index for count. Pus substing on the stack.

string index count getinterval : substring

For example:

(CptS355) 0 3 getinterval

After running the above, the operand stack will be: