$30
ASSIGNMENT 2 (POSTSCRIPT INTERPRETER PART A)
CPTS355 ASSIGNMENT 2 (POSTSCRIPT INTERPRETER PART A)
Cpts 355
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 intention is to make sure that you are on the right track and have a chance for midcourse correction before completing Part 2. However, note that the work and amount of code involved in Part
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 by uploading
on the Assignment2(InterpreterPartA) 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 your code is
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 need to
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 3.
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 web, or
anything else that lets you avoid solving the problems for yourself.
Grading
The assignment will be marked for good programming style (appropriate algorithms, good indentation and appropriate comments refer to the Python style guide) as well 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, and (3) follow
a good programming style.
The Problem
In this assignment you will write an interpreter in Python for a simplified PostScriptlike language, concentrating on key computational features of the abstract machine, omitting
all PS features related to graphics, and using a somewhatsimplified 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 { ... }
builtin operators on numbers: add, sub, mul, div, mod
builtin operators on string values: length, get, put, getinterval. Check Appendix for more information on string functions.
builtin 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 happening.
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 actual Postscript
programs. The pieces you are going to build first are:
1. The operand stack
2. The dictionary stack
3. Defining varibles with def
4. Looking up names
5. 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 loop, calling
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 stack
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 a stack one
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 head of
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
http://www.eecs.wsu.edu/~arslanay/CptS355/assignments/interpreterPartA-2016.html 2/4
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 stack needs
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 zeroargument Python functions that manipulate the operand and dictionary stacks. For example, the div operator could be implemented as the
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 operator
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) and a value.
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 of
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 noop: replace it with your code.
def opPop():
pass
def opPush(value):
pass
# 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():
pass
def dictPush():
pass
def define(name, value):
pass
def lookup(name):
pass
# 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
12/11/2016 CptS 355 - Assignment 2 - Part A
http://www.eecs.wsu.edu/~arslanay/CptS355/assignments/interpreterPartA-2016.html 3/4
Test your code:
def testAdd():
opPush(1)
opPush(2)
add()
if opPop() != 3: return False
return True
def testLookup():
opPush("n1")
opPush(3)
psDef()
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
STRING OPERATIONS
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:
7
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:
67
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 ASCII
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 operation on
the value of this variable.
12/11/2016 CptS 355 - Assignment 2 - Part A
http://www.eecs.wsu.edu/~arslanay/CptS355/assignments/interpreterPartA-2016.html 4/4
string index int put :
For example:
/s1 (CptS355) def
s1 0 99 put
s1
After running the above, the operand stack will be:
cptS355
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 dictionary.
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. Pushes the
substing on the stack.
string index count getinterval : substring
For example:
(CptS355) 0 3 getinterval
After running the above, the operand stack will be:
Cpt
