problem 1: Given the production:

S-> aSAb | Ab
A-> bbb
implement a complete pseudo code for a recursive descent parser. Assume scanner ( ) returns the next token.

problem 2: Give all needed first and follow sets needed to check if the grammar is LL(1). Is it?:

S -> aA | BB
A -> aaA | empty
B -> bB | Cd
C -> cA | dC

problem 3: A function returns a number, takes no arguments, and its body is a block. Functions are defined exactly like variables in the grammar except that function name is follow by a block. Show the grammar. Is the resulting grammar LL(1)?

problem 4: A function definition must be before the program token, and functions cannot be nested (exactly like in C). Every function has a return type (no void) and one argument. Function call is like in C, with an expression for the argument and the function call itself is an expression. Show the grammar. exs:

int fun1(long x)
begin
/* same as in any block*/
end;
long fun2(int x)
begin
/** ... */
end;
program xxx(void)
begin
int x;
x=fun1(5+2)*10;
end;

problem 5: Design unambiguous grammar to parse expressions involving +, -, *, / and unary -. Unary minus is strongest, followed by * and /(same precedence, right associative), then +, left associative, then finally -, left associative. Do not use any other operators, and use only number tokens.

problem 6: Assume function f ( ) has local variables a, b, and function g is nested inside of f ( ) and has local variable a. There is also a global variable c.

a) show the complete memory space for the program when it begins execution
b) show the stack after f ( ) is called, which subsequently calls g ( ), which calls itself once.
c) assume we have three statements in g ( )

stat1: c=10;
stat2: a=20;
stat3: b=30;
how would they be translated by the compiler: describe in words.

problem 7: Show the grammar for:

a) Allow global variables placed just before the first begin – these variables are optional and are listed separated by commas. For ex:

program
int x,y,z;
begin {etc.}

b) Also allow functions. Each function takes any number of arguments and always returns an integer. Parameter list is C-like, and the return statement (followed by an expression) is mandatory. Functions can be called in place of any expression. Functions are defined with a block, which is the same as the begin-end block in our grammar. Functions are defined separately, as in C but before the main program. Assume we have a multi-pass compiler so that prototypes is not an issue. The following is an ex program

int sum(int a, b) {paramater list is same as for globals}
begin
int c;
return a+b;
end;
program
int x,y;
begin
readI(x);
readI(y);
z:=10+sum(x,y+1);
prepareI(z);
end.

problem 8: Given the program (like Pascal, with nested functions)

int x, y; {global}
function A
begin
int z; {z is in A}
function B {B is defined inside A}
begin
int x; {x is in B}
function C {C is inside B}
begin
int x; {x is in C}
z:=10:
x:=100;
y:=1000;
C(); {recursive call on C}
end; {end of C}
C();
end; {end of B}
B(); { A calls B}
end; {end of A}

a) show ARs (activation Records) for A, B, C (show only local data, static and dynamic link}
b) What is in the persistent data space?
c) assume call to A() is done somewhere. Then, show that contents of the stack during the 3rd recursive call to C(). Make sure to fill out all info on the stack.
d) How would the left-hand-side variables in C()be translated by the compiler (describe in words, separately for each variable).

problem 9: Given the grammar, with lower case terminals and upper case nonterminals, and S the initial nonterminal

S -> aS | aA | bA
A -> Aa | ABb | cA
B -> bB | bdB | c

a) remove left recursion as needed, showing the modified grammar

b) left-factorize as needed what you get in a), showing the new grammar

c) Is the resulting grammar LL(1)? Argue piece by piece why it is or why it is not, showing all (and only the necessary) First and Follow sets.

problem 10: Assume the following static program structure, show the static chains and display when exactly five ARs are on the stack, assuming procedure A is called first.

proc A
begin /* proc A */
proc B
begin /* proc B */
proc C
begin /* proc C */
call A
end /* proc C */
call C
end /* proc B */
proc D
begin /* proc D */
call B
end /* proc D */
call D
end /* proc A */