We will develop a program that generates random sentences from a phrase-structure grammar. The most straightforward approach is to represent each grammar rule by a separate Lisp function:
> (sentence) => (1 ENTER SENTENCE) (1 ENTER NOUN-PHRASE) (1 ENTER ARTICLE) (1 EXIT ARTICLE: (THE)) (1 ENTER NOUN) (1 EXIT NOUN: (MAN)) (1 EXIT NOUN-PHRASE: (THE MAN)) (1 ENTER VERB-PHRASE) (1 ENTER VERB) (1 EXIT VERB: (HIT)) (1 ENTER NOUN-PHRASE) (1 ENTER ARTICLE) (1 EXIT ARTICLE: (THE)) (1 ENTER NOUN) (1 EXIT NOUN: (BALL)) (1 EXIT NOUN-PHRASE: (THE BALL)) (1 EXIT VERB-PHRASE: (HIT THE BALL)) (1 EXIT SENTENCE: (THE MAN HIT THE BALL)) (THE MAN HIT THE BALL)
The program works fine, and the trace looks just like the sample derivation above, but the Lisp definitions are a bit harder to read than the original grammar rules. This problem will be compounded as we consider more complex rules. Suppose we wanted to allow noun phrases to be modified by an indefinite number of adjectives and an indefinite number of prepositional phrases. In grammatical notation, we might have the following rules:
(defun Adj* () (if (= (random2) 0) nil (append (Adj) (Adj*)))) (defun PP* () (if (random-elt '(t nil)) (append (PP) (PP*)) nil)) (defun noun-phrase () (append (Article) (Adj*) (Noun) (PP*))) (defun PP () (append (Prep) (noun-phrase))) (defun Adj () (one-of '(big little blue green adiabatic))) (defun Prep () (one-of '(to in by with on)))
I’ve chosen two different implementations for Adj* and PP*; either approach would work in either function. We have to be careful, though; here are two approaches that would not work:
An alternative implementation of this program would concentrate on making it easy to write grammar rules and would worry later about how they will be processed. Let’s look again at the original grammar rules: