EECS665 – Compiler Construction

Written work 2

Due on September 11th @ 3:00 PM (in class, to Drew, or at Engineering front office)

Not accepted late

Question 1

Draw out the expression tree representation of the following regular expression

		(ab*|ac)d

Remember to respect the precedence of regex operators.

Question 2

Convert the regular expression from above into an ε-NFA (i.e. an NFA with ε-edges) using Thompson's algorithm.

Question 3

Use the ε-elimination technique to remove the ε-edges from the previous ε-NFA.

Question 4

Let DotList be a language such that:

The empty string is in the language
The single terminal dot is in the language
Sequences of more than 1 dot terminal separated by the comma terminal are in the language. e.g.:
- dot comma dot
- dot comma dot comma dot

No other strings are in the language

Write an unambiguous grammar that recognizes DotList