;;; Code stored as:  {turing}<3-lisp.problem-sets>general-parser.3-lisp
;;;                  {phylum}<3-lisp>course>problem-sets>general-parser.3-lisp


;;; =======================================================================
;;; 
;;;         RECURSIVE DESCENT PARSER
;;;
;;; =======================================================================

;;; Similar to Recognizer, but returns the parse:
;;; 
;;; Basic idea is to have all the parsing routines return a sequence of
;;; parse/word-sequence pairs, where the parse is the parse so far and
;;; the word-sequence is the postfix of the input sequence after the part
;;; that has been parsed so far. 

(define PARSE
   (lambda [expression start-symbol grammar]
      (let [[good-parses
               (filtered-map first
                             (compose null second)
                             (parse-symbol (lexical-analysis expression)
                                           start-symbol
                                           grammar))]]
         (if (null good-parses)
             "rejected"
             good-parses))))

(define PARSE-SYMBOL
   (lambda [expression symbol grammar]
      (if (match symbol (first expression))
          (singleton [[symbol (first expression)] (rest expression)])
          (collect (lambda [rhs]
                      (parse-frontier symbol expression rhs grammar))
                   (rhsides symbol grammar)))))

;;; Other routines are as in GENERAL-RECOGNIZER.