CD |Gate-2012| Compiler Design
1. Consider the program given below, in a block-structured pseudo-language with lexical scoping and nesting of procedures permitted.
Program main;
Var …
Procedure A1;
Var …
Call A2;
End A1
Procedure A2;
Var …
Procedure A21;
Var …
Call A1;
End A21
Call A21;
End A21
Call A1;
End main.
Consider the calling chain : Main->A1->A2->A21->A1 The correct set of activation records along with their access links is given by : [GATE – 2012]
a.
b.
c.
d.
Answer : d)
2. For the grammar below, a partial LL (1) parsing along with the grammar . Entries that need to be filled are indicated as E1, E2 and E3 .ε is the empty string , $ indicates end of input , and , | separates alternate right hand sides of productions .
S→aAbB |bAaB| ε
A → S
B → S
| A | b | $ | |
| S | E1 | E2 | S→ ε |
| A | A → S | A → S | Error |
| B | B → S | B → S | E3 |
The first and Follow sets for the non-terminals A and B are: [GATE – 2012]
a. FIRST(A) = {a,b,ε} = FIRST(B)
FOLLOW(A) = {a,b}
FOLLOW(B) = {a,b,$}
b. FIRST(A) = {a,b,$}
FIRST(B) = {a,b,ε}
FOLLOW(A) = {a,b}
FOLLOW(B) = {$}
c. FIRST(A) = {a,b,ε} = FIRST(B)
FOLLOW(A) = {a,b}
FOLLOW(B) = ∅
d. FIRST(A) = {a,b} = FIRST(B)
FOLLOW(A) = {a,b}
FOLLOW(B) = {a,b}
Answer : a)
CD |Gate-2012|
3. For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.
S→aAbB |bAaB| ε
A → S
B → S
| A | b | $ | |
| S | E1 | E2 | S→ ε |
| A | A → S | A → S | Error |
| B | B → S | B → S | E3 |
The appropriate entries for E1, E2 and E3 are :
Note:In the table second column first row it’s not “A” it’s “a”. [GATE – 2012]
a. E1: S → aAbB,A → S
E2: S → bAaB,B→S
E3: B → S
b. E1: S → aAbB,S→ ε
E2: S → bAaB,S → ε
E3: S → ε
c. E1: S → aAbB,S → ε
E2: S → bAaB,S→ε
E3: B → S
d. E1: A → S,S →ε
E2: B → S,S → ε
E3: B →S
Answer : c)