Homework #1

1. (5 points) Give a regular expression which generates only the set of all strings of letters which contain the five vowels in order. Use only lower case letters. For example, your regular expression must be capable of generating the strings aeiou, ateitou, and zaeztiouzpq, but not aeou, aaeiou, and aeitgaou.
   
   You may use only the ., *, [ ], ^ wildcards, with the following meanings, in your regular expression.

   . (any single character)
   * (0 or more of previous character)
   [a-z] (one of the characters in this range)
   [abcd] (any one character from this set)
   [^a-z] (any character other than one in this range)
   [^abcd] (any character other than one from this set)
   

   examples:
   • [a-zA-Z] matches any one alphabetic character
   • [0-9a-zA-Z] matches any one alphanumeric character
   • [^xyz] matches any character other than x, y, and z
   • [1-9][0-9]* matches any integer
   
   
2. (5 points) Give a context-free grammar for the language of the previous problem.
   
   
3. (10 points) The following grammar for if-then-else is proposed to remedy the dangling else ambiguity:

           <stmt> ::= if <expr> then <stmt> | <matched_stmt>
   <matched_stmt> ::= if <expr> then <matched_stmt> else <stmt> | <other>
   

   where the non-terminal <other> generates some non-if statement such as a print statement.
   
   Prove that this grammar is still ambiguous.
   
   
4. (15 points) Consider the following EBNF grammar:

   <expr> -> (<list>) | a
   <list> -> <expr> [<list>]
   

   Write a program (in any language) which accepts strings from standard input (one per line) unitl EOF and determines whether each string is in the langauge defined by this grammar. Print only one line of output per line of input as follows:

   "( a )" is a sentence.
   "a" is a sentence.
   "( a ) )" is not a sentence.
   "( ( a ) )" is a sentence.
   "( ( ( a ) ) )" is a sentence.
   "( ( ( a a ) ) )" is a sentence.
   "( a ( a ) )" is a sentence.
   "( )" is not a sentence.
   "(" is not a sentence.
   "( a ( a ) ) )" is not a sentence.
   

   You may assume that all lexemes will be valid and separated by exactly one space, and that each line will contain no leading or trailing whitespace.
   
   Limit your program to approximately 100 lines, e-mail it to the TA by the deadline, and submit a listing of it in class.
   
   
5. (10 points) The following grammar generates declarations for a single identifier:

          <stmt> ::= declare <id> <option_list>
            <id> ::= any string beginning with an alphabetic character other than
                     "declare", "real", "complex", "scale", "fixed",
                     "floating", "single", "double", "binary", and "decimal"
   <option_list> ::= <option> | <option_list> <option>
        <option> ::= <mode> | <scale> | <precision> | <base>
          <mode> ::= real | complex
         <scale> ::= fixed | floating
     <precision> ::= single | double
          <base> ::= binary | decimal
   

   As you can see, this grammar permits redundant or contradictory declarations such as:

   declare zippy real fixed real floating
   

   Revise the grammar so that it forbids such obviously incorrect declarations. Write a grammar for legal declarations, where legal means each option appearing at most once (so there can be at most one mode, one scale, one precision, and one base). The options can still can appear in any order. For example, the following are legal declarations:

   declare zippy floating double
   declare zippy double floating
   

   It is also legal to not have anything specified for one or more (or all) of the options. For instance, just

   declare zippy
   

   is legal.
   
   
6. (5 points) [EOPL] Exercise 1.2 on p. 7. Give the derivation of the expression (#t (foo . ()) 3).
   
   
7. (5 points) [EOPL] Exercise 1.3 on p. 7. Use the grammar on p. 6.