-CS3342

CS3342 – Midterm Exam – Wednesday, Mar. 1, 3:30 - 5:30pm 3

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

2. (25pt) Consider the following grammar, G:

5

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 su?cient 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 ?! EEO 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 12+345-67--** 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.)