Exercises for the Compiler Design Course
- What is the Chomsky hierarchy of languages ? Why do we use Regular
Expressions instead of Context Free Grammars to describe tokens ? 4
- (a) What are some advantages of high level languages over assembly
languages? Why is translation to machine language from HLL more
complicated than from assembly language? 3 + 3
(b) What are the advantages of assembly languages over high level
languages? 3
- (a) What are the major stages in the process of compilation?
5
(b) What do you understand by cross-compilation?
3
- Suppose in a programming language the word if is reserved
keyword, and all other strings of alphabetic characters are identifiers.
Draw a transition diagram for recognising these two classes of words.
Represent the transition diagram in the form of a transition table.
3 + 4
- What is "flex"? 3
- What is lex (or flex) used for ? Write the regular expression that
describes a word that has a sequence of hexadecimal digits followed by a
dot and then another sequence of hexadecimal digits. The word may
optionally have a hyphen as a prefix. Give two examples of such words.
2 + 2 + 1
- What does parsing mean in the context of compilers? 3
- Write context free grammar for a single statement for defining simple
scalar variables (not arrays, structures, or unions) in C language. What
are the tokens that may be returned by the lexical analyser during
analysis of such a statement? 3 + 2
- Describe the syntax for a variable definition statement in C
language for simple scalar variables using Context Free Grammar. Give the
rightmost derivation sequence for the statement -
4 + 2
short a, count, *p;
- (a) Using a simple example show that a regular grammar can be
represented as a context free grammar. 5
(b) Write the leftmost and rightmost derivations,
and draw the parse-tree for the string - 6
id id + id * id ^
with the grammar
E -> E T + | T
T -> T F * | F
F -> F P ^ | P
P -> E | id
- Describe the syntax for a variable definition statement in C language
for simple scalar variables using Context Free Grammar. Give the
rightmost derivation sequence for the statement-
4 + 2
short a, count, *p;
- What do you understand by ambiguity of a grammar? 2
- (a) Using a small example briefly explain ambiguous grammar.
If the ambiguity is removed by rewriting the grammar, will the
unambiguous grammar recognise exactly the same language as the ambiguous
grammar? 3 + 2
(b) What is the significance of left-most or
right-most derivations while using an unambiguous grammar?
2
- What is operator precedence parsing? Give an example of a grammar that is
unambiguous but not an operator precedence grammar. 3 + 2
- (a) What are the different precedence relations used in operator
precedence parsing? Draw the operator precedence table for the following
grammar- 2 + 4
E -> E * T | T
T -> T + F | F
F -> (E) | id
(b) What do you understand by left-recursion and
left-factoring? How are they relevant in top-down parsing?
3 + 3
- (a) Construct the operator precedence parsing table for parsing
simple arithmetic expressions involving addition, subtraction,
multiplication, division and exponentiation assuming the usual precedence
and associativity of the operators. [Use ^ as the operator for
exponentiation.] Briefly explain each of the important steps in the
process. 4 + 2
(b) Depict the parsing action (stack content, remaining input)
sequence of the above parser for the input string - 5
20 + 30 * 6 ^ 5
- How does left recurssion create problem in top down parsing. Explain
with a small example. How would you eliminate left recurssion in the
grammar - S -> S,i | i ?
4 + 3
- (a) Briefly describe the algorithm of predictive parsing ? How is
the use of stack in top-down different from that in
bottom-up parsing ? 5 + 3
(b) Briefly describe the method of recursive descent
parsing. 5
- Consider the following grammar where E is the start symbol:
E -> TE'
E' -> +E | Ø
T -> FT'
T' -> T | Ø
F -> PF'
F' -> *F' | Ø
P -> (E) | a | Ø
( Ø means the empty string )
(a) Compute FIRST and FOLLOW for each non-terminal of the above grammar.
4
(b) Construct the predictive parsing table for the grammar.
4
(c) Is the grammar LL(1)? Why? 2
- Consider the following grammar G where E is the start symbol-
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
(a) Is G un-ambiguous? Why? 1 + 2
(b) Why is G not suitable for recurssive descent parsing? Rewrite G
as G' to make it suitable. 1 + 2
(c) Compute FIRST and FOLLOW for each non-terminal of G'.
4
(d) Construct the predictive parsing table for the grammar G'.
3
(e) Why or why not is the grammar G' LL(1)? 2
- Construct the sets of LR(0) and the SLR parsing table for the grammar
4 + 5
F -> id ( P );
P -> P & id | id
- Write the C program statement to define the data structures for storing
a grammar given in BNF, and to represent LR(0) items. 4
- Consider the following grammar where S is the start symbol:
S -> ictSeS | ictS | a
(a) Compute FOLLOW for each non-terminal of the above grammar.
3
(b) Construct the canonical collection of LR(0) items for the
grammar. 4
(c) Is the grammar SLR(1)? Why? 2
- What are shift-reduce and reduce-reduce conflicts? 4
- (a) Construct the set of LR(0) items for the grammar given below and
construct the SLR parsing table for it. Is the grammar LR(0) ?
8 + 2
T -> B | { L }
L -> T L | B
B -> a | b
(b) Depict the parsing action (stack content, remaining input, action)
sequence of the above parser for the input string - 3
{ a { b a } }
- Consider the grammar-
S -> i c t { S } e S | i c t S | a = a P a
P -> + | *
(a) List all the LR(0) item sets for the grammar. 4
(b) Construct the SLR(1) parsing table. 5
(c) Is the grammar SLR(1)? Is the grammar unambiguous?
3
- (a) How is canonical LR parsing different from LALR
parsing? 3
(b) What is yacc? 2
- How is canonical LR parsing method different from SLR parsing? What
would you say about their respective language recognition power?
3 + 2
- What does the UNIX utility YACC do ? What is the essential part
(that must be present) in the input to YACC? 3 + 2
- What do you understand by ambiguity of a grammar? 2
- Why is it sometimes useful to use an ambiguous grammar for parsing
instead of a rewriting the grammar to remove ambiguity? How is it
possible to ambiguous grammar for parsing? 3 + 2
- What is the difference between error detection and error recovery?
Describe a simple method for error recovery for syntax errors.
3 + 4
- What are some of the errors that a compiler should detect? What course
of action should the compiler take when it detects an error?
3 + 3
- Which of the following expressions have l-values? Which have
r-values:
- A[I+1]
- *A
- &A
- &(*A)
- *(&A)
- (a) Present a suitable format for Intermediate Code that may be
generated by a compiler. Using that format express the following source
code segment in the intermediate code form - 3 + 3
x = a + 30 * 6;
y = square( x );
(b) Briefly describe the different types of storage requirements of a
program and how a compiler may handle each of these requirements.
3 + 4
- Write the outline of the semantic actions for translation that may be
associated with the production for the common if-construct -
S -> iCtSeS 4 + 2
Why may we rewrite the production to incorporate the semantic actions?
- What is syntax directed translation? 3
- (a) Consider the following grammar for arithmatic expressions-
E -> E + T | T
T -> T * F | F
F -> (E) | id
Write the semantic actions for a syntax-directed translation scheme for
converting input expressions into intermediate code in
three-address code notation. 8
(b) Using a simple example, show the need for back patching
during intermediate code generation by syntax directed translation.
5
- (a) What does a compiler do to facilitate linking? 3
(b) Why do programming languages provide the macro feature
despite the procedure call mechanism ? What do you understand by
conditional expansion during macro processing? 4 + 2
- Why is a symbol table used by a compiler ? Give a possible format
of a symbol table record used by a compiler and state why you would use
either an array, a hash table, or any other data structure to
keep these records. 5
- Describe a scheme to create a symbol table for processing programs in a
block-structured language in multiple passes. 5
- In a block-structured language, when there are multiple symbols
with the same string, how can hashing be used to locate the appropriate
symbol table record for a particular symbol? Describe using block
diagram. 5
- (a) What is an activation record and why is it used ? Why
are activation records maintained in a stack ? 4 + 2
(b) What does an activation record contain? What kind of
program data is allocated in an activation record? Why is indirection
used for some data objects in the activation record?
2 + 2 + 2
- Why is code optimization done by compilers but not by assemblers ?
4
- What are some of the optimisations that can be performed by a
compiler ? Which kind of optimisation is more effective inside loops -
space optimisation or time optimisation ? Why ? 5 + 2
- (a) What are basic blocks and flow graphs? Identify the
basic blocks and draw the flow graph for the following three-address code
segment- 2 + 3 + 2
(1) PROD = 0
(2) I = 1
(3) T1 = 04 * I
(4) T2 = addr(A) - 4
(5) T3 = T2[T1]
(6) T4 = addr(B) - 4
(7) T5 = T4[T1]
(8) T6 = T3 * T5
(9) PROD = PROD + T6
(10) I = I + 1
(11) if I <= 20 goto (3)
(b) What is a Directed Acyclic Graph and what are its uses?
2 + 2
- (a) What do the register descriptor contain? How are these
useful in code generation? 2 + 2
(b) Give an example to show how reordering of intermediate code
statements can improve code generation. 3