MANGAYARKARASI COLLEGE OF ENGINEERING

(Approved by AICTE, New Delhi & Affiliated to Anna University, Chennai) MANGAYARKARASI
NAGAR, PARAVAI, MADURAI – 625 402
Website: E-Mail: :

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

CS8602-COMPILER DESIGN QUESTION BANK – UNIT 1
Part-A
1. Define Compiler. (Understand)
Compiler is a program that read a program in one language - Source language -
and translate it into an equivalent program in another language - Target language.
Compiler reports to its user the presence of errors in the source program that it detects
during the translation process.

Source
Compiler Target
Program
Program

Error Messages
2. What are the two parts of Compilation? Explain briefly. (Understand) (Apr 2016, Apr 2017)
There are two parts of compilation process
 Analysis part
 Synthesis part
Analysis Part – It breaks up the source program into constituent pieces and applies the
grammatical structure on them. It uses this structure to create an intermediate representation
of the source program. It also collects information about the source program and stores it in a
data structure called symbol table.
The analysis must provide information to the user if the source program is
syntactically incorrect and semantically unsound, so the user can take the corrective
measures. The analysis part is called as front end of the compiler.
Synthesis Part – It constructs the desired target program from the intermediate representation
and the information in the symbol table. The synthesis part is called as back end of the
compiler.

Frond Back end

Source End of Intermediate of
Program Compiler Compile Target
representation of
source Program Program
3. Illustrate diagrammatically how a language is processed? (Understand) (Apr 2016)
In addition to the compiler, there are several other programs may be required
to produce an executable target program. They are called cousins of compiler.
They are listed below.
1. Preprocessor.
2. Assembler
3. Loader
4. Linker
Each program helps in compilation process.

Source Program

Preprocessor

Modified Source Program

Compiler

Target Assembly Program

Assembler

Relocatable Machine Code

Linker/Loader Library Files,
Relocatable Object files

Target machine code

A Language Processing System

4. What are the various phases of compiler? (Understand)
Compiler operates in phases, each of which transforms the source program from
one representation to another.
There are six phases of a compiler. They are
 Lexical Analyzer
  Syntax Analyzer
 Semantic Analyzer
 Intermediate Code generator
 Code Optimizer (Machine Independent / Machine Dependent)
 Code generator
5. What is an interpreter? (Understand) (Dec 2017)
Interpreter is a program translator. During translation, it executes the operations
specified in the source program instead of creating a target program as an output.

Source Program Interpreter

Output
input

6. What do you mean by cross-compiler? (Understand) (Dec 2017)

A cross compiler is a compiler capable of creating executable code for a
platform other than the one on which the compiler is running. For example, a compiler
that runs on a PC but generates code that runs on Android smartphone is a cross
compiler.
7. Define Lexeme. (Understand) (Dec 2017)
Lexeme is a sequence of characters that matches the pattern for a token.
Example: sum,total are the lexemes of token identifier.
8. What advantages are there to a language-processing system in which the compiler
produces assembly language rather than machine language? (Understand) (Dec 2020)
 The assembly language program is easier to produce and debug.
 It is not necessary the compiler aware of the target machine details.
9. Compare Compiler and Interpreter. (Understand)
S.No Compiler Interpreter
Interpreter executes the operations
Compiler translates the source
1 specified in the source program
program into target program
statement by statement
2 Compilation is a faster process Interpretation is a slower process
Error diagnostics is not easy as Error diagnostics is better than
3
interpretation compilation
 10. Explain the need for grouping of phases. (Understand) (Apr 2016, Dec 2016)
Pass of the compiler: The activities from several phases are grouped together into pass
that reads an input file and writes an output file.
There are two passes of the compiler.
1. Front end pass – It includes lexical analysis, syntax analysis, semantic analysis
and intermediate code generation phases of the compiler
2. Back end pass – It includes code generation phase of the compiler.
Advantages of grouping the phases into pass:
 Compilers for different source languages for one target machine is produced by
combining the front end of different languages with the back end for a certain
target machine.
 Compilers for different target machines for a same source language is produced by
combining a front end with back ends for different machines.
11. Differentiate between lexeme, token and pattern. (Understand) (Apr 2016, Dec 2016,
Apr 2017)
Tokens, Patterns, Lexemes
Tokens - Taken is the smallest unit in the program, that cannot be further divided into
meaningful unit. It is represented by a pair consisting of a token name and an optional
attribute value. The token name is an abstract symbol representing a kind of lexical unit.
Patterns - Pattern is the description that tells the lexemes of the token.
Lexeme - Lexeme is a sequence of characters that matches the pattern for a token.
Example:
TOKEN PATTERN SAMPLE LEXEMES
if Characters i,f if
else Characters e,l,s,e else
comparison < or <= or > or >= or = or <> <, <=, >, >=, =, <>
id letter followed by letters and digits pi, const, D2
num any numerical constant 3.1416,0,6.02E23
literal Any characters between “, and ” “core dumped”
 12. What are the tasks performed by the lexical analyzer? (Understand)
