Consider the following grammar.

     S → aSB|d
     B → b 

The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is _______.

Consider the following statements.

I. Symbol table is accessed only during lexical analysis and syntax analysis.
II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment.
III. Errors violating the condition ‘any variable must be declared before its use’ are detected during syntax analysis.

Which of the above statements is/are TRUE?

Consider the productions A⟶PQ and A⟶XY. Each of the five non-terminals A, P, Q, X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.

    Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s
    Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i 

Which one of the following is TRUE?

The pass number for each of the following activities

1. Object code generation
2. Literals added to literal table
3. Listing printed
4. Address resolution of local symbols

That occur in a two pass assembler respectively are

Which of the following macros can put a micro assembler into an infinite loop?

(i)  .MACRO M1 X
     .IF EQ, X      ;if X=0 then
      M1 X + 1
     .ENDC
     .IF NE X       ;IF X≠0 then
     .WORD X        ;address (X) is stored here
     .ENDC
     .ENDM
(ii) .MACRO M2 X
     .IF EQ X
      M2 X
     .ENDC
     .IF NE, X
     .WORD X+1
     .ENDC
     .ENDM 

Given below are the transition diagrams for two finite state machine M₁ and M₂ recognizing languages L₁ and L₂ respectively.
(a) Display the transition diagram for a machine that recognizes L₁.L₂, obtained from transition diagrams for M₁ and M₂ by adding only ε transitions and no new states.
(b) Modify the transition diagram obtained in part(a) obtain a transition diagram for a machine that recognizes (L₁.L₂)∗ by adding only ε transitions and no new states. (Final states are enclosed in double circles).

Consider the syntax-directed translation schema (SDTS) shown below:

    E → E + E  {print “+”}
    E → E ∗ E  {print “.”}
    E → id     {print id.name}
    E → (E) 

An LR-parser executes the actions associated with the productions immediately after a reduction by the corresponding production. Draw the parse tree and write the translation for the sentence.

(a+b)∗(c+d), using the SDTS given above. 

In the following grammar

         X ::= X ⊕ Y/Y
         Y ::= Z * Y/Z
         Z ::= id  

Which of the following is true?

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

The conditional expansion facility of macro processor is provided to

Heap allocation is required for languages

In a resident – OS computer, which of the following systems must reside in the main memory under all situations?

Which of the following statements is true?

Type checking is normally done during

Let the attribute ‘val’ give the value of a binary number generated by S in the following grammar:

S → L.L | L 
L→ LB | B 
B → 0 | 1 

For example, an input 101.101 gives S.val = 5.625

Construct a syntax directed translation scheme using only synthesized attributes, to determine S.val.

Which of the following is the most powerful parsing method?

The number of tokens in the Fortran statement DO 10 I = 1.25 is

Let synthesized attribute val give the value of the binary number generated by S in the following grammar. For example, on output 101.101, S.val = 5.625.

   S → LL|L 
   L → LB|B 
   B → 0|1 

Write S-attributed values corresponding to each of the productions to find S.val.

The number of tokens in the following C statement.

printf("i = %d, &i = %x", i, &i); 

is

Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.

Given the following expression grammar:

    E → E * F | F + E | F
    F → F - F | id  

which of the following is true?

Consider the syntax directed translation scheme (SDTS) given in the following.
Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction.

 E → E1 * T {E.val = E1.val * T.val}
 E → T {E.val = T.val}
 T → F – T1{T.val = F.val – T1.val}
 T → F {T.val = F.val}
 F → 2 {F.val = 2}
 F → 4 {F.val = 4} 

(a) Using this SDTS, construct a parse tree for the expression
4 – 2 – 4 * 2
and also compute its E.val.

(b) It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the SDTS given, without changing the grammar, to find E.red, the number of reductions performed while reducing an input to E.

(a) Construct all the parse trees corresponding to i + j * k for the grammar

      E → E+E
      E → E*E
      E → id  

(b) In this grammar, what is the precedence of the two operators * and +?
(c) If only one parse tree is desired for any string in the same language, what changes are to be made so that the resulting LALR(1) grammar is non-ambiguous?

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

Assume that the SLR parser for a grammar G has n₁ states and the LALR parser for G has n₂ states. The relationship between n₁ and n₂ is:

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

Which of the following statements is FALSE?

Consider the grammar shown below

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

In the predictive parse table. M, of this grammar, the entries M[S’, e] and M[S’, $] respectively are

Consider the grammar shown below.

S → C C
C → c C | d

The grammar is

Consider the translation scheme shown below.

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

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string ‘9 + 5 + 2’, this translation scheme will print

Consider the syntax directed definition shown below.

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

Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti’s are the temporary variable names generated by newtemp. For the statement ‘X: = Y + Z’, the 3-address code sequence generated by this definition is

Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?

Which of the following grammar rules violate the requirements of an operator grammar? P,Q,R are nonterminals, and r,s,t are terminals.

(i) P → Q R
(ii) P → Q s R
(iii) P → ε
(iv) P → Q t R r

Consider a program P that consists of two source modules M₁ and M₂ contained in two different files. If M₁ contains a reference to a function defined in M₂, the reference will be resolved at

Consider the grammar rule E → E₁ – E₂ for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If E₁ and E₂ do not have any common sub expression, in order to get the shortest possible code

Consider the grammar with the following translation rules and E as the start symbol.

E → E1 # T     {E.value = E1.value * T.value}
    |    T     {E.value = T.value}
T → T1 & F     {T.value = T1.value + F.value}
    |    F     {T.value = F.value}
F → num        {F.value = num.value}  

Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.

Consider the following grammar G:

S → bS| aA| b
A → bA| aB
B → bB| aS |a 

Let N_a(w) and N_b(w) denote the number of a’s and b’s in a string w respectively. The language L(G) ⊆ {a, b}⁺ generated by G is

The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is:

Consider the grammar:

  E → E + n | E × n | n 

For a sentence n + n × n, the handles in the right-sentential form of the reduction are:

Consider the grammar:

   S → (S) | a 

Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n₁, n₂ and n₃ respectively. The following relationship holds good:

Consider line number 3 of the following C-program.

int main ( ) {                   /* Line 1 */
  int I, N;                      /* Line 2 */
  fro (I = 0, I < N, I++);       /* Line 3 */
} 

Identify the compiler's response about this line while creating the object-module:

Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.

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

The above grammar and the semantic rules are fed to a yacc tool (which is an LALR(1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?

Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.

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

Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?

Consider the following grammar.

   S → S * E
   S → E
   E → F + E
   E → F
   F → id 

Consider the following LR(0) items corresponding to the grammar above.

(i) S → S * .E
(ii) E → F. + E
(iii) E → F + .E 

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

Consider these two functions and two statements S1 and S2 about them

int work1(int *a, int i, int j)          int work2(int *a, int i, int j)
{                                          {      
    int x = a[i+2];                            int t1 = i+2;
    a[j] = x+1;                                int t2 = a[t1]; 
    return a[i+2] – 3;                         a[j] = t2+1;
}                                              return t2 – 3; 
                                           } 

S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1
S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1

Consider the following grammar:

   S → FR
   R → S | ε
   F → id

In the predictive parser table, M, of the grammar the entries M[S,id] and M[R,$] respectively.

Consider the following translation scheme.

   S → ER 
   R → *E{print("*");}R|ε 
   E → F + E {print("+");}|F 
   F → (S)|id {print(id.value);} 

Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints