;;; 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) grammar)
          (singleton [[symbol (first expression)] (rest expression)])
          (collect (lambda [rhs]
                      (parse-frontier symbol expression rhs grammar))
                   (rhsides symbol grammar)))))

(define PARSE-FRONTIER
   (lambda [symbol expression frontier grammar]
      (cond [(null frontier) (singleton [symbol expression])]
            [(null expression) (nothing)]
            [$t (map (lambda [parse]
                        [[symbol (first parse)] (second parse)])
                     (collect (lambda [fragment]
                                 (parse-frontier (first fragment)
                                                 (second fragment)
                                                 (rest frontier)
                                                 grammar))
                              (parse-symbol expression
                                            (first frontier)
                                            grammar)))])))

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