Homework #1

Assigned: January 13
Due: January 20, 4:30pm, in class


  1. (5 points) Give a regular grammar defines a langauge whose sentences are all strings of lower case letters which contain the five vowels in order. For example, your regular grammar must be capable of generating the strings aeiou, ateitou, and zaeztiouzpq, but not aeou, aaeiou, and aeitgaou.

    You may use only the ., *, [ ], ^ symbols, with the following meanings, in your regular grammar.
    . (any single character)
    + (or)
    * (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)
    

    Understand that ., [] (brackets), and ^ are not part of the language of regular grammars, and are provided simply as syntactic sugar to simplify the definition of a regular grammar.

    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> ::= <term> * <term>
              <expr> ::= <term> - <term>
              <expr> ::= <term>
              <term> ::= <factor> / <factor>
              <term> ::= <factor> + <factor>
              <term> ::= <factor>
            <factor> ::= <identifier> | <number> | ( <expr> )
        <identifier> ::= <alpha> <alphanumrest> | <alpha>
             <alpha> ::= a | b | ... | z | A | B | ... | Z | _
      <alphanumrest> ::= <alphanum> <alphanumrest> | <alphanum>
          <alphanum> ::= <alpha> | <digit>
            <number> ::= <non-zero digit> <rest> | <non-zero digit>
              <rest> ::= <digit> <rest> | <digit>
    <non-zero digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
             <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    
    Notice that lexemes (or terminals) are never longer than one character in this language.

    Build a recursive descent parser 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 to standard output per line of input as follows:

    "( 6 )" is a sentence.
    "a" is a sentence.
    "( i) )" is not a sentence.
    ",a - 1" contains invalid lexemes and, thus, is not a sentence.
    "( ( a ) )" is a sentence.
    "id * index - rate * 1001 - (r - 32) * key" is not a sentence.
    "( ( ( a ) ) )" is a sentence.
    ";10 - 10" contains invalid lexemes and, thus, is not a sentence.
    "01 - 10" is not a sentence.
    "a * b - c" is not a sentence.
    "( ( ( a a ) ) )" is a sentence.
    "( a ( a ) )" is not a sentence.
    "2 * 3" is a sentence.
    "( )" is not a sentence.
    "2 * rate - (((3)))" is not a sentence.
    "(" is not a sentence.
    "( f ( t ) ) )" is not a sentence.
    "f!a+u" contains invalid lexemes and, thus, is not a sentence.
    "a*" is not a sentence.
    "_aaa+1" is a sentence.
    "____aa+y" is a sentence.
    
    Factor your program into a scanner (lexical analyzer) and parser (syntactic analyzer). You may assume that whitespace is ignored, and that no line of input will exceed 4,096 characters.

    Try to keep your program as short as possible (approximately 200 lines of code).

  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.


Return Home