Programming Languages – Final ExamGeneral Directions:QuestionsG22.2210-001 Programming Languages 1 Final ExamProgramming Languages – Final ExamGeneral Directions:1. This is an open book test; you may bring any kind of books or notes to the room. No computers, no communication2. Each question is preceded by a numeric score in square brackets: that score indicates both the weight of the question, and a (high) estimate of how many minutes you should be spending on it. The total is 100. The official exam period is 110 minutes.3. Write your answers on the examination paper. We don’t expect you will need additional sheets, but there will be a supply of extra paper. Be sure to write your name on any sheet that you will be submitting.Name______________________G22.2210-001 Programming Languages 2 Final ExamQuestions1. Context-free (BNF) grammar [3]Here is a piece of a BNF grammar for a language with IF statements:statement ::= simple-statement |if-statementif-statement ::= “IF” “(“ expression “)” “THEN” statement [“ELSE” statement ] (The square brackets indicate that the [“ELSE” statement] is optional.)It was recognized early on that this grammar was ambiguous, because of the so-called “dangling ELSE” problem.Assume that “x == 0” reduces to “expression”, that “print x;” reduces to “statement”. Show that the statement:IF (x == 0) THEN IF (x == 0) THEN print x; ELSE print x;has two different parse trees, thereby demonstrating that the grammar is ambiguous.The outer if-statement could reduce to “IF ( expression ) THEN statement”, where “statement”reduces to “IF ( expression ) THEN statement ELSE statement”.Alternatively, the outer if-statement could reduce to “IF ( expression ) THEN statement ELSE statement” where the first “statement” reduces to “IF ( expression ) THEN statement”.Name______________________G22.2210-001 Programming Languages 3 Final Exam2. Argument passing [2 + 2 + 2 = 6]. In a hypothetical imperative language (I am giving it Java syntax), here is a calling program:// callerint[] a = {2, 5, 8, 10}; // that is, a[0] = 2, a[1] = 5, a[2] = 8, a[3] = 10int i = 0;int j = sub(a[++i]); // Note: expression ++i first increments i, then // returns the incremented value.Here is a called program:// calleeint sub (int p) { int x = p; p = p + x; return x;}What values in the calling program change1 if arguments are: (a) passed by value, as in Java or C? (Underlined parts are part of the answer students must give; the rest is an explanation.)First i becomes 1, then a[1] is evaluated to 5, and 5 is passed by value to sub, where it is bound to p. Then x = 5. Then p is set to 5 + 5, or 10. The value 5 is returned to j.(b) passed by reference, as in Fortran? First i becomes 1, then a[1] is passed by reference to sub, where it is bound to p. Then x is set toa[1], or 5. Then a[1] is added to 5, producing 10. The value 10 is then stored into p, which means a[1] gets the value 10. The value 5 is returned to j. (c) passed by name, as in Algol? In call by name, the expression is not initially evaluated, but is passed to the parameter p. The first statement evaluates p, which will evaluate a[++i], incrementing i to 1, and assigning a[1], or5, to x. The next statement evaluates p + x. This time, a[++i] is evaluated again, setting i to 2, and returning a[2], or 8. The expression evaluates to 8+5=13, which is then stored in p, which will cause i to be incremented to 3, and 13 is stored in a[3]. The value x , or 5, is returned to j.Some students did not realize that in p = p + x, the right side is evaluated before the left side. Therefore, the p on the right side becomes a[2], and the p on the left side becomes a[3].1 In class, this was clarified to “Which variables from a, i, and j in the calling program change after the statement that calls sub and what do they change to?”Name______________________G22.2210-001 Programming Languages 4 Final Exam3. Mimicking call-by-name with closures [12]. For the program of Question 2, assume the language is really Java, which has call by value, but we want to get the effect of call by name. Rewrite the program to obtain this effect by (a) creating a closure, including a get and set method, (b) passing it to sub at the call site, and (c) modifying sub to use the closure. That is:class Closure {// fill in closure here private int[] a; // holds a reference to a private int i; // holds a copy of i public Closure(int[] a, int i) {this.a = a; this.i = i;} public int getI() { return i;} // retrieves i public int get() {return a[++i];} // evaluates a[++i] public void set(int arg) {a[++i] = arg;} // stores into a[++i]}// caller:int[] a = {2, 5, 8, 10}; int i = 0;// ... create a closure instance that will simulate calling// sub and passing it a[++i] by name Closure c = new Closure(a, i); // make a closure, passing a and iint j = sub(c); // call sub passing it the closurei = c.getI(); // retrieve the updated value of i// callee – modify to invoke the closure to read/write the parameterint sub (Closure p) {// same as original sub with reads of p replaced by p.get()// and assignment to p replaced by p.set(…)int x = p.get(); p.set(p.get() + x);return x;}Discussion: Call by name is equivalent to passing a closure containing an expression, without evaluating the expression. Many students missed the basic point, that the evaluation of ++i must happen inside the closure that is invoked by the callee, not inside the caller. In Java, you need a Closure object with two methods, one to read the parameter, and one to write it. When the closure is constructed, it is passed access to a and i. The subroutine sub calls get or set each time p appears on the right or left, respectively. The get method evaluates the expression a[++i] returning the result; the set method stores a number into a[++i]. One wrinkle in Java is that unlike the array, the integer i can’t be passed into the closure’s constructor by reference; it must be copied to the closure at construction time, and after the call isName______________________G22.2210-001 Programming Languages 5 Final Examcomplete, the changed value of i must be copied back from the closure and stored into i. Many students who got the rest right missed this!Name______________________G22.2210-001 Programming Languages 6 Final Exam4. Variant records [1 + 1 + 3 = 5]. Here