Re: LPEG and token lists

[Fabio Mascarenhas <mascarenhas@...>]

On Tue, Mar 16, 2010 at 6:21 AM, Michal Kottman <k0mpjut0r@gmail.com> wrote:
>> Is there some way to seduce LPEG into doing something like this as is
>> or am I out of luck?
>
> Hi, I'm not sure if this is what you are looking for, but I have just
> found this: http://github.com/mascarenhas/lpeg-list "Support for
> matching lists with LPEG".

I think Wesley wanted to do incremental parsing, but lpeg-list also
needs to have the whole list in memory, just like LPEG needs to have
the whole string in memory. Incremental parsing with PEGs is hard
because of the arbitrary lookahead and backtracking...

> Taken from the README file:
>
> p = re.compile([[
> exp <- { "add", <exp>, <exp> } -> add
>              / { "sub", <exp>, <exp> } -> sub
>              / { "mul", <exp>, <exp> } -> mul
>              / { "div", <exp>, <exp> } -> div
>              / <.>
>    ]], { add = function (x, y) return x + y end,
>          sub = function (x, y) return x - y end,
>          mul = function (x, y) return x * y end,
>          div = function (x, y) return x / y end, })
>
> assert(p:match{{ "add", { "div", 8, 2 }, 3 }} == 7)
>
> And from the paper:
>
> "Extending PEGs to match structured data make PEGs useful for a larger part of the
> compilation pipeline. A PEG-based scannerless parser can construct an abstract syntax
> tree..."
>
> Looks a lot like what you want to achieve. I hope it is what you are
> looking for.

Lpeg-list can transform a list of tokens into an AST easily enough,
but you don't gain much that way, it is just as easy to go directly
from the source string to the AST. I wrote it more as help for
processing the AST once it is ready, and for things like XPath-like
searches in a DOM.

It has been a while since I have worked on it, but the code works
quite well, apart from a quirky RE syntax, the buggy substitution
captures, and the fact that it only works on lists, not arbitrary
tables. I want to revisit this, as well as my other experiment with
LPEG (http://github.com/mascarenhas/leg), but am spread a little too
thin right now. :-)

>
> Michal
>

--
Fabio Mascarenhas