Assignment Questions
Subject : Compiler Design Year & Sem : III- I
Subject code : 16CS5T09
Assignment Questions
S.No Question BTL CO
.
UNIT-I
1 Set -1
Explain the role of assembler, compiler, loader and linker Remember
in the language processing system.
2 Explain the role of Lexical Analysis. Understand
3 Show the output of each phase in compiler for the Apply
following statement.
position=initial+rate*60
1 Set 2 Remember
Draw a block diagram of phases in compiler and list the
main functions of each phase CO1
2 Compare and contrast compilers and interpreters Understand
3 Write a lexical analyzer program to identify Strings, Apply
Sequences, Comments, Reserved words and identifiers
1 Set 3
Explain about the structure of a compiler Remember
2 Explain about input buffering in detail. Understand
3 Design a transition diagram for identifier and the keyword Apply
“else”.
UNIT-II
1 Set -1 Remember CO2
Explain about ambiguous Grammar with an example
2 Construct a recursive descent parser for the following Apply
grammar.
E->E+T|T
T->TF|F
F->F*|a|b
3 Consider the grammar given below Apply
E->E+E|E-E|E*E|E/E|a|b
Obtain leftmost and rightmost derivation for the
string a+b*a+b
1 Set -2 Understand
Explain about LL(1) grammars in detail.
2 Explain the role of parser in the compiler design. Understand
3 Construct predictive parsing table for the following Apply
grammar.
E->TE'
E'->+TE'|e
T->FT'
T'->*FT'|e
F->(E)|id
1 Set -3 Remember
Explain about parse tree with an example.
2 Explain about the working of LL(1) parser with a neat Understand
diagram
3 Consider the following grammar Apply
E->TE`
E`->+TE`|e
T->FT`
T->*FT`|e
F->(E)|id
find the FIRST and FOLLOW functions for the above
grammar
UNIT-III
1 Set -1 Remember CO3
Explain about Shift Reduce Parsing in detail.
2 Explain about LR parsers in detail. Remember
3 Set -2 Understand
Compare and contrast LR Parsers and LL Parsers
4 Write the procedure for construction of canonical LR Understand
parsing table.
5 Set -3 Apply
Consider the following grammar
E->E+T|T
T->TF|F
F->F*|a|b
Construct the SLR parsing table and parse the input a*b+a
6 Construct LALR parsing table for the following grammar. Apply
S->Aa
S->bAc
S->dc
S->bda
A->d
Parse the input string bdc.
UNIT-IV
1 Level-1 (Low): Remember
Explain in brief about Synthesized and Inherited Attributes
2 What is an Abstract syntax tree? How to construct it using Remember
mknode(), mkleaf() functions? Give an example.
3 Level-2 (Medium): Apply
Draw the dependency graph for the following grammar
with the input string int a,b,c
S->T list
T-> int
T->float
T->char
T->double
List->List,id
List->id
4 Write the semantic rules for the following grammar. Apply CO4
S -> TL
T-> int
T->float
T->char
T->double
L->L,id
L->id
5 Level-3 (High): Apply
Consider the following input statement and represent it in
three address code, Quadruples
a=b*-c+b*-c
6 Consider the following input statement and represent it in Apply
triples, indirect triples
a=b*-c+b*-c
UNIT-V
1 Level-1 (Low): Remember CO5
Define Symbol table. Explain about the data structures for
Symbol table.
2 Explain about peephole optimization techniques in detail. Remember
3 Level-2 (Medium): Understand
Draw and explain the Runtime memory organization static
storage allocation strategy with pros and cons.
4 Explain how names can be stored in symbol table with Understand
example.
5 Level-3 (High): Apply
Construct basic blocks and data flow graph for the
following code snippet
for (i=1 to n)
{
j=1;
while(j<=n)
{
A=B*C/D;
j=j+1;
}
}
6 Consider the following program code for computing dot Apply
product of two vectors a and b of length 10 and partition it
into basic blocks.
prod=0;
i=1;
do
{
prod=prod+a[i]*b[i];
i=i+1;
} while(i<=10);
UNIT-VI
1 Level-1 (Low): Remember
Explain about the sources and criterions of code
optimization as machine dependent and independent types
2 Explain common sub expression elimination with an Understand
example.
3 Level-2 (Medium): Understand
Explain about i) Instruction Scheduling ii) Elimination of
Loop invariant variable with an example
4 Explain the following with an example Understand
a) Dead code elimination
b) Copy propagation, constant folding.
c) Strength Reduction CO6
5 Level-3 (High): Apply
Consider the pseudo code for quick sort and perform all the
function preserving transformation techniques on flow graph
of it.
6 Apply loop unrolling optimization technique for the Apply
following code snippet
int i=1;
while(i<=100)
{
a[i]=b[i];
i++;
}
Compiler Design GATE Questions with Solutions
From The Compiler Design Topic of the GATE CSE Question Paper
MCQ- Single Answer Questions
1. Match the following:
LIST – I LIST – II
(a)Lexical Analysis (1) DAG’s
(b)Code Optimization (2) Syntax trees
(c) Code Generation (3) Push Down automata
(d) Abelian Group (4) Finite automata
a. a-4, b-1, c-2, d-3
b. a-3, b-1, c-2, d-4
c. a-4, b-2, c-1, d-3
d. a-4, b-1,c-3, d-2
2. Look at these statements given below. Which of these are true?
I. A programming language that does not permit global variables of any kind and has no nesting of procedures/functions, but permits
recursion can be implemented with static storage allocation
II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being
implemented has nesting of procedures/functions
III. Recursion in programming languages cannot be implemented with dynamic storage allocation
IV. Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based
allocation scheme for activation records
V. Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage
allocation scheme for activation records
a. I, II and V only
b. II only
c. II, III and V only
d. I, III and IV only
3. Choose the correct statement from the following.
a. LALR parser is more powerful than canonical LR parser
b. The parsers SLR, Canonical CR, and LALR have the same power
c. SLR parser is more powerful than LALR
d. Canonical LR parser is more powerful than LALR parser
4. A linker is assigned object modules for a set of programs that were compiled separately. So, what is the information that needs to be
included in an object module?
a. Absolute addresses of internal symbols
b. Object code
c. Relocation bits
d. Names and locations of all external symbols defined in the object module
5. Take a look at the basic block given below.
a=b+c
c=a+d
d=b+c
e=d–b
a=e+b
In this basic block given above, the respective minimum number of nodes and edges present in the DAG representation are_____
a. 4 and 4
b. 6 and 6
c. 8 and 10
d. 9 and 12
6. Which are the languages that necessarily need heap allocation in the runtime environment?
a. Those that allow dynamic data structures
b. Those that support recursion
c. Those that use dynamic scoping
d. Those that use global variables
7. ________ is not an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries.
a. Faster program setup
b. Smaller sizes of executable files
c. Existing programs need not be re-linked to take advantage of newer versions of libraries
d. Lesser overall page fault in the system
x = x ∗ (a + b) – 5
8. What are the number of tokens that will be generated by the scanner for the below given statement?
a. 7
b. 10
c. 11
d. 12
9. What is the data structure in a compiler used for managing information about variables and their attributes?
a. Symbol table
b. Symbol tree
c. Abstract syntax tree
d. Semantic stack
10. When is the symbol table, generated in a two-pass assembler?
a. Generated in second pass
b. Generated and used only in second pass
c. Generated in first pass
d. Not generated at all
11. _______ phase of compiler generates stream of atoms.
a. Code Generation
b. Syntax analysis
c. Code Optimisation
d. Lexical Analysis
12. What is the kind of derivation used by LR parsers?
a. Rightmost in reverse
b. Leftmost in reverse
c. Rightmost
d. Leftmost
13. What is the output of a lexical analyser?
a. Machine code
b. A parse tree
c. A stream of tokens
d. Intermediate code
14. From the below given data: a b b a a b b a a b which is not a word in the dictionary created by LZ-coding (the initial words are a, b)?
a. ab
b. ba
c. baab
d. bb
15. ________ among these listed below is a top-down parser.
a. An LR(k) parser
b. Operator precedence parser
c. An LALR(k) parser
d. Recursive descent parser
16. One of the purposes of using intermediate code in compilers is to________
a. improve error recovery and error reporting
b. increase the chances of reusing the machine-independent code optimizer in other compilers
c. Improve the register allocation
d. make parsing and semantic analysis simpler
17. What is 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?
18. Debugger is a programming language that______
a. allows to set breakpoints, execute a segment of program and display contents of register
b. allows to examine and modify the contents of register
c. does not allow execution of a segment of program
d. All the above
19. Which among these is required to convert an infix expression to the postfix form efficiently?
a. An operand stack and an operator stack
b. An operator stack
c. An operand stack
d. A parse tree
20. A CFG is not closed under ___________
a. Concatenation
b. Dot operation
c. Iteration
d. Union Operation
21. Which of the following is incorrect for the actions of A LR-Parser
I) shift s
ii) reduce A->ß
iii) Accept
iv) reject?
Only I)
a. I) and ii)
b. I), ii) , iii) and iv)
c. I), ii) and iii)
d. None of the above
22. 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________
a. n, E+ n and E + n x n
b. n, n + n and n + n x n
c. n, E + n and E + E x n
d. n, E + n and E x n
23. Which of the following grammar rules violate the requirements of an operator grammar ? P, Q, R are non-terminals, and r, s, t are
terminals.
i) P → Q R
ii) P → Q s R
iii) P → ε
iv) P → Q t R r
(a) i) only
(b) i) and iii) only
(c) ii) and iii) only
(d) iii) and iv) only
24. Look at the following code segment.
x = u – t;
y = x * v;
x = y + w;
y = t – z;
y = x * y;
What is the minimum number of total variables required to convert the above code segment to static single assignment form?
25. Some code optimizations are carried out on the intermediate code because____
a. program analysis is more accurate on intermediate code than on machine code
b. the information from dataflow analysis cannot otherwise be used for optimisation
c. they enhance the portability of the computer to other target processors
d. the information from the front end cannot otherwise be used for optimisation
26. State if the given statement is true or false: R->R|T T->ε is an ambiguous grammar
(a) true
(b) false
27. If a state does not know whether it will make a shift operation or reduction for a terminal, it is _________
a. Reduce/ Shift conflict
b. Reduce conflict
c. Shift/ reduce conflict
d. Shift conflict
28. The construction of the canonical collection of the sets of LR (1) items and LR (0) items are similar. Which of these will be an exception?
a. Closure and go to operations work similarly
b. Closure and associatively operations work slightly different
c. Closure and go to operations work slightly different
d. Closure and additive operations slightly different
29. Which among these is the most powerful parsing method?
a. LL(1)
b. SLR
c. LALR
d. Canonical LR
30. Which of these classes of statements below usually produces no executable code when compiled?
a. Input and output statements
b. Declaration
c. Assignment statements
d. Structural statements
31. Which of these below given statements about peephole optimisation is true?
a. It can be applied to a portion of the code that is not contiguous
b. It is applied to a small part of the code and applied repeatedly
c. It is applied in the symbol table to optimize the memory requirements
d. It is applied to a small part of the code and applied repeatedly
32. Linking:
a. cannot be performed after relocation
b. is not required if relocation is performed
c. cannot be performed before relocation
d. can be performed both before and after relocation
33. In compiler terminology, what does reduction in strength mean?
a. Removing common subexpressions
b. Replacing run time computation by compile time computation
c. Replacing a costly operation by a relatively cheaper one
d. Removing loop invariant computation
34. What is the graph that shows basic blocks and their successor relationship, called as?
a. Hamilton Graph
b. Flow Graph
c. DAG
d. Control Graph
35. Loop unrolling is a code optimisation technique:
a. That improves performance by decreasing the number of instructions in a basic block
b. That reorders operations to allow multiple computations to happen in parallel
c. That avoids tests at every iteration of the loop
d. That exchanges inner loops with outer loops
36. Consider the grammar rule E → E1 – E2 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 E1 and E2 do not have any common sub expression, in
order to get the shortest possible code,___
a. E2 should be evaluated first
b. E1 should be evaluated first
c. Order of evaluation of E1 and E2 is of no consequence
d. )Evaluation of E1 and E2 should necessarily be interleaved
37. What is the identification of common sub-expression and replacement of runtime computations by compile-time computations?
a. Data flow analysis
b. Constant folding
c. Loop optimisation
d. Local optimisation
38. Who has the responsibility for code optimisation?
a. Operating system
b. Application programmer
c. System programmer
d. All of these
39. What is the dead- code elimination in machine code optimisation referred to?
a. Removal of the values that never get used
b. Removal of function which are not involved
c. Removal of all labels
d. Removal of a module after its use
40. Which of these below given operations are not performed during compilation?
a. Type checking
b. Dynamic memory allocation
c. Inline expansion
d. Symbol table management
41. Substitution of values for names who have constant values are done in_____
a. Strength reduction
b. Loop optimisation
c. Constant folding
d. Local optimisation
42. In which, are the bodies of the two loops merged together to form a single loop, provided that they do not make any references to each
other?
a. Loop Jamming
b. Loop unrolling
c. Strength reduction
d. Loop concatenation
43. 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?
a. 2n-1
b. n-1
c. n/2
d. 2n
44. The number of tokens in the Fortran statement DO 10 I = 1.25 is_____
a. 3
b. 4
c. 5
d. None of the above
45. Which one of the following statements is false?
a. In un-typed languages, values do not have any types
b. In statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program
c. In statically typed languages, each variable in a program has a fixed type
d. In dynamically typed languages, variables have no types
46. Look at the below given statements :
S1 : The front end of compiler consists of Lexical analyser , Syntax analyser and semantic analyser.
S2 : Target code generator is known as the back-end of compiler.
S3 : Code optimizer is middle end of compiler and is a optional phase in compiler.
Which among these above given option is correct ?
a. Only S1 and S2 are correct
b. Only S1 and S3 are correct
c. Only S2 and S3 are correct
d. None of the above are correct
47. Which of the following menu types are also known as drop-down menus?
a. Pull- down
b. Cascading
c. Fly-out
d. Pop-up
48. Data is stored in computer as______
a. Matter
b. Files
c. Floppies
d. Directories
49. The register or the main memory location that contains the effective address of the operand is known as________
a. special location
b. pointer
c. Indexed register
d. Question does not provide sufficient data or is vague
50. What is object code the output of?
a. Only assembler
b. Only compiler
c. Compiler or Assembler
d. Operating system
