Compiler Design KCS502
Question Bank
Top Down Parsing
1. What are the problems with top down parsing. Write the algorithm for FIRST and FOLLOW.
[2018-19][2015-16]
2. Check whether left recursion exists for the following grammar: [2014-15]
S -> Aa| b
A -> Ac | Sd |e
3. Give the algorithm for constructing predictive parsing table. Consider the following grammar
and construct predictive parsing table: [2014-15]
S -> iEtSS1 | a
S1 -> eS | E
E -> b
Bottom Up-Parsing
1. What is meant by viable prefixes. [2018-19]
2. Perform Shift Reduce parsing for the given input strings using the grammar: [2018-19]
S -> (L)|a
L -> L,S|S
(i) (a,(a,a))
(ii) (a,a)
3. Construct LR(0) parsing table for the following grammar: [2018-19]
S -> cB | ccA
A -> cA |a
B -> ccB | b
4. Give operator precedence parsing algorithm. Consider the following grammar and create
operator precedence table. Also parse the input string (id+(id*id)) [2017-18]
E -> E+T|T
T -> T*F|F
F -> (E)|id
5. For the grammar, [2017-18]
S -> aAd | bBd | aBe | bAe
A -> f
B -> f
Construct LR(1) parsing table. Also draw the LALR table from derived LR(1) parsing table.
6. Consider the following grammar [2017-18]
E -> E+E | E*E | (E) | id
Construct the SLR parsing table.
7. Consider the following grammar [2016-17]
S -> AS l b
A -> SA l a
Construct the SLR parse table for the grammar. Show the actions of the parser for the input
string "abab".
8. Construct SLR(1) parsing table for the following grammar: [2015-16]
S -> A)
A -> A,P)(P,P
P -> {num, num}
9. Give the algorithm for computing precedence function. Consider the following operator
precedence matrix, draw the precedence graph and compute the precedence function.
[2015-16]
a ( ) ; $
a > > >
( < < = <
) > > >
; < < > >
$ < <
10. Construct the LALR parsing for the following grammar: [2015-16]
A -> AA
A -> aA
A -> b
11. Construct the CLR parsing table for the following grammar: [2014-15]
S -> CC
C -> cC
C -> d
Automatic Parser Generator - YACC
1. Write short note on YACC parser generator. [2017-18][2014-15]
2. How YACC can be used to generate parser. [2015-16]
Syntax Directed Translation and Intermediate Code:
1. Write the quadruples, triple and indirect tuple for the following expression: [2018-19]
(x+y)*(y+z)+(x+y+z)
2. Define Syntax Directed Translation. Construct an annotated parse tree for the expression
(4 * 7 + 1) * 2 , using simple desk calculator grammar. [2018-19][2014-15]
3. What is postfix notations and postfix translation? Explain with suitable example.
[2017-18][2014-15]
4. Define three address code. What are its various representations [2017-18][2014-15]
5. What are Quadruples and Triples [2017-18][2015-16]
6. What is postfix notations? Translate (C+D)*(E+Y) into postfix syntax directed translation
scheme (STDS). [2017-18]
7. Why are quadruples preferred over triples in an optimizing compiler? [2016-17]
8. What is a syntax tree? Draw the syntax tree for the following statement :
cbcba-*+-*= [2016-17]
9. Write an algorithm to partition a sequence of three address statements into basic blocks.
[2016-17]
10. Translate the expression into three address code: [2014-15]
-(a+b) * (c+d) + (a+b+c)
11. What is syntax directed translation? How are semantic actions attached to the production?
Explain with example. [2014-15]
Translation of Programming Statements:
1. Generate three address code for C[A[I, j]] = B[I, j] + C[A[I, j]] + D[I+j] (You can assume any data
for solving question, if needed). Assuming that all array elements are integer. Let A and B a
10 * 20 array with low1= low2 =1 [2017-18]
2. How would you convert the following into intermediate code? Give a suitable example.
i) Assignment Statements. ii) Case Statements [2016-17]
3. Define backpatching and semantic rules for boolean expression. Derive the three address code
for the following expression: P < Q or R < S and T < U [2015-16][2014-15]
4. Generate three address code for the following code: [2015-16]
switch a+b
{
case 1: x=x+1
case 2: y=y+2
case 3: z=z+3
default: c=c-I
}
5. Generate three address code for the following code segment: [2014-15]
while (a<b) do
if (c<d) then x=y+z
Symbol Table:
1. Distinguish between static scope and dynamic scope. Briefly explain access to non-local names in
static scope. [2018-19]
2. Describe the data structure for symbol table. [2017-18][2014-15]
3. How names can be looked up in symbol table? Discuss. [2016-17]
4. Describe symbol table and its entries. Also discuss various data structure used for symbol table.
[2015-16]
5. Define scoping. [2014-15]
Runtime Administration:
1. Draw the format of Activation Record in stack allocation and explain each field in it. [2018-19]
2. What is meant by Activation Record. [2017-18][2014-15]
3. How to subdivide a run time memory into code and data areas. Explain. [2016-17]
Error Detection and Recovery:
1. List the various error recovery strategies for a lexical analysis. [2018-19]
2. Explain in detail the error recovery process in operator precedence parsing method. [2018-19]
3. Explain logical phase error and syntactic phase error. Also suggest methods for recovery of error.
[2017-18]
4. What are lexical phase errors, syntactic phase errors and semantic phase errors? Explain with
suitable example. Also suggest methods for recovery of errors. [2015-16][2014-15]
