CMSC 323: Design and Implementation of Programming Languages
Exercise 3: Parsing in Python
Due Date: 02-22-24
Total Points: 100
Users of programming languages find it tedious and difficult to write programs using ASTs, so we use
simpler, more user-friendly notation to write our programs (The Java, Python, etc syntax programmers
interact with). We will call this our input or surface syntax. Converting the input syntax into ASTs (abstract
syntax trees) is called parsing.
For example, consider the following surface syntax and corresponding trees in Python.
Surface Snytax:
(/(* 8 (+ 2 (* 1 3))) 5)
Corresponding AST:
ast5 = Node("/")
ast5.left_child = Node("*")
ast5.left_child.left_child = Node(8)
ast5.left_child.right_child = Node("+")
ast5.left_child.right_child.left_child = Node(2)
ast5.left_child.right_child.right_child = Node("*")
ast5.left_child.right_child.right_child.left_child = Node(1)
ast5.left_child.right_child.right_child.right_child = Node(3)
ast5.right_child = Node(5);
It is obvious that the surface syntax is a much easier notation for a human to interact with.
For this exercise, we choose a simple pre-order notation which allows us not to worry about the
precedence of operations in our expressions as it is implicit in the notation.
You have been provided a Node (same as in Exercise 1) and a Parser class. Complete the method
parse in the Parse class. It should take the surface syntax in the example above (i.e. simple preorder
arithmetic expressions with parentheses) as input and build the corresponding syntax tree. Your
interpret method from Exercise 1 should be able to interpret the output of parse correctly.
Note that our surface syntax expects parentheses, spaces, numbers, and arithmetic operations (*, +, -, /)
only. Your trees will not be tested with any other characters.
Example surface syntaxes and corresponding trees:
1. Surface syntax: (/ 8 2)
AST:
ast3 = Node("/")
ast3.left_child = Node(8)
ast3.right_child = Node(2)
/
* 5
8 +
2 *
1 3
8 * (2 + 1 * 3) / 5
/
8 2
8/2
2. Surface syntax: (* 8 (+ 2 1))
AST:
ast4 = Node("*")
ast4.left_child = Node(a)
ast4.right_child = Node("+");
ast4.right_child.left_child = Node(b);
ast4.right_child.right_child = Node(c);
3. Surface syntax: (+ (* 8 2) 1)
AST:
ast4 = Node("+")
ast4.left_child = Node("*")
ast4.right_child = Node(1);
ast4.left_child.left_child = Node(8);
ast4.left_child.right_child = Node(2);