From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Miles Bader Newsgroups: gmane.emacs.devel Subject: Re: CEDET merge question Date: Mon, 14 Sep 2009 21:15:02 +0900 Message-ID: References: <87eiql2w5s.fsf@cyd.mit.edu> <87k50bixsl.fsf@engster.org> <1252759780.4770.76.camel@projectile.siege-engine.com> <87bplgthau.fsf@catnip.gol.com> <20090914112203.GA2231@tomas> Reply-To: Miles Bader NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1252930532 19333 80.91.229.12 (14 Sep 2009 12:15:32 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 14 Sep 2009 12:15:32 +0000 (UTC) Cc: Richard Stallman , deng@randomsample.de, cyd@stupidchicken.com, emacs-devel@gnu.org, raeburn@raeburn.org, eric@siege-engine.com To: tomas@tuxteam.de Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Sep 14 14:15:24 2009 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1MnASp-00020I-9x for ged-emacs-devel@m.gmane.org; Mon, 14 Sep 2009 14:15:23 +0200 Original-Received: from localhost ([127.0.0.1]:40566 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MnASo-0006VI-At for ged-emacs-devel@m.gmane.org; Mon, 14 Sep 2009 08:15:22 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1MnASi-0006VA-OB for emacs-devel@gnu.org; Mon, 14 Sep 2009 08:15:16 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1MnASe-0006T3-4D for emacs-devel@gnu.org; Mon, 14 Sep 2009 08:15:16 -0400 Original-Received: from [199.232.76.173] (port=38139 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MnASd-0006Sr-U7 for emacs-devel@gnu.org; Mon, 14 Sep 2009 08:15:11 -0400 Original-Received: from tyo201.gate.nec.co.jp ([202.32.8.193]:49048) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1MnASZ-0001e1-76; Mon, 14 Sep 2009 08:15:08 -0400 Original-Received: from relay31.aps.necel.com ([10.29.19.54]) by tyo201.gate.nec.co.jp (8.13.8/8.13.4) with ESMTP id n8ECEeph025670; Mon, 14 Sep 2009 21:15:03 +0900 (JST) Original-Received: from relay21.aps.necel.com ([10.29.19.24] [10.29.19.24]) by relay31.aps.necel.com with ESMTP; Mon, 14 Sep 2009 21:15:03 +0900 Original-Received: from dhlpc061 ([10.114.113.123] [10.114.113.123]) by relay21.aps.necel.com with ESMTP; Mon, 14 Sep 2009 21:15:03 +0900 Original-Received: by dhlpc061 (Postfix, from userid 31295) id 3529552E1E7; Mon, 14 Sep 2009 21:15:03 +0900 (JST) System-Type: x86_64-unknown-linux-gnu Blat: Foop In-Reply-To: <20090914112203.GA2231@tomas> (tomas@tuxteam.de's message of "Mon, 14 Sep 2009 13:22:03 +0200") Original-Lines: 75 X-detected-operating-system: by monty-python.gnu.org: Solaris 8 (1) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:115300 Archived-At: 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] 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 =E2=80=9Clarge amounts= of relatively flat=E2=80=9D 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=E2=80=99s 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 --=20 Back, n. That part of your friend which it is your privilege to contemplate= in your adversity.