ESRAP – a packrat parser for Common Lisp

Introduction

In addition to regular Packrat / Parsing Grammar / TDPL features ESRAP supports:

• dynamic redefinition of nonterminals
• inline grammars
• semantic predicates
• introspective facilities (describing grammars, tracing, setting breaks)
• left-recursive grammars
• functions as terminals
• accurate, customizable parse error reports

Homepage & Documentation

https://scymtym.github.io/esrap/

References

• Bryan Ford, 2002, “Packrat Parsing: a Practical Linear Time Algorithm with Backtracking”.

  http://pdos.csail.mit.edu/~baford/packrat/thesis/

• A. Warth et al, 2008, “Packrat Parsers Can Support Left Recursion”.

  http://www.vpri.org/pdf/tr2007002_packrat.pdf

License

Copyright (c) 2007-2013 Nikodemus Siivola <nikodemus@random-state.net>
Copyright (c) 2012-2019 Jan Moringen <jmoringe@techfak.uni-bielefeld.de>

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use, copy,
modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.

Syntax Overview

<literal>                   -- case-sensitive terminal
(~ <literal>)               -- case-insensitive terminal
character                   -- any single character
(string <length>)           -- any string of length
(character-ranges <ranges>) -- character ranges
(<predicate> <expr>)        -- semantic parsing
(function <function>)       -- call <function> to parse some text

(not <expr>)                -- complement of expression
(and &rest <exprs>)         -- sequence
(or &rest <exprs>)          -- ordered-choices

(* <expr>)                  -- greedy-repetition
(+ <expr>)                  -- greedy-positive-repetition
(? <expr>)                  -- optional
(& <expr>)                  -- followed-by; does not consume
(! <expr>)                  -- not-followed-by; does not consume
(< <amount> <expr>)         -- lookbehind <amount> characters; does not consume
(> <amount> <expr>)         -- lookahead <amount> characters; does not consume

Trivial Examples

(ql:quickload :esrap)

The parse function takes an expression:

(multiple-value-list (esrap:parse '(or "foo" "bar") "foo"))

("foo" NIL T)

New rules can be added.

Normally you’d use the declarative defrule interface to define new rules, but everything it does can be done directly by building instances of the rule class and using add-rule to activate them.

(progn
  (esrap:add-rule 'foo+ (make-instance 'esrap:rule :expression '(+ "foo")))

  (multiple-value-list (esrap:parse 'foo+ "foofoofoo")))

(("foo" "foo" "foo") NIL T)

The equivalent defrule form is

(esrap:defrule foo+ (+ "foo"))

Note that rules can be redefined, i.e. this defrule form replaces the previous definition of the foo+ rule.

Rules can transform their matches:

(esrap:add-rule
 'decimal
 (make-instance
  'esrap:rule
  :expression '(+ (or "0" "1" "2" "3" "4" "5" "6" "7" "8" "9"))
  :transform (lambda (list start end)
               (declare (ignore start end))
               (parse-integer (format nil "~{~A~}" list)))))

or using defrule

(esrap:defrule decimal
    (+ (or "0" "1" "2" "3" "4" "5" "6" "7" "8" "9"))
  (:lambda (list)
    (parse-integer (format nil "~{~A~}" list))))

Any lisp function can be used as a semantic predicate:

(list
 (multiple-value-list (esrap:parse '(oddp decimal) "123"))
 (multiple-value-list (esrap:parse '(evenp decimal) "123" :junk-allowed t)))

((123 NIL T) (NIL 0))

Example Files

More complete examples can be found in the following self-contained example files:

• examples/sexp.lisp: complete sample grammar and usage
• examples/symbol-table.lisp: grammar with lexical scope
• examples/left-recursion.lisp: multiple grammars with left recursion
• examples/function-terminals.lisp: grammars with functions as terminals