2009 May 11 / |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u
Carleton College CS 254, Prof. Joshua R. Davis
There are three questions on this assignment. They are due Friday May 15 at 5:00 PM. Hand in problems A and B on paper; hand in problem C electronically, either by hsp
or by putting your file on COURSES manually.
A. Prove that if A is a CFL and R is a regular language, then their intersection is a CFL. (This is page 308, problem 2.)
B. Prove that the set {ap : p is prime} is not a CFL. (This is page 335, problem 82.)
C. I want to implement a certain programming language. It is essentially a simple calculator, like this:
Press Control-D to exit. >> x = 2.718 2.718 >> 13 + x 15.718 >> x = 3 * 2 ^ 4 48.0 >> x 48.0 >> jim = x / 2 24.0 >> 17 - jim * 2.43 -41.32
The interpreter for my programming language performs the following steps in a never-ending loop.
stack.py
, binarytree.py
, and interpreter.py
to a single folder on your computer. You will write your code in interpreter.py
; do not edit or hand in the other files.
Here are the scanning rules of our language. Word breaks occur at spaces, at parentheses, and at the operators, which are +
, *
, -
, /
, ^
, and =
. For example, the string
scans to a token list of'jan = 3.14xy + (3 - rewgy3-1)'
Write a Python function['jan', '=', '3.14xy', '+', '(', '3', '-', 'rewgy3', '-', '1', ')']
scan()
that takes in an input string and returns the list of tokens (which are themselves strings). Use a regular expression.
Here are the parsing rules of our language. All of the operators are binary, meaning that they take two arguments. I leave it to you, to figure out what their precedences should be. Write a Python function parse()
that takes in a token list, parses using our parsing algorithm from class (with precedence ties broken to the left), and returns a parse tree. The nodes of the parse tree should store tokens — that is, strings — not the values associated to those strings. For example, 3 + 5
parses to the tree
[+, [3, [], []], [5, [], []]]
where +
, 3
, and 5
are strings, not numbers or functions.
Once you have written scan()
and parse()
you should have a working interpreter. That is, they should connect perfectly to the evaluator and user interface. Test your interpreter thoroughly. Also make sure that the code is clean, concise, and appropriately commented.