Assignment 1 LISP problem solution

You can see the solution to undergrad LISP problem here. Note that this is not a "model writeup", you would have to provide better testing data with more complex grammar, as well as timing data and your conclusions.

There are 2 main functions in the program. In order to generate a sentence you have to call

  (generate top_category grammar)
  
Top_category is any nonterminal in the grammar which you want to generate, so our generation won't be restricted to sentences only. Grammar is represented as a hash table, with category names serving as keys, each entry holding the list of possible expansions for that category. It can be generated from lisp representation by another function,
  (make-grammar list)
  
The argument is the list of grammar rules. Each is the list which has the rule LHS as the first element, and the rest of the elements represent the RHS.

The generate function is just a wrapper to the real generator function,

  (generate_phrase unfinished_list finished_list grammar)
  
The generator is very simple. Unfinished_list represents the part of the phrase being generated that can be expanded, and finished_list holds the string of terminals generated so far. At each step we take the first item off the unfinished_list. If this is a non-terminal, we just move it to the finished_list. Otherwise we get the list of possible RHS expansions and use LISP random generator to pick one of them, then push the selected expansion back on the unfinished_list. The process continues until the unfinished_list is empty, in which case finished_list holds the generated string. Here are the 2 possible grammars
  (setf gr1 '((S NP VP) ;; S  => NP VP
              (NP N)    ;; NP => N
              (VP V)    ;; VP => V
              (VP V NP) ;; VP => V NP
  	    (N Jack) (N Sue) (V likes) (V smiles)))
  
  (setf gr2 '((S NP VP)      ;; S  => NP VP
              (NP NP and NP) ;; NP => NP and NP (*)
              (NP N)         ;; NP => N         (**)
              (VP V NP)      ;; VP => V NP
  	    (N Jack) (N Sue) (N John) (V likes)))
  
Here are the result of test runs on the first grammar. I'm using a wrapper functions that loops the given number of times calling generate.
  USER(28): (setf g1 (make-grammar gr1))
  #
  USER(29): (GENERATE-SENTENCES G1 10)
  
  (JACK LIKES) 
  (SUE LIKES) 
  (JACK SMILES) 
  (SUE LIKES JACK) 
  (SUE SMILES SUE) 
  (SUE LIKES SUE) 
  (JACK LIKES JACK) 
  (JACK LIKES JACK) 
  (JACK LIKES JACK) 
  (JACK LIKES) 
  
As it turns out, the second grammar looks simple, but it is rather dangerous. Since the generator has no built-in sentence length restrictions, and every rule can be selected with equal probability, it turns out that once it first selected NP conjunction rule (*) to expand NP, with high probability (around 3/4) it will select the same rule again to expand one of its sides. The process cannot go on forever, because there is a probability that it will select to expand both sides as nouns rather then NP conjunctions, but quite a few times I got stack overflow before it happened.

As you can easily see most of the sentences are incoherent. One would require more complex mechanisms to handle agreement, and even more complex ones to provide semantically coherent sentences.