Hatena::Groupcadr

bulbのLisp日記 RSSフィード

2008-01-06

[][]A Rule-Based Solution 20:36 A Rule-Based Solution - bulbのLisp日記 を含むブックマーク はてなブックマーク - A Rule-Based Solution - bulbのLisp日記

Sentence => Noun-Phrase+Verb-Phrase

Noun-Phrase=>Article+Noun

Verb-Phrase => Verb+Noun-Phrase

Article => the, a, ...

Noun => man, ball, woman, table ...

Verb => hit, took, saw, liked ...

上記をLispで表現すると、

(defparameter *simple-grammar*
  '((sentence -> (noun-phrase verb-phrase))
    (noun-phrase -> (Article Noun))
    (verb-phrase -> (Verb noun-phrase))
    (Article -> the a)
    (Noun -> man ball woman table)
    (Verb -> hit took saw liked))
  "A grammar for a trivial subset of English.")

(defvar *grammar* *simple-grammar*
  "The grammar used by generate.  Initially, this is
*simple-grammar*, but we can switch to other grammars.")

CL-USER> (assoc 'noun *grammar*)
(NOUN -> MAN BALL WOMAN TABLE)


(defun rule-lhs (rule)
  "The left-hand side of a rule."
  (first rule))
(defun rule-rhs (rule)
  "The right-hand side of a rule."
  (rest (rest rule)))
(defun rewrites (category)
  "Return a list of the possible rewrites for this category."
  (rule-rhs (assoc category *grammar*)))
(defun generate (phrase)
  "Generate a random sentence or phrase"
  (cond ((listp phrase)
	 (mappend #'generate phrase))
	((rewrites phrase)
	 (generate (random-elt (rewrites phrase))))
	(t
	 (list phrase))))
CL-USER> (generate 'sentence)
(THE MAN TOOK A WOMAN)
CL-USER> (generate 'sentence)
(THE MAN SAW THE MAN)