Starting from:
$30

$24

ASSIGNMENT 2 (POSTSCRIPT INTERPRETER ­ PART A) SOlution




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.




Grading




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:




The operand stack



The dictionary stack
Defining varibles with def
Looking up names
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.



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




http://www.eecs.wsu.edu/~arslanay/CptS355/assignments/interpreterPartA-2016.html
1/4
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():




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



­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­




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():




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 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.




3/4
12/11/2016 CptS 355 - Assignment 2 - Part A




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 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:




Cpt























































































































































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

More products