Packrat: Simple Packrat Parsing

David Van Horn <dvanhorn@ccs.neu.edu>

This module provides a small library of Packrat parsing combinators and a syntax for defining parsers.

Report a bug.

1 Main

(require (planet dvanhorn/packrat:1:1))

This module provides bindings from the combinator library and the parser syntax.

2 Combinator library

(require (planet dvanhorn/packrat:1:1/combinator))

(struct parse-position (filename line column))

filename : string?

line : number?

column : number?

(struct parse-result (successful? semantic-value next error))

successful? : boolean?

semantic-value : any/c

next : (or/c false? parse-results?)

error : (or/c false? parse-error?)

(struct parse-results (position base next* map))

position : (or/c false? parse-position?)

base : any/c

next* : (or/c false? parse-results? (-> parse-results?))

map : (hash/c symbol? (or/c false? parse-result?))

(struct parse-error (position expected messages))

position : (or/c parse-position? false?)

expected : (or/c false? (listof any/c))

messages : (listof string?)

(top-parse-position filename) → parse-position?

filename : string?

(update-parse-position pos ch) → parse-position?

pos : parse-position?

ch : char?

(empty-results pos) → parse-results?

pos : (or/c parse-position? false?)

(make-results pos base next-generator) → parse-results?

pos : (or/c parse-position? false?)

base : (or/c false? (cons/c any/c any/c))

next-generator : (-> parse-results?)

(make-error-expected pos thing) → parse-error?

pos : (or/c parse-position? false?)

thing : any/c

(make-error-message pos msg) → parse-error?

pos : parse-position?

msg : string?

(make-result semantic-value next) → parse-result?

semantic-value : any/c

next : parse-results?

(parse-error->parse-result err) → parse-result?

err : parse-error?

(make-expected-result pos thing) → parse-result?

pos : (or/c parse-position? false?)

thing : any/c

(make-message-result pos msg) → parse-result?

pos : (or/c parse-position? false?)

msg : string?

(base-generator->results generator) → parse-results?

generator   :   (-> (values (or/c parse-position? false?)             (or/c (cons/c any/c any/c) false?)))

(parse-results-next results) → parse-results?

results : parse-results?

(results->result results key fn) → parse-result?

results : parse-results?

key : symbol?

fn : (-> parse-result?)

(parse-position>? a b) → boolean?

a : (or/c parse-position? false?)

b : (or/c parse-position? false?)

(parse-error-empty? e) → boolean?

e : parse-error?

(merge-parse-errors e1 e2) → (or/c parse-error? false?)

e1 : (or/c parse-error? false?)

e2 : (or/c parse-error? false?)

(merge-result-errors result errs) → parse-result?

result : parse-result?

errs : (or/c parse-error? false?)

(packrat-check-base token-kind k)

→ (-> parse-results? parse-result?)

token-kind : any/c

k : (-> any/c (-> parse-results? parse-result?))

(packrat-check-pred token-pred k)

→ (-> parse-results? parse-result?)

token-pred : (-> any/c boolean?)

k : (-> any/c (-> parse-results? parse-result?))

(packrat-check parser k) → (-> parse-results? parse-result?)

parser : (-> parse-results? parse-result?)

k : (-> any/c (-> parse-results? parse-result?))

(packrat-or p1 p2) → (-> parse-results? parse-result?)

p1 : (-> parse-results? parse-result?)

p2 : (-> parse-results? parse-result?)

(packrat-unless explanation p1 p2)

→ (-> parse-results? parse-result?)

explanation : string?

p1 : (-> parse-results? parse-result?)

p2 : (-> parse-results? parse-result?)

(packrat-port-results filename p) → parse-results?

filename : string?

p : port?

(packrat-string-results filename s) → parse-results?

filename : string?

s : string?

(packrat-list-results tokens) → parse-results?

tokens : (listof any/c)

3 Parser syntax

(require (planet dvanhorn/packrat:1:1/parser))

(parse id ([nonterminal-id (sequence body body0 ...)] ...))

sequence   =   (part ...)           part   =   (! part ...)     |   (/ sequence ...)     |   (? expr)     |   id := 'kind     |   id := @     |   id := nonterminal-id     |   id := (? expr)     |   nonterminal-id

4 Examples

Here is an example of a simple calculator.

Examples:

(define calc     (parse expr            (expr ((a := mulexp '+ b := mulexp)                   (+ a b))                  ((a := mulexp) a))            (mulexp ((a := simple '* b := simple)                     (* a b))                    ((a := simple '* b := simple)                     (* a b))                    ((a := simple) a))            (simple ((a := 'num) a)                    (('oparen a := expr 'cparen) a))))

(define g     (packrat-list-results '((num . 1) (+) (num . 2) (*) (num . 3))))

> (parse-result-semantic-value (calc g))

7

See the tests source file for an example of a parser for a simplified Scheme grammar.

5 Test suite

(require (planet dvanhorn/packrat:1:1/test))

Requiring this module will run the test suite.

Index