"""A module of functions that reformat an input program into an operator tree. Call parse() to run the parser.

PROGRAM ::= COMMANDLIST COMMANDLIST ::= COMMAND | COMMAND ; COMMANDLIST COMMAND ::= VAR = EXPRESSSION | print EXPRESSION | while EXPRESSION : COMMANDLIST end | if EXPRESSION : COMMANDLIST else COMMANDLIST end

EXPRESSION ::= NUMERAL | VAR | ( EXPRESSION OPERATOR EXPRESSION ) OPERATOR is + or - NUMERAL is a sequence of digits from the set, {0,1,2,...,9} VAR is a string of lower-case letters, not a keyword

The output operator trees are nested lists:

PTREE ::= [ CLIST ] CLIST ::= [ CTREE+ ] where CTREE+ means one or more CTREEs CTREE ::= ["=", VAR, ETREE] | ["print", ETREE] | ["while", ETREE, CLIST] | ["if", ETREE, CTREE, CTREE] | ["call", VAR] ETREE ::= NUMERAL | VAR | [OP, ETREE, ETREE] where OP is either "+" or "-" """

### data structures for parser: wordlist = [] # holds the remaining unread words nextword = "" # holds the first unread word # global invariant: nextword + wordlist == all remaining unread words EOF = "!" # a word that marks the end of the input words

def getNextword(): """moves the front word in wordlist to nextword. If wordlist is empty, sets nextword = EOF """ global nextword, wordlist if wordlist == []: nextword = EOF else: nextword = wordlist[0] wordlist = wordlist[1:]

#####

def error(message): """prints an error message and halts the parse""" print("parse error: " + message) print(nextword, wordlist) raise Exception

def isVar(word): """checks whether word is a legal variable name""" # TODO # modify the KEYWORDS to include "if", "else" KEYWORDS = ("print", "while", "end", "if", "else") ans = (word.isalpha() and not (word in KEYWORDS)) return ans

def parseEXPR(): """builds an ETREE from the words in nextword + wordlist, where EXPR ::= NUMERAL | VAR | ( EXPR OP EXPR ) OP is "+" or "-" and ETREE ::= NUMERAL | VAR | [OP, ETREE, ETREE] Also, maintains the global invariant (on wordlist and nextword) """ if nextword.isdigit(): # a NUMERAL ? ans = nextword getNextword() elif isVar(nextword): # a VARIABLE ? ans = nextword getNextword() elif nextword == "(": # ( EXPR op EXPR ) ? getNextword() tree1 = parseEXPR() op = nextword if op == "+" or op == "-": getNextword() tree2 = parseEXPR() if nextword == ")": ans = [op, tree1, tree2] getNextword() else: error("missing )") else: error("missing operator") else: error("illegal symbol to start an expression")

return ans

def parseCOMMAND(): """builds a CTREE from the words in nextword + wordlist, where COMMAND ::= VAR = EXPRESSSION | print VAR | while EXPRESSION : COMMANDLIST end | if EXPRESSION : COMMANDLIST else COMMANDLIST end and CTREE ::= ["=", VAR, ETREE] | ["print", VAR] | ["while", ETREE, CLIST] | ["if", ETREE, CTREE, CTREE] Also, maintains the global invariant (on wordlist and nextword) """ if isVar(nextword): # VARIABLE = EXPRESSION ? v = nextword getNextword() if nextword == "=": getNextword() exprtree = parseEXPR() ans = ["=", v, exprtree] else: error("missing =") elif nextword == "print": # print VARIABLE ? getNextword() exprtree = parseEXPR() ans = ["print", exprtree] elif nextword == "while": # while EXPRESSION : COMMANDLIST end ? getNextword() exprtree = parseEXPR() if nextword == ":": getNextword() else: error("missing :") cmdlisttree = parseCMDLIST() if nextword == "end": ans = ["while", exprtree, cmdlisttree] getNextword() else: error("missing end") # TODO # complete this part of the code here # elif nextword == "if": # if EXPRESSION : COMMANDLIST else COMMANDLIST end # getNextword() # exprtree = parseEXPR() # if nextword == ":" : # getNextword() # else : # #error(..) # clisttree1 = parseCMDLIST() # # check next word is "else" or not # # if it is, then get next word # # call parseCMDLIST() to get the tree for the else part statements # # otherwise report syntax error missing "else" # # check next word is "end" or not # # if it is: # # ans = ["if", exprtree, clisttree1, clisttree2] # # call get next word # # otherwise report error missing "end" else: # error -- bad command error("bad word to start a command") return ans

def parseCMDLIST(): """builds a CLIST from the words in nextword + wordlist, where COMMANDLIST ::= COMMAND | COMMAND ; COMMANDLIST and CLIST ::= [ CTREE+ ] Also, maintains the global invariant (on wordlist and nextword) """ ans = [parseCOMMAND()] # parse first command while nextword == ";": # collect any other COMMANDS getNextword() ans.append(parseCOMMAND()) return ans

def parsePROGRAM(): """builds a PTREE from nextword + wordlist, where PROGRAM ::= COMMANDLIST and PTREE ::= [ CLIST ] """ cmds = parseCMDLIST() ans = [cmds] return ans

def parse(words): """reads the input program, initializes the nextword and wordlist, and builds an operator tree

precondition: words is a list of strings, the words in the program postcondition: returns an operator tree for wordlist """ global wordlist # we will reset this global variable wordlist = words getNextword() # assert: global invariant for nextword and wordlist holds true here tree = parsePROGRAM() # assert: tree holds the entire operator tree for text # print "The parsed program is:" # print(tree) # print if nextword != EOF: error("there are extra words") return tree

REQUIRED TEST CASES ---------------------

1.

if (2 + 1): print 99 else print 88 end !

2a.

x = 2; print x !

2b. x = 2; y = (x + 1) !

3.

x = 2; while x : print x end; if (x + 1) : print x else print (x-9) end !