1. Four small grammars are given below:
a) For each grammar, show whether or not it is suitable for LL(1) parsing.
b) For each grammar, show whether or not it is suitable for LL(2) parsing.
c) Choose ONE grammar that is not suitable for LL(1), and using standard transformations, make it suitable for LL(1).
1. S--> a S b | S b a | S a b | e
2. S--> a b S | a c S | b a
2. S--> a S b | a S c | b a
4. S--> a S b | b S a | e
2. Consider the C-like function below.
int f(int n) {
if (n==0 || n==1)
return 1;
else
return f(n-1) + f(n-2);
}
a) What will an "activation record" for this function look like? Show ONE typical example of an activation record, including all necessary links, variables, and parameters.
b) What is the greatest height of the run time stack used during the evaluation of this function for f(100); (i.e., what is the maximum number of activation records needed)? Describe which activation records will be on the stack at the maximum.
3. Consider the code generated for the following while statement in a language that does short-circuit evaluation (Program has declared a,b integer variables, MAX as an integer constant).
while (a<5 || b<=2*MAX) {
a = a + b + 1;
b = a + b + 1;
}
a) Give the intermediate code generated for this block of code (you may invent a suitable form and operations for the intermediate code).
b. Briefy analyze your code for efficiency. State what optimizations should be done.
4) Consider the following program written in some new language that uses the keywords "IN OUT" for one method of passing parameters. This new language uses static scope rules.
int b:=11; int c:=9; // declare and initialize b and c
procedure first(IN OUT int x,y);
begin
=x-y; // := is the assignment operator
b:=5;
c:=6;
if(x==b) then =7; // == is test-for-equality operation
end;
begin {test}
first(b,c);
print("b and c are:",b,c);
end;
What are the results of this program if:
a) IN OUT is implemented by call-by-copy.
b) IN OUT is implemented by call-by-reference.