Re: Parsing

[Mark H Weaver <mhw@netris.org>]

Ian Grant <ian.a.n.grant@googlemail.com> writes:

> LALR parser generators are not the last word in parsing technology.
[...]
> Important examples of grammars which are not LALR parsable include
> ASN.1 and Standard ML.
[...]
> But I think the problem of parsing has actually been solved. Tom
> Ridge's "p3" combinator parsers with oracles will parse any
> unambiguous CFG in polynomial time complexity at most O^3, or possibly
> O^2, I need to check, in the length of the input. The advantage of
> combinator parsers is that they parse top-down, in a way which follows
> the natural structure of the grammar. So errors can be explained to
> the user (and the developer!) in terms of the actual derivations
> (parsing decisions) taken on the input, This is not the case with
> bottom-up parsers such as LALR.
>
> It would be really good to have a p3-like parser generator working in
> Guile.

I agree that combinator parsers would be a useful addition to Guile.

> Again, one cold implement the recursive parser combinators in
> scheme-generated lightning. If this were done abstractly then Guile
> could generate fast machine code parsers for any host language.

I would prefer to work within the framework of our compiler tower,
and have the combinator parsers generate one of our higher-level
intermediate languages, if not scheme itself (via syntax-case macros).
This should enable our compiler to analyze the combined program and
perform partial evaluation between the generated parser and other scheme
code.  For many reasons, it makes sense to keep our code generation in
one place.

      Thanks,
        Mark