UNIT-1

1. Match the following :

(i) Regular Grammar (a) Pushdown automaton

(ii) Context free Grammar (b) Linear bounded automaton

(iii) Unrestricted Grammar (c) Deterministic finite automaton

(iv) Context Sensitive Grammar(d) Turing machine

A (c) (a) (b) (d) B (c) (a) (d) (b)

C (c) (b) (a) (d D (c) (b) (d) (a)

Answer B

2. For which of the following application regular expressions cannot be used?

A Designing compilers B Developing text editors

C Simulating sequential circuits D All of these

Answer C

3. The word formal in formal languages means

A The symbols used have well defined meaning

B They are unnecessary ,in reality

C Only the form of the string of symbols is significant

D None of the above

Answer C

4. Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two
zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of
length less than 3 are also in the language. A partially completed DFA that accepts this language
is shown below.

A A B B

C C D D
Answer D

5. FSM can recognize

A Any grammar B Only CFG

C Any unambiguous grammar D Only regular grammar

Answer D

6. Which of the following is the most general phase structured grammar ?

A Regular B Context-sensitive

C Context free D None of the above

Answer B

7. For input null ,the output produced by a Mealy machine is

A Null B Dependent on present state

C Depends on given machine D Cannot decide

Answer A

8. A formal grammar is a___________for rewriting strings.

A Set of rules B Set of functions

C Both A and B D None of the above

Answer A

9. The language accepted by finite automata is

A Context free B Regular

C Non regular D None of these

Answer B

10. The basic limitation of a FSM is that

A It cannot remember arbitrary large amount of information

B It sometimes recognizes grammar that are not regular

C It sometimes fails to recognize grammars that are regular

D All of the above

Answer A

11. A formal language theory is the discipline which studies

A Formal grammars and languages B Unusual grammars and languages

C Both A and B D None of the above

Answer A

12. Finite state machine___________recognize palindromes.

A Can B Cannot

C May D May not

Answer B

13. How many states can a process be in ?

A 2 B 3

C 4 D 5

Answer D

14. If two finite state machines are equivalent they should have the same number of

A States B Edges

C States and edges D None of these

Answer D

15. Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of

states in finite automaton that recognizes the language represented by this regular expression
contains

A n states B n + 1 states

C n + 2 states D 2n states

Answer B

16. The following CFG

S®aB|bA, A®a|as|bAA, B®b|bs|aBB

generates strings of terminals that have

A Odd number of a’s and odd number of b’s

B Even number of a’s and even number of b’s

C Equal number of a’s and b’s

D Not equal number of a’s and b’s

Answer C

17. Which of the following permanent database that has an entry for each terminal symbol ?

A Literal table B Identifier table

C Terminal table D Source table

Answer C

18. The classic formalization of generative grammars first proposed by

A Alexender B Bill Gates

C Noam Chomsky D Charles Babbage

Answer A

19. The equivalent grammar corresponding to the grammar G : S®aA, A®BB, B®aBb|Î is

A S®aA, A®BB, B®aBb B S®a|aA, A®BB, B®aBb|ab

C S®a|aA, A®BB|B, B®aBb D S®a|aA, A®BB|B, B®aBb|ab

Answer D

20. A language L is accepted by a finite automaton if and only if

A Context free B Context sensitive

C Recursive D Right linear

Answer D
 UNIT-2
1.______obtains string of tokens from lexical analyzer?

Ans: parser

2. BNF stands for____________

Ans. Backus naur form.

3.. Define syntax?

Ans. It is a directed graph. Used to represent the information present in BNF.

4. Define parse tree?

Ans. the hierarchicall representation of sentences of a languages.

5. Define Derivation?

Ans. the process of generating sentences

6.Define Grammer?

Ans.Set of rules

7.Define Ambiguous Grammer?

Ans: a grammer produce 2 or more parse Trees

8.String used in the derivation are called _________

Ans:Sentential form

9.______attribute moves information up in a Parse Tree.

Ans:Synthesized

10. .______attribute moves information down Parse Tree

Ans.inherited
11_______describes meaning of a program?

Ans:semantic

12.recursive descent parser is top down parser

Ans.True

13.Build parse tree starting from root node to leaves is called_________

Ans:Top down parsing

14.Build parse tree starting from leaves to root node is called_________

Ans:Bottom up parsing

15______errors are discovered by lexical analyzer.

Ans:Lex

16. Non terminal are indicated by capital letters [T/F]

Ans:T

17.what are the methods to eliminate ambiguity ?

Ans: Left recursive,left factoring

18.____is a process of factoring the common prefixes of a grammar rule

Ans: Left factoring

19.In LL(1) parser L stands for _______

Ans: Left to right scanning

20.CFG Stands for ___________

Ans: Context Free Grammer

 UNIT – 3

1. Context Sensitive grammars are called as _______

Ans: Type 1
2. Context free grammars are called as _______
Ans: Type 2
3. Unrestricted grammars are called as _______
Ans: Type 0
4. Regular grammars are called as _______
Ans: Type 3
5. PDA Stands _________
Ans: Push Down Automata
6. LBA Stands ______________
Ans: Linear Bounded Automata
7. A grammar is _________ if it has more than one derivation tree.
Ans: Ambiguous grammar
8. A grammar is _________ if it has one derivation tree. Ans:
UnAmbiguous grammar
9. _____________ Parsers satishfy LL Grammars
Ans: TOPDOWN Parsers
10. ___________ Parsers can not be used commercially
Ans: Universal Parsers
11. ________________ parser is recursive descent parser that needs no back tracking
Ans: predictive
12. Predictive parser as a procedure for every ________
Ans: Grammar
13. The right most derivation in reverse is obtained by ___________
Ans: Handle Pruning
14. Define left recursion?
Ans: A -> A α
15. __________ , ____________ are the types of parsing.
Ans: Top down, Bottom up
16. SLR Stands _________
Ans: Simple LR
17. CLR Stands for __________
Ans: Cannonical LR
18. LALR Stands for ____________
Ans: LookAhead LR
19. YACC Stands for ______________
Ans: Yet Another Compiler Compiler
20. _________ , __________ are data structures of Shift Reduce Parser.
Ans: Stack, Input Buffer

UNIT-4

1. What are the 3 common implementations for TAC?

Ans: Quadruple, Triple, Indirect Triple
2. The translation of parse tree to intermediate form is ________
Ans: Syntax Directed Translation
3. ab * is an example of _________
Ans: Postfix notation
4. a*b is an example of _________
Ans: infix notation
5. *ab is an example of _________
Ans: prefix notation
6. the nodes of AST deals with______ entities.
 Ans: Semantics

7. Tac Statements are implemented in the compiler____________

Ans: records

8. ________ are pointers to tuples

Ans: Indirect triples.
9. ________ Graph identifies dependency of the attributes of parse tree
Ans: Dependency Graph
10. What are the methods are used to translate the source code to intermediate code
Ans: Parse tree , Bottom Up
11. In ________ the global variables are stored
Ans: Data segment
12. Global and local variables are stored in _______
Ans: Symbol Table
13. ________ attribute hold the value of expression
Ans: Place
14. ________ attribute hold the Sequence of three address statement
Ans: Code
15. ________ attribute hold the type of result
Ans: Mode
16. SDD Stands ____________
Ans: Syntax Directed Definition
17. TAC Stands for _______
Ans: Three Address Code
18. DAG Stands for ___________
Ans: Directed Acyclic Graph
19. Attribute of child depends on attribute of the parent node is called as _______
Ans: Inherited
20. Attribute of Parent depends on attribute of the Child node is called as _______
Ans: Synthesized
 UNIT-5

1. _________or scanning is the process where the stream of characters making up the source
program is read from left to right and grouped into tokens.

A Lexical analysis B Diversion

C Modeling D None of the above

Answer A

2. Which of the following is used for grouping of characters into tokens?

A Parser B Code optimization

C Code generator D Lexical analyzer

Answer D

3. The lexical analyzer takes_________as input and produces a stream of_______as output.

A Source program,tokens B Token,source program

C Either A and B D None of the above

Answer A

4. The action of parsing the source program into proper syntactic classes is called

A Syntax analysis B Lexical analysis

C Interpretation analysis D General Syntax analysis

Answer B

5. Task of the lexical analysis

A To parse the source program into the basic elements or tokens of the language

B To build a literal table and an identifier table

C To build a uniform symbol table

D All of these
Answer D

6. The output of lexical analyzer is

A A set of regular expressions B Syntax tree

C Set of tokens D Strings of character

Answer C

7. The output of a lexical analyzer is

A Machine code B Intermediate code

C A stream of tokens D A parse tree

Answer C

8. Shift reduce parsers are

A Top down parser B Bottom up parser

C May be top down or bottom up parser D None of the above

Answer B

9. A bottom up parser generates

A Right most derivation B Right most derivation in reverse

C Left most derivation D Left most derivation in reverse

Answer B

10. Which of the following is the most powerful parser?

A SLR B LALR

C Canonical LR D Operator precedence

Answer C

11. Which of the following parser is most powerful?

A Operator precedence B Canonical LR

C LALR D SLR

Answer B
12. A parser with the valid prefix property is advantageous because it

A Detects error as soon as possible B Detects errors as and when they

occur

C Limits the amount of erroneous output passed to the text phase D All of
these

Answer C

13. A grammar that produces more than one parse tree for some sentence is called

A Ambiguous B Unambiguous

C Regular D None of these

Answer A

14. In operator precedence parsing , precedence relations are defoned

A For all pair of non terminals B For all pair of terminals

C To delimit the handle D Only for a certain pair of terminals

Answer D

15. Recursive descent parsing is an example

A Top down parsing B Bottom up parsing

C Predictive parsing D None of the above

Answer A

16. ___________is a graph representation of a derivation.

A The parse tree B The oct tree

C The binary tree D None of the above

Answer A

17. LR stands for

A Left to right B Left to right reduction

C Right to left D Left to right and right most derivation in
reverse

Answer D

18. A top down parser generates

A Right most derivation B Right most derivation in reverse

C Left most derivation D Left most derivation in reverse

Answer C

19. YACC builds up

A SLR parsing table B Canonical LR parsing table

C LALR parsing table D None of the above

Answer C

20. Any description error can be repaired by

A Insertion alone B Deletion alone

C Insertion and deletion alone D Replacement alone

Answer C
 UNIT-6

1. Inherited attribute is a natural choice in

A Keeping track of variable declaration

B Checking for the correct use of L values and R values

C Both A and B

D None of these

Answer A

2. Syntax directed translation scheme is desirable because

A It is based on the syntax B Its description is independent of any implementation

C It is easy to modify D All of these

Answer C

3. Advantage of panic mode of error recovery is that

A It is simple ti implement B It never gets into an infinite loop

C Both A and B D None of these

Answer D

4. An intermediate code form is

A Postfix notation B Syntax trees

C Three address code D All of these

Answer D

5. Three address code involves

A Exactly 3 address B At most most 3 address

C No unary operators D None of these

Answer D
6. Intermediate code generation phase gets input from

A Lexical analyzer B Syntax analyzer

C Semantic analyzer D Error handling

Answer C

7. The graph that shows basic blocks and their successor relationship is called

A DAG B Flow chart

C Control graph D Hamiltonian graph

Answer B

8. Relocating bits used by relocating loader are specified by

A Relocating loader itself B Linker

C Assembler D Macro processor

Answer B

9. Which of the following can be accessed by transfer vector approach of linking?

A External data segments B External subroutines

C Data located in other procedure D All of these

Answer B

10. Reduction in strength means

A Replacing run time computation by compile time computation

B Removing loop invariant computation

C Removing common sub expression

D Replacing a costly operation by a relatively cheaper one

Answer A

11. Scissoring enables

A A part of data to be diaplayed B Entire data to be displayed

C Full data display on full area of screen D No data to be displayed

Answer A

12. Running time of a program depends on

A The way the registers and addressing modes are used

B The order in which computations are performed

C The usage of machine idioms

D All of these

Answer D

13. Which of the following does not interrupt a running process?

A A device B Timer

C Scheduler D Power failure

Answer D

14. A grammar is meaningless

A If terminal set and non terminal set are not disjoint

B If left hand side of a production is a single terminal

C If left hand side of a production has no non terminal

D All of these

Answer A

15. Which of the following is not an intermediate code form?

A Postfix notation B Syntax trees

C Three address codes D Quadruples

Answer D

16. The optimization technique which is typically applied on loops is

A Removal of invariant computation B Peephole optimization

C Constant folding D All of these

Answer D
17. Whether a given pattern constitutes a token or not depends on the

A Source language B Target language

C Compiler D All of these

Answer C

18. The optimization which avoids test at every iteration is

A Loop unrolling B Loop jamming

C Constant folding D None of these

Answer A

19. We can optimize code by

A Dead code elimination B Common subprograms

C Copy intermediate loop D Loop declaration

Answer A

20. An optimizer compiler

A Is optimized to occupy less space B Is optimized to take less time for execution

C Optimizes the code D None of these

Answer D
 UNIT-7

1. Concept which can be used to identify loops is

A Dominators B Reducible graphs

C Depth first ordering D All of these

Answer D

2. Input to code generator

A Source code B Intermediate code

C Target code D All of the above

Answer B

3. Pee hole optimization

A Loop optimization B Local optimization

C Constant folding D Data flow analysis

Answer C

4. Code can be optimized at

A Source from user B Target code

C Intermediate code D All of the above

Answer A

5. Type checking is normally done during

A Lexical analysis B Syntax analysis

C Syntax directed translation D Code optimization

Answer C

6. A compiler for a high level language that runs on one machine and produce code for different
machine is called
A Optimizing compiler B One pass compiler

C Cross compiler D Multipass compiler

Answer C

7. Grammar of the programming is checked at ________ phase of compiler.

A semantic analysis B code generation

C syntax analysis D code optimization

Answer C

8. In which way(s) a macroprocessor for assembly language can be implemented ?

A Independent two-pass processor

B Independent one-pass processor

C Expand macrocalls and substitute arguments

D All of the above

Answer D

9. The linker

A is similar to interpreter

B uses source code as its input

C is required to create a load module

D none of the above

Answer C

10. Macro-processors are ______

A Hardware

B Compiler

C Registers

D None of the above

Answer B

11. ‘Macro’ in an assembly level program is _______.

A sub program

B a complete program

C a hardware portion

D relative coding

Answer A

12. In an absolute loading scheme which loader function is accomplished by assembler ?

A re-allocation

B allocation

C linking

D loading

Answer A

13. Synthesized attribute can be easily simulated by a

A LL grammar

B Ambiguous grammar

C LR grammar

D None of the above

Answer C

14. In an absolute loading scheme, which loader function is accomplished by a loader ?

A Re-allocation

B Allocation

C Linking

D Loading

Answer D
15. A compiler that runs on one machine and produces code for a different machine is called

A Cross compilation

B One pass compilation

C Two pass compilation

D None of the above

Answer A

16. Which of the following is used for grouping of characters into tokens (in a computer)

A A parser

B Code optimizer

C Code generator

D Scanner

Answer D

17. Basic blocks are constructed for _______ optimization

A. Local B. global C. loop D. data flow analysis

Answer A

18. Replacement of run-time computations by compile time computations is _____

A. elimination of common sub-expressions

B. constant folding

C. local optimization

D. algorithm optimization

Answer B

19. Find odd man out?

A. live variable analysis B. detection of common sub expression

C. minimum distance matching D. computation of values outside the blocks

Answer C
20. Optimization connected with x:x+0 is

A. peephole and algebraic

B. Reduction in strength and algebraic

C. peephole only

D. loop and peephole

Answer A

UNIT-8

1. The cost of instruction MUL #1,R1 is

A. 2 B. 3 C. 1 D. 6

Answer A

2. An address descriptor is maintained for ________

A. Each name in block B. each symbol in the program

C.each register variable D. each memory variable

Answer B

3. Identify the odd statement in the list

A. A=b+c B. b[i]=a C. a=&b D. a=b+*c

Answer Ds

4. The cost of the following instruction sequence is

MOV b,R0
ADD c,R0
MOV R0,a
A. 3 B. 2 C. 6 D. 4

Answer D

5. The names are mapped to storage in the machine in _______

A. Symbol tables B. runtime support system
 C.stack D. extra segment

Answer B

6. Each execution of the procedure is called ________

A. Control stack
B. Ativiation
C. Symbol
D. Stack

Answer B

7. The _____ is used to keep track of currently –active activations

A. Control stack
B. Activation
C. Symbol
D. Stack

Answer A

8. In ___ the global variables are stored

A. Data segment
B. Symbol tables
C. Extra segment
D. Main memory

Answer A

9. Global and local variables are stored in _____

A. Data segment
B. Symbol tables
C. Extra segment
D. Main memory

Answer B

10. The ____ attribute holds the value of the expression

A. Place
B. Code
C. Symbol
D. Mode

Answer A

11. The ____ attribute holds the sequence of three address statements
 A. Place
B. Code
C. Symbol
D. Mode

Answer B

12. The ________ attribute indicates the type of the result

A. Place
B. Code
C. Symbol
D. Mode

Answer D

13. The translation of the parse tree to intermediate form is ______

A. Syntax directed translation
B. Lexical analysis
C. Syntax analysis
D. Code generation

Answer A

14. ab* is an example of ___

A. postfix notation
B. abstract syntax tree
C. Three address code
D. None

Answer A

15. The nodes of AST deals with _____ entities.

A. Syntactic
B. Semantic
C. Operators
D. Operands

Answer B

16. ________ have pointers to triplex

A. Triples
B. Quadruples
C. TAC
D. Indirect triples
 Answer D

17. Isf attributes of the child depends on the attributes of parent node then it is ____
attributes.
A. TAC
B. Synthesized
C. Inherited
D. Directed

Answer C

18. Isf attributes of the parent depends on its children then it is ____ attributes.
A. TAC
B. Synthesized
C. Inherited
D. Directed

Answer D

19. A CLR parser tries to eliminate

A. Shift-reduce conflicts
B. Reduce-reduce conflicts
C. Shift-shift conflicts
D. All types of conflicts

Answer A

20. ______ parser is more powerful

A. SLR
B. CLR
C. LALR
D. All of the above

Answer B
I