Final ExamCSC 4101, Fall 20047 December 2004Scan the whole exam first (there are a total of 7 pages) and plan your time. You have 1 hour, 50 minutes to completeall five questions. There are a total of 100 points. The exam is open book, open notes, and closed neighbors. GoodLuck and Have a Cool Yule!Name:11. (20 pts)The following grammar<qualname> -> IDENT| <qualname> DOT IDENT<expr> -> INTCONST| <qualname>| <expr> DOT IDENT| <expr> LBRACK <expr> RBRACKdefines a subset of Java expressions. E.g., it allows expressions of the forma.b.c[1].x[2].y.z[3][4][5](a) (5 pts)What are the problems (if any) with this grammar that might prevent us writing a recursive descent parserfor this grammar.(b) (5 pts)Rewrite <qualname> so it can be parsed with a recursive descent parser. Do not use EBNF.(c) (5 pts)Rewrite <expr> so it can be parsed with a recursive descent parser assuming that <qualname> is aterminal symbol. Do not use EBNF.(d) (5 pts)Is the above grammar ambiguous? If yes, provide an input string that can be parsed in more than one way.If no, explain why not. Is your modified grammar ambiguous?22. (20 pts)We have seen that different languages require different run-time data structures for representing activationrecords of functions. Assuming that the language allows recursive functions (and ignoring the use of regis-ters for optimization purposes), we have the following design choices:• use a static link or don’t use a static link,• use a dynamic link or don’t use a dynamic link,• allocate activation records on the stack or on the heap,• represent functions as simple function pointers or as closures.For the following languages, state which implementation mechanisms you need. Note that when an exceptionis thrown, we need to find the exception handler along the call chain.(a) (5 pts)Pascal: static scoping, nested functions, no functions as return values, no exceptions(b) (5 pts)C++: static scoping, no nested functions, functions as return values, exceptions(c) (5 pts)Scheme: static scoping, nested functions, functions as return values, no exceptions(d) (5 pts)ML: static scoping, nested functions, functions as return values, exceptions33. (20 pts)Consider the following program fragment in C-style syntax, but with static scoping:void test() {int a[5];int i;void f(int x) {a[i] = 9;i++;i = x;}i = 1;a[1] = 7;a[2] = 4;f(a[i]);// print i and a[1]}What are the values of i and a[1] after function f returns if the parameter is passed byi a[1]valuereferencecopy-in-copy-outneed44. (20 pts)For each of the following two ML functions, state in English what the function does and translate the functioninto Scheme. The types of the ML functions are provided in comments for reference.(a) (10 pts)The function foo takes a function and a list as argument and returns a list.(* val foo = fn : (’a -> ’b) -> ’a list -> ’b list *)fun foo f nil = nil| foo f (h::t) = f h :: foo f t(b) (10 pts)The function bar takes a binary function, a value, and a list as arguments and returns a value.(* val bar = fn : (’a * ’b -> ’b) -> ’b -> ’a list -> ’b *)fun bar f b nil = b| bar f b (h::t) = f (h, bar f b t)The operator :: corresponds to cons in Scheme.Hint: for finding out what the functions do, take ’a and ’b to be int, pick some simple argument values thatfit the types, and trace the functions.55. (20 pts)Translate the following Scheme code into a C++ or Java class hierarchy.;; Tree data structure:;; (leaf integer-value);; (node left-subtree right-subtree);; E.g.,;; (node (leaf 1) (node (leaf 2) (leaf 3)));; Add all leaf values in the tree(define (sum t)(if (eq? (car t) leaf)(cadr t)(let ((left (caddr t))(right (cadddr t)))(+ (sum left) (sum right)))))Define the class hierarchy with classes Tree, Leaf, and Node, such that the following code works (in C++syntax):Tree * left = new Leaf(1);Tree * right = new Node(new Leaf(2), new Leaf(3));Tree * root = new Node(left, right);int h = root->sum();where sum() is a virtual function. Do not use an if-then-else.6(Additional space for answering question