Use Python to finish an parser for the mini-command language in the Lecture Notes 1, extended with if-else commands, then it will be able to parse a sample program looks like this:

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

Here is the execution of this program:

python run.py Type program; OK to do it on multiple lines; terminate with ! as the first symbol on a line by itself: x = 2; while x : print x end; if (x + 1) : print x else print (x-9) end ! scanned program: ['x', '=', '2', ';', 'while', 'x', ':', 'print', 'x', 'end', ';', 'if', '(', 'x', '+', '1', ')', ':', 'print', 'x', 'else', 'print', '(', 'x', '-', '9', ')', 'end'] parsed program: [[['=', 'x', '2'], ['while', 'x', [['print', 'x']]], ['if', ['+', 'x', '1'], [['print', 'x']], [['print', ['-', 'x', '9']]]]]] press Enter key to finish

The program is parsed into its tree.

Here the grammar of the language we implement:

===================================================

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 ===================================================

A scanner essentially same as the one in Lecture Note 1 to build parse trees for this grammar has been provided, you job is to modify the parser so that it will parse if-else as well with grammar defined above.

Abstract syntax tree (operator tree) format

The parser will construct the list-represented tree for a program. The syntax of trees is this:

===================================================

PTREE ::= [ CLIST ]

CLIST ::= [ CTREE+ ]

where CTREE+ means one or more CTREEs

CTREE ::= ["=", VAR, ETREE] | ["print", ETREE] | ["while", ETREE, CLIST] | ["if", ETREE, CLIST, CLIST]

ETREE ::= NUMERAL | VAR | [OP, ETREE, ETREE]

where OP is either "+" or "-" ===================================================

Notice how the trees match the grammar constructions. Since the trees are nested lists, it is easy to disassemble them and compute on their parts.

Please complete TODO portion please and thank you very much...

"""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