Theory of Computation and Compiler Design

Section-A
1 .What is compiler? Explain its phases with diagram.

2 .What is lexical analyser? Explain how token is identified?

3 .What is parser? Explain LR parser.

4 .What is intermediate code? What type of intermediate code is used in compiler?

5 .What is symbol table? Explain any two data structure to maintain symbol table.

6 .What is flow control? Explain basic block with a suitable example.

7 .Explain the issues related to code generation.
 

Section-B
1. Explain three addressing code with a suitable example.

2. The Example which is taken for three addressing mode, make direct acyclic graph (DAG) for the same.

3. What is code optimization and code generation?

Section-C

Question No.  1    Marks - 10

Suppose L={am bn:n=1} then L is    
 
Options    
    
Regular

Context free but not Regular

Context sensitive but not Context free

None of these

    

Question No.  2    Marks - 10

In a compiler, Parsing is done by    
 
Options    
    
Lexical

syntax

Code generation

Code optimization

    

Question No.  3    Marks - 10
Contaxt-free grammar is also known as    
 
Options    
    
Type-0

Type-1

Type-2

Type-3

Question No.  4    Marks - 10

A top-down parser generates    
 
Options    
    
Left most derivation

Right most derivation

Left most derivation in reverse

Right most derivation in reverse

    
Question No.  5    Marks - 10
A Bottom-up parser generates    
 
Options    
    
Left most derivation

Right most derivation

Left most derivation in reverse

Right most derivation in reverse

Question No.  6    Marks - 10
A grammar is said to be Ambiguous if    
 
Options    
    
Two or more productions have the same nonterminal on the left hand side

A derivation tree has more than associated sentence

a sentence with more than one derivation tree

Brackets are not present in the grammar

    
Question No.  7    Marks – 10
Which of the following is NOT a Context-free-grammar    
 
Options    
    
S-->Aba/B B-->b

S-->AbA/b/A A-->b

S-->aA/b A-->bA/b

S-->aSa/bSb/e
    

Question No.  8    Marks - 10
Suppose L1 and L2 are two Regular Language, then which one is true?    
 
Options    
    
Union of L1 and L2 is also regular

Concatenation of L1 and L2 is also regular

Complement of L1 or L2 is also Regular

All of these

    

Question No.  9    Marks - 10
Suppose L1 and L2 are two context-free Language, then which one is False    
 
Options    
    
Union of L1 and L2 is also Cntext-free

Concatenation of L1 and L2 is also Context-free

Complement of L1 is also Context-free

All of these

    

Question No.  10    Marks - 10
The concept of FSA is much used in this part of the compiler    
 
Options    
    
Lexical Analysis

Parser

Code generation

Code optimization

    

Question No.  11    Marks - 10
The concept of grammar is much used in this part of the compiler    
 
Options    
    
Lexical Analysis

Parser

Code generation

Code optimization

    

Question No.  12    Marks - 10
The set of all strings over the alphabet S = {a, b} (excluding e) is denoted by    
 
Options    
    
(a + b)*

(a+b)+

a*b*

(a*+b*)

Question No.  13    Marks - 10
Which of the following denotes Chomskian hiearchy    
 
Options    
    
REG ? CFL ? CSL ? type0

CFL ? REG ? type0? CSL

CSL ? type0 ? REG ? CFL

CSL ? CFL ? REG ? type0

Question No.  14    Marks - 10
Which of the following regular expression identity is true    
 
Options    
    
p*=p(p*)

(p+ q)*=(p*q*)*

(p + q)* = p* + q*

p*q*= p*+q*

Question No.  15    Marks - 10
Which of the following conversion is not possible (algorithmically)?    
 
Options    
    
regular grammar to context-free grammar

nondeterministic FSA to deterministic FSA

nondeterministic PDA to deterministic PDA

nondeterministic TM to deterministic TM

    

Question No.  16    Marks - 10
Which of the following Parsing Technique is most powerfull    
 
Options    
    
SLR

LALR

Canonical LR

LL(1)

Question No.  17    Marks - 10
Cosider the Grammar (G): S?iEtSA/a A?eS/? E?b    
 
Options    
    
FIRST(S)={i,? }

FIRST(S)={i,a}

FIRST(S)={e,? }

None of these

Question No.  18    Marks - 10
Cosider the Grammar (G): S? iEtSA/a A? eS/? E?b    
 
Options    
    
FOLLOW(S)={e,?}

FOLLOW(S)={e,$}

FOLLOW(S) = {i?}

FOLLOW(S)={i, $}

    
Question No.  19    Marks - 10
Cosider the Grammar (G): S? iEtSA/a A? eS/? E?b then G is    
 
Options    
    
LL(1)

Not a LL(1)

SLR(1) but not LL(1)

