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_phrase unfinished_list finished_list grammar)The generator is very simple.
(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)) #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.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 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.