1 Main
2 Combinator library
parse-position
parse-result
parse-results
parse-error
top-parse-position
update-parse-position
empty-results
make-results
make-error-expected
make-error-message
make-result
parse-error->parse-result
make-expected-result
make-message-result
base-generator->results
parse-results-next
results->result
parse-position>?
parse-error-empty?
merge-parse-errors
merge-result-errors
packrat-check-base
packrat-check-pred
packrat-check
packrat-or
packrat-unless
packrat-port-results
packrat-string-results
packrat-list-results
3 Parser syntax
parse
4 Examples
5 Test suite
Index

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.

This code is based on the portable packrat parsing library by Tony Garnock-Jones:

Report a bug.

    1 Main

    2 Combinator library

    3 Parser syntax

    4 Examples

    5 Test suite

    Index

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

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

 

(planet dvanhorn/packrat:1:1)
(planet dvanhorn/packrat:1:1/combinator)
(planet dvanhorn/packrat:1:1/parser)
(planet dvanhorn/packrat:1:1/test)
base-generator->results
Combinator library
empty-results
Examples
Main
make-error-expected
make-error-message
make-expected-result
make-message-result
make-parse-error
make-parse-position
make-parse-result
make-parse-results
make-result
make-results
merge-parse-errors
merge-result-errors
packrat-check
packrat-check-base
packrat-check-pred
packrat-list-results
packrat-or
packrat-port-results
packrat-string-results
packrat-unless
Packrat: Simple Packrat Parsing
parse
parse-error
parse-error->parse-result
parse-error-empty?
parse-error-expected
parse-error-messages
parse-error-position
parse-error?
parse-position
parse-position-column
parse-position-filename
parse-position-line
parse-position>?
parse-position?
parse-result
parse-result-error
parse-result-next
parse-result-semantic-value
parse-result-successful?
parse-result?
parse-results
parse-results-base
parse-results-map
parse-results-next
parse-results-next*
parse-results-position
parse-results?
Parser syntax
results->result
struct:parse-error
struct:parse-position
struct:parse-result
struct:parse-results
Test suite
top-parse-position
update-parse-position