S → Aa
A → BD
B → b | ε
D → d | ε

Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $}, then the answer should be 3210)

    S' → S
    S → 〈L〉 | id
    L → L,S | S

Let I₀ = CLOSURE ({[S' → ·S]}). The number of items in the set GOTO (I₀ , 〈 ) is: _____.

Consider the following grammar and the semantic actions to support the inheriteatd type declaration attributes. Let X₁, X₂, X₃, X₄, X₅ and X₆ be the placeholders for the non-terminals D, T, L or L₁ in the following table:

Which one of the following are the appropriate choices for X₁, X₂, X₃ and X₄?

Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #.

Which one of the following is correct for the given parse tree?

A lexical analyzer uses the following patterns to recognize three tokens T₁, T₂, and T₃ over the alphabet {a,b,c}.

T₁: a?(b∣c)*a
T₂: b?(a∣c)*b
T₃: c?(b∣a)*c

Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix.

If the string bbaacabc is processes by the analyzer, which one of the following is the sequence of tokens it outputs?

Consider the following intermediate program in three address code

           p = a - b
           q = p * c
           p = u * v
           q = p + q

Which of the following corresponds to a static single assignment form of the above code?

Consider the following grammar:

What is FOLLOW(Q)?

Consider the following grammar:

    stmt    →  if expr then expr else expr; stmt | ȯ
    expr    →  term relop term | term
    term    →  id | number
    id      →  a | b |  c
    number  → [0-9]

where relop is a relational operator (e.g., <, >, …), ȯ refers to the empty statement, and if, then, else are terminals.

Consider a program P following the above grammar containing ten if terminals. The number of control flow paths in P is ________. For example, the program

     if e1 then e2 else e3

has 2 control flow paths, e₁ → e₂ and e₁ → e₃.

Consider the expression (a-1)*(((b+c)/3)+d)). Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which (i) only load and store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands. The value of X is ___________.

Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it:

Which of the following statements about parser is/are CORRECT?

I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR.
III. SLR is more powerful than Canonical LR.

Consider the following expression grammar G:

E → E - T | T
T → T + F | F
F → (E) | id

Which of the following grammars is not left recursive, but is equivalent to G?

Consider the following code segment.

x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;

The minimum number of  variables required to convert the above code segment to static single assignment form is ________.

The attributes of three arithmetic operators in some programming language are given below.

Operator      Precedence     Associativity     Arity 
   +             High            Left          Binary
   −            Medium           Right         Binary
   ∗             Low             Left          Binary

The value of the expression 2 – 5 + 1 – 7 * 3 in this language is __________.

Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S, A} and terminals {a,b}.

  S → aA   { print 1 }
  S → a    { print 2 }
  A → Sb   { print 3 }

Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:

Match the following:

(P) Lexical analysis              (i) Leftmost derivation
(Q) Top down parsing             (ii) Type checking
(R) Semantic analysis           (iii) Regular expressions
(S) Runtime environments         (iv) Activation records

Which one of the following grammars is free from left recursion?

Which one of the following is True at any valid state in shift-reduce parsing?

1. There exists a statement Sj that uses x
2. There is a path from Si to Sj in the flow
   graph corresponding to the program
3. The path has no intervening assignment to x 
   including at Si and Sj

  S → F ⎪ H
  F → p ⎪ c
  H → d ⎪ c

S1: LL(1) can parse all strings that are generated using grammar G.
S2: LR(1) can parse all strings that are generated using grammar

S --> L. > R
Q --> R.

I) 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1

    S --> T * P 
    T --> U | T * U
    P --> Q + P | Q
    Q --> Id
    U --> Id

  t0 = i ∗ 1024
  t1 = j ∗ 32
  t2 = k ∗ 4
  t3 = t1 + t0
  t4 = t3 + t2
  t5 = X[t4]

X -> c.X, c/d
   X -> .cX, c/d
   X -> .d, c/d
   X -> c.X, $
   X -> .cX, $
   X -> .d, $

1. Cannot be merged since look aheads are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.

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.

 
    a = 1
    b = 10
    c = 20
    d = a+b
    e = c+d
    f = c+e
    b = c+e
    e = b+f
    d = 5+e
    return d+f

S --> iCtSS1|a
S1 --> eS|ε
C --> b

P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar

S --> aB        S --> bA
B --> b         A --> a
B --> bS        A --> aS
B --> aBB       A --> bAA

S --> aB        S --> bA
B --> b         A --> a
B --> bS        A --> aS
B --> aBB       A --> bAA

S -> S * E
S -> E
E -> F + E
E -> F
F -> id

(i) S -> S * .E
(ii) E -> F. + E
(iii) E -> F + .E

S → FR
R → S | ε
F → id

subroutine swap(ix,iy)
     it = ix
L1 : ix = iy
L2 : iy = it
end
  ia = 3
  ib = 8
  call swap (ia, 1b+5)
  print *, ia, ib
end

 E → number 	 E.val = number. val
    | E '+' E 	 E(1).val = E(2).val + E(3).val
    | E '×' E	 E(1).val = E(2).val × E(3).val

 E → number 	 E.val = number. val
    | E '+' E 	 E(1).val = E(2).val + E(3).val
    | E '×' E	 E(1).val = E(2).val × E(3).val

E → E + n | E × n | n

S → (S) | a

S → i E t S S' | a
S' → e S | ε
E → b

S → C C
C → c C | d

S → T R
R → + T {print ('+');} R | ε
T → num {print (num.val);}

S → id : = E  {gen (id.place = E.place;);}
E → E1 + E2   {t = newtemp ( ); gen (t = El.place + E2.place;); E.place = t}
E → id     {E.place = id.place;}

A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which one of the following is true?