The lexical analyzer task is divided into cascade of two processes
i. Scanning – It consists of the simple processes such as deletion of comments
and compaction of whitespace characters.
ii. Lexical Analysis – It is the complex portion which produces tokens
from the output of the scanner.
13. What are the issues in lexical analysis? (Understand) (Apr 2016, Apr 2017,Dec 2017)
There are several reasons for separating the analysis phase of compiling into lexical
analysis and parsing.
1. Compiler design is simplified.
2. Compiler efficiency is improved.
3. Compiler portability is enhanced.
14. What is Symbol table? (Understand) (Dec 2016)
A symbol table is a data structure containing a record for each variable name
with fields for the attributes of the name. These attributes may provide information
about the storage allocated for each name, its type, its scope. If the name is a
procedure name, then the attributes provide information about number and types of its
arguments, the method of passing each argument and the type returned.
15. List the various compiler construction tools. (Remember) (Dec 2016)
 Scanner generators
 Parser generators
 Syntax directed translation engines
 Code-generator generators
 Data flow analysis engines
 Compiler-construction toolkits
16. What are Lexical errors? What are the possible recovery mechanisms? (Understand)
Lexical Analyzer reports a lexical error if none of the pattern for tokens
matches any prefix of the remaining input. If lexical error occurs, the lexical
analyzer applies an error recovery strategy to correct the errors. Since the lexical
errors involve a single character, the possible error recovery actions are:
1. Delete one character from the remaining input.
2. Inserting a missing character into the remaining input.
3. Replacing an incorrect character by a correct character.
 4. Transposing two adjacent characters.
17. Why Buffering scheme is required in the process of lexical analysis?
(Understand) For many source languages the lexical analyzer needs to look ahead
several characters beyond the lexeme to identify the token. The large number of
characters should be processed rather than a single character to find a single token.
The specialized buffering technique is required to reduce the amount of overhead
required to process a
single input character.
18. Write the algorithm to advancing the forward pointer in the presence of sentinel
character. (Understand)
Algorithm for advancing forward pointer with sentinel character
switch(*forward++)
{
case eof:
if (forward is end of the first buffer)
{
reload the second buffer;
forward=beginning of second buffer;
}
else if(forward is end of the second buffer)
{
reload the first buffer;
forward=beginning of first buffer;
}
else
terminate lexical analysis;
break;
cases for other characters
}
19. Define Regular Expression. (Understand)
Regular Expression is the notation to specify the tokens of the language.
Ex: a*b is the regular expression.
A language denoted by a regular expression is said to be a regular set.
Regular Expression is defined recursively.
Basis Rules :
 1. ‘Ɛ’ is the regular expression denotes the language L(Ɛ) and its member is {Ɛ}
2. ‘a’ is the regular expression denotes the language L(a) and its member is {a}
Inductive Rules:
1. r|s is the regular expression denotes the language L(r)UL(s).
2. r.s is the regular expression denotes the language L(r).L(s)
3. r* is the regular expression denotes the language (L(r))*.
20. What is Regular Definition? (Understand)
Regular definitions are name to the regular expressions. Then the regular expressions
are defined using the names. If ∑ is an alphabet of basic symbols, then the regular definition
is a sequence of definitions of the form:
d1 r1
d2 r2
.....
dn rn
Where,
1. Each di is a new symbol, not in ∑.
2. Each ri is a regular expression over ∑ U {d1,d2,d3,……di-1}
Ex: Regular definition of identifier
letter-> A|B|……|Z|a|b|……|z
digit-> 0|1|2|…….|9
id->letter(letter|digit)*
21. List the rules that form the BASIS. (Remember) (Dec 2016)
Regular Expression is the notation to specify the tokens of the language.
Regular Expression is defined recursively.
Basis Rules :
1. ‘Ɛ’ is the regular expression denotes the language L(Ɛ) and its member is {Ɛ}
2. ‘a’ is the regular expression denotes the language L(a) and its member is {a}
22. List the cousins of compiler. (Remember) (Apr 2017)
 Preprocessor
 Assembler
 Loader
 Linker
