; The following grammar defines a simple language:
; 
; S --> the N V the N
; 
; N --> hawk  |  dove  |  J N
; 
; J --> red  |  gray  |  rapid  |  slow  |  hungry  |  plump
; 
; V --> ate  |  fed
; 
; The sentences of this language include
; 
;     the dove ate the hawk
;     the rapid gray plump hawk fed the slow hungry dove
; 
; There are infinitely many sentences in this language, e.g.
; 
;     the dove ate the hawk
;     the rapid gray plump hawk fed the slow hungry dove
; 
;     the dove ate the hawk
;     the dove ate the red hawk
;     the dove ate the red red hawk
;     the dove ate the red red red hawk
;     the dove ate the red red red red hawk
;     the dove ate the red red red red red hawk
;     ...

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; Given a list of symbols, returns true if and only if
; the symbols form a sentence in the language that is
; generated by the grammar above.

(define (isSentence? words)
  (and (startsWith? 'the words)
       (let ((words (parse-N (cdr words))))
         (and words
              (let ((words (parse-V words)))
                (and words
                     (startsWith? 'the words)
                     (let ((words (parse-N (cdr words))))
                       (null? words))))))))

; Given a symbol and a list of symbols, returns #f unless the
; given symbol is the first element of the list of symbols, in
; which case it returns the list of symbols without its first
; element.

(define (startsWith? word0 words)
  (if (and (not (null? words))
           (eq? word0 (car words)))
      (cdr words)
      #f))

; Given a list of symbols, divides the list into a sequence of
; symbols generated by the nonterminal V, followed by leftover
; symbols.  If the list begins with a sequence generated by the
; nonterminal V, then the list of leftover symbols is returned.
; Otherwise #f is returned.

(define (parse-V words)
  (or (startsWith? 'ate words)
      (startsWith? 'fed words)))

; Given a list of symbols, divides the list into a sequence of
; symbols generated by the nonterminal N, followed by leftover
; symbols.  If the list begins with a sequence generated by the
; nonterminal N, then the list of leftover symbols is returned.
; Otherwise #f is returned.

(define (parse-N words)
  (or (startsWith? 'hawk words)
      (startsWith? 'dove words)
      (and (startsWith? 'red words)
           (parse-N (startsWith? 'red words)))
      (and (startsWith? 'gray words)
           (parse-N (startsWith? 'gray words)))
      (and (startsWith? 'rapid words)
           (parse-N (startsWith? 'rapid words)))
      (and (startsWith? 'slow words)
           (parse-N (startsWith? 'slow words)))
      (and (startsWith? 'hungry words)
           (parse-N (startsWith? 'hungry words)))
      (and (startsWith? 'plump words)
           (parse-N (startsWith? 'plump words)))))