CD |Gate-2012| Previous Year Questions| Set-9

Set-15 GATE-2006 CD

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

 Ab$
SE1E2S→ ε
AA → SA → SError
B B → SB → SE3

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. \epsilon is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.

S→aAbB |bAaB| ε
A → S
B → S

 Ab$
SE1E2S→ ε
AA → SA → SError
B B → SB → SE3

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)


Back to GATE-HOME


Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *