Which one of the following kinds of derivation is used by LR parsers?

Consider the augmented grammar given below:

    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 inheritance 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₄?

Which one of the following statements is FALSE?

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?

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

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?

The least number of temporary variables required to create a three-address code in static single assignment form for the expression q + r/3 + s – t * 5 + u * v/w is _________.

Let a_n represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a_n?

A variable x is said to be live at a statement S_i in a program if the following three conditions hold simultaneously:

i. There exists a statement S_j that uses x
ii. There is a path from S_i to S_j in the flow graph corresponding to the program
iii. The path has no intervening assignment to x including at S_i and S_j

The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph are

In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?

Match the following:

(P) Lexical analysis       (1) Graph coloring
(Q) Parsing                (2) DFA minimization
(R) Register allocation    (3) Post-order traversal
(S) Expression evaluation  (4) Production tree

Consider the intermediate code given below.

1. i = 1
2. j = 1
3. t1 = 5 * i
4. t2 = t1 + j
5. t3 = 4 * t2
6. t4 = t3
7. a[t4] = –1
8. j = j + 1
9. if j <= 5 goto(3)
10. i = i + 1
11. if i < 5 goto(2)

The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are

Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?

Consider the following grammar G.

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

Where S, F and H are non-terminal symbols, p, d and c are terminal symbols. Which of the following statement(s) is/are correct?

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

Which one of the following is FALSE?

A canonical set of items is given below

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

On input symbol < the set has

Let L be a language and L’ be its complement. Which one of the following is NOT a viable possibility?

Which of the regular expressions given below represent the following DFA?

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

Consider the grammar defined by the following production rules, with two operators ∗ and +

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

Which one of the following is TRUE?

Which one of the following is NOT performed during compilation?

For a C program accessing X[i][j][k], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits.

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

Which one of the following statements about the source code for the C program is CORRECT?

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is _______.

One of the purposes of using intermediate code in compilers is to

Which of the following statements are CORRECT?

1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.
2) Automatic garbage collection is essential to implement recursion.
3) Dynamic allocation of activation records is essential to implement recursion.
4) Both heap and stack are essential to implement recursion.

A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?

4, 7, 6, 1, 7, 6, 1, 2, 7, 2

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A → є and A → a) to parse a string with n tokens?

Consider the following two sets of LR(1) items of an LR(1) grammar.

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

Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?

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.

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:

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

The FIRST and FOLLOW sets for the non-terminals A and B are

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

The appropriate entries for E1, E2, and E3 are

The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

In a compiler, keywords of a language are recognized during

Consider two binary operators ‘↑’ and ‘↓’ with the precedence of operator ↓ being lower than that of the operator ↑. Operator ↑ is right associative while operator ↓, is left associative. Which one of the following represents the parse tree for expression (7↓3↑4↑3↓2)?

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e initially stored in memory. The binary operators used in this expression tree can be evaluate by the machine only when the operands are in registers. The instructions produce results only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

Which data structure in a compiler is used for managing information about variables and their attributes?

Which languages necessarily need heap allocation in the runtime environment?