CMSC 323代做、代写Java, Python编程

日期：2024-02-25 08:25

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);

*

8

8a

+

2 1

8 * (2 + 1)

+

* c

a b

8 * 2 + 1