Construct the LL(1) table for the following grammar.

 1. Expr → _Expr
 2. Expr → (Expr)
 3. Expr → Var Expr Tail
 4. ExprTail → _Expr
 5. ExprTail → λ
 6. Var → Id Var Tail
 7. VarTail → (Expr)
 8. VarTail → λ
 9. Goal → Expr$ 

(a) Translate the arithmetic expression a*-(b+c) into syntax tree.
(b) A grammar is said to have cycles if it is the case that
A ⇒ +_A
Show that no grammar that has cycles can be LL(I).

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar

S → xxW {print "1"}
S → y {print "2"}
W → Sz {print "3"} 

What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?

A linker is given object modules for a set of programs that were compiled separately. What information need to be included in an object module?

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?

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 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 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. 

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).

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 

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

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 the following grammar

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

Which of the following is true?

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.

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 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 Fortran statement DO 10 I = 1.25 is

Which of the following is the most powerful parsing method?

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.

Given the following expression grammar:

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

which of the following is true?

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.

(a) Remove left-recursion from the following grammar:

    S → Sa| Sb | a | b 

(b) Consider the following grammar:

    S → aSbS| bSaS |ε  

Construct all possible parse trees for the string abab. Is the grammar ambiguous?

Consider the following grammar with terminal alphabet ∑{a,(,),+,*} and start symbol E. The production rules of the grammar are:

              E → aA
              E → (E)
              A → +E
              A → *E
              A → ε 

(a) Compute the FIRST and FOLLOW sets for E and A.
(b) Complete the LL(1) parse table for the grammar.

The syntax of the repeat-until statement is given by the gollowing grammar

   S → repeat S1 until E  

Where E stands for expressions, S and S₁ stand for statement. The non-terminals S and S₁ have an attribute code that represents generated code. The nonterminal E has two attributes. The attribute code represents generated code to evaluate the expression and store its truth value in a distinct variable, and the attribute varName contains the name of the variable in which the truth value is stored? The truth-value stored in the variable is 1 if E is true, 0 if E is false.

Give a syntax-directed definition to generate three-address code for the repeatuntil statement. Assume that you can call a function newlabel( ) that returns a distinct label for a statement. Use the operator ‘\\’ to concatenate two strings and the function gen(s) to generate a line containing the string s.

The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called

Which of the following statements is false?

(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 is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?

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

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 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 grammar shown below.

S → C C
C → c C | d

The grammar is

Which of the following statements is FALSE?

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

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:

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

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

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 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

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