CS143 Midterm
Spring 2021
• Please read all instructions (including these) carefully.
• There are 5 questions on the exam, some with multiple parts. You have 95 minutes to
both finish the exam and upload it. After 95 minutes, gradescope will close your exam
and automatically submit it, so make sure submit what you have by then.
• The exam is open note. You may use laptops, phones, e-readers, and the internet, but
you may not consult anyone.
• You must upload the answer to each question as an image file or a PDF. You may submit
images of hand-written answers taken with your phone (but allow yourself time to send
the image to your computer, so you can upload it to gradescope). It is your responsibility,
however, to ensure they are legible. Computer typed answers as a PDF are also permitted.
• Solutions will be graded on correctness and clarity. Each problem has a relatively simple
and straightforward solution. You may get as few as 0 points for a question if your solution
is far more complicated than necessary. Partial solutions will be graded for partial credit.
Problem Max points Points
1 15
2 15
3 20
4 20
5 30
TOTAL 100
In accordance with both the letter and spirit of the Honor Code, I have neither given
nor received assistance on this examination.
Type your name as a signature below:
1. Sizes
1. Sizes of NFAs
of NFAs andand DFAs
DFAs
A regular
A regular expression
expression can can be converted
be converted to both
to both an NFA
an NFA and and a DFA.
a DFA. (Remember
(Remember thatthat
NFAsNFAs
andand
DFAsDFAs
mustmust
havehave a starting
a starting statestate
and and accepting
accepting states
states and and
thatthat
eacheach
statestate
of a of a DFA
DFA
must have an outgoing transition for every symbol in the alphabet.) Given
must have an outgoing transition for every symbol in the alphabet.) Given the alphabet the alphabet
{0, provide
{0, 1}, 1}, provide
• a •regular
a regular expression,
expression,
• a •corresponding
a corresponding
NFA,NFA,
and and
• a •corresponding
a corresponding
DFADFA
where:
where:
(a) (a)
TheThe
NFANFA
has has fewer
fewer states
states thanthan
the the
DFA.DFA.
Answer:
Answer:
• (0|1)⇤
0,1
q0
•
0,1
q0 q1
0,1
•
(b) (b)
The The
NFANFA has same
has the the same number
number of states
of states as DFA.
as the the DFA.
Answer:
Answer:
• (0|1)⇤
0,1
q0
•
(b) The NFA has the same number of states as the DFA.
Answer: 0,1
• (0|1)⇤
0,1
q0
•
q0
•
(c) The NFA has more states than the DFA.
Answer: 0,1
• (0|1)⇤
q0 0,1
• q0 q1
0,1
•
(c) The
(c) The NFANFA has more
has more states
states thanthan the DFA.
the DFA.
0,1
Answer:
Answer:
• (0|1)⇤
q0 0,1
•
q0 q1
0,1
•
0,1
q0
•
2. CFG Transformations
Left factor and remove immediate left recursion in the following grammar:
S → cA | cBe | cBd | Sc | SA
A → e
B → f
Answer:
Left factored:
S → cX | SY
X → BZ | A
Y → c|A
Z → e|d
A → e
B → f
With immediate recursion eliminated:
S → cXS 0
S0 → Y S0 |
X → BZ | A
Y → c|A
Z → e|d
A → e
B → f
3. Syntax-Directed Translation
Given the following grammar, add semantic actions that computes the number of se-
quences of successive a’s. For example, both acab and aacabb have two sequences of a’s
each, while abacabcb have three such sequences.
You must use the following attributes: int val, bool left, and bool right. Use bison
syntax: $i.val refers to the val attribute of the ith symbol of the production and $$.val
refers to the val attribute of the production’s result. You may not use global variables.
S → TS
|
T → aT b
| bT c
| cT a
|
Answer:
S -> TS {
if ($1.right && $2.left) {
$$.val = $1.val + $2.val - 1;
} else {
$$.val = $1.val + $2.val;
}
$$.left = $1.left;
$$.right = $2.right;
}
| epsilon {
$$.val = 0;
$$.left = false;
$$.right = false;
}
T -> aTb {
$$.val = $2.left ? $2.val : $2.val + 1;
$$.left = true;
$$.right = false;
}
| bTc {
$$.val = $2.val;
$$.left = false;
$$.right = false;
}
| cTa {
$$.val = $2.right ? $2.val : $2.val + 1;
$$.left = false;
$$.right = true;
}
| epsilon {
$$.val = 0;
$$.left = false;
$$.right = false;
}
4. Top-Down Parsers
In this question we will explore top-down parsers and LL(k) grammars.
4. Top-Down Parsers
(a) Construct the LL(1) top-down parser table for the following grammar.
In this question we will explore top-down parsers and LL(k) grammars.
S → aSA
(a) Construct the LL(1) top-down parser table
| for the following grammar.
A → bS
S ! aSA
| c
| ✏
Answer: A ! bS
| c
First(S) = {a, }
Answer:
First(A) = {b, c}
F irst(S) = {a, ✏}
F irst(A) = {b, c} Follow(S) = Follow(A) = {$, b, c}
F ollow(S)
(Since = {$,
A never goesb, c}
to = F ollow(A)
epsilon, the Follow sets are not useful in filling the table.)
a b c $
S aSA ✏ ✏ ✏
A bS c
(b) Show that the following grammar is not LL(1) by pointing out where a conflict occurs
when constructing its LL(1) top-down parser table.
S → aSA
|
A → abS
| c
Answer:
First(S) = {a, }
First(A) = {a, c}
Follow(S) = Follow(A) = {$, a, c}
Since a ∈ First(aSA), the table must have an entry T [S, a] = aSA corresponding to
the production S → aSA. However, as ∈ First() and a ∈ Follow(S), there must
also be an entry T [S, a] = corresponding to S → .
5. Bottom-Up Parsers
Consider the following grammar:
S → Ae | AB | dB
A → d|f
B → g
where the terminals are {d, e, f, g}.
(a) List the first and follow sets of the non-terminals.
Answer:
First(S) = {d, f }
First(A) = {d, f }
First(B) = {g}
Follow(S) = Follow(B) = {$}
Follow(A) = {e, g}
(b) Draw the LR(0) DFA. (In this question, you need only provide accepting states,
including their items, and transitions between accepting states.)
Answer:
S’ → S. S → Ae. S → AB.
S
e
B
S’ → .S
S → .Ae
A S → A.e g
S → .AB
S → A.B B → g.
S → .dB
B → .g
A → .d
A → .f
d g
f
A → f. S → d.B B
A → d. S → dB.
B → .g
(c) Is the grammar SLR(1)? Justify your answer.
Answer:
No, there is a shift-reduce conflict in the state in the middle, between S → A.B and
B → .g, since g ∈ Follow(A).
