From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Miles Bader Newsgroups: gmane.emacs.help Subject: Re: how to use parsing expressing grammar Date: Wed, 04 Mar 2009 09:35:00 +0900 Message-ID: <87d4cyqg5n.fsf@catnip.gol.com> References: <6b8a1070-1a89-48b0-9287-343b673b5758@a29g2000pra.googlegroups.com> <098ddc5b-7074-41fb-a921-caee3bddddff@t39g2000prh.googlegroups.com> <91fa65a0-a7e7-4374-8f96-5786c8908615@w24g2000prd.googlegroups.com> <067151a4-b892-4e9a-8600-e2dcd92cb0ad@v18g2000pro.googlegroups.com> <87fxhukvuu.fsf@gmail.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1236127255 21834 80.91.229.12 (4 Mar 2009 00:40:55 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 4 Mar 2009 00:40:55 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Wed Mar 04 01:42:10 2009 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1LefBZ-0003G2-0N for geh-help-gnu-emacs@m.gmane.org; Wed, 04 Mar 2009 01:42:09 +0100 Original-Received: from localhost ([127.0.0.1]:36165 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LefAD-0004Ou-NM for geh-help-gnu-emacs@m.gmane.org; Tue, 03 Mar 2009 19:40:45 -0500 Original-Path: news.stanford.edu!newsfeed.stanford.edu!news.tele.dk!news.tele.dk!small.news.tele.dk!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail Original-Newsgroups: gnu.emacs.help,comp.emacs,comp.lang.lisp Original-Lines: 46 Original-X-Trace: individual.net 3VzhhYylHJPeXcWQfAhusAtmiTUFiyAvZ4CoWwbuZgTICLFlaG Cancel-Lock: sha1:V7JPDz0b4bbk1xrYfH8/OWMP/6Q= sha1:nXqu4YfYiTNkz4xwEsqkyAYS9JY= System-Type: x86_64-unknown-linux-gnu Original-Xref: news.stanford.edu gnu.emacs.help:167271 comp.emacs:97917 comp.lang.lisp:262169 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:62565 Archived-At: W Dan Meyer writes: > Are we talking about memoising PEG (e.g Packrat) in elisp? ... > Packrat parser is the best option out there currently because it > recognises much complex grammar then LALR(1), and it has no > ambiguities with expressing these grammars. 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 -- Justice, n. A commodity which in a more or less adulterated condition the State sells to the citizen as a reward for his allegiance, taxes and personal service.