Emacs Docs

Appearance

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 match-pattern or search-for-pattern, 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-peg-string-patterns peg-string ​

Defines all the nonterminals in the PEG peg-string. More precisely, define-peg-string-patterns takes a superset of PEGs. A normal PEG has a <- between the nonterminal and the pattern. define-peg-string-patterns 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 include “-” character, while in normal PEG it is not allowed.

For example, if we:

emacs-lisp
(define-peg-string-patterns 
  "as <- 'a'+
bs <- 'b'+
as-or-bs <- as/bs")
(define-peg-string-patterns 
  "as-tag <-- 'a'+
bs-tag <-- 'b'+
as-or-bs-tag <-- as-tag/bs-tag")

Then:

emacs-lisp
(match-pattern as-or-bs "aabbcc") ⇒
#<peg start: 0 end: 2 string: aabbcc tree: aa>
(match-pattern 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-peg-pattern 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:

emacs-lisp
(define-peg-pattern as body (+ "a"))
(define-peg-pattern bs body (+ "b"))
(define-peg-pattern as-or-bs body (or as bs))
(define-peg-pattern as-tag all (+ "a"))
(define-peg-pattern bs-tag all (+ "b"))
(define-peg-pattern as-or-bs-tag all (or as-tag bs-tag))

Then:

emacs-lisp
(match-pattern as-or-bs "aabbcc") ⇒ 
#<peg start: 0 end: 2 string: aabbcc tree: aa>
(match-pattern 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).

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-peg-pattern).

Scheme Procedure: compile-peg-pattern 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-peg-pattern).

The functions return syntax objects, which can be useful if you want to use them in macros. If all you want is to define a new nonterminal, you can do the following:

emacs-lisp
(define exp '(+ "a"))
(define as (compile (compile-peg-pattern exp 'body)))

You can use this nonterminal with all of the regular PEG functions:

emacs-lisp
(match-pattern as "aaaaa") ⇒
#<peg start: 0 end: 5 string: aaaaa tree: aaaaa>

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 match-pattern gives up if it can’t find a valid substring starting at index 0 and search-for-pattern keeps looking. They are both equally capable of “parsing” and “matching” given those constraints.

Scheme Procedure: match-pattern nonterm string ​

Parses string using the PEG stored in nonterm. If no match was found, match-pattern returns false. If a match was found, a PEG match record is returned.

The capture-type argument to define-peg-pattern 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

emacs-lisp
(define-peg-pattern as all (+ "a"))
(match-pattern as "aabbcc") ⇒ 
#<peg start: 0 end: 2 string: aabbcc tree: (as aa)>

(define-peg-pattern as body (+ "a"))
(match-pattern as "aabbcc") ⇒ 
#<peg start: 0 end: 2 string: aabbcc tree: aa>

(define-peg-pattern as none (+ "a"))
(match-pattern as "aabbcc") ⇒ 
#<peg start: 0 end: 2 string: aabbcc tree: ()>

(define-peg-pattern bs body (+ "b"))
(match-pattern bs "aabbcc") ⇒ 
#f

Scheme Macro: search-for-pattern 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, search-for-pattern works very similarly to the regular expression searches many hackers are used to. If no match was found, search-for-pattern returns false. If a match was found, a PEG match record is returned.

emacs-lisp
(define-peg-pattern as body (+ "a"))
(search-for-pattern as "aabbcc") ⇒ 
#<peg start: 0 end: 2 string: aabbcc tree: aa>
(search-for-pattern (+ "a") "aabbcc") ⇒ 
#<peg start: 0 end: 2 string: aabbcc tree: aa>
(search-for-pattern "'a'+" "aabbcc") ⇒ 
#<peg start: 0 end: 2 string: aabbcc tree: aa>

(define-peg-pattern as all (+ "a"))
(search-for-pattern as "aabbcc") ⇒ 
#<peg start: 0 end: 2 string: aabbcc tree: (as aa)>

(define-peg-pattern bs body (+ "b"))
(search-for-pattern bs "aabbcc") ⇒ 
#<peg start: 2 end: 4 string: aabbcc tree: bb>
(search-for-pattern (+ "b") "aabbcc") ⇒ 
#<peg start: 2 end: 4 string: aabbcc tree: bb>
(search-for-pattern "'b'+" "aabbcc") ⇒ 
#<peg start: 2 end: 4 string: aabbcc tree: bb>

(define-peg-pattern zs body (+ "z"))
(search-for-pattern zs "aabbcc") ⇒ 
#f
(search-for-pattern (+ "z") "aabbcc") ⇒ 
#f
(search-for-pattern "'z'+" "aabbcc") ⇒ 
#f

PEG Match Records ​

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

Scheme Procedure: peg:string match-record ​

Returns the original string that was parsed in the creation of match-record.

Scheme Procedure: peg:start match-record ​

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 match-record ​

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 match-record ​

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

Scheme Procedure: peg:tree match-record ​

Returns the tree parsed by match-record.

Scheme Procedure: peg-record? match-record ​

Returns true if match-record is a PEG match record, or false otherwise.

Example:

emacs-lisp
(define-peg-pattern bs all (peg "'b'+"))

(search-for-pattern bs "aabbcc") ⇒
#<peg start: 2 end: 4 string: aabbcc tree: (bs bb)>

(let ((pm (search-for-pattern 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).

emacs-lisp
(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.

emacs-lisp
(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.