diff options
Diffstat (limited to 'doc/ref/api-peg.texi')
-rw-r--r-- | doc/ref/api-peg.texi | 1036 |
1 files changed, 1036 insertions, 0 deletions
diff --git a/doc/ref/api-peg.texi b/doc/ref/api-peg.texi new file mode 100644 index 000000000..0e16aab7e --- /dev/null +++ b/doc/ref/api-peg.texi @@ -0,0 +1,1036 @@ +@c -*-texinfo-*- +@c This is part of the GNU Guile Reference Manual. +@c Copyright (C) 2006, 2010, 2011 +@c Free Software Foundation, Inc. +@c See the file guile.texi for copying conditions. + +@node PEG Parsing +@section 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: +@url{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 +(@code{define-peg-pattern} and @code{define-peg-string-patterns}) or calculated +explicitly at runtime with the compile functions +(@code{compile-peg-pattern} and @code{peg-string-compile}). + +They can then be used for either parsing (@code{match-pattern}) or searching +(@code{search-for-pattern}). For convenience, @code{search-for-pattern} +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. + +@menu +* PEG Syntax Reference:: +* PEG API Reference:: +* PEG Tutorial:: +* PEG Internals:: +@end menu + +@node PEG Syntax Reference +@subsection PEG Syntax Reference + +@subsubheading Normal PEG Syntax: + +@deftp {PEG Pattern} sequence a b +Parses @var{a}. If this succeeds, continues to parse @var{b} from the +end of the text parsed as @var{a}. Succeeds if both @var{a} and +@var{b} succeed. + +@code{"a b"} + +@code{(and a b)} +@end deftp + +@deftp {PEG Pattern} {ordered choice} a b +Parses @var{a}. If this fails, backtracks and parses @var{b}. +Succeeds if either @var{a} or @var{b} succeeds. + +@code{"a/b"} + +@code{(or a b)} +@end deftp + +@deftp {PEG Pattern} {zero or more} a +Parses @var{a} as many times in a row as it can, starting each @var{a} +at the end of the text parsed by the previous @var{a}. Always +succeeds. + +@code{"a*"} + +@code{(* a)} +@end deftp + +@deftp {PEG Pattern} {one or more} a +Parses @var{a} as many times in a row as it can, starting each @var{a} +at the end of the text parsed by the previous @var{a}. Succeeds if at +least one @var{a} was parsed. + +@code{"a+"} + +@code{(+ a)} +@end deftp + +@deftp {PEG Pattern} optional a +Tries to parse @var{a}. Succeeds if @var{a} succeeds. + +@code{"a?"} + +@code{(? a)} +@end deftp + +@deftp {PEG Pattern} {followed by} a +Makes sure it is possible to parse @var{a}, but does not actually parse +it. Succeeds if @var{a} would succeed. + +@code{"&a"} + +@code{(followed-by a)} +@end deftp + +@deftp {PEG Pattern} {not followed by} a +Makes sure it is impossible to parse @var{a}, but does not actually +parse it. Succeeds if @var{a} would fail. + +@code{"!a"} + +@code{(not-followed-by a)} +@end deftp + +@deftp {PEG Pattern} {string literal} ``abc'' +Parses the string @var{"abc"}. Succeeds if that parsing succeeds. + +@code{"'abc'"} + +@code{"abc"} +@end deftp + +@deftp {PEG Pattern} {any character} +Parses any single character. Succeeds unless there is no more text to +be parsed. + +@code{"."} + +@code{peg-any} +@end deftp + +@deftp {PEG Pattern} {character class} a b +Alternative syntax for ``Ordered Choice @var{a} @var{b}'' if @var{a} and +@var{b} are characters. + +@code{"[ab]"} + +@code{(or "a" "b")} +@end deftp + +@deftp {PEG Pattern} {range of characters} a z +Parses any character falling between @var{a} and @var{z}. + +@code{"[a-z]"} + +@code{(range #\a #\z)} +@end deftp + +Example: + +@example +"(a !b / c &d*) 'e'+" +@end example + +Would be: + +@lisp +(and + (or + (and a (not-followed-by b)) + (and c (followed-by (* d)))) + (+ "e")) +@end lisp + +@subsubheading Extended Syntax + +There is some extra syntax for S-expressions. + +@deftp {PEG Pattern} ignore a +Ignore the text matching @var{a} +@end deftp + +@deftp {PEG Pattern} capture a +Capture the text matching @var{a}. +@end deftp + +@deftp {PEG Pattern} peg a +Embed the PEG pattern @var{a} using string syntax. +@end deftp + +Example: + +@example +"!a / 'b'" +@end example + +Is equivalent to + +@lisp +(or (peg "!a") "b") +@end lisp + +and + +@lisp +(or (not-followed-by a) "b") +@end lisp + +@node PEG API Reference +@subsection PEG API Reference + +@subsubheading Define Macros + +The most straightforward way to define a PEG is by using one of the +define macros (both of these macroexpand into @code{define} +expressions). These macros bind parsing functions to variables. These +parsing functions may be invoked by @code{match-pattern} or +@code{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. + +@deffn {Scheme Macro} define-peg-string-patterns peg-string +Defines all the nonterminals in the PEG @var{peg-string}. More +precisely, @code{define-peg-string-patterns} takes a superset of PEGs. A normal PEG +has a @code{<-} between the nonterminal and the pattern. +@code{define-peg-string-patterns} uses this symbol to determine what information it +should propagate up the parse tree. The normal @code{<-} propagates the +matched text up the parse tree, @code{<--} propagates the matched text +up the parse tree tagged with the name of the nonterminal, and @code{<} +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: +@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") +@end lisp +Then: +@lisp +(match-pattern as-or-bs "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> +(match-pattern as-or-bs-tag "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: (as-or-bs-tag (as-tag aa))> +@end lisp + +Note that in doing this, we have bound 6 variables at the toplevel +(@var{as}, @var{bs}, @var{as-or-bs}, @var{as-tag}, @var{bs-tag}, and +@var{as-or-bs-tag}). +@end deffn + +@deffn {Scheme Macro} define-peg-pattern name capture-type peg-sexp +Defines a single nonterminal @var{name}. @var{capture-type} determines +how much information is passed up the parse tree. @var{peg-sexp} is a +PEG in S-expression form. + +Possible values for capture-type: + +@table @code +@item all +passes the matched text up the parse tree tagged with the name of the +nonterminal. +@item body +passes the matched text up the parse tree. +@item none +passes nothing up the parse tree. +@end table + +For Example, if we: +@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)) +@end lisp +Then: +@lisp +(match-pattern as-or-bs "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> +(match-pattern as-or-bs-tag "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: (as-or-bs-tag (as-tag aa))> +@end lisp + +Note that in doing this, we have bound 6 variables at the toplevel +(@var{as}, @var{bs}, @var{as-or-bs}, @var{as-tag}, @var{bs-tag}, and +@var{as-or-bs-tag}). +@end deffn + +@subsubheading 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. + +@deffn {Scheme Procedure} peg-string-compile peg-string capture-type +Compiles the PEG pattern in @var{peg-string} propagating according to +@var{capture-type} (capture-type can be any of the values from +@code{define-peg-pattern}). +@end deffn + + +@deffn {Scheme Procedure} compile-peg-pattern peg-sexp capture-type +Compiles the PEG pattern in @var{peg-sexp} propagating according to +@var{capture-type} (capture-type can be any of the values from +@code{define-peg-pattern}). +@end deffn + +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: + +@lisp +(define exp '(+ "a")) +(define as (compile (compile-peg-pattern exp 'body))) +@end lisp + +You can use this nonterminal with all of the regular PEG functions: + +@lisp +(match-pattern as "aaaaa") @result{} +#<peg start: 0 end: 5 string: bbbbb tree: bbbbb> +@end lisp + +@subsubheading 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 @code{match-pattern} gives up if it can't +find a valid substring starting at index 0 and @code{search-for-pattern} keeps +looking. They are both equally capable of ``parsing'' and ``matching'' +given those constraints. + +@deffn {Scheme Procedure} match-pattern nonterm string +Parses @var{string} using the PEG stored in @var{nonterm}. If no match +was found, @code{match-pattern} returns false. If a match was found, a PEG +match record is returned. + +The @code{capture-type} argument to @code{define-peg-pattern} allows you to +choose what information to hold on to while parsing. The options are: + +@table @code +@item all +tag the matched text with the nonterminal +@item body +just the matched text +@item none +nothing +@end table + +@lisp +(define-peg-pattern as all (+ "a")) +(match-pattern as "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: (as aa)> + +(define-peg-pattern as body (+ "a")) +(match-pattern as "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> + +(define-peg-pattern as none (+ "a")) +(match-pattern as "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: ()> + +(define-peg-pattern bs body (+ "b")) +(match-pattern bs "aabbcc") @result{} +#f +@end lisp +@end deffn + +@deffn {Scheme Macro} search-for-pattern nonterm-or-peg string +Searches through @var{string} looking for a matching subexpression. +@var{nonterm-or-peg} can either be a nonterminal or a literal PEG +pattern. When a literal PEG pattern is provided, @code{search-for-pattern} works +very similarly to the regular expression searches many hackers are used +to. If no match was found, @code{search-for-pattern} returns false. If a match +was found, a PEG match record is returned. + +@lisp +(define-peg-pattern as body (+ "a")) +(search-for-pattern as "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> +(search-for-pattern (+ "a") "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> +(search-for-pattern "'a'+" "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: aa> + +(define-peg-pattern as all (+ "a")) +(search-for-pattern as "aabbcc") @result{} +#<peg start: 0 end: 2 string: aabbcc tree: (as aa)> + +(define-peg-pattern bs body (+ "b")) +(search-for-pattern bs "aabbcc") @result{} +#<peg start: 2 end: 4 string: aabbcc tree: bb> +(search-for-pattern (+ "b") "aabbcc") @result{} +#<peg start: 2 end: 4 string: aabbcc tree: bb> +(search-for-pattern "'b'+" "aabbcc") @result{} +#<peg start: 2 end: 4 string: aabbcc tree: bb> + +(define-peg-pattern zs body (+ "z")) +(search-for-pattern zs "aabbcc") @result{} +#f +(search-for-pattern (+ "z") "aabbcc") @result{} +#f +(search-for-pattern "'z'+" "aabbcc") @result{} +#f +@end lisp +@end deffn + +@subsubheading PEG Match Records +The @code{match-pattern} and @code{search-for-pattern} functions both return PEG +match records. Actual information can be extracted from these with the +following functions. + +@deffn {Scheme Procedure} peg:string match-record +Returns the original string that was parsed in the creation of +@code{match-record}. +@end deffn + +@deffn {Scheme Procedure} peg:start match-record +Returns the index of the first parsed character in the original string +(from @code{peg:string}). If this is the same as @code{peg:end}, +nothing was parsed. +@end deffn + +@deffn {Scheme Procedure} peg:end match-record +Returns one more than the index of the last parsed character in the +original string (from @code{peg:string}). If this is the same as +@code{peg:start}, nothing was parsed. +@end deffn + +@deffn {Scheme Procedure} peg:substring match-record +Returns the substring parsed by @code{match-record}. This is equivalent to +@code{(substring (peg:string match-record) (peg:start match-record) (peg:end +match-record))}. +@end deffn + +@deffn {Scheme Procedure} peg:tree match-record +Returns the tree parsed by @code{match-record}. +@end deffn + +@deffn {Scheme Procedure} peg-record? match-record +Returns true if @code{match-record} is a PEG match record, or false +otherwise. +@end deffn + +Example: +@lisp +(define-peg-pattern bs all (peg "'b'+")) + +(search-for-pattern bs "aabbcc") @result{} +#<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)))) @result{} +((string "aabbcc") + (start 2) + (end 4) + (substring "bb") + (tree (bs "bb")) + (record? #t)) +@end lisp + +@subsubheading Miscellaneous + +@deffn {Scheme Procedure} context-flatten tst lst +Takes a predicate @var{tst} and a list @var{lst}. Flattens @var{lst} +until all elements are either atoms or satisfy @var{tst}. If @var{lst} +itself satisfies @var{tst}, @code{(list lst)} is returned (this is a +flat list whose only element satisfies @var{tst}). + +@lisp +(context-flatten (lambda (x) (and (number? (car x)) (= (car x) 1))) '(2 2 (1 1 (2 2)) (2 2 (1 1)))) @result{} +(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)))) @result{} +((1 1 (1 1 (2 2)) (2 2 (1 1)))) +@end lisp + +If you're wondering why this is here, take a look at the tutorial. +@end deffn + +@deffn {Scheme Procedure} keyword-flatten terms lst +A less general form of @code{context-flatten}. Takes a list of terminal +atoms @code{terms} and flattens @var{lst} until all elements are either +atoms, or lists which have an atom from @code{terms} as their first +element. +@lisp +(keyword-flatten '(a b) '(c a b (a c) (b c) (c (b a) (c a)))) @result{} +(c a b (a c) (b c) c (b a) c a) +@end lisp + +If you're wondering why this is here, take a look at the tutorial. +@end deffn + +@node PEG Tutorial +@subsection PEG Tutorial + +@subsubheading Parsing /etc/passwd +This example will show how to parse /etc/passwd using PEGs. + +First we define an example /etc/passwd file: + +@lisp +(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 +") +@end lisp + +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: +@lisp +(define-peg-string-patterns + "passwd <- entry* !. +entry <-- (! NL .)* NL* +NL < '\n'") +@end lisp + +A @code{passwd} file is 0 or more entries (@code{entry*}) until the end +of the file (@code{!.} (@code{.} is any character, so @code{!.} means +``not anything'')). We want to capture the data in the nonterminal +@code{passwd}, but not tag it with the name, so we use @code{<-}. + +An entry is a series of 0 or more characters that aren't newlines +(@code{(! NL .)*}) followed by 0 or more newlines (@code{NL*}). We want +to tag all the entries with @code{entry}, so we use @code{<--}. + +A newline is just a literal newline (@code{'\n'}). We don't want a +bunch of newlines cluttering up the output, so we use @code{<} to throw +away the captured data. + +Here is the same PEG defined using S-expressions: +@lisp +(define-peg-pattern passwd body (and (* entry) (not-followed-by peg-any))) +(define-peg-pattern entry all (and (* (and (not-followed-by NL) peg-any)) + (* NL))) +(define-peg-pattern NL none "\n") +@end lisp + +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 @code{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 @code{NL}. In +the S-expression syntax, we could have simply written @code{(ignore +"\n")}. Also, for the cases where string syntax is really much cleaner, +the @code{peg} keyword can be used to embed string syntax in +S-expression syntax. For instance, we could have written: + +@lisp +(define-peg-pattern passwd body (peg "entry* !.")) +@end lisp + +However we define it, parsing @code{*etc-passwd*} with the @code{passwd} +nonterminal yields the same results: + +@lisp +(peg:tree (match-pattern passwd *etc-passwd*)) @result{} +((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")) +@end lisp + +However, here is something to be wary of: + +@lisp +(peg:tree (match-pattern passwd "one entry")) @result{} +(entry "one entry") +@end lisp + +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 @code{((entry "one entry"))} is +compressed to @code{(entry "one entry")}, but in this particular case it +probably isn't what we want. + +There are two functions for easily dealing with this: +@code{keyword-flatten} and @code{context-flatten}. The +@code{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 @code{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 @code{keyword-flatten}. +@lisp +(keyword-flatten '(entry) (peg:tree (match-pattern passwd *etc-passwd*))) @result{} +((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 (match-pattern passwd "one entry"))) @result{} +((entry "one entry")) +@end lisp + +Of course, this is a somewhat contrived example. In practice we would +probably just tag the @code{passwd} nonterminal to remove the ambiguity +(using either the @code{all} keyword for S-expressions or the @code{<--} +symbol for strings).. + +@lisp +(define-peg-pattern tag-passwd all (peg "entry* !.")) +(peg:tree (match-pattern tag-passwd *etc-passwd*)) @result{} +(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 (match-pattern tag-passwd "one entry")) +(tag-passwd + (entry "one entry")) +@end lisp + +If you're ever uncertain about the potential results of parsing +something, remember the two absolute rules: +@enumerate +@item +No parsing information will ever be discarded. +@item +There will never be any lists with fewer than 2 elements. +@end enumerate + +For the purposes of (1), "parsing information" means things tagged with +the @code{any} keyword or the @code{<--} 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: + +@lisp +(define-peg-string-patterns + "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 < '/'") +@end lisp + +This produces rather pretty parse trees: +@lisp +(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"))))) +@end lisp + +Notice that when there's no entry in a field (e.g. @code{nameORcomment} +for messagebus) the symbol is inserted. This is the ``don't throw away +any information'' rule---we succesfully matched a @code{nameORcomment} +of 0 characters (since we used @code{*} when defining it). This is +usually what you want, because it allows you to e.g. use @code{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 @code{*} with a @code{+} and add a @code{?} after the +@code{nameORcomment} in @code{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. + + +@subsubheading Embedding Arithmetic Expressions + +We can parse simple mathematical expressions with the following PEG: + +@lisp +(define-peg-string-patterns + "expr <- sum +sum <-- (product ('+' / '-') sum) / product +product <-- (value ('*' / '/') product) / value +value <-- number / '(' expr ')' +number <-- [0-9]+") +@end lisp + +Then: +@lisp +(peg:tree (match-pattern expr "1+1/2*3+(1+1)/2")) @result{} +(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"))))))) +@end lisp + +There is very little wasted effort in this PEG. The @code{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: + +@lisp +(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) +@end lisp + +(Notice all these functions look very similar; for a more complicated +PEG, it would be worth abstracting.) + +Then: +@lisp +(apply parse-expr (peg:tree (match-pattern expr "1+1/2*3+(1+1)/2"))) @result{} +(+ 1 (+ (/ 1 (* 2 3)) (/ (+ 1 1) 2))) +@end lisp + +But wait! The associativity is wrong! Where it says @code{(/ 1 (* 2 +3))}, it should say @code{(* (/ 1 2) 3)}. + +It's tempting to try replacing e.g. @code{"sum <-- (product ('+' / '-') +sum) / product"} with @code{"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 @code{sum}, it first has to try and parse @code{sum}. But to do +that, it first has to try and parse @code{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: + +@lisp +(use-modules (srfi srfi-1)) + +(define-peg-string-patterns + "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) +@end lisp + +Then: +@lisp +(apply parse-expr (peg:tree (match-pattern expr "1+1/2*3+(1+1)/2"))) @result{} +(+ (+ 1 (* (/ 1 2) 3)) (/ (+ 1 1) 2)) +@end lisp + +As you can see, this is much uglier (it could be made prettier by using +@code{context-flatten}, but the way it's written above makes it clear +how we deal with the three ways the zero-or-more @code{*} expression can +parse). Fortunately, most of the time we can get away with only using +right-associativity. + +@subsubheading Simplified Functions + +For a more tantalizing example, consider the following grammar that +parses (highly) simplified C functions: + +@lisp +(define-peg-string-patterns + "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]*") +@end lisp + +Then: +@lisp +(match-pattern cfunc "int square(int a) @{ return a*a;@}") @result{} +(32 + (cfunc (ctype "int") + (cname "square") + (cargs (carg (ctype "int") (cname "a"))) + (cbody (cstatement "return a*a")))) +@end lisp + +And: +@lisp +(match-pattern cfunc "int mod(int a, int b) @{ int c = a/b;return a-b*c; @}") @result{} +(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")))) +@end lisp + +By wrapping all the @code{carg} nonterminals in a @code{cargs} +nonterminal, we were able to remove any ambiguity in the parsing +structure and avoid having to call @code{context-flatten} on the output +of @code{match-pattern}. We used the same trick with the @code{cstatement} +nonterminals, wrapping them in a @code{cbody} nonterminal. + +The whitespace nonterminal @code{cSP} used here is a (very) useful +instantiation of a common pattern for matching syntactically irrelevant +information. Since it's tagged with @code{<} and ends with @code{*} 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. + +@node PEG Internals +@subsection 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 @code{"ab"}, which could also be +written @code{(and "a" "b")}. It matches the string ``ab''. Here's how +that might be implemented in the PEG style: + +@lisp +(define (match-and-a-b str) + (match-a str) + (match-b str)) +@end lisp + +As you can see, the use of functions provides an easy way to model +sequencing. In a similar way, one could model @code{(or a b)} with +something like the following: + +@lisp +(define (match-or-a-b str) + (or (match-a str) (match-b str))) +@end lisp + +Here the semantics of a PEG @code{or} expression map naturally onto +Scheme's @code{or} operator. This function will attempt to run +@code{(match-a str)}, and return its result if it succeeds. Otherwise it +will run @code{(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. + +@subsubheading 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 @code{match-pattern}. For +instance, if a parsing function returns @code{(13 ("a" "b" "c"))}, +@code{match-pattern} will take @code{(13 ("abc"))} as its value. + +For example, here is a function to match ``ab'' using the actual +interface. + +@lisp +(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 +@end lisp + +The above function can be used to match a string by running +@code{(match-pattern match-a-b "ab")}. + +@subsubheading Code Generators and Extensible Syntax + +PEG expressions, such as those in a @code{define-peg-pattern} form, are +interpreted internally in two steps. + +First, any string PEG is expanded into an s-expression PEG by the code +in the @code{(ice-9 peg string-peg)} module. + +Then, then s-expression PEG that results is compiled into a parsing +function by the @code{(ice-9 peg codegen)} module. In particular, the +function @code{compile-peg-pattern} 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 @code{compile-peg-pattern} more +options for what to do with its forms. The extended syntax will be +associated with a symbol, for instance @code{my-parsing-form}, and will +be called on all PEG expressions of the form +@lisp +(my-parsing-form ...) +@end lisp + +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 +@code{capture-type} argument that is passed to @code{define-peg-pattern}. + +New functions can be registered by calling @code{(add-peg-compiler! +symbol function)}, where @code{symbol} is the symbol that will indicate +a form of this type and @code{function} is the code generating function +described above. The function @code{add-peg-compiler!} is exported from +the @code{(ice-9 peg codegen)} module. |