PEG Parser

[Noah Lavine]

Hello all,

I was just looking at the PEG parser code, which is currently in the
"mlucy" branch of the Guile repo. I was looking at it to see if it was
ready to be merged.

First of all, it passes its test suite. This is pretty good, because
its test suite includes a grammar for itself, a grammar for basic
mathematical equations, and a grammar for parsing /etc/passwd files.
These all seem like good examples of things you'd want to parse.

I also looked at the code. It's pretty clear. I like the way it does
code generation by defining lots of little functions that generate
bits of code and then calling those functions. I tried to compare its
style to the existing LALR parser generator, but they're too different
- the LALR generator computes tables in advance but doesn't seem to
actually generate code (it just uses a pre-written driver function),
whereas the PEG parser generator doesn't do much other than generating
code. Also, the way it handles parsing descriptions of grammar is
really elegant - it first defines its code generator using an
s-expression representation of grammars, then uses an s-expression
representation of PEG grammar descriptions to parse PEG grammars
written as strings.

The only thing that seemed really weird is the macro safe-bind, which
basically reimplements hygienic macros. It's used all over the place
in the function-generating code. I also saw a couple of lines that
were too long, but not many, and the whole thing could be split into a
few modules, but it's not that long the way it is, so neither of those
seem like big issues. It could also stand to have a bigger test suite
(as the test suite itself says).

In summary, I think the code is good and functional, and should be
merged into Guile. I think it would also be very useful to have a PEG
parser generator.

Noah