None of these

Question No.  20    Marks - 10
A grammar is called Operetor precedence, if    
 
Options    
    
No production on the Right hand side has?

No two consecutive non-terminals on the Right side of any production

Both (1) and (2)

Only (2)

Question No.  21    Marks - 10
Which of the following grammar is Operator precedence    
 
Options    
    
S?aSa/bSb/ab

S?SAa/SAb/ab A?b

E?E+E/E*E/id/?

All of these

Question No.  22    Marks - 10
Consider the grammar(G): E?E+T/T T?T*F/F F?(E)/id then    
 
Options    
    
LEADING(E)={+,*,),id}

LEADING(E)={+,*,(,id}

LEADING(E)={+,*,id}

LEADING(E)={*,(,id}

    
Question No.  23    Marks - 10
Consider the grammar(G): E?E+T/T T?T*F/F F?(E)/id then    
 
Options    
    
TRAILING(T)={+,*,),id}

TRAILING(T)={*,),id}

TRAILING(T)={+,*,id}

TRAILING(T)={*,+,id}

Question No.  24    Marks - 10
After removing Left recursion for the production(s): A?Aa1/Aa2/…./Aan/ß1/…./ßm    
 
Options    
    
A?ßiA' A'?aiA'/?

A?ßiA' A'?aiA/a

A?aiA' A'?ßiA'/?

A?aiA' A'?ßiA'/b

Question No.  25    Marks - 10
Which of the following is NOT an Intermediate Code generation method    
 
Options    
    
Quadruples

triples

Indirect Triples

Parse tree

    
Question No.  26    Marks - 10
Top-Down parser always do the    
 
Options    

Left-most Derivation

Right-most derivation

Left-most derivation in reverse

Right-most derivation in reverse

Question No.  27    Marks - 10
Bottom-up parser always do the    
 
Options    
    
Left-most Derivation

Right-most derivation

Left-most derivation in reverse

Right-most derivation in reverse

Question No.  28    Marks - 10
Loading operating system from secondary memory to primary memory is called    
 
Options    
    
Compiling

Booting

Refreshing

Reassembling

Question No.  29    Marks - 10

A compiler for a high level language that runs on one machine and produces code for a different machine is called    
 
Options    
    
Optimizing

One pass compiler

Cross compiler

Multipass Compiler

Question No.  30    Marks - 10
A Tabular implementation of Recursive-descendent parser is also known as    
 
Options    
    
Predictive Parser

Operator precedence

SLR parser

LALR parser

Question No.  31    Marks - 10
In the context of compiler design, "reduction in strength" refers to    
 
Options    
    
Code optimization obtained by the use of cheaper machine instructions

Reduction in accuracy of the output

Reduction in the range of values of input variables

Reduction in the efficiency of the program

Question No.  32    Marks - 10
Symbol table can be used for    
 
Options    
    
Checking type compatibility

Supressing duplication of error message

Storage allocation

All of these

Question No.  33    Marks - 10
Which of the following is NOT a method to implement symbol table    
 
Options    
    
Linear list

Hash table

self-organizing list

parse tree

Question No.  34    Marks - 10
Consider the grammar (G): A?abAbc/abBbc/b/a ; After eliminating left factoring    
 
Options    
    
A?abA'/b/a A'?Abc/Bbc

A?abA'bc/abB'bc/b/a A'?? B'??

A?abbc/abbc/b/a

None of these

Question No.  35    Marks - 10
Cosider the grammar (G): E?E+T/T T?T*F/F F?(E)/id , the canonical collection of LR(0) set {i.e. I0 item is}    
 
Options    
    
E’? E E?.E+T T?.T*F F?.(E)/.id

E'?E E?.E+T/.T T?.T*F/.F F?.(E)/.id

E'?E E?E.+T/.T T?T.*F/.F F?.(E)/.id

All of these

Question No.  36    Marks - 10
Which of the following is related with code optimization    
 
Options    
    
loop optimization

Code motion

Induction variable elimination

All of these

Question No.  37    Marks - 10

Code motion referes to    
 
Options    
    
removing costly operator with cheaper one

Removing loop invarient computation

increasing space complexity

All of these

Question No.  38    Marks - 10
which language is accepted corresponds to grammar(G): S?0S0/1S1/0/1    
 
Options    
    
0*1*

1*0*

plindrome string over ?={0,1}

Even number of 0's and 1's

Question No.  39    Marks - 10
The logic of pumping lemma is a good example of    
 
Options    
    
pigeon-hole principle

recursion

iteration

Divide & conquer technique

Question No.  40    Marks - 10
Intermediate code generation of compiler phase takes input from    
 
Options    
    
Lexical analyzer

code optimizer

Syntax Analyzer

semantic Analyzer