CSC401 – Compiler Construction
Tutorial Questions
1. Using the production rule below, determine the First and Follow derivatives.
E => TE'
E' => +T E' | ɛ
T => FT'
T' => *FT' | ɛ
F => id | (E)
2. What are the First and Follow sets for the following grammar? The start nonterminal is E.
E -> A
E -> L
A -> n
A -> i
L -> ( S )
S -> E , S
S -> E
Left factor the grammar of the preceding question and then write a recursive descent parser for it. The parser
should only read a string and tell whether it is in this language.
3. With the aid of annotated diagram, describe the various stages of compilation.
4. The analysis of a source program is divided into the following phases, briefly discuss each of the
phases.
(i) Linear Analysis (ii) Hierarchical Analysis (iii) Semantic Analysis.
5. Briefly explain the following terms as they are used in compilation
(i) Cross Compiler (ii) Source-to-source Compiler (iii)Pre-Processor
(iv) Relocatable Machine Code (v) Loader/Linker.
6. Explain what happens in the following phases of compilation of source program to target
program:
(i) Intermediate Code generation (ii) Code Optimizer (iii) Target Code generator
7. When is a grammar said to be left-recursive?
8. What is a disadvantage of left recursion?
9. Consider the grammar S → Af |
G1 A → Ac | Sd | Be
B → Ag | Sh | k
Is the grammar G1 left recursive? If yes, attempt to remove left recursion from the grammar.
10. State five roles of a parser in program compilation.
11. Briefly describe the purpose of the lexical and syntax analysis phases in a compiler.
12. What are Lexical errors? Give four examples of lexical errors you know
13. Consider the following Context Free Grammar
S → Aa | BAb
A → BB | c
B → Sd | e
i. Give a right-most derivation of ecadeb
ii. Give a left-most derivation of ecadeb.
iii. Compute FIRST and FOLLOW for this grammar. Show your work.
iv. Is the grammar LL(1)? Justify your answer.
v. Is the grammar SLR(1)? Justify your answer.
14. What is a compiler? How important is compiler to Computer Architects?
15. What is a grammar?
sentence –> <subject> <verb-phrase> <object>
subject –> This | Computers | I
verb-phrase –> <adverb> <verb> | <verb>
adverb –> never
verb –> is | run | am | tell
object –> the <noun> | a <noun> | <noun>
noun –> university | world | cheese | lies
16. Using the above rules or productions, derive the simple sentence below:
This is a university
17. Explain the role of the following in program compilation.
(i). Lexical Analyzer (ii). Syntax Analyzer (iii). Symbol Table.
18. a. Using the productions (G) below, rewrite the grammar in LL(1) form.
b. Compute the FIRST and FOLLOW sets for the grammar G given as:
E→A
E→L
A→n
G = A→i
L → (S)
S → E, S
S→E
19. The tokens of this language are characters. Presume a lexical analyzer is available and that statement
match (c) will check the current lookahead token to see whether it is character c. If so, it will put the
next token into variable lookahead. If not, it will print "no" and stop the program. Statement
INIT_LEXER initializes the Lexer, setting lookahead to the first token. Write a recursive descent
parser for it. The parser should only read a string and tell whether it is in this language.
20. What is the difference between a compiler and an interpreter?
21. What advantages are there to a language-processing system in which the compiler produces
assembly language rather than machine language?
22. Convert the following NFA in the figure below to a corresponding DFA using subset construction.
23. Consider grammar G2 and grammar G3 given below:
S → E$ S→X
G2 = E → E + T | T G3 = X → Y | id
T→T*F|F Y → id
F → id | (E)
i. Show whether grammar G2 and grammar G3 are LR (0) or not. Give reasons for your answer.
ii. With an example in each case identified, discuss the problems with LR (0) grammars.
iii. Suggest solutions to the problems identified in (ii) above.
24. There are mainly four classifications of grammars by Chomsky as depicted by the diagram below.
Describe each type with examples.
Type 0
Type 1
Type 2
Type 3
