Reference no: EM132706832

Assignment

1 LR(1) Grammars
Consider the following grammar, where {a,b,c,d,e} are terminal symbols and S is the initial symbol.
S → A a (1)
S → e (2)
A → d B (3)

A → b B S (4)

B → c B (5)
B → ? (6)

1. Write the First sets for all non-terminal symbols of the grammar.

2. Construct the full LR(1) DFA, showing all items in each state.

3. Construct the LR(1) parsing table using the DFA. For the reduce actions, use the provided enumeration of the productions in the grammar.

4. Show all steps required to parse the following string: bbcceaa

5. Is this grammar LALR(1)?

2 Activation Records

In the following listing we show an excerpt of a program in a language that allows nested definitions for functions and uses call-by-value:int collatz_length(int n, int len) {

boolean collatz_base() { return n == 34;
}

if (collatz_base()) return len + 13;
else
if ((n mod 2) == 1)
return collatz_length(3 * n + 1, len + 1); else
return collatz_length(n div 2, len + 1);
}

Suppose we have in our main() function a call to collatz length(7, 0). Assume that the compiler allocates all the variables (i.e. both named and temporary) on the stack.
Questions
1. What will the return value of this call be?
2. What is the maximum number of activation records that will ever be in the stack before the call from main returns? (Assume that the compiler does not optimize tail calls.)

3. Give a diagram of the state of the stack just before collatz base returns true. Your diagram should contain at least the following information:
(a) Boundaries of the activation records.
(b) Location and content of the actual parameters for the calls to the functions.
(c) Where in the stack is the value of n, for which collatz base returns true.
(d) Location of the return values.
(e) Location of the return addresses.
(f) Location and content of the control links and access links.
(g) Optional: Location and content of temporary variables.
4. How should the value of n be retrieved, in order to make the comparison in collatz base?

5. Optional: Describe briefly the tail call (or tail recursion) optimization and whether it can be applied to this code snippet. You can read about it in the Wikipedia.

Attachment:- CSE_assignment 3.rar