about summary refs log tree commit diff
path: root/third_party/lisp/npg/src
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/lisp/npg/src')
-rw-r--r--third_party/lisp/npg/src/define.lisp366
-rw-r--r--third_party/lisp/npg/src/parser.lisp238
2 files changed, 302 insertions, 302 deletions
diff --git a/third_party/lisp/npg/src/define.lisp b/third_party/lisp/npg/src/define.lisp
index f52f0381a2de..783f071fc5d9 100644
--- a/third_party/lisp/npg/src/define.lisp
+++ b/third_party/lisp/npg/src/define.lisp
@@ -37,13 +37,13 @@ those that are not declared as strings in the grammar.")
 the list of variables for the function reducing this production, those
 that are non static and their unambiguous user-friendly names."
   (flet ((unique (sym list)
-	   (if (not (assoc sym list))
-	       sym
-	       (loop
-		  for i of-type fixnum from 2
-		  for x = (intern (format nil "~:@(~A~)~A" sym i))
-		  while (assoc x list)
-		  finally (return x)))))
+           (if (not (assoc sym list))
+               sym
+               (loop
+                  for i of-type fixnum from 2
+                  for x = (intern (format nil "~:@(~A~)~A" sym i))
+                  while (assoc x list)
+                  finally (return x)))))
     (loop
        for tok in tokens
        for i of-type fixnum from 1
@@ -54,8 +54,8 @@ that are non static and their unambiguous user-friendly names."
          and when (symbolp tok)
            collect (list (unique tok named-vars) arg) into named-vars
        when (and (listp tok)
-		 (symbolp (cadr tok)))
-	 collect (list (unique (cadr tok) named-vars) arg) into named-vars
+                 (symbolp (cadr tok)))
+         collect (list (unique (cadr tok) named-vars) arg) into named-vars
        finally
        (return (values args vars named-vars)))))
 
@@ -63,56 +63,56 @@ that are non static and their unambiguous user-friendly names."
   "Create a function with name NAME, arguments derived from TOKENS and
 body ACTION.  Return it's definition."
   (let ((function
-	 (multiple-value-bind (args vars named-vars)
-	     (make-action-arguments tokens)
-	   `(lambda ,args
-	      (declare (ignorable ,@args))
-	      (let (($vars (list ,@vars))
-		    ($all (list ,@args))
-		    ,@named-vars
-		    ($alist (list ,@(mapcar #'(lambda (v)
-						`(cons ',(intern (symbol-name (car v)))
-						       ,(cadr v)))
-					    named-vars))))
-		(declare (ignorable $vars $all $alist ,@(mapcar #'car named-vars)))
-		(flet ((make-object (&optional type args)
-			 (apply #'make-instance (or type ',name)
-				(append args $alist))))
-		  ,action))))))
+         (multiple-value-bind (args vars named-vars)
+             (make-action-arguments tokens)
+           `(lambda ,args
+              (declare (ignorable ,@args))
+              (let (($vars (list ,@vars))
+                    ($all (list ,@args))
+                    ,@named-vars
+                    ($alist (list ,@(mapcar #'(lambda (v)
+                                                `(cons ',(intern (symbol-name (car v)))
+                                                       ,(cadr v)))
+                                            named-vars))))
+                (declare (ignorable $vars $all $alist ,@(mapcar #'car named-vars)))
+                (flet ((make-object (&optional type args)
+                         (apply #'make-instance (or type ',name)
+                                (append args $alist))))
+                  ,action))))))
     (when *compile-print*
       (if *compile-verbose*
-	  (format t "; Compiling ~S:~%  ~S~%" name function)
-	  (format t "; Compiling ~S~%" name)))
+          (format t "; Compiling ~S:~%  ~S~%" name function)
+          (format t "; Compiling ~S~%" name)))
     (compile name function)))
 
 (defun define-rule (name productions)
   "Accept a rule in EBNF-like syntax, translate it into a sexp and a
 call to INSERT-RULE-IN-CURRENT-GRAMMAR."
   (flet ((transform (productions)
-	   (loop
-	      for tok in productions
-	      with prod = nil
-	      with action = nil
-	      with phase = nil
-	      with new-prods = nil
-	      while tok
-	      do (cond ((eq tok :=)
-			(push (list (nreverse prod) action) new-prods)
-			(setf prod nil
-			      action nil
-			      phase :prod))
-		       ((eq tok :reduce)
-			(setf phase :action))
-		       ((eq tok :tag)
-			(setf phase :tag))
-		       ((eq phase :tag)
-			(setf action `(cons ,tok $vars)))
-		       ((eq phase :action)
-			(setf action tok))
-		       ((eq phase :prod)
-			(push tok prod)))
-	      finally
-		(return (cdr (nreverse (cons (list (nreverse prod) action) new-prods)))))))
+           (loop
+              for tok in productions
+              with prod = nil
+              with action = nil
+              with phase = nil
+              with new-prods = nil
+              while tok
+              do (cond ((eq tok :=)
+                        (push (list (nreverse prod) action) new-prods)
+                        (setf prod nil
+                              action nil
+                              phase :prod))
+                       ((eq tok :reduce)
+                        (setf phase :action))
+                       ((eq tok :tag)
+                        (setf phase :tag))
+                       ((eq phase :tag)
+                        (setf action `(cons ,tok $vars)))
+                       ((eq phase :action)
+                        (setf action tok))
+                       ((eq phase :prod)
+                        (push tok prod)))
+              finally
+                (return (cdr (nreverse (cons (list (nreverse prod) action) new-prods)))))))
     (insert-rule-in-current-grammar name (transform productions))))
 
 (defmacro defrule (name &rest productions)
@@ -124,9 +124,9 @@ call to INSERT-RULE-IN-CURRENT-GRAMMAR."
 return it."
   (insert-rule-in-current-grammar
    (gensym (concatenate 'string "OPT-"
-			(if (rule-p token)
-			    (symbol-name (rule-name token))
-			    (string-upcase token))))
+                        (if (rule-p token)
+                            (symbol-name (rule-name token))
+                            (string-upcase token))))
    `(((,token)) (()))))
 
 (defun make-alternative-rule (tokens)
@@ -134,24 +134,24 @@ return it."
   (insert-rule-in-current-grammar
    (gensym "ALT")
    (mapcar #'(lambda (alternative)
-	       `((,alternative)))
-	   tokens)))
+               `((,alternative)))
+           tokens)))
 
 (defun make-nonempty-list-rule (token &optional separator)
   "Make a rule for a non-empty list (+ syntax) and return it."
   (let ((rule-name (gensym (concatenate 'string "NELST-"
-					(if (rule-p token)
-					    (symbol-name (rule-name token))
-					    (string-upcase token))))))
+                                        (if (rule-p token)
+                                            (symbol-name (rule-name token))
+                                            (string-upcase token))))))
     (insert-rule-in-current-grammar
      rule-name
      (if separator
-	 `(((,token ,separator ,rule-name)
-	    (cons $1 $3))
-	   ((,token) ,#'list))
-	 `(((,token ,rule-name)
-	    (cons $1 $2))
-	   ((,token) ,#'list))))))
+         `(((,token ,separator ,rule-name)
+            (cons $1 $3))
+           ((,token) ,#'list))
+         `(((,token ,rule-name)
+            (cons $1 $2))
+           ((,token) ,#'list))))))
 
 (defun make-list-rule (token &optional separator)
   "Make a rule for a possibly empty list (* syntax) return it."
@@ -166,14 +166,14 @@ return it."
 or (* NAME) or (+ NAME).  This is used by the DEFRULE macro."
   (if (symbolp tok)
       (let* ((name (symbol-name tok))
-	     (last (char name (1- (length name))))
-	     ;; this looks silly but we need to make sure that we
-	     ;; return symbols interned in this package, no one else
-	     (op (cadr (assoc last '((#\? ?) (#\+ +) (#\* *))))))
-	(if (and (> (length name) 1) op)
-	    (list op
-		  (intern (subseq name 0 (1- (length name)))))
-	    tok))
+             (last (char name (1- (length name))))
+             ;; this looks silly but we need to make sure that we
+             ;; return symbols interned in this package, no one else
+             (op (cadr (assoc last '((#\? ?) (#\+ +) (#\* *))))))
+        (if (and (> (length name) 1) op)
+            (list op
+                  (intern (subseq name 0 (1- (length name)))))
+            tok))
       tok))
 
 (defun EBNF-to-SEBNF (tokens)
@@ -184,10 +184,10 @@ EBNF syntax into a sexp-based EBNF syntax or SEBNF."
      for token = (expand-production-token tok)
      with new-tokens = '()
      do (cond ((member token '(* + ?))
-	       (setf (car new-tokens)
-		     (list token (car new-tokens))))
-	      (t
-	       (push token new-tokens)))
+               (setf (car new-tokens)
+                     (list token (car new-tokens))))
+              (t
+               (push token new-tokens)))
      finally (return (nreverse new-tokens))))
 
 (defun SEBNF-to-BNF (tokens)
@@ -195,21 +195,21 @@ EBNF syntax into a sexp-based EBNF syntax or SEBNF."
 it into BNF.  The production is simplified but the current grammar is
 populated with additional rules."
   (flet ((make-complex-token-rule (tok)
-	   (ecase (car tok)
-	     (* (apply #'make-list-rule (cdr tok)))
-	     (+ (apply #'make-nonempty-list-rule (cdr tok)))
-	     (? (make-optional-rule (cadr tok)))
-	     (or (make-alternative-rule (cdr tok))))))
+           (ecase (car tok)
+             (* (apply #'make-list-rule (cdr tok)))
+             (+ (apply #'make-nonempty-list-rule (cdr tok)))
+             (? (make-optional-rule (cadr tok)))
+             (or (make-alternative-rule (cdr tok))))))
     (loop
        for token in tokens
        with new-tokens = '()
        with keywords = '()
        do (cond ((listp token)
-		 (push (make-complex-token-rule token) new-tokens))
-		(t
-		 (push token new-tokens)
-		 (when (const-terminal-p token)
-		   (push token keywords))))
+                 (push (make-complex-token-rule token) new-tokens))
+                (t
+                 (push token new-tokens)
+                 (when (const-terminal-p token)
+                   (push token keywords))))
        finally (return (values (nreverse new-tokens) keywords)))))
 
 (defun make-default-action-function (name tokens)
@@ -220,28 +220,28 @@ list and in case only a variable token is available that one is
 returned (not included in a list).  If all the tokens are
 constant, then all of them are returned in a list."
   (cond ((null tokens)
-	 ;; if the production matched the empty list (no tokens) we
-	 ;; return always nil, that is the function LIST applied to no
-	 ;; arguments
-	 #'list)
-	((null (cdr tokens))
-	 ;; if the production matches just one token we simply return
-	 ;; that
-	 #'identity)
-	(*smart-default-reduction*
-	 ;; If we are required to be "smart" then create a function
-	 ;; that simply returns the non static tokens of the
-	 ;; production.  If the production doesn't have nonterminal,
-	 ;; then return all the tokens.  If the production has only
-	 ;; one argument then return that one only.
-	 (make-action-function name tokens '(cond
-					     ((null $vars) $all)
-					     ((null (cdr $vars)) (car $vars))
-					     (t $vars))))
-	(t
-	 ;; in all the other cases we return all the token matching
-	 ;; the production
-	 #'list)))
+         ;; if the production matched the empty list (no tokens) we
+         ;; return always nil, that is the function LIST applied to no
+         ;; arguments
+         #'list)
+        ((null (cdr tokens))
+         ;; if the production matches just one token we simply return
+         ;; that
+         #'identity)
+        (*smart-default-reduction*
+         ;; If we are required to be "smart" then create a function
+         ;; that simply returns the non static tokens of the
+         ;; production.  If the production doesn't have nonterminal,
+         ;; then return all the tokens.  If the production has only
+         ;; one argument then return that one only.
+         (make-action-function name tokens '(cond
+                                             ((null $vars) $all)
+                                             ((null (cdr $vars)) (car $vars))
+                                             (t $vars))))
+        (t
+         ;; in all the other cases we return all the token matching
+         ;; the production
+         #'list)))
 
 (defun make-production-from-descr (name production-description)
   "Take a production NAME and its description in the form of a sexp
@@ -250,28 +250,28 @@ keywords."
   (destructuring-bind (tokens &optional action) production-description
     (let ((expanded-tokens (EBNF-to-SEBNF tokens)))
       (multiple-value-bind (production-tokens keywords)
-	  (sebnf-to-bnf expanded-tokens)
+          (sebnf-to-bnf expanded-tokens)
       (let ((funct
-	     (cond ((not action)
-		    (make-default-action-function name expanded-tokens))
-		   ((or (listp action)
-			;; the case when the action is simply to
-			;; return a token (ie $2) or a constant value
-			(symbolp action))
-		    (make-action-function name expanded-tokens action))
-		   ((functionp action)
-		    action)
-		   (t			; action is a constant
-		    #'(lambda (&rest args)
-			(declare (ignore args))
-			action)))))
-	(values
-	 ;; Make a promise instead of actually resolving the
-	 ;; nonterminals.  This avoids endless recursion.
-	 (make-production :tokens production-tokens
-			  :tokens-length (length production-tokens)
-			  :action funct)
-	 keywords))))))
+             (cond ((not action)
+                    (make-default-action-function name expanded-tokens))
+                   ((or (listp action)
+                        ;; the case when the action is simply to
+                        ;; return a token (ie $2) or a constant value
+                        (symbolp action))
+                    (make-action-function name expanded-tokens action))
+                   ((functionp action)
+                    action)
+                   (t			; action is a constant
+                    #'(lambda (&rest args)
+                        (declare (ignore args))
+                        action)))))
+        (values
+         ;; Make a promise instead of actually resolving the
+         ;; nonterminals.  This avoids endless recursion.
+         (make-production :tokens production-tokens
+                          :tokens-length (length production-tokens)
+                          :action funct)
+         keywords))))))
 
 (defun remove-immediate-left-recursivity (rule)
   "Turn left recursive rules of the type
@@ -281,7 +281,7 @@ into
     A2 -> x A2 | E
 where E is the empty production."
   (let ((name (rule-name rule))
-	(productions (rule-productions rule)))
+        (productions (rule-productions rule)))
     (loop
        for prod in productions
        for tokens = (prod-tokens prod)
@@ -291,40 +291,40 @@ where E is the empty production."
        else
        collect prod into non-left-recursive
        finally
-	 ;; found any left recursive production?
-	 (when left-recursive
-	   (warn "rule ~S is left recursive" name)
-	   (let ((new-rule (make-rule :name (gensym "REWRITE"))))
-	     ;; A -> y A2
-	     (setf (rule-productions rule)
-		   (mapcar #'(lambda (p)
-			       (let ((tokens (prod-tokens p))
-				     (action (prod-action p)))
-				 (make-production :tokens (append tokens (list new-rule))
-						  :tokens-length (1+ (prod-tokens-length p))
-						  :action #'(lambda (&rest args)
-							      (let ((f-A2 (car (last args)))
-								    (head (butlast args)))
-								(funcall f-A2 (apply action head)))))))
-			   non-left-recursive))
-	     ;; A2 -> x A2 | E
-	     (setf (rule-productions new-rule)
-		   (append
-		    (mapcar #'(lambda (p)
-				(let ((tokens (prod-tokens p))
-				      (action (prod-action p)))
-				  (make-production :tokens (append (cdr tokens) (list new-rule))
-						   :tokens-length (prod-tokens-length p)
-						   :action #'(lambda (&rest args)
-							       (let ((f-A2 (car (last args)))
-								     (head (butlast args)))
-								 #'(lambda (x)
-								     (funcall f-A2 (apply action x head))))))))
-			    left-recursive)
-		    (list
-		     (make-production :tokens nil
-				      :tokens-length 0
-				      :action #'(lambda () #'(lambda (arg) arg)))))))))))
+         ;; found any left recursive production?
+         (when left-recursive
+           (warn "rule ~S is left recursive" name)
+           (let ((new-rule (make-rule :name (gensym "REWRITE"))))
+             ;; A -> y A2
+             (setf (rule-productions rule)
+                   (mapcar #'(lambda (p)
+                               (let ((tokens (prod-tokens p))
+                                     (action (prod-action p)))
+                                 (make-production :tokens (append tokens (list new-rule))
+                                                  :tokens-length (1+ (prod-tokens-length p))
+                                                  :action #'(lambda (&rest args)
+                                                              (let ((f-A2 (car (last args)))
+                                                                    (head (butlast args)))
+                                                                (funcall f-A2 (apply action head)))))))
+                           non-left-recursive))
+             ;; A2 -> x A2 | E
+             (setf (rule-productions new-rule)
+                   (append
+                    (mapcar #'(lambda (p)
+                                (let ((tokens (prod-tokens p))
+                                      (action (prod-action p)))
+                                  (make-production :tokens (append (cdr tokens) (list new-rule))
+                                                   :tokens-length (prod-tokens-length p)
+                                                   :action #'(lambda (&rest args)
+                                                               (let ((f-A2 (car (last args)))
+                                                                     (head (butlast args)))
+                                                                 #'(lambda (x)
+                                                                     (funcall f-A2 (apply action x head))))))))
+                            left-recursive)
+                    (list
+                     (make-production :tokens nil
+                                      :tokens-length 0
+                                      :action #'(lambda () #'(lambda (arg) arg)))))))))))
 
 (defun remove-left-recursivity-from-rules (rules)
   (loop
@@ -338,9 +338,9 @@ where E is the empty production."
   (loop
      for rule being each hash-value in rules
      do (loop
-	   for production in (rule-productions rule)
-	   do (setf (prod-tokens production)
-		    (resolve-nonterminals (prod-tokens production) rules)))))
+           for production in (rule-productions rule)
+           do (setf (prod-tokens production)
+                    (resolve-nonterminals (prod-tokens production) rules)))))
 
 (defun make-rule-productions (rule-name production-descriptions)
   "Return a production object that belongs to RULE-NAME made according
@@ -352,12 +352,12 @@ to PRODUCTION-DESCRIPTIONS.  See also MAKE-PRODUCTION-FROM-DESCR."
      with productions = '()
      with keywords = '()
      do (progn
-	  (multiple-value-bind (production keyws)
-	      (make-production-from-descr prod-name descr)
-	    (push production productions)
-	    (setf keywords (append keyws keywords))))
+          (multiple-value-bind (production keyws)
+              (make-production-from-descr prod-name descr)
+            (push production productions)
+            (setf keywords (append keyws keywords))))
      finally (return
-	       (values (nreverse productions) keywords))))
+               (values (nreverse productions) keywords))))
 
 (defun create-rule (name production-descriptions)
   "Return a new rule object together with a list of keywords making up
@@ -365,7 +365,7 @@ the production definitions."
   (multiple-value-bind (productions keywords)
       (make-rule-productions name production-descriptions)
     (values (make-rule :name name :productions productions)
-	    keywords)))
+            keywords)))
 
 (defun insert-rule-in-current-grammar (name productions)
   "Add rule to the current grammar and its keywords to the keywords
@@ -384,18 +384,18 @@ instead."
   "Given a list of production tokens, try to expand the nonterminal
 ones with their respective rule from the the RULES pool."
   (flet ((resolve-symbol (sym)
-	   (or (find-rule sym rules)
-	       sym)))
+           (or (find-rule sym rules)
+               sym)))
     (mapcar #'(lambda (tok)
-		(if (symbolp tok)
-		    (resolve-symbol tok)
-		    tok))
-	    tokens)))
+                (if (symbolp tok)
+                    (resolve-symbol tok)
+                    tok))
+            tokens)))
 
 (defun reset-grammar ()
   "Empty the current grammar from any existing rule."
   (setf *rules* (make-rules-table)
-	*keywords* (make-keywords-table)))
+        *keywords* (make-keywords-table)))
 
 (defun generate-grammar (&optional (equal-p #'string-equal))
   "Return a GRAMMAR structure suitable for the PARSE function, using
@@ -404,5 +404,5 @@ match the input tokens; it defaults to STRING-EQUAL."
   (resolve-all-nonterminals *rules*)
   (remove-left-recursivity-from-rules *rules*)
   (make-grammar :rules *rules*
-		:keywords *keywords*
-		:equal-p equal-p))
+                :keywords *keywords*
+                :equal-p equal-p))
diff --git a/third_party/lisp/npg/src/parser.lisp b/third_party/lisp/npg/src/parser.lisp
index 328be1dcf30f..c15d26fe394e 100644
--- a/third_party/lisp/npg/src/parser.lisp
+++ b/third_party/lisp/npg/src/parser.lisp
@@ -43,9 +43,9 @@ Tune this if your grammar is unusually complex.")
   (when *debug*
     (format *debug* "reducing ~S on ~S~%" production arguments))
   (flet ((safe-token-value (token)
-	   (if (token-p token)
-	       (token-value token)
-	       token)))
+           (if (token-p token)
+               (token-value token)
+               token)))
     (apply (prod-action production) (mapcar #'safe-token-value arguments))))
 
 (defgeneric later-position (pos1 pos2)
@@ -75,120 +75,120 @@ supposed to specialise this method."))
 Return the reduced values according to the nonterminal actions.  Raise
 an error on failure."
   (declare (type grammar grammar)
-	   (type symbol start))
+           (type symbol start))
   (labels
       ((match-token (expected token)
-	 (when *debug*
-	   (format *debug* "match-token ~S ~S -> " expected token))
-	 (let ((res (cond ((symbolp expected)
-			   ;; non-costant terminal (like identifiers)
-			   (eq expected (token-type token)))
-			  ((and (stringp expected)
-				(stringp (token-value token)))
-			   ;; string costant terminal
-			   (funcall (the function (grammar-equal-p grammar)) expected (token-value token)))
-			  ((functionp expected)
-			   ;; custom equality predicate (must be able
-			   ;; to deal with token objects)
-			   (funcall expected token))
-			  ;; all the rest
-			  (t (equal expected (token-value token))))))
-	   (when *debug*
-	     (format *debug* "~Amatched~%" (if res "" "not ")))
-	   res))
+         (when *debug*
+           (format *debug* "match-token ~S ~S -> " expected token))
+         (let ((res (cond ((symbolp expected)
+                           ;; non-costant terminal (like identifiers)
+                           (eq expected (token-type token)))
+                          ((and (stringp expected)
+                                (stringp (token-value token)))
+                           ;; string costant terminal
+                           (funcall (the function (grammar-equal-p grammar)) expected (token-value token)))
+                          ((functionp expected)
+                           ;; custom equality predicate (must be able
+                           ;; to deal with token objects)
+                           (funcall expected token))
+                          ;; all the rest
+                          (t (equal expected (token-value token))))))
+           (when *debug*
+             (format *debug* "~Amatched~%" (if res "" "not ")))
+           res))
        (match (expected matched #+debug depth)
-	 (declare (list expected matched)
-		  #+debug (fixnum depth))
-	 (let ((first-expected (car expected)))
-	   (cond #+debug ((> depth *maximum-recursion-depth*)
-		  (error "endless recursion on ~A ~A at ~A expecting ~S"
-			 (token-type (car matched)) (token-value (car matched))
-			 (token-position (car matched)) expected))
-		 ((eq first-expected :any)
-		  (match (cdr expected) (cdr matched) #+debug depth))
-		 ;; This is a trick to obtain partial parses.  When we
-		 ;; reach this expected token we assume we succeeded
-		 ;; the parsing and return the remaining tokens as
-		 ;; part of the match.
-		 ((eq first-expected :rest)
-		  ;; we could be at the end of input so we check this
-		  (unless (cdr matched)
-		    (setf (cdr matched) (list :rest)))
-		  (list nil nil))
-		 ((rule-p first-expected)
-		  ;; If it's a rule, then we try to match all its
-		  ;; productions.  We return the first that succeeds.
-		  (loop
-		     for production in (rule-productions first-expected)
-		     for production-tokens of-type list = (prod-tokens production)
-		     with last-error-position = nil
-		     with last-error = nil
-		     for (error-position error-descr) =
-		       (progn
-			 (when *debug*
-			   (format *debug* "trying to match ~A: ~S~%"
-				   (rule-name first-expected) production-tokens))
-			 (match (append production-tokens (cdr expected)) matched #+debug (1+ depth)))
-		     do (cond ((not error-position)
-			       (return (let ((args-count (prod-tokens-length production)))
-					 (setf (cdr matched)
-					       (cons (reduce-production
-						      production
-						      (subseq (the list (cdr matched)) 0 args-count))
-						     (nthcdr (1+ args-count) matched)))
-					 (list nil nil))))
-			      ((or (not last-error)
-				   (later-position error-position last-error-position))
-			       (setf last-error-position error-position
-				     last-error error-descr)))
-		     ;; if everything fails return the "best" error
-		     finally (return (list last-error-position
-					   (if *debug*
-					       #'(lambda ()
-						   (format nil "~A, trying to match ~A"
-							   (funcall (the function last-error))
-							   (rule-name first-expected)))
-					       last-error)))))
-		 (t
-		  ;; if necessary load the next tokens
-		  (when (null (cdr matched))
-		    (setf (cdr matched) (read-next-tokens tokenizer)))
-		  (cond ((and (or (null expected) (eq first-expected :eof))
-			      (null (cdr matched)))
-			 ;; This point is reached only once for each complete
-			 ;; parsing.  The expected tokens and the input
-			 ;; tokens have been exhausted at the same time.
-			 ;; Hence we succeeded the parsing.
-			 (setf (cdr matched) (list :eof))
-			 (list nil nil))
-			((null expected)
-			 ;; Garbage at end of parsing.  This may mean that we
-			 ;; have considered a production completed too soon.
-			 (list (token-position (car matched))
-			       #'(lambda ()
-				   "garbage at end of parsing")))
-			((null (cdr matched))
-			 ;; EOF error
-			 (list :eof
-			       #'(lambda ()
-				   (format nil "end of input expecting ~S" expected))))
-			(t ;; normal token
-			 (let ((first-token (cadr matched)))
-			   (if (match-token first-expected first-token)
-			       (match (cdr expected) (cdr matched) #+debug depth)
-			       ;; failed: we return the error
-			       (list (token-position first-token)
-				     #'(lambda ()
-					 (format nil "expected ~S but got ~S ~S"
-						 first-expected (token-type first-token)
-						 (token-value first-token)))))))))))))
+         (declare (list expected matched)
+                  #+debug (fixnum depth))
+         (let ((first-expected (car expected)))
+           (cond #+debug ((> depth *maximum-recursion-depth*)
+                  (error "endless recursion on ~A ~A at ~A expecting ~S"
+                         (token-type (car matched)) (token-value (car matched))
+                         (token-position (car matched)) expected))
+                 ((eq first-expected :any)
+                  (match (cdr expected) (cdr matched) #+debug depth))
+                 ;; This is a trick to obtain partial parses.  When we
+                 ;; reach this expected token we assume we succeeded
+                 ;; the parsing and return the remaining tokens as
+                 ;; part of the match.
+                 ((eq first-expected :rest)
+                  ;; we could be at the end of input so we check this
+                  (unless (cdr matched)
+                    (setf (cdr matched) (list :rest)))
+                  (list nil nil))
+                 ((rule-p first-expected)
+                  ;; If it's a rule, then we try to match all its
+                  ;; productions.  We return the first that succeeds.
+                  (loop
+                     for production in (rule-productions first-expected)
+                     for production-tokens of-type list = (prod-tokens production)
+                     with last-error-position = nil
+                     with last-error = nil
+                     for (error-position error-descr) =
+                       (progn
+                         (when *debug*
+                           (format *debug* "trying to match ~A: ~S~%"
+                                   (rule-name first-expected) production-tokens))
+                         (match (append production-tokens (cdr expected)) matched #+debug (1+ depth)))
+                     do (cond ((not error-position)
+                               (return (let ((args-count (prod-tokens-length production)))
+                                         (setf (cdr matched)
+                                               (cons (reduce-production
+                                                      production
+                                                      (subseq (the list (cdr matched)) 0 args-count))
+                                                     (nthcdr (1+ args-count) matched)))
+                                         (list nil nil))))
+                              ((or (not last-error)
+                                   (later-position error-position last-error-position))
+                               (setf last-error-position error-position
+                                     last-error error-descr)))
+                     ;; if everything fails return the "best" error
+                     finally (return (list last-error-position
+                                           (if *debug*
+                                               #'(lambda ()
+                                                   (format nil "~A, trying to match ~A"
+                                                           (funcall (the function last-error))
+                                                           (rule-name first-expected)))
+                                               last-error)))))
+                 (t
+                  ;; if necessary load the next tokens
+                  (when (null (cdr matched))
+                    (setf (cdr matched) (read-next-tokens tokenizer)))
+                  (cond ((and (or (null expected) (eq first-expected :eof))
+                              (null (cdr matched)))
+                         ;; This point is reached only once for each complete
+                         ;; parsing.  The expected tokens and the input
+                         ;; tokens have been exhausted at the same time.
+                         ;; Hence we succeeded the parsing.
+                         (setf (cdr matched) (list :eof))
+                         (list nil nil))
+                        ((null expected)
+                         ;; Garbage at end of parsing.  This may mean that we
+                         ;; have considered a production completed too soon.
+                         (list (token-position (car matched))
+                               #'(lambda ()
+                                   "garbage at end of parsing")))
+                        ((null (cdr matched))
+                         ;; EOF error
+                         (list :eof
+                               #'(lambda ()
+                                   (format nil "end of input expecting ~S" expected))))
+                        (t ;; normal token
+                         (let ((first-token (cadr matched)))
+                           (if (match-token first-expected first-token)
+                               (match (cdr expected) (cdr matched) #+debug depth)
+                               ;; failed: we return the error
+                               (list (token-position first-token)
+                                     #'(lambda ()
+                                         (format nil "expected ~S but got ~S ~S"
+                                                 first-expected (token-type first-token)
+                                                 (token-value first-token)))))))))))))
     (declare (inline match-token))
     (let ((result (list :head)))
       (destructuring-bind (error-position error)
-	  (match (list (find-rule start (grammar-rules grammar))) result #+debug 0)
-	(when error-position
-	  (error "~A at ~A~%" (funcall (the function error)) error-position))
-	(cadr result)))))
+          (match (list (find-rule start (grammar-rules grammar))) result #+debug 0)
+        (when error-position
+          (error "~A at ~A~%" (funcall (the function error)) error-position))
+        (cadr result)))))
 
 (defgeneric terminals-in-grammar (grammar-or-hashtable)
   (:documentation
@@ -199,11 +199,11 @@ an error on failure."
      for rule being each hash-value of grammar
      with terminals = '()
      do (loop
-	   for prod in (rule-productions rule)
-	   do (loop
-		 for tok in (prod-tokens prod)
-		 when (symbolp tok)
-		 do (pushnew tok terminals)))
+           for prod in (rule-productions rule)
+           do (loop
+                 for tok in (prod-tokens prod)
+                 when (symbolp tok)
+                 do (pushnew tok terminals)))
      finally (return terminals)))
 
 (defmethod terminals-in-grammar ((grammar grammar))
@@ -211,9 +211,9 @@ an error on failure."
 
 (defun print-grammar-figures (grammar &optional (stream *standard-output*))
   (format stream "rules: ~A~%constant terminals: ~A~%variable terminals: ~S~%"
-	  (hash-table-count (grammar-rules grammar))
-	  (hash-table-count (grammar-keywords grammar))
-	  (terminals-in-grammar (grammar-rules grammar))))
+          (hash-table-count (grammar-rules grammar))
+          (hash-table-count (grammar-keywords grammar))
+          (terminals-in-grammar (grammar-rules grammar))))
 
 
 (defun grammar-keyword-p (keyword grammar)