; This file defines functions that can generate random elements of
; languages defined by BNF grammars.  Two examples, english_grammar
; and math_grammar, are defined as examples.  A grammar must be given
; as a list in the following form:  Each element of the list is a
; pair in which the first element is a non-terminal symbol of the 
; grammar and the second element is the definition of that symbol.
; The special symbols  *number*,  optional,  loop,  and  or  are
; reserved and cannot be used as the names of non-terminals.
; The definition of a non-terminal can have the following forms:
;
;      1. nil, representing an empty list of terminal symbols.
;      2. A string, enclosed in quotes, representing a terminal
;           symbol of the grammar.
;      3. The special symbol *number*, representing a small
;            non-negative integer.
;      4. An atom, which must be a non-terminal symbol of the grammar.
;      5. A list containing a sequence of arbitrary items of type
;            1 through 8, as given here.  A list of terminals is generated for
;            each element of the list, and the results are concatenated.
;      6. A list in which the first item is the atom  or  and the
;           remaining items are arbitrary items of types 1 through 8.
;           One of the items in (cdr item) is chosen at random and used 
;           to generate a list of terminals.
;      7. A list in which the first item is the atom  optional  and the
;           remaining items are arbitrary items of types 1 through 8.
;           This will, at random, either generate the empty list or
;           will generate a list of terminals corresponding to (cdr item).
;           (Note that the probability of a non-empty result should be
;           fairly small, such as 1 in 4, or random generation procedure
;           might generate a huge or even infinite result.)
;      8. A list in which the first item is the atom  loop  and the
;           remaining items are arbitrary items of types 1 through 8.
;           The list (cdr item) is used zero or more times and the
;           results are concatenated together.  (Note that the probability
;           that the number of repetitions is greater than zero should
;           be rather small, such as 1 in 4.)


; Define a grammar for a subset of English.
(setf english_grammar
  '(
      (sentence (simple_sentence (loop conjunction simple_sentence)))
      (simple_sentence (noun_phrase verb_phrase))
      (noun_phrase (or proper_noun common_noun_phrase))
      (common_noun_phrase 
           (determiner (loop adjective) common_noun 
               (optional "who" verb_phrase)))
      (verb_phrase (or intransitive_verb 
                       (transitive_verb noun_phrase)
                       (mental_state_verb "that" simple_sentence)))
      (conjunction (or "and" "or" "but"))
      (determiner (or "the" "a" "every" "some"))
      (proper_noun (or "John" "Mary" "Chris" "Pat" "Fred" "Jill" "Elvis"
                      "Richard Nixon" "Miss America" "The President"))
      (common_noun (or "fish" "dog" "cat" "unicorn"
                         "man" "woman" "rock" "toaster"))
      (intransitive_verb (or "runs" "jumps" "talks" "walks" "thinks" "is bald"
                          "plays" "dies" "lives"))
      (transitive_verb (or "knows" "loves" "hates" "remembers" "sees" "steals"
              "understands" "is kind to" "thinks about" "looks for" "finds"))
      (mental_state_verb (or "knows" "believes" "understands"
                                "sees" "thinks" "hopes"))
  ))


; Define a grammar for a set of mathematical expressions.
(setf math_grammar
  '(
      (expression ((optional "-") term (loop (or "+" "-") term)))
      (term (factor (loop (or "*" "/") factor)))
      (factor (primary (loop "^" primary)))
      (primary (or *number* variable ((optional function) "(" expression ")")))
      (variable (or "w" "x" "y" "z" "i" "j" "k" "n" "r" "s" "t"))
      (function (or "sin" "cos" "tan" "log" "exp" "sqrt" "abs"))
  ))


; Convenience methods for generating an printing random elements of
;    the languages defined by english_grammar and math_grammar.
(defun sentence () (write_list (expand 'sentence english_grammar)))
(defun math () (write_list (expand 'expression math_grammar)))


; Output routine for printing a list of items with spaces between the
;    items, and leaving off the parentheses around the list and the
;    quotes around strings.  (princ prints strings without the quotes.)
(defun write_list (lst)
   (terpri)
   (princ "     ")
   (dolist (item lst)
       (princ item)
       (princ " "))
   (terpri)
   (terpri)
 )


; If the value of grammar is a list that describes a grammar as described
;    above, and if the value of symb is one of the non-terminal symbols
;    in that grammar, then (get_def symb grammar) returns the definition
;    associated with that non-terminal in the grammar.  (If symb is
;    not found, then the return value is nil.)
(defun get_def (symb grammar)

     ***** Can be done in 4 lines *****
  

; If the value of grammar is a list that describes a grammar as described
;    above, and if the value of symb is one of the non-terminal symbols
;    in that grammar, then expand produces a random element of the
;    language defined by that non-terminal according to the grammar.
;    (This is just a one-liner using expand_item and get_def.)
(defun expand (symb grammar)

     ***** Can be done in 1 line ******


; If the value of grammar is a list that describes a grammar as described
;    above, and if the value of item is the sort of thing that could occur
;    as the definition of a non-terminal symbol in the grammar, then
;    expand_item produces a random element of the language defined
;    by item.  The value is always returned as a list, even if there
;    is only one item in the list.  The returned list can be empty in
;    the cases where item is nil or where it is a list beginning with 
;    one of the words loop or optional.
(defun expand_item (item grammar)
 
     ***** Can be done in 20 lines *****