From: Miles Bader <miles@gnu.org>
To: tomas@tuxteam.de
Cc: Richard Stallman <rms@gnu.org>,
deng@randomsample.de, cyd@stupidchicken.com, emacs-devel@gnu.org,
raeburn@raeburn.org, eric@siege-engine.com
Subject: Re: CEDET merge question
Date: Mon, 14 Sep 2009 21:15:02 +0900 [thread overview]
Message-ID: <buoab0xsoxl.fsf@dhlpc061.dev.necel.com> (raw)
In-Reply-To: <20090914112203.GA2231@tomas> (tomas@tuxteam.de's message of "Mon, 14 Sep 2009 13:22:03 +0200")
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.
next prev parent reply other threads:[~2009-09-14 12:15 UTC|newest]
Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-09-05 16:28 CEDET merge question Chong Yidong
2009-09-05 17:22 ` David Engster
2009-09-05 20:53 ` Chong Yidong
2009-09-05 23:08 ` David Engster
2009-09-06 15:37 ` Richard Stallman
2009-09-06 17:46 ` Ken Raeburn
2009-09-06 21:11 ` David Engster
2009-09-06 22:26 ` Ken Raeburn
2009-09-07 13:33 ` Richard Stallman
2009-09-12 12:49 ` Eric M. Ludlam
2009-09-12 13:37 ` Miles Bader
2009-09-13 16:39 ` Richard Stallman
2009-09-14 11:22 ` tomas
2009-09-14 12:15 ` Miles Bader [this message]
2009-09-14 20:04 ` tomas
2009-09-12 16:34 ` David Engster
2009-09-13 16:39 ` Richard Stallman
2009-09-13 17:38 ` Eric M. Ludlam
2009-09-14 18:28 ` Richard Stallman
2009-09-13 16:40 ` Richard Stallman
2009-09-07 13:34 ` Richard Stallman
2009-09-08 8:11 ` joakim
2009-09-08 9:07 ` Lennart Borgman
2009-09-08 9:09 ` Lennart Borgman
2009-09-08 14:41 ` Chong Yidong
2009-09-08 15:10 ` joakim
2009-09-08 17:18 ` Chong Yidong
2009-09-08 21:21 ` Romain Francoise
2009-09-08 22:27 ` Chong Yidong
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=buoab0xsoxl.fsf@dhlpc061.dev.necel.com \
--to=miles@gnu.org \
--cc=cyd@stupidchicken.com \
--cc=deng@randomsample.de \
--cc=emacs-devel@gnu.org \
--cc=eric@siege-engine.com \
--cc=raeburn@raeburn.org \
--cc=rms@gnu.org \
--cc=tomas@tuxteam.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.