Consider the following grammars where anything starting in a lowercase or special character (parenthesis, colon) is a terminal symbol, and anything starting in an uppercase is a non-terminal symbol. Are these grammars LL(k) for some k, and if yes, what is the value of k? Explain your answer.

a.
A => a B a a
A => b B b a
B => b
B => epsilon

b.
ClassAttr => Name ( ) ;
ClassAttr => Name ;
Name => id Qual
Qual => . id Qual
Qual => epsilon

Download the following Lisp source file:
parse_expr.el
This file contains a partial implementation of the parse functions to recognize arithmetic expressions based on the grammar discussed in class (see Arithmetic Expression here or in the PowerPoint slides) 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.

Reference: rec_descent.el expr.el.

b. (Optional, 3 extra credit points) Download one of the following two files:
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.

a. Draw the parsing trees for the expression

a * b - (3 + a)

b. Show a few (at least 7) of 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 in each step.

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).

Upload the relevant files to Canvas.