CMPS 274 Final, Fall 2001
American University of Beirut · Compiler Construction · 20 pages
Showing the first 10 of 20 pages. Download the PDF to see all of it.
More CMPS 274 files
Show the text of this final exam
AMERICAN UNIVERSIT®
LIBRARY
Ok te Faculty of Arts & Sciences
Department of Mathematics & Computer Sciences
CMPS 274—Compiler Construction
Fall 2001-2002
Final Exam
Wednesday, February 6, 2002
Student Id:
Signature:
Instructions
e There are 5 problems and 20 pages. Make sure you have all of them.
The exam is closed book, closed notes, and closed neighbor.
e graded. Include all work or justification for partial credit.
© Your handwriting should be readable so itcan b
Problem 1 23 7
La
I.b 10
Lc 4
Id 4
Le
Problem 2 3H
2a
2b
2c
2d
Ze
Problem 3 1
3.a 10
3.b 5
Problem 4 31
ta 3-
4b 34
de 10
did i 15
Problem 5 | 35
Sa 5
“5b 10
ERICAN UNIVERSITY)
LIBRARY
OF KEDRU
toa | Ga
to | wo} oo
N
a OF REPRE
10
RICAN UNIVERSIT?)
LIBRARY
OF REIAL?
: . , .
a February 6, 2002 Initials:
Problem 1 (2+10+4+4+5)
Consider the following grammar where lower-case bold letters are terminal symbols and upper-case letters are
non-terminals:
I. s > Aa
2. s > bAc
3. S > be
4. S ed bda
5. A > d
(a) Compute the FIRST and FOLLOW sets of this grammar.
Compiler Construction (CMPS 274) . Page 2 of 20
, February 6. 2002
(b) Compute the LR(1) states clearly indicating the kernel and non-kernel items.
Compiler Construction (CMPS 274) Page 3 of 20
February 6, 2002 Initials:
(c) Establish the SLR(1) parsing table.
Compiler Construction (CMPS 274) Page 4 of 20
February 6, 2002 Initials:
(d) Establish the LALR(1) parsing lable.
Compiler Construction (CMPS 274) Page 5 of 20
February 6, 2002 Initials:
te) Prove that the grammar is LALR(1). but not SLR(1) clearly indicating how the LALR(1) machine solves
the problems associated with the SLR(1) machine.
Compiler Construction (CMPS 274) Page 6 of 20
_ February 6, 2002 Initials:
Problem 2 (15% =3* 5)
Consider the following action-augmented grammar shown below. In this grammar, lower-case letters in bold
are terminal symbols and upper-case letters are non-terminals..
LoS > TU { print("1"); }
2, S$ > UV ¢ print("2"); }
3. T > aT ¢ print("3"); }
4. T > bd { print("4"); }
5 Ure ( print("5"); }
6 U > dU { print("6"); }
7 Vo > a { print("7"); }
(a) Computer the FIRST sets for the above grammar,
(b) Compute the FOLLOW sets for the above grammar.
Compiler Construction (CMPS 274) Page 7 of 20
"February 6, 2002 Initials:
’ . ’
(c) Compute the SELECT sets for the above grammar.
(d) Construct the LL(1) parse table.
Compiler Construction (CMPS 274) Page 8 of 20
February 6, 2002 Initials:
(ec) Use the table to derive the output of the translation of the string “abcd”.
Compiler Construction (CMPS 274) Page 9 of 20
February 6, 2002 Initials:
Problem 3 (15%)
Given the following C-- program:
float myprog (int n)
{
float x = 1.0;
while (n > 0) {
x= ((n > 5) [jf (rs
nen- 1;
}
return x;
}
(a) Draw the source tree for this program.
(b) Manually simulate semantic analysis and annotate the tree nodes with conversions and types.
Compiler Construction (CMPS 274) : Page 10 of 20