;;;;
;;;; Test program: Parse and build ASTs for simple expressions
;;;;

;; Produce an eval tree for sum or product lists
(defun sum-tree (tree l)
  (if l
      (sum-tree `(,(first l) ,tree ,(second l))
                (cddr l))
      tree))

;; Define an LL(1) parser
(def-ll1 *my-ll1*

  ;; Statement
  (S  (E eof)     %0)

  ;; Left-factored sum list
  (E  (T Ep)      (sum-tree %0 %1))
  (Ep (+ T Ep)    `(+ ,%1 . ,%2))
  (Ep (- T Ep)    `(- ,%1 . ,%2))
  (Ep ()          nil)

  ;; Left-factored product list
  (T  (F Tp)      (sum-tree %0 %1))
  (Tp (* F Tp)    `(* ,%1 . ,%2))
  (Tp (/ F Tp)    `(/ ,%1 . ,%2))
  (Tp ()          nil)

  ;; Terminals and parened exprs
  (F  (id)         %0)
  (F  (num)        %0)
  (F  (#\( E #\))  %1))

(defun test-parse (l)
  (let ((op '(+ - * / #\( #\))))
    (setf (ll1-parser-lookahead *my-ll1*)
          #'(lambda ()
              (cond ((null l)            'eof)
                    ((numberp (car l))   'num)
                    ((member (car l) op) (car l))
                    (t                   'id)))))
  (setf (ll1-parser-get-token *my-ll1*) #'(lambda () (pop l)))
  (parse-ll1 *my-ll1*))

(pprint (test-parse '(#\( 1 + 1 #\) / 2 + 2 * 3 - x)))