CS 164 Programming Languages and Compilers Handout 8
Midterm I
o Please read all instructions (including these) carefully.
o There are six questions on the exam, each worth between 15 and 30 points.
You have 3 hours to work on the exam.
o The exam is closed book, but you may refer to your four sheets of
prepared notes.
o Please write your answers in the space provided on the exam, and clearly
mark your solutions. You may use the backs of the exam pages as scratch
paper. Please do not use any additional scratch paper.
o Solutions will be graded on correctness and clarity. There are no
``tricky'' problems on the exam---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.
NAME: _______________________________________________
SID or SS#: _______________________________________________
|_Problem_|Max_points_|Points_|_
|____1____|___15_____|_______|
|____2____|___15_____|_______|
|____3____|___20_____|_______|
|____4____|___20_____|_______|
|____5____|___30_____|_______|
|____6____|___30_____|_______|_
|__TOTAL__|___130____|_______|
Fall 95 page 1 of 8
CS 164 Programming Languages and Compilers Handout 8
1. Regular Expressions (15 points) The following description of integer
constants in C++ appears on page 480 of ``The C++ Programming Language.''
An integer constant consisting of a sequence of digits is taken to
be decimal (base ten) unless it begins with 0 (digit zero). A
sequence of digits starting with 0 is taken to be an octal integer
(base eight). The digits 8 and 9 are not octal digits. A sequence
of digits preceded by 0x or 0X is taken to be a hexadecimal integer
(base sixteen). The hexadecimal digits include a or A through f or
F : ::. The type of an integer depends on its :: :suffix. [An
integer may have no suffix.] : ::If [the integer] is suffixed by u
or U, its type is :: :. If it is suffixed by l or L, its type
is :: :. [Either or both suffixes may appear at most once each in
either order.]
Give a regular expression for C++ integer constants. Use only the
operations +, *, and concatenation in your expression (no special
flex notation). You may also use parentheses and ffl (which are not
operations). For convenience, you may name a regular expression R by
writing name= R.
Fall 95 page 2 of 8
CS 164 Programming Languages and Compilers Handout 8
2. Finite Automata and Regular Expressions (15 points)
For each of the following finite automata, give an equivalent regular
expression. Clearly mark your answer to each part. As in the previous
problem, use only the basic regular expression notation.
(a)
(b)
(c)
Fall 95 page 3 of 8
CS 164 Programming Languages and Compilers Handout 8
3. Grammars (20 points)
Give a context-free grammar for each of the following languages.
(a) Any string of x's followed by an equal number of y's.
(b) Any string of x's of length n followed by a string of y's of length
2n+ 1, for any n0.
(c) Any string of x's and y's with an equal number of x's and y's. The x's
and y's may appear in any order.
Fall 95 page 4 of 8
CS 164 Programming Languages and Compilers Handout 8
4. Top-Down Parsing (20 points)
Consider the following grammar for a subset of English sentences. The
nonterminals are S; NP;VP;AP. The terminals are the, noun, adjective,
verb. The start symbol is S.
S ! NP VP
| NP VP NP
NP ! the AP noun
AP ! AP adjective
| ffl
VP ! verb
Give an LL(1) grammar that generates the same language as this grammar.
Show the parsing table for the grammar you produce.
Fall 95 page 5 of 8
CS 164 Programming Languages and Compilers Handout 8
5. LALR Parsing and Conflicts (30 points)
Consider the following DFA of LR(1) items for a LALR(1) parser. The
states are numbered; refer to these numbers where appropriate in the
following questions.
Fall 95 page 6 of 8
CS 164 Programming Languages and Compilers Handout 8
(a) Give the grammar used in constructing the DFA.
(b) Show that the grammar is ambiguous.
(c) Which of the following strings are viable prefixes? For each string
that is a viable prefix, give a suffix that produces a right sentential
form.
i. S
ii. + S +
iii. S + id :=
(d) Which states of the DFA have conflicts and of what kind (shift-reduce
or reduce-reduce)? Be sure to state clearly the cause of the conflict
in each case.
(e) Which conflicts should be resolved in which way to give the := operator
Fall 95 page 7 of 8
CS 164 Programming Languages and Compilers Handout 8
higher precedence than +?
(f) Which conflicts should be resolved in which way to cause the + operator
to associate to the right?
Fall 95 page 8 of 8
CS 164 Programming Languages and Compilers Handout 8
6. Error Recovery (30 points)
This problem uses the same DFA as the previous problem. You will need
to refer to that DFA again to answer the parts of this question. Assume
that any shift/reduce conflicts are resolved in favor of reducing.
(a) Consider the string
id := string string
Show the sequence of configurations of the LALR(1) parsing algorithm as
it parses this string according to the DFA of the previous problem.
Indicate exactly where the error is detected.
(b) Consider a new action panic N t, where N is a non-terminal and t is
a terminal. The meaning of the action is to push N on the stack and
discard all input tokens up to, but not including, the next t. If
there is no next t, then N is pushed on the stack and all remaining
input is discarded. Assume we want the parser to take action panic
S + whenever it is in configuration S+ #w and the first token of w
is erroneous. Which entries in the action table should have panic S
+? (You do not need to give the entire action table to answer the
question; just indicate which entries have the new action.) Show the
sequence of configurations of the parser on input
id+ :=id ++id
(c) Consider a new action insert t where t is a terminal. The meaning
of the action is to insert t before the next input token (i.e., t
becomes the next input). Give insert actions that implement each of
the following local recovery strategies. Be sure to say which entries
in the action table have the insert actions.
i. If the input contains an id followed by a string, insert an :=
between them.
Fall 95 page 9 of 8
CS 164 Programming Languages and Compilers Handout 8
ii. If the input contains two consecutive strings, insert a + between
them.
iii. If the input contains a string followed by an id, insert a + between
them.
Fall 95 page 10 of 8