CMPS 274 Final, Fall 2003
American University of Beirut · Compiler Construction · 26 pages
Showing the first 10 of 26 pages. Download the PDF to see all of it.
More CMPS 274 files
Show the text of this final exam
Faculty of Arts & Sciences
Department of Mathematics & Computer Sciences
en CMPS 274—Compiler Construction
Fall 2003-2004
Thursday, January 29, 2004
Name:
Final Exam
Student Id:
Signature:
Instructions
boobed ats
os vane |
anime mena nin
* There are 6 problems and 26 pages. Make sure you have all of them.
* The exam is closed book, closed notes, and closed neighbor.
¢ The questions are organized by topic and are not sorted by difficulty. Scan the whole exam before you start
working.
e Your handwriting should be readable so it can be graded. Include all work or justification for partial credit.
Problem 1 20
1.1 5
1.2 5
1.3 5
14 5
Problem 2 35
2.1 10
2.2 5
2.3 10
2.4
2.5
Problem 3 20
34 5
3.2 15
Problem 4 10
Problem 5 25
5.1 10
5.2 5
5.3 10
Problem 6 15
6.1 5
6.2 10
Total 125
od
MERIC. S ONEV REGIE
LIBRARY
oF BriRtt
Final Exam (2004-01-29) Initials:
Si, ay
oF BEIRUT
Problem 1. Regular ExpresS (20 =5 + 5+ 5+ 5)
In Modula-3, integer literals have the form base_digits where the base component is optional and defaults to 10 (i.e.,
integer literals represent decimal numbers by default). For example, the literals 2.11010, 8 32,16 1A,10 26,
and 26 are all equivalent; their value is decimal 26.
1. Write a regular expression that generates the set of integer literals in Modula-3.
CMPS 274 2 of 26
Final Exam (2004-01-29) Initials:
2. Write an equivalent regular grammar that generates the same language (i.e., integer literals in Modula-3).
CMPS 274 3 of 26
Final Exam (2004-01-29) Initials:
3. Augment this grammar with attributes and actions to compute the decimal value of a literal, ‘Clearly define the
attributes associated with symbols in the grammar and their types (inherited or synthesized), and describe any
functions that you use.
CMPS 274
4 of 26
Final Exam (2004-01-29) Initials:
4. What would happen to the lexical analysis task concerning Modula-3 integer literals if the pattern for these
literals were switched to digits_base’
AMERICAS FS. ERSTE
LIBRARY
OF BEIRUT
CMPS 274 5 of 26
Final Exam (2004-01-29)
Problem 2. LL & LR Parsing (35 =10+5+10+5+5)
Consider the following simple context-free grammar:
1.
2.
3. | bSd
4, | bSeSd
i. Is this grammar LL(1)? Lf yes, prove it. Otherwise, explain why it is not and rewrite the-grammar as an LL(1)
grammar. -
CMPS 274
Final Exam (2004-01-29) Initials:
2. Is this grammar LR(0)? Explain. peers
Ercas t-
LIBKAKY
OF EWIAUT
CMPS 274 7 of 26
_ Final Exam (2004-01-29) Initials:
3. Is this grammar LR(1)? Answer this question by first constructing the LR(1) state machine along with its
parsing table and then reasoning about it.
CMPS 274 8 of 26
Final Exam (2004-01-29) Initials:
4. Is this grammar LALR(1)? Answer this question by first constructing the LALR(1) state machine along with its
parsing table and then reasoning about it.
RICAN Tater: i
LiBRAKY |
OF BEET
oe
AD RD pee
Laiieiwvde t
. i
| py eneame \
. : eet
CMPS 274
9 of 26
_ Final Exam (2004-01-29) Initials:
5. Is the language modeled by this grammar a regular language? Explain.
r
~
CMPS 274 10 of 26