Re: how to use parsing expressing grammar

[Miles Bader]

W Dan Meyer <specuu@gmail.com> 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.