Ex. 1. a. Draw the parsing trees for the expression
a * b - (3 + a)using the grammar from the slides.
b. Show the steps taken by the parser to check that the expression above is correct from the point of view of the grammar. Show what the parsed string is at each step.
Ex. 2. a.The following grammar is not LL(k), for any given constant k, where a, b, 0, 1 are terminal symbols, and A, B, G are non terminal symbols. Justify why.
G => a A b G => a B b b A => a A b A => 0 B => a B b b B => 1
b. What kind of strings does this grammar produce / recognize?
Note. This homework can be turned in either electronically or on paper.
Ex. 3. Justify if the following grammar is LL(k) for any given constant k. If yes, what is the constant? All the keywords in lowercase and the punctuation are terminal tokens, the others are non terminals. This represents a conditional in Python. Note that the expression and the statement are considered terminals in this case. There are two non terminals below: Cond and Elif_stmt.
Cond => if expr : stmt Cond => if expr : stmt else : stmt Cond => if expr : stmt Elif_stmt Elif_stmt => elif expr : stmt else : stmt Elif_stmt => elif expr : stmt Elif_stmt
Ex. 1 Download the following Lisp source file: parse_expr.el. This file contains a partial implementation of the parse functions to recognize arithmetic expressions using the recursive descent approach.
a. Complete the implementation of the parse functions that both check if the expression is correct and return the parse tree. Note that the functions parse-T and parse-TT were implemented in a temporary version to allow testing the other parse functions that needed them. The results shown in the file for the testing are also temporary.
b. Download one of the following two files (or both):
eval1_expr.el
eval2_expr.el
The first one implements the evaluation of a parse tree using an additional parameter. The second one implements the evaluation of a parse tree using lambda expression. Both of them contain a couple of examples of such evaluation functions for the arithmetic expressions, but they are not complete. Both of them implement the evaluation for the symbol T (term) is a temporary manner returning a constant for the purpose of testing the other functions.
Complete the implementation of the evaluation functions in the form of your choice.
Note. Notice that the evaluation file loads the parsing file at the beginning. Once you implement the parsing correctly you can evaluate the load-file expression to import it into the evaluation file. The load function evaluation all of the expressions in that file during the load, so you'll have to comment out the result of any evaluation you do in that file (as in the examples I provided in the file).
Send the completed file parse_expr.el and your choice of eval1_expr.el or eval2_expr.el.