2. [7 pts] Consider the following grammar for simple arithmetic expressions (num is a token representing an integer): -> term {('+'|'-') term} -> factor {('*'1'/') factor} factor -> '-' factor '('exp')' exp term num Here is a sample expression written in this language: 12 + 2 * (10 - - 4 / 2) + 6 Note that the symbol '-' denotes both the unary negative operator and the binary subtraction operator. You are to write two parsers and an interpreter for this language. (a) [3] The first parser only verifies the input, it does not generate output. If the input string is a syntac- tically correct program, the parser prints "OK"; otherwise it raises an exception with an informative error message. The file arithexo.py contains a partially implemented parser function, parse(str). Your task is to complete the implementation. Recall in Lab 3, you worked on a regular expression parser, regex.py. This new parser shares the same program structure as the regex parser. However, there are two noticeable differences: The regex language is "character-based, meaning that every token is a single character. The arithex language, on the other hand, has an integer token that can have multiple digits. The regex expressions are "compact", meaning that there is no whitespace in the input string. The arithex expressions, on the other hand, allow whitespace. In completing the parser implementation, you need to pay attention to these two issues. Specifically, in the function next(), you need to add code to skip over whitespace, so that next() always returns the next non-space character. In the function factor(), in handling the num token, you need to add code to collect all the digits of the integer. (Hint: The utility functions next() and advance() can help in this case.) Make sure you test your program not only with correct inputs, but also with incorrect ones. Here are some sample test cases, included in the testing section of arithexo.py: if __name_- _main__": parse('12 + (4 * 2 - 5)') parse ('12 + 2 + (10 - - 4 / 2) + 6') # below are error cases; should test each one separately parse('x') # parse('1=2') # parse('1++2') # parse('(1+2') 11 # Usage: linux> ./python3 arithexo.py 'arith exp' # import sys # str is an input program, e.g. '12 + (4 * 2 - 5)' def parse(str): i = 0 # idx to input string # lookahead next non-space char, return '$' if reaches the end def next(): # ... add code to skip spaces if i term {('+'|'-') term} def exp(): term() while next() == '+' or next() == advance() term() 1-': # term -> factor {('*'|'/') factor} def term(): # ... add code pass I-': # factor -> '-' factor | '('exp')' | num def factor(): if next() == # add code elif add code else: C = next(). if not c.isdigit(): raise Exception("expected a number, got # ... add code to collect all digits # 11 + c) # parsing starts here exp() if i term {('+'|'-') term} -> factor {('*'1'/') factor} factor -> '-' factor '('exp')' exp term num Here is a sample expression written in this language: 12 + 2 * (10 - - 4 / 2) + 6 Note that the symbol '-' denotes both the unary negative operator and the binary subtraction operator. You are to write two parsers and an interpreter for this language. (a) [3] The first parser only verifies the input, it does not generate output. If the input string is a syntac- tically correct program, the parser prints "OK"; otherwise it raises an exception with an informative error message. The file arithexo.py contains a partially implemented parser function, parse(str). Your task is to complete the implementation. Recall in Lab 3, you worked on a regular expression parser, regex.py. This new parser shares the same program structure as the regex parser. However, there are two noticeable differences: The regex language is "character-based, meaning that every token is a single character. The arithex language, on the other hand, has an integer token that can have multiple digits. The regex expressions are "compact", meaning that there is no whitespace in the input string. The arithex expressions, on the other hand, allow whitespace. In completing the parser implementation, you need to pay attention to these two issues. Specifically, in the function next(), you need to add code to skip over whitespace, so that next() always returns the next non-space character. In the function factor(), in handling the num token, you need to add code to collect all the digits of the integer. (Hint: The utility functions next() and advance() can help in this case.) Make sure you test your program not only with correct inputs, but also with incorrect ones. Here are some sample test cases, included in the testing section of arithexo.py: if __name_- _main__": parse('12 + (4 * 2 - 5)') parse ('12 + 2 + (10 - - 4 / 2) + 6') # below are error cases; should test each one separately parse('x') # parse('1=2') # parse('1++2') # parse('(1+2') 11 # Usage: linux> ./python3 arithexo.py 'arith exp' # import sys # str is an input program, e.g. '12 + (4 * 2 - 5)' def parse(str): i = 0 # idx to input string # lookahead next non-space char, return '$' if reaches the end def next(): # ... add code to skip spaces if i term {('+'|'-') term} def exp(): term() while next() == '+' or next() == advance() term() 1-': # term -> factor {('*'|'/') factor} def term(): # ... add code pass I-': # factor -> '-' factor | '('exp')' | num def factor(): if next() == # add code elif add code else: C = next(). if not c.isdigit(): raise Exception("expected a number, got # ... add code to collect all digits # 11 + c) # parsing starts here exp() if i