;; ;; Takes a list representign a grammar as an argument ;; returns a hash table with the grammar ;; The list is of the form ((VP V) (VP V NP) (V (worked)) ...) ;; Putting terminals in parens is the easiest way to distinguish them in the future ;; The resulting table is indexed by constitent name, each entry is a possible list of RHS's (defun make-grammar (l) (let ((res (make-hash-table))) (mapcar (lambda (x) (add-entry (car x) (cdr x) res)) l) res )) ;; ;; Adds current entry to the new grammar entry ;; (defun add-entry (lhs rhs table) (setf (gethash lhs table) (cons rhs (gethash lhs table))) ) ;; ;; A wrapper functions that calls phrase generation ;; (defun generate (top grammar) (generate-phrase (list top) nil grammar)) ;; ;; performs actual generation ;; rest is yet unexpanded material ;; finished is already generated part (defun generate-phrase (rest finished grammar) (let ((lhs (pop rest))) (if (null lhs) (reverse finished) ;; completed expansion is in reverse order (let ((rhs-list (gethash lhs grammar))) (if (null rhs-list) ;; the symbol encountered is a terminal (generate-phrase rest (cons lhs finished) grammar) (generate-phrase (random-rhs rhs-list rest) finished grammar)) )) )) ;; expands a current entry by randomly selecting a production ;; and prepending it to the rest of the current analysis (defun random-rhs (rhs-list rest) ;; We generate a random number n between 0 and (number_of_rhs's - 1) ;; then we pick the nth rhs from the list and prepend it to the string being generated (let ((n (random (length rhs-list)))) ;; (print rhs-list) (prin1 n) (append (nth n rhs-list) rest) )) (defun generate-sentences (grammar n) (dotimes (i n) (print (generate 'S grammar))))