PEG Parsing
===========

Parsing Expression Grammars (PEGs) are a way of specifying formal languages for text processing.  They can be used either for matching (like regular expressions) or for building recursive descent parsers (like lex/yacc).  Guile uses a superset of PEG syntax that allows more control over what information is preserved during parsing.

Wikipedia has a clear and concise introduction to PEGs if you want to familiarize yourself with the syntax: http://en.wikipedia.org/wiki/Parsing_expression_grammar.

The module works by compiling PEGs down to lambda expressions.  These can either be stored in variables at compile-time by the define macros (define-nonterm and define-grammar) or calculated explicitly at runtime with the compile functions (peg-sexp-compile and peg-string-compile).

They can then be used for either parsing (peg-parse) or matching (peg-match).  For convenience, peg-match also takes pattern literals in case you want to inline a simple search (people often use regular expressions this way).

The rest of this documentation consists of a syntax reference, an API reference, and a tutorial.

PEG Syntax Reference
--------------------

Normal PEG Syntax:
..................

 -- PEG Pattern: sequence a b
     Parses A.  If this succeeds, continues to parse B from the end of the text parsed as A.  Succeeds if both A and B succeed.

     "a b"

     (and a b)

 -- PEG Pattern: ordered choice a b
     Parses A.  If this fails, backtracks and parses B. Succeeds if either A or B succeeds.

     "a/b"

     (or a b)

 -- PEG Pattern: zero or more a
     Parses A as many times in a row as it can, starting each A at the end of the text parsed by the previous A.  Always succeeds.

     "a*"

     (* a)

 -- PEG Pattern: one or more a
     Parses A as many times in a row as it can, starting each A at the end of the text parsed by the previous A.  Succeeds if at least one A was parsed.

     "a+"

     (+ a)

 -- PEG Pattern: optional a
     Tries to parse A.  Succeeds if A succeeds.

     "a?"

     (? a)

 -- PEG Pattern: and predicate a
     Makes sure it is possible to parse A, but does not actually parse it.  Succeeds if A would succeed.

     "&a"

     (body & a 1)

 -- PEG Pattern: not predicate a
     Makes sure it is impossible to parse A, but does not actually parse it.  Succeeds if A would fail.

     "!a"

     (body ! a 1)

 -- PEG Pattern: string literal ``abc''
     Parses the string "ABC".  Succeeds if that parsing succeeds.

     "'abc'"

     "abc"

 -- PEG Pattern: any character
     Parses any single character.  Succeeds unless there is no more text to be parsed.

     "."

     peg-any

 -- PEG Pattern: character class a b
     Alternative syntax for ``Ordered Choice A B'' if A and B are characters.

     "[ab]"

     (or "a" "b")

 -- PEG Pattern: range of characters a z
     Parses any character falling between A and Z.

     "[a-z]"

     (range #\a #\z)

Example:

     "(a !b / c &d*) 'e'+"

Would be:

     (and
      (or
       (and a (body ! b 1))
       (and c (body & d *)))
      (body lit "e" +))

Extended Syntax
...............

There is some extra syntax for S-expressions.

 -- PEG Pattern: ignore a
     Ignore the text matching A

 -- PEG Pattern: capture a
     Capture the text matching A.

 -- PEG Pattern: peg a
     Embed the PEG pattern A using string syntax.

Example:

     "!a / 'b'"

Would be:

     (or (peg "!a") "b")

PEG API Reference
-----------------

Define Macros
.............

The most straightforward way to define a PEG is by using one of the define macros (both of these macroexpand into define expressions).  These macros bind parsing functions to variables.  These parsing functions may be invoked by peg-parse or peg-match, which return a PEG match record.  Raw data can be retrieved from this record with the PEG match deconstructor functions. More complicated (and perhaps enlightening) examples can be found in the tutorial.

 -- Scheme Macro: define-grammar peg-string
     Defines all the nonterminals in the PEG PEG-STRING.  More precisely, define-grammar takes a superset of PEGs.  A normal PEG has a <- between the nonterminal and the pattern. define-grammar uses this symbol to determine what information it should propagate up the parse tree.  The normal <- propagates the matched text up the parse tree, <-- propagates the matched text up the parse tree tagged with the name of the nonterminal, and < discards that matched text and propagates nothing up the parse tree. Also, nonterminals may consist of any alphanumeric character or a ``-'' character (in normal PEGs nonterminals can only be alphabetic).

     For example, if we:

          (define-grammar
            "as <- 'a'+
          bs <- 'b'+
          as-or-bs <- as/bs")
          (define-grammar
            "as-tag <-- 'a'+
          bs-tag <-- 'b'+
          as-or-bs-tag <-- as-tag/bs-tag")

     Then:

          (peg-parse as-or-bs "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: aa>
          (peg-parse as-or-bs-tag "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: (as-or-bs-tag (as-tag aa))>

     Note that in doing this, we have bound 6 variables at the toplevel (AS, BS, AS-OR-BS, AS-TAG, BS-TAG, and AS-OR-BS-TAG).

 -- Scheme Macro: define-nonterm name capture-type peg-sexp
     Defines a single nonterminal NAME.  CAPTURE-TYPE determines how much information is passed up the parse tree.  PEG-SEXP is a PEG in S-expression form.

     Possible values for capture-type:

     all
          passes the matched text up the parse tree tagged with the name of the nonterminal.

     body
          passes the matched text up the parse tree.

     none
          passes nothing up the parse tree.

     For Example, if we:

          (define-nonterm as body (body lit "a" +))
          (define-nonterm bs body (body lit "b" +))
          (define-nonterm as-or-bs body (or as bs))
          (define-nonterm as-tag all (body lit "a" +))
          (define-nonterm bs-tag all (body lit "b" +))
          (define-nonterm as-or-bs-tag all (or as-tag bs-tag))

     Then:

          (peg-parse as-or-bs "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: aa>
          (peg-parse as-or-bs-tag "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: (as-or-bs-tag (as-tag aa))>

     Note that in doing this, we have bound 6 variables at the toplevel (AS, BS, AS-OR-BS, AS-TAG, BS-TAG, and AS-OR-BS-TAG).

These are macros, with all that entails.  If you've built up a list at runtime and want to define a new PEG from it, you should e.g.:

     (define exp '(body lit "a" +))
     (eval `(define-nonterm as body ,exp) (interaction-environment))

The eval function has a bad reputation with regard to efficiency, but this is mostly because of the extra work that has to be done compiling the expressions, which has to be done anyway when compiling the PEGs at runtime.

Compile Functions
.................

It is sometimes useful to be able to compile anonymous PEG patterns at runtime.  These functions let you do that using either syntax.

 -- Scheme Procedure: peg-string-compile peg-string capture-type
     Compiles the PEG pattern in PEG-STRING propagating according to CAPTURE-TYPE (capture-type can be any of the values from define-nonterm).

 -- Scheme Procedure: peg-sexp-compile peg-sexp capture-type
     Compiles the PEG pattern in PEG-SEXP propagating according to CAPTURE-TYPE (capture-type can be any of the values from define-nonterm).

Parsing & Matching Functions
............................

For our purposes, ``parsing'' means parsing a string into a tree starting from the first character, while ``matching'' means searching through the string for a substring.  In practice, the only difference between the two functions is that peg-parse gives up if it can't find a valid substring starting at index 0 and peg-match keeps looking.  They are both equally capable of ``parsing'' and ``matching'' given those constraints.

 -- Scheme Procedure: peg-parse nonterm string
     Parses STRING using the PEG stored in NONTERM.  If no match was found, peg-parse returns false.  If a match was found, a PEG match record is returned.

     The capture-type argument to define-nonterm allows you to choose what information to hold on to while parsing.  The options are:

     all
          tag the matched text with the nonterminal

     body
          just the matched text

     none
          nothing

          (define-nonterm as all (body lit "a" +))
          (peg-parse as "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: (as aa)>

          (define-nonterm as body (body lit "a" +))
          (peg-parse as "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: aa>

          (define-nonterm as none (body lit "a" +))
          (peg-parse as "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: ()>

          (define-nonterm bs body (body lit "b" +))
          (peg-parse bs "aabbcc") =>
          #f

 -- Scheme Macro: peg-match nonterm-or-peg string
     Searches through STRING looking for a matching subexpression. NONTERM-OR-PEG can either be a nonterminal or a literal PEG pattern.  When a literal PEG pattern is provided, peg-match works very similarly to the regular expression searches many hackers are used to.  If no match was found, peg-match returns false.  If a match was found, a PEG match record is returned.

          (define-nonterm as body (body lit "a" +))
          (peg-match as "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: aa>
          (peg-match (body lit "a" +) "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: aa>
          (peg-match "'a'+" "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: aa>

          (define-nonterm as all (body lit "a" +))
          (peg-match as "aabbcc") =>
          #<peg start: 0 end: 2 string: aabbcc tree: (as aa)>

          (define-nonterm bs body (body lit "b" +))
          (peg-match bs "aabbcc") =>
          #<peg start: 2 end: 4 string: aabbcc tree: bb>
          (peg-match (body lit "b" +) "aabbcc") =>
          #<peg start: 2 end: 4 string: aabbcc tree: bb>
          (peg-match "'b'+" "aabbcc") =>
          #<peg start: 2 end: 4 string: aabbcc tree: bb>

          (define-nonterm zs body (body lit "z" +))
          (peg-match zs "aabbcc") =>
          #f
          (peg-match (body lit "z" +) "aabbcc") =>
          #f
          (peg-match "'z'+" "aabbcc") =>
          #f

PEG Match Records
.................

The peg-parse and peg-match functions both return PEG match records.  Actual information can be extracted from these with the following functions.

 -- Scheme Procedure: peg:string peg-match
     Returns the original string that was parsed in the creation of peg-match.

 -- Scheme Procedure: peg:start peg-match
     Returns the index of the first parsed character in the original string (from peg:string).  If this is the same as peg:end, nothing was parsed.

 -- Scheme Procedure: peg:end peg-match
     Returns one more than the index of the last parsed character in the original string (from peg:string).  If this is the same as peg:start, nothing was parsed.

 -- Scheme Procedure: peg:substring peg-match
     Returns the substring parsed by peg-match.  This is equivalent to (substring (peg:string peg-match) (peg:start peg-match) (peg:end peg-match)).

 -- Scheme Procedure: peg:tree peg-match
     Returns the tree parsed by peg-match.

 -- Scheme Procedure: peg-record? peg-match
     Returns true if peg-match is a PEG match record, or false otherwise.

Example:

     (define-nonterm bs all (peg "'b'+"))

     (peg-match bs "aabbcc") =>
     #<peg start: 2 end: 4 string: aabbcc tree: (bs bb)>

     (let ((pm (peg-match bs "aabbcc")))
        `((string ,(peg:string pm))
          (start ,(peg:start pm))
          (end ,(peg:end pm))
          (substring ,(peg:substring pm))
          (tree ,(peg:tree pm))
          (record? ,(peg-record? pm)))) =>
     ((string "aabbcc")
      (start 2)
      (end 4)
      (substring "bb")
      (tree (bs "bb"))
      (record? #t))

Miscellaneous
.............

 -- Scheme Procedure: context-flatten tst lst
     Takes a predicate TST and a list LST.  Flattens LST until all elements are either atoms or satisfy TST.  If LST itself satisfies TST, (list lst) is returned (this is a flat list whose only element satisfies TST).

          (context-flatten (lambda (x) (and (number? (car x)) (= (car x) 1))) '(2 2 (1 1 (2 2)) (2 2 (1 1)))) =>
          (2 2 (1 1 (2 2)) 2 2 (1 1))
          (context-flatten (lambda (x) (and (number? (car x)) (= (car x) 1))) '(1 1 (1 1 (2 2)) (2 2 (1 1)))) =>
          ((1 1 (1 1 (2 2)) (2 2 (1 1))))

     If you're wondering why this is here, take a look at the tutorial.

 -- Scheme Procedure: keyword-flatten terms lst
     A less general form of context-flatten.  Takes a list of terminal atoms terms and flattens LST until all elements are either atoms, or lists which have an atom from terms as their first element.

          (keyword-flatten '(a b) '(c a b (a c) (b c) (c (b a) (c a)))) =>
          (c a b (a c) (b c) c (b a) c a)

     If you're wondering why this is here, take a look at the tutorial.

PEG Tutorial
------------

Parsing /etc/passwd
...................

This example will show how to parse /etc/passwd using PEGs.

First we define an example /etc/passwd file:

     (define *etc-passwd*
       "root:x:0:0:root:/root:/bin/bash
     daemon:x:1:1:daemon:/usr/sbin:/bin/sh
     bin:x:2:2:bin:/bin:/bin/sh
     sys:x:3:3:sys:/dev:/bin/sh
     nobody:x:65534:65534:nobody:/nonexistent:/bin/sh
     messagebus:x:103:107::/var/run/dbus:/bin/false
     ")

As a first pass at this, we might want to have all the entries in /etc/passwd in a list.

Doing this with string-based PEG syntax would look like this:

     (define-grammar
       "passwd <- entry* !.
     entry <-- (! NL .)* NL*
     NL < '\n'")

A passwd file is 0 or more entries (entry*) until the end of the file (!. (. is any character, so !. means ``not anything'')).  We want to capture the data in the nonterminal passwd, but not tag it with the name, so we use <-.

An entry is a series of 0 or more characters that aren't newlines ((! NL .)*) followed by 0 or more newlines (NL*).  We want to tag all the entries with entry, so we use <--.

A newline is just a literal newline ('\n').  We don't want a bunch of newlines cluttering up the output, so we use < to throw away the captured data.

Here is the same PEG defined using S-expressions:

     (define-nonterm passwd body (and (body lit entry *) (body ! peg-any 1)))
     (define-nonterm entry all (and (body lit (and (body ! NL 1) peg-any) *)
     			       (body lit NL *)))
     (define-nonterm NL none "\n")

Obviously this is much more verbose.  On the other hand, it's more explicit, and thus easier to build automatically.  However, there are some tricks that make S-expressions easier to use in some cases.  One is the ignore keyword; the string syntax has no way to say ``throw away this text'' except breaking it out into a separate nonterminal. For instance, to throw away the newlines we had to define NL.  In the S-expression syntax, we could have simply written (ignore "\n").  Also, for the cases where string syntax is really much cleaner, the peg keyword can be used to embed string syntax in S-expression syntax.  For instance, we could have written:

     (define-nonterm passwd body (peg "entry* !."))

However we define it, parsing *etc-passwd* with the passwd nonterminal yields the same results:

     (peg:tree (peg-parse passwd *etc-passwd*)) =>
     ((entry "root:x:0:0:root:/root:/bin/bash")
      (entry "daemon:x:1:1:daemon:/usr/sbin:/bin/sh")
      (entry "bin:x:2:2:bin:/bin:/bin/sh")
      (entry "sys:x:3:3:sys:/dev:/bin/sh")
      (entry "nobody:x:65534:65534:nobody:/nonexistent:/bin/sh")
      (entry "messagebus:x:103:107::/var/run/dbus:/bin/false"))

However, here is something to be wary of:

     (peg:tree (peg-parse passwd "one entry")) =>
     (entry "one entry")

By default, the parse trees generated by PEGs are compressed as much as possible without losing information.  It may not look like this is what you want at first, but uncompressed parse trees are an enormous headache (there's no easy way to predict how deep particular lists will nest, there are empty lists littered everywhere, etc. etc.).  One side-effect of this, however, is that sometimes the compressor is too aggressive. No information is discarded when ((entry "one entry")) is compressed to (entry "one entry"), but in this particular case it probably isn't what we want.

There are two functions for easily dealing with this: keyword-flatten and context-flatten.  The keyword-flatten function takes a list of keywords and a list to flatten, then tries to coerce the list such that the first element of all sublists is one of the keywords.  The context-flatten function is similar, but instead of a list of keywords it takes a predicate that should indicate whether a given sublist is good enough (refer to the API reference for more details).

What we want here is keyword-flatten.

     (keyword-flatten '(entry) (peg:tree (peg-parse passwd *etc-passwd*))) =>
     ((entry "root:x:0:0:root:/root:/bin/bash")
      (entry "daemon:x:1:1:daemon:/usr/sbin:/bin/sh")
      (entry "bin:x:2:2:bin:/bin:/bin/sh")
      (entry "sys:x:3:3:sys:/dev:/bin/sh")
      (entry "nobody:x:65534:65534:nobody:/nonexistent:/bin/sh")
      (entry "messagebus:x:103:107::/var/run/dbus:/bin/false"))
     (keyword-flatten '(entry) (peg:tree (peg-parse passwd "one entry"))) =>
     ((entry "one entry"))

Of course, this is a somewhat contrived example.  In practice we would probably just tag the passwd nonterminal to remove the ambiguity (using either the all keyword for S-expressions or the <-- symbol for strings)..

     (define-nonterm tag-passwd all (peg "entry* !."))
     (peg:tree (peg-parse tag-passwd *etc-passwd*)) =>
     (tag-passwd
       (entry "root:x:0:0:root:/root:/bin/bash")
       (entry "daemon:x:1:1:daemon:/usr/sbin:/bin/sh")
       (entry "bin:x:2:2:bin:/bin:/bin/sh")
       (entry "sys:x:3:3:sys:/dev:/bin/sh")
       (entry "nobody:x:65534:65534:nobody:/nonexistent:/bin/sh")
       (entry "messagebus:x:103:107::/var/run/dbus:/bin/false"))
     (peg:tree (peg-parse tag-passwd "one entry"))
     (tag-passwd
       (entry "one entry"))

If you're ever uncertain about the potential results of parsing something, remember the two absolute rules:

 1. No parsing information will ever be discarded.

 2. There will never be any lists with fewer than 2 elements.

For the purposes of (1), "parsing information" means things tagged with the any keyword or the <-- symbol.  Plain strings will be concatenated.

Let's extend this example a bit more and actually pull some useful information out of the passwd file:

     (define-grammar
       "passwd <-- entry* !.
     entry <-- login C pass C uid C gid C nameORcomment C homedir C shell NL*
     login <-- text
     pass <-- text
     uid <-- [0-9]*
     gid <-- [0-9]*
     nameORcomment <-- text
     homedir <-- path
     shell <-- path
     path <-- (SLASH pathELEMENT)*
     pathELEMENT <-- (!NL !C  !'/' .)*
     text <- (!NL !C  .)*
     C < ':'
     NL < '\n'
     SLASH < '/'")

This produces rather pretty parse trees:

     (passwd
       (entry (login "root")
              (pass "x")
              (uid "0")
              (gid "0")
              (nameORcomment "root")
              (homedir (path (pathELEMENT "root")))
              (shell (path (pathELEMENT "bin") (pathELEMENT "bash"))))
       (entry (login "daemon")
              (pass "x")
              (uid "1")
              (gid "1")
              (nameORcomment "daemon")
              (homedir
                (path (pathELEMENT "usr") (pathELEMENT "sbin")))
              (shell (path (pathELEMENT "bin") (pathELEMENT "sh"))))
       (entry (login "bin")
              (pass "x")
              (uid "2")
              (gid "2")
              (nameORcomment "bin")
              (homedir (path (pathELEMENT "bin")))
              (shell (path (pathELEMENT "bin") (pathELEMENT "sh"))))
       (entry (login "sys")
              (pass "x")
              (uid "3")
              (gid "3")
              (nameORcomment "sys")
              (homedir (path (pathELEMENT "dev")))
              (shell (path (pathELEMENT "bin") (pathELEMENT "sh"))))
       (entry (login "nobody")
              (pass "x")
              (uid "65534")
              (gid "65534")
              (nameORcomment "nobody")
              (homedir (path (pathELEMENT "nonexistent")))
              (shell (path (pathELEMENT "bin") (pathELEMENT "sh"))))
       (entry (login "messagebus")
              (pass "x")
              (uid "103")
              (gid "107")
              nameORcomment
              (homedir
                (path (pathELEMENT "var")
                      (pathELEMENT "run")
                      (pathELEMENT "dbus")))
              (shell (path (pathELEMENT "bin") (pathELEMENT "false")))))

Notice that when there's no entry in a field (e.g. nameORcomment for messagebus) the symbol is inserted.  This is the ``don't throw away any information'' rule---we succesfully matched a nameORcomment of 0 characters (since we used * when defining it).  This is usually what you want, because it allows you to e.g. use list-ref to pull out elements (since they all have known offsets).

If you'd prefer not to have symbols for empty matches, you can replace the * with a + and add a ? after the nameORcomment in entry.  Then it will try to parse 1 or more characters, fail (inserting nothing into the parse tree), but continue because it didn't have to match the nameORcomment to continue.

Embedding Arithmetic Expressions
................................

We can parse simple mathematical expressions with the following PEG:

     (define-grammar
       "expr <- sum
     sum <-- (product ('+' / '-') sum) / product
     product <-- (value ('*' / '/') product) / value
     value <-- number / '(' expr ')'
     number <-- [0-9]+")

Then:

     (peg:tree (peg-parse expr "1+1/2*3+(1+1)/2")) =>
     (sum (product (value (number "1")))
          "+"
          (sum (product
                 (value (number "1"))
                 "/"
                 (product
                   (value (number "2"))
                   "*"
                   (product (value (number "3")))))
               "+"
               (sum (product
                      (value "("
                             (sum (product (value (number "1")))
                                  "+"
                                  (sum (product (value (number "1")))))
                             ")")
                      "/"
                      (product (value (number "2")))))))

There is very little wasted effort in this PEG.  The number nonterminal has to be tagged because otherwise the numbers might run together with the arithmetic expressions during the string concatenation stage of parse-tree compression (the parser will see ``1'' followed by ``/'' and decide to call it ``1/'').  When in doubt, tag.

It is very easy to turn these parse trees into lisp expressions:

     (define (parse-sum sum left . rest)
       (if (null? rest)
           (apply parse-product left)
           (list (string->symbol (car rest))
     	    (apply parse-product left)
     	    (apply parse-sum (cadr rest)))))

     (define (parse-product product left . rest)
       (if (null? rest)
           (apply parse-value left)
           (list (string->symbol (car rest))
     	    (apply parse-value left)
     	    (apply parse-product (cadr rest)))))

     (define (parse-value value first . rest)
       (if (null? rest)
           (string->number (cadr first))
           (apply parse-sum (car rest))))

     (define parse-expr parse-sum)

(Notice all these functions look very similar; for a more complicated PEG, it would be worth abstracting.)

Then:

     (apply parse-expr (peg:tree (peg-parse expr "1+1/2*3+(1+1)/2"))) =>
     (+ 1 (+ (/ 1 (* 2 3)) (/ (+ 1 1) 2)))

But wait!  The associativity is wrong!  Where it says (/ 1 (* 2 3)), it should say (* (/ 1 2) 3).

It's tempting to try replacing e.g. "sum <-- (product ('+' / '-') sum) / product" with "sum <-- (sum ('+' / '-') product) / product", but this is a Bad Idea.  PEGs don't support left recursion. To see why, imagine what the parser will do here.  When it tries to parse sum, it first has to try and parse sum.  But to do that, it first has to try and parse sum.  This will continue until the stack gets blown off.

So how does one parse left-associative binary operators with PEGs? Honestly, this is one of their major shortcomings.  There's no general-purpose way of doing this, but here the repetition operators are a good choice:

     (use-modules (srfi srfi-1))

     (define-grammar
       "expr <- sum
     sum <-- (product ('+' / '-'))* product
     product <-- (value ('*' / '/'))* value
     value <-- number / '(' expr ')'
     number <-- [0-9]+")

     ;; take a deep breath...
     (define (make-left-parser next-func)
       (lambda (sum first . rest) ;; general form, comments below assume
         ;; that we're dealing with a sum expression
         (if (null? rest) ;; form (sum (product ...))
           (apply next-func first)
           (if (string? (cadr first));; form (sum ((product ...) "+") (product ...))
     	  (list (string->symbol (cadr first))
     		(apply next-func (car first))
     		(apply next-func (car rest)))
               ;; form (sum (((product ...) "+") ((product ...) "+")) (product ...))
     	  (car
     	   (reduce ;; walk through the list and build a left-associative tree
     	    (lambda (l r)
     	      (list (list (cadr r) (car r) (apply next-func (car l)))
     		    (string->symbol (cadr l))))
     	    'ignore
     	    (append ;; make a list of all the products
                  ;; the first one should be pre-parsed
     	     (list (list (apply next-func (caar first))
     			 (string->symbol (cadar first))))
     	     (cdr first)
                  ;; the last one has to be added in
     	     (list (append rest '("done"))))))))))

     (define (parse-value value first . rest)
       (if (null? rest)
           (string->number (cadr first))
           (apply parse-sum (car rest))))
     (define parse-product (make-left-parser parse-value))
     (define parse-sum (make-left-parser parse-product))
     (define parse-expr parse-sum)

Then:

     (apply parse-expr (peg:tree (peg-parse expr "1+1/2*3+(1+1)/2"))) =>
     (+ (+ 1 (* (/ 1 2) 3)) (/ (+ 1 1) 2))

As you can see, this is much uglier (it could be made prettier by using context-flatten, but the way it's written above makes it clear how we deal with the three ways the zero-or-more * expression can parse).  Fortunately, most of the time we can get away with only using right-associativity.

Simplified Functions
....................

For a more tantalizing example, consider the following grammar that parses (highly) simplified C functions:

     (define-grammar
       "cfunc <-- cSP ctype cSP cname cSP cargs cLB cSP cbody cRB
     ctype <-- cidentifier
     cname <-- cidentifier
     cargs <-- cLP (! (cSP cRP) carg cSP (cCOMMA / cRP) cSP)* cSP
     carg <-- cSP ctype cSP cname
     cbody <-- cstatement *
     cidentifier <- [a-zA-z][a-zA-Z0-9_]*
     cstatement <-- (!';'.)*cSC cSP
     cSC < ';'
     cCOMMA < ','
     cLP < '('
     cRP < ')'
     cLB < '{'
     cRB < '}'
     cSP < [ \t\n]*")

Then:

     (peg-parse cfunc "int square(int a) { return a*a;}") =>
     (32
      (cfunc (ctype "int")
             (cname "square")
             (cargs (carg (ctype "int") (cname "a")))
             (cbody (cstatement "return a*a"))))

And:

     (peg-parse cfunc "int mod(int a, int b) { int c = a/b;return a-b*c; }") =>
     (52
      (cfunc (ctype "int")
             (cname "mod")
             (cargs (carg (ctype "int") (cname "a"))
                    (carg (ctype "int") (cname "b")))
             (cbody (cstatement "int c = a/b")
                    (cstatement "return a- b*c"))))

By wrapping all the carg nonterminals in a cargs nonterminal, we were able to remove any ambiguity in the parsing structure and avoid having to call context-flatten on the output of peg-parse.  We used the same trick with the cstatement nonterminals, wrapping them in a cbody nonterminal.

The whitespace nonterminal cSP used here is a (very) useful instantiation of a common pattern for matching syntactically irrelevant information.  Since it's tagged with < and ends with * it won't clutter up the parse trees (all the empty lists will be discarded during the compression step) and it will never cause parsing to fail.

PEG Internals
-------------

A PEG parser takes a string as input and attempts to parse it as a given nonterminal. The key idea of the PEG implementation is that every nonterminal is just a function that takes a string as an argument and attempts to parse that string as its nonterminal. The functions always start from the beginning, but a parse is considered successful if there is material left over at the end.

This makes it easy to model different PEG parsing operations. For instance, consider the PEG grammar "ab", which could also be written (and "a" "b"). It matches the string ``ab''. Here's how that might be implemented in the PEG style:

     (define (match-and-a-b str)
       (match-a str)
       (match-b str))

As you can see, the use of functions provides an easy way to model sequencing. In a similar way, one could model (or a b) with something like the following:

     (define (match-or-a-b str)
       (or (match-a str) (match-b str)))

Here the semantics of a PEG or expression map naturally onto Scheme's or operator. This function will attempt to run (match-a str), and return its result if it succeeds. Otherwise it will run (match-b str).

Of course, the code above wouldn't quite work. We need some way for the parsing functions to communicate. The actual interface used is below.

Parsing Function Interface
..........................

A parsing function takes three arguments - a string, the length of that string, and the position in that string it should start parsing at. In effect, the parsing functions pass around substrings in pieces - the first argument is a buffer of characters, and the second two give a range within that buffer that the parsing function should look at.

Parsing functions return either #f, if they failed to match their nonterminal, or a list whose first element must be an integer representing the final position in the string they matched and whose cdr can be any other data the function wishes to return, or '() if it doesn't have any more data.

The one caveat is that if the extra data it returns is a list, any adjacent strings in that list will be appended by peg-parse. For instance, if a parsing function returns (13 ("a" "b" "c")), peg-parse will take (13 ("abc")) as its value.

For example, here is a function to match ``ab'' using the actual interface.

     (define (match-a-b str len pos)
        (and (<= (+ pos 2) len)
             (string= str "ab" pos (+ pos 2))
             (list (+ pos 2) '()))) ; we return no extra information

The above function can be used to match a string by running (peg-parse match-a-b "ab").

Code Generators and Extensible Syntax
.....................................

PEG expressions, such as those in a define-nonterm form, are interpreted internally in two steps.

First, any string PEG is expanded into an s-expression PEG by the code in the (ice-9 peg string-peg) module.

Then, then s-expression PEG that results is compiled into a parsing function by the (ice-9 peg codegen) module. In particular, the function peg-sexp-compile is called on the s-expression. It then decides what to do based on the form it is passed.

The PEG syntax can be expanded by providing peg-sexp-compile more options for what to do with its forms. The extended syntax will be associated with a symbol, for instance my-parsing-form, and will be called on all PEG expressions of the form

     (my-parsing-form ...)

The parsing function should take two arguments. The first will be a syntax object containing a list with all of the arguments to the form (but not the form's name), and the second will be the capture-type argument that is passed to define-nonterm.

New functions can be registered by calling (add-peg-compiler! symbol function), where symbol is the symbol that will indicate a form of this type and function is the code generating function described above. The function add-peg-compiler! is exported from the (ice-9 peg codegen) module.