Introduction to Compilers

CIS 461/561 Homework/Discussion Questions

Lexical Analysis, DFAs, NFAs, Regular Expressions

1. Appel exercise 2.3

2. Appel exercise 2.5

3. The basic definition of regular expressions only uses union, concatenation, and Kleene star. Many tools, including scanner generators like JFlex, extend the notation with notation like:
   • r? to mean zero or more occurrences of r
   • r{m,n} to mean m to n occurrences of r
   Show that any regular expression containing either of these operators has an equivalent regular expression without the operators.

4. The original C Programming Language book gives the following definition of a floating constant:

   "A floating constant consists of an integer part, a decimal point, a fraction part, an e or E, and an optionally signed integer exponent. Either the integer part or the fraction part (not both) may be missing; either the decimal point or the e and the exponent (not both) may be missing."

   Can you diagram a DFA to recognize a floating point constant? Can you specify a regular expression to recognize a floating point constant?