Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS3342
1. (25pt) The identifiers in a programming language consist of one or more lower case letters, a, b,..., z, which
must appear in non-decreasing alphabetical order. For example, correct identifiers include: accent, begin, x,
zzz. Examples of incorrect identifiers are: bad, id.
(a) (10pt) Write a regular expression for these identifiers.
(b) (15pt) Draw a deterministic finite automaton that accepts precisely these identifiers.
CS3342 – Midterm Exam – Wednesday, Mar. 1, 3:30 - 5:30pm 5
2. (25pt) Consider the following grammar, G:
0. P ! S$
1. S ! ABC
2. A ! aA
3. A ! "
4. B ! bB
5. B ! bA
6. C ! Cc
7. C ! "
(a) (10pt) Compute first(X), follow(X), for nonterminals X, and predict(p), for productions p, 0 p 7.
(b) (5pt) Explain why G is not LL(1). Include all conflicts G has in your explanation.
(c) (10pt) Modify G to become LL(1). Explain why the new, equivalent, grammar is LL(1). You don’t need to
rebuild the first(), follow(), and predict() tables. Include sucient explanation as to why the conflicts
have been resolved.
CS3342 – Midterm Exam – Wednesday, Mar. 1, 3:30 - 5:30pm 7
3. (25pt) Consider the same grammar, G, from question 2 above, repeated here for convenience:
0. P ! S$
1. S ! ABC
2. A ! aA
3. A ! "
4. B ! bB
5. B ! bA
6. C ! Cc
7. C ! "
(a) (15pt) Draw the LR parser in the form of the graph; the states contain the LR-items, the transitions are
labelled by terminals. Reduce states are double circled. Include also (as jflap does and as shown in class)
the trivial states, those containing a single LR-item with the dot at the end.
(b) (5pt) Is this grammar SLR(1)? Explain your answer.
(c) (5pt) In general, in the definition of an SLR(1) grammar, shift/reduce and reduce/reduce conflict are
forbidden. What about shift/shift conflicts?
CS3342 – Midterm Exam – Wednesday, Mar. 1, 3:30 - 5:30pm 9
4. (25pt) Consider the following grammar, G, for arithmetic expressions in postfix notation:
E ! E E O
E ! const
O ! +
O ! -
O ! *
O ! /
(a) (10pt) Based on G, write an S-attributed grammar that computes the infix version of the postfix expression
represented by the yield of the parse tree.
(b) (10pt) The same problem except that now you have to minimize the number of parentheses.
(c) (5pt) Draw the annotated parse tree for the string 1 2 + 3 4 5 - 6 7 - - * * and the grammar you designed at
(b). Show the attribute flow (arrows and values).
Alternative (c) (3pt) If you built a grammar for (a) but not for (b), then use the grammar you designed at
(a). In this case, for a correct answer, you receive 3pt instead of 5pt. (If you solve the original (c), then
you don’t have to do this.)