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.