Name: __________________________ RCSID: ________
1. Grammars, ambiguity, precedence and associativity (25 points)
Consider the Boolean expression grammar. S and E are nonterminals; and, or, not, and b are terminals.
S¡úE
E ¡ú EandE | EorE |notE |b
a) (12 points) Show that the grammar is ambiguous by drawing all parse trees for expression b or not b and b.
CSCI 4430 Exam 1, Fall 2018 2
Name: __________________________ RCSID: ________
Suppose that we wanted b or not b and b to have only one possible parse tree (call this property P):
S
E
EX o B
or
E
B
b
E
BB
b
b
b) (5 points) Describe in English the precedence needed to ensure property P.
c) (8 points) Construct an equivalent unambiguous grammar that gives precedence to operators or, and, and not according to property P, and left associativity to or and and.
I
i
E
B
E
Eand
not
CSCI 4430 Exam 1, Fall 2018 3
Name: __________________________ RCSID: ________ Consider the following grammar over terminals 0, 1, a, and b.
S ¡ú A $$ A¡úBA|0A1A|¦Å B¡úaCb C¡úBC|0C1C|¦Å
a) (9 points)* Fill in the table below with the FIRST and FOLLOW sets for the nonterminals:
2. LL Parsing (22 points)
FIRST
FOLLOW
A
B
C
b) (10 points)* Fill in the column headings and the entries for the LL(1) parsing table for this grammar: (There may be more columns than needed.)
S
A
B
C
c) (3 points) Is the above grammar LL(1)? Explain briefly why yes, or why not.
3. SLR(1) Parsing (50 points)
We return to the ambiguous grammar for Boolean expressions from Part 1.
S¡úE
E ¡ú EandE | EorE |notE |b
CSCI 4430 Exam 1, Fall 2018 4
S ¡ú AcAd | BdBc A¡ú¦Å
B¡ú¦Å
(1) LL(1) only (2) SLR(1) only (3) LL(1) and SLR(1)
(4) neither LL(1) nor SLR(1)
CSCI 4430 Exam 1, Fall 2018
7
Name: __________________________ RCSID: ________
h) (3 points)* Given the conflict resolution rules from g), what is the maximal number of grammar symbols, terminals or nonterminals, that can appear on the stack?
4. LL and SLR grammars (8 points)
a) (2 points)* Consider this grammar over terminals (, ). The grammar is
S¡úA
A ¡ú AA | ( A ) | ¦Å
(1) LL(1) only (2) SLR(1) only (3) LL(1) and SLR(1) (4) neither LL(1) nor SLR(1) b) (2 points)* Consider this grammar over terminals and, or, not, b. The grammar is
S¡úE
E ¡úandE E |orE E |notE |b
(1) LL(1) only (2) SLR(1) only (3) LL(1) and SLR(1) c) (2 points)* Now this one:
S¡úE
E¡ú EandE | E orE |notE |b
(1) LL(1) only (2) SLR(1) only (3) LL(1) and SLR(1)
d) (2 points)* Consider the following grammar over terminals c and d. The grammar is
(4) neither LL(1) nor SLR(1)
(4) neither LL(1) nor SLR(1)
Name: __________________________ RCSID: ________
5. Prolog (20 points)
a) (8 points) Consider the program below. You may assume that the first two
arguments are positive integers.
d(A, B, 0, A) :- A < B.
d(A, B, Q, R) :- A >= B, A1 is A-B, d(A1, B, Q1, R), Q is Q1+1.
Show ALL answers to this query
?- d(5, 3, Q, R).
d(A, B, Q, R) does ____________________ Q contains ________________________
R contains ________________________
b) (12 points)** Write a Prolog predicate eval that takes a list representing a boolean expression in preorder, and prints its boolean value. 0 and 1 stand for boolean values false and true respectively.
E.g., eval([or,0,1],V). yields V = 1, and eval([and,or,0,and,0,1,1],V). yields V = 0. However, eval([and,or,0,and,0,1],V). yields false.
Note: You may use built-in or helper predicates as needed. You may use arithmetic operators + and * to help emulate or and and respectively.
CSCI 4430 Exam 1, Fall 2018 8