Warning: This is the manual of the legacy Guile 2.2 series. You may want to read the manual of the current stable series instead.

Next: , Previous: , Up: PEG Parsing   [Contents][Index]

6.17.3 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-peg-string-patterns
  "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-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")

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-peg-pattern passwd body (peg "entry* !."))

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

(peg:tree (match-pattern 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 (match-pattern 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 (match-pattern 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 (match-pattern 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-peg-pattern tag-passwd all (peg "entry* !."))
(peg:tree (match-pattern 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 (match-pattern 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-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 < '/'")

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-peg-string-patterns
  "expr <- sum
sum <-- (product ('+' / '-') sum) / product
product <-- (value ('*' / '/') product) / value
value <-- number / '(' expr ')'
number <-- [0-9]+")

Then: 

(peg:tree (match-pattern 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 (match-pattern 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-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)

Then: 

(apply parse-expr (peg:tree (match-pattern 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-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]*")

Then: 

(match-pattern 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: 

(match-pattern 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 match-pattern. 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.

Next: , Previous: , Up: PEG Parsing   [Contents][Index]