You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Colin Okay 0097eab237 tutorial tweakin 4 weeks ago
examples tutorial tweakin 4 weeks ago
LICENSE initial commit 3 years ago tutorial link 4 weeks ago
package.lisp added <<conditionally 1 year ago
parzival.asd bump and reauthor 2 years ago
parzival.lisp addded note about gotchas using <<or 1 year ago
tests.lisp Altered tests.lisp to use character input streams 2 years ago


The quest of parzival is to make it fun and easy to build parsers that consume streams and return common lisp values. E.g. A JSON parser or can be written reasonbly succinctly in parzival.

Check out the Tutorial for a detailed introduction.

A Neat / Dumb Example

What follows is a quick example of using parzival to build a parser for simple arithmetic expressions. But first, you should be aware of two completely optional naming conventions that parzival adopts.

  1. Names beginning and ending in a < are parsers.

  2. Names that begin with << are higher-order functions that accept or return parsers.

  (defpackage :parzival-user (:use :cl :parzival))
  (in-package :parzival-user)
  ;; we want to parse + - / or * and result in a function that can be
  ;; used do arithmetic on numbers
  (<<def <op<  
         (<<bind (<<strip (<<any-char "+-*/"))
                 (lambda (op-char)
                    (case op-char
                      (#\+ #'+)
                      (#\- #'-)
                      (#\* #'*)
                      (t #'/))))))

  ;; parse a two real numbers separated by a valid operator
  ;; result in the operator applied to the numbers
  (<<def <simple-expression<
         (<<let ((arg1 (<<strip <real<))
                 (op <op<)
                 (arg2 (<<strip <real<)))
                (<<result (funcall op arg1 arg2))))

The above is "good enough" to parse simple expressions like "44.32 + 55" or "88 / 11.11". E.g.

PARZIVAL-USER> (parse "33 * 2.5" <simple-expression< t)
PARZIVAL-USER> (parse "331 / 2.5" <simple-expression< t)
PARZIVAL-USER> (parse "foozball / 2.5" <simple-expression< t)

In the last example the string foozball does not represent a real number, and hence, the parse fails. You can examine the third return value to see where in the input stream the parse failed.

An Extended Silly / Dumber Example

The code for this example is a little long winded, so for the impatient I present below the grand payoff.

What we have here is a natural language calculator. It computes addition, subtraction, multipication, and division with all the convenience of typing out numbers without the cumbersome use of digits!

Here is a REPL session

PARZIVAL-NUMBERS> (natural-language-calc)
Hello! And Welcome To the Super Practical Natural Language Calculator!

Type quit to quit

> one hundred minus eight
EQUALS ninety-two

> twenty-nine plus four hundred seventy-seven
EQUALS five hundred six

> twenty over four

> twenty-one times sixteen
EQUALS three hundred thirty-six

> four thousand nine hundred fifty-five times two hundred seventeen
EQUALS one million seventy-five thousand two hundred thirty-five

> quit




The Code

(defpackage :parzival-numbers
  (:use :cl :parzival))

(in-package :parzival-numbers)

(defun <<map-to (parser value)
  (<<map (lambda (x) value) parser))

(<<def <ones<
  (<<or (<<map-to (<<string "one") 1)
        (<<map-to (<<string "two") 2)
        (<<map-to (<<string "three") 3)
        (<<map-to (<<string "four") 4)
        (<<map-to (<<string "five") 5)
        (<<map-to (<<string "six") 6)
        (<<map-to (<<string "seven") 7)
        (<<map-to (<<string "eight") 8)
        (<<map-to (<<string "nine") 9)))

(<<def <teens<
  (<<or (<<map-to (<<string "ten") 10)
        (<<map-to (<<string "eleven") 11)
        (<<map-to (<<string "twelve") 12)
        (<<map-to (<<string "thirteen") 13)
        (<<map-to (<<string "fourteen") 14)
        (<<map-to (<<string "fifteen") 15)
        (<<map-to (<<string "sixteen") 16)
        (<<map-to (<<string "seventeen") 17)
        (<<map-to (<<string "eighteen") 18)
        (<<map-to (<<string "nineteen") 19)))

(<<def <tens<
  (<<or (<<map-to (<<string "twenty") 20)
        (<<map-to (<<string "thirty") 30)
        (<<map-to (<<string "forty") 40)
        (<<map-to (<<string "fifty") 50)
        (<<map-to (<<string "sixty") 60)
        (<<map-to (<<string "seventy") 70)
        (<<map-to (<<string "eighty") 80)
        (<<map-to (<<string "ninety") 90)))

(<<def <20-to-99<
  (<<bind <tens<
          (lambda (tens)
            (<<map (lambda (ones) (+ tens ones))
                   (<<and (<<char #\-) <ones<)))))

(<<def <1-to-99<
  (<<or <20-to-99< <tens< <teens< <ones<))

(<<def <one-hundreds<
  (<<bind <ones<
          (lambda (num)
            (<<map (lambda (ignore) (* num 100))
                   (<<and (<<+ <space<) (<<string "hundred"))))))

(<<def <in-hundreds<
  (<<bind <one-hundreds<
          (lambda (hundreds)
            (<<map (lambda (num) (+ hundreds num))
                   (<<and (<<+ <space<) <1-to-99<)))))

(<<def <all-hundreds<
  (<<plus <in-hundreds< <one-hundreds<))

(defun <<magnitude-order (name factor)
  (<<bind (<<or <all-hundreds< <1-to-99<)
          (lambda (val)
            (<<map (lambda (ignore) (* val factor))
                   (<<and (<<+ <space<) (<<string name))))))

(<<def <thousands< (<<magnitude-order "thousand" 1000))

(<<def <millions< (<<magnitude-order "million" 1000000))

(<<def <billions< (<<magnitude-order "billion" 1000000000))

(<<def <trillions< (<<magnitude-order "trillion" 1000000000000))

(<<def <quadrillions< (<<magnitude-order "quadrillion" 1000000000000000))

(<<def <number<
  (<<map (lambda (ls) (apply #'+ ls))
         (apply #'parzival::<<list
                (mapcar (lambda (p) (<<or (<<strip p) (<<result 0)))
                        (list <quadrillions< <trillions< <billions<
                              <millions< <thousands<
                              <all-hundreds< <1-to-99<)))))

(defun parse-number (str)
  "Just for parsing numbers"
  (parse str <number< t))

;; three plus forty-seven thousand plus two hundred million sixty-five

(<<def <op< (<<strip (<<or (<<string "plus")
                           (<<string "minus")
                           (<<string "times")
                           (<<string "over"))))

(<<def <calc<
   (<<bind <number<
           (lambda (number)
             (<<map (lambda (op-calc)
                      (cond ((equal (car op-calc) "plus")
                             (+ number (cdr op-calc)))
                            ((equal (car op-calc) "minus")
                             (- number (cdr op-calc)))
                            ((equal (car op-calc) "times")
                             (* number (cdr op-calc)))
                            ((equal (car op-calc) "over")
                             (round (/ number (cdr op-calc))))))
                    (<<cons <op< #'<calc<))))

(defun natural-language-calc ()
  (format t "Hello! And Welcome To the Super Practical Natural Language Calculator!~%~%")
  (format t "Type quit to quit~%")
  (format t "> ")
  (loop named goof-calc
        for line = (read-line)
        (if (equal line "quit")
            (return-from goof-calc "OK")
            (let ((parsed (parse (string-downcase line) <calc< t)))
              (if parsed
                  (format t "EQUALS ~R~%> " parsed)
                  (format t "No no no.. all wrong...~%> "))))))