Re: CEDET merge question

[Miles Bader <miles@gnu.org>]

tomas@tuxteam.de writes:
> PEG stands for "Parsing Expression Grammars" and it is a grammar
> notation which basically represents formally a recursive descent parser.
>
> They are said to be a bit more powerful than context free grammars and
> (usually) more expressive. The most salient point for us "old-timers"
> is probably that the choices are "ordered" -- this has some price, but
> we get someething for that: the distinction between lexer and parser
> becomes more flexible. The relevant paper seems to be [1].
>
> LPEG is the implementation of PEGs to be used in Lua.
>
> [1] <http://pdos.csail.mit.edu/~baford/packrat/popl04/peg-popl04.pdf>

Note that while LPEG is a PEG parser, it's _not_ a packrat parser (as in
[1]); the packrat algorithm is just an implementation technique.

I've appended a copy of an a message I sent a while ago to emacs-devel
on the same subject (LPEG vs. packrat).

Note that I think it's not just the implementation technique which is
interesting about LPEG, but also the very nice manner in which it's
integrated with the language and made available for use.  It's just an
amazingly powerful and handy tool.  I recommend reading the LPEG web
page, where it gives a quick overview of it.

Since Lua is in many ways feels quite similar to lisp, I think an elisp
version would be similarly very natural and powerful.  One difference
though -- for Lua, LPEG uses overloaded operators for building up
grammars; in elisp, it would probably be better to just use
s-expressions to represent grammars, using backquotes to embed
non-literal values.


[earlier message:]

You also might be interested in Roberto Ierusalimschy's paper on the
implemenation of LPEG, which is a PEG implementation for Lua:

  http://www.inf.puc-rio.br/~roberto/docs/peg.pdf


Note that LPEG does _not_ use the packrat algorithm, as apparently it
presents some serious practical problems for common uses of parsing
tools:

     In 2002, Ford proposed Packrat [5], an adaptation of the original
  algorithm that uses lazy evaluation to avoid that inefficiency.

     Even with this improvement, however, the space complexity of the
  algorithm is still linear on the subject size (with a somewhat big
  constant), even in the best case. As its author himself recognizes,
  this makes the algorithm not befitting for parsing “large amounts of
  relatively flat” data ([5], p. 57). However, unlike parsing tools,
  regular-expression tools aim exactly at large amounts of relatively
  flat data.

     To avoid these difficulties, we did not use the Packrat algorithm
  for LPEG. To implement LPEG we created a virtual parsing machine, not
  unlike Knuth’s parsing machine [15], where each pattern is
  represented as a program for the machine. The program is somewhat
  similar to a recursive-descendent parser (with limited backtracking)
  for the pattern, but it uses an explicit stack instead of recursion.


The general LPEG page is here:

  http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html


-Miles

-- 
Back, n. That part of your friend which it is your privilege to contemplate in
your adversity.