Objective To demonstrate working knowledge of derivation and

Objective:
To demonstrate working knowledge of derivation and parsing.
Required:
Write a program that tokenizes and parses an expression, generates the derivation, and the Parse Trees for
that expression given the simple grammar below. Your program should indicate that an expression is invalid
if it does not follow the grammar. Moreover, it should demonstrate that this grammar is ambiguous. The next
step is to propose and make some changes to the grammar to make it unambiguous.
Submit a soft copy of the program, with a hard copy of the program, and sample outputs. Please include the
honor code. The programming languages that can be used to write the parser is Lisp. Your
name should be on all documents submitted.
The grammar is:
e ::= n | e+e | e-e
n ::= d | nd
d ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
where e is the start symbol. Symbols e, n, d are nonterminals, and 0-9, +, and – are the
terminals

Solution

from pythonds.basic.stack import Stack
from pythonds.trees.binaryTree import BinaryTree

def buildParseTree(fpexp):
fplist = fpexp.split()
pStack = Stack()
eTree = BinaryTree(\'\')
pStack.push(eTree)
currentTree = eTree
for i in fplist:
if i == \'(\':
currentTree.insertLeft(\'\')
pStack.push(currentTree)
currentTree = currentTree.getLeftChild()
elif i not in [\'+\', \'-\', \'*\', \'/\', \')\']:
currentTree.setRootVal(int(i))
parent = pStack.pop()
currentTree = parent
elif i in [\'+\', \'-\', \'*\', \'/\']:
currentTree.setRootVal(i)
currentTree.insertRight(\'\')
pStack.push(currentTree)
currentTree = currentTree.getRightChild()
elif i == \')\':
currentTree = pStack.pop()
else:
raise ValueError
return eTree

pt = buildParseTree(\"( ( 10 + 5 ) * 3 )\")
pt.postorder() #defined and explained in the next section