23. Write the regular expression for identifier and number. (Understand) (Apr 2017)
Regular definition of identifier
letter-> A|B|……|Z|a|b|……|z
digit-> 0|1|2|…….|9
id->letter(letter|digit)*
Regular definition of unsigned number
Unsigned numbers are in the form of 528, 8.79, 6.34E4 or 18E-4
digit -> 0|1|…….|9
digits -> digit.digit*
fraction ->.digits | ɛ
exponent -> (E(+|-| ɛ)digits) | ɛ
number -> digits fraction
exponent
24. Explain various errors encountered in different phases of compiler. (Understand)
(Apr 2016, Dec 2016)
The common programming errors are
i. Lexical Errors: It include misspelling of keywords, identifiers or operators.
E,g; Use of identifier sum1 instead of sum
ii. Syntax errors: It include misplaced semicolons or extra or missing braces.
E.g : “ { “ instead of “{ } “
iii. Semantic errors: It include the type mismatches between operands and
operators.
E.g: Return of a value in functions with return type void.
iv. Logical errors: It can be anything from incorrect reasoning on the part of the
programmar.
E.g: Usage of “=” in place of “==” in C program
25. What are the various parts in LEX program? (Understand) (Apr 2017)
A Lex program has the following form:
declarations
%%
translation rules
%%
auxiliary functions
The declarations section includes declarations of variables, manifest
constants (identifiers declared to stand for a constant), and regular definitions.
The translation rules each have the form
Pattern {Action }
Each pattern is a regular expression. The actions are fragments of code, typically
written in C, although many variants of Lex using other languages have been created.
The third section holds whatever additional functions are used in the actions.
26. Draw the transition diagram for relational operators and unsigned numbers.
(Understand) (Apr 2017)
Transition diagram for relational Operators

Transition diagram for Unsigned Number

27. Differentiate NFA and DFA. (Understand)

S.No NFA DFA
The same symbol can label For each state s and input symbol a,
1 edges from one state to several there is exactly one edge out of s
different states. labeled a.
An edge may be labeled by Ɛ, There are no moves on input Ɛ
2
the empty string.
28. Define firstpos, lastpos and followpos. (Understand)
Firstpos (Firstposition): At each node n of the syntax tree of a regular expression, we
define a function firstpos(n) that gives the set of first positions that can match first symbol
of a string generated by sub expression rooted at ‘n’.
Lastpos (lastposition) : At each node n of the syntax tree of a regular expression, we
define a function lastpos(n) that gives the set of last positions that can match last symbol
of a string generated by sub expression rooted at ‘n’.
Followpos : Followpos(i) tells us what positions can follow position ‘i’ in the syntax tree.
29. How the DFA can be optimized? (Understand)
i. Constructing DFA directly from the Regular Expression.
ii. Minimizing the states of DFA.
iii. Represent the transition table in a compact form.
Part-B
30. Describe the various phases of the compiler and trace it with the program segment
(Position=initial + rate *60) (Understand) (Apr 2016, Dec 2016, Apr 2017,Dec
2017)
31. Explain language processing system with neat diagram. (Understand) (Apr 2016)
32. Write notes on Regular expressions. (Understand) (Apr 2016)
33. Write notes on convert regular expression to NFA. Convert the Regular Expression
(a|b)*a (Understand) (Apr 2016)
34. Construct DFA to recognize the language (a|b)*ab (Apply) (Apr 2016)
35. Write notes on compiler construction tools. (Understand) (Dec 2016, Apr 2017,Dec
2017)
36. Discuss the role of lexical analyser in detail with necessary examples. (Understand)
(Dec 2016, Dec 2017)
37. Discuss how finite automata is used to represent the tokens and perform lexical
analysis with examples. (Understand) (Dec 2016)
38. Convert the regular expression (a|b)*abb to NFA. (Apply) (Dec 2016)
39. Write an algorithm to minimize the number of states in DFA. (Understand) (Dec 2016)
40. Describe in detail about cousins of compiler. (Understand) (Apr 2017)
41. Draw the NFA for the regular expression ab*|ab (Apply) (Dec 2017)
42. Write an algorithm to convert NFA to DFA and minimize the DFA with example.
(Understand) (Dec 2017)
43. With a neat block diagram specify the interactions between the lexical analyzer and
the parser. (Understand) (Dec 2020)
44. What is a transition diagrams? Explain briefly how the keywords and identifiers are
recognized using a running example. (Understand) (Dec 2020)
45. Solve the given expressions a:=b+c*4 with different phases of the compiler.
(Understand)
46. What are Lexical errors? What are the possible recovery mechanisms? Divide the
following C++ program : float limitedSquare(x) float x; {/* returns x-squared, but
never more than 100 */ return (x<= –10.0||x>=10.0)?100 : x*x ;}into appropriate
lexemes. Which lexemes should get associated lexical values? What should those
values be? (Understand) (Dec 2020)
Lexical Analyzer reports a lexical error if none of the pattern for tokens matches
any prefix of the remaining input. If lexical error occurs, the lexical analyzer
applies an error recovery strategy to correct the errors. Since the lexical errors
involve a single character, the possible error recovery actions are:
5. Delete one character from the remaining input.
6. Inserting a missing character into the remaining input.
7. Replacing an incorrect character by a correct character.
8. Transposing two adjacent characters.
Lexemes identified with Attribute value:
1. float - nil
2. limitedsquare - pointer to table entry
3. ( - nil
4. x - pointer to table entry
5. ) - nil
6. float - nil
7. x - pointer to table entry
8. ; - nil
9. { - nil
10. return - nil
11. ( - nil
12. x - pointer to table entry
13. <= - le
14. -10.0 - pointer to table entry
15. || - or
16. x - pointer to table entry
 17. >= - ge
18. 10.0 - pointer to table entry
19. ) - nil
20. ? - nil
21. 100 - pointer to table entry
22. : - nil
23. x - pointer to table entry
24. * - mul
25. x - pointer to table entry
26. ; - nil
27. } - nil
47. Convert the regular expression (a|b)*abb using direct method and minimize it.
(Apply) (Apr 2017)
48. Explain input buffering scheme in detail. (Understand)