5 Regular expressions

“Regular expressions” is a class of formal languages. Each regular expression language must be expressible by a set of productions that satisfy certain constraints:

• the LHS can only be a single nonterminal.
• The RHS can be:
  • an empty string
  • any finite number of terminals
  • any finite number of terminals followed by a nonterminal
  • a nonterminal followed by any number of terminals

At first glance, integers is not a regular expression. However, we can rewrite the I productions as follows:

• I ::= I"0"
• I ::= I"1"
• I ::= I"2"
• I ::= I"3"
• I ::= I"4"
• I ::= I"5"
• I ::= I"6"
• I ::= I"7"
• I ::= I"8"
• I ::= I"9"
• I ::= D