#lang scheme

;;; This is a simple Scheme module that provides a function to
;;; generate sequences from a context free grammar.  It was adapted
;;; from an example written by Peter Norvig.

(provide generate)

(define grammar 
  '((S -> (NP VP) (NP VP) (NP VP) (NP VP) (NP VP) (S CONJ S))
    (NP -> (ARTICLE ADJS? NOUN PP?))
    (VP -> (VERB NP) (VERB NP) (VERB NP) VERB)
    (ARTICLE -> the the the a a a a a one every)
    (NOUN -> man ball woman table penguin student book dog worm computer robot )
    (PRO -> I you he she it we they)
    (ADJS? -> () () () () (ADJ ADJS?))
    (ADJ -> large blue hungry mysterious)
    (VERB -> hit took saw liked ate chased hated)
    (PREP -> in on under over across by with)
    (CONJ -> and or but because (even though) while from)
    (PP -> (PREP NP))
    (PP? -> () () () () PP)))

(define (generate phrase)
  ;; generate a random sentence or phrase from grammar
  (cond ((list? phrase)
	 (apply append (map generate phrase)))
	((non-terminal? phrase)
	 (generate (random-element (rewrites phrase))))
	(#t (list phrase))))

(define (non-terminal? x)
  ;; True iff x is a on-terminal in grammar
  (assoc x grammar))

(define (rewrites non-terminal)
  ;; Return a list of the possible rewrites for non-terminal in grammar
  (rest (rest (assoc non-terminal grammar))))

(define (random-element list)
  ;; returns a random top-level element from list
  (list-ref list (random (length list))))