Why doesn't Spirit use an Earley parser?

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Why doesn't Spirit use an Earley parser?

tyler

Is there any reason why Spirit doesn't use an Earley parser? I mean, you get all context-free grammars and, from what I've read, little to no cost for LR/LALR grammars.

I'm thinking of writing a Spirit-like library based on a Earley parser. Are there any reasons that would be a bad idea?

Thanks,
Tyler


------------------------------------------------------------------------------

_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Why doesn't Spirit use an Earley parser?

Michael Powell-2
On Tue, Jun 2, 2015 at 3:54 PM, Tyler Hardin <[hidden email]> wrote:
> Is there any reason why Spirit doesn't use an Earley parser? I mean, you get
> all context-free grammars and, from what I've read, little to no cost for
> LR/LALR grammars.

Can't speak to closely to the technicalities, but there have been a
lot of studies done on speed / performance improvements.

http://en.wikipedia.org/wiki/Earley_parser

Don't know how that compares with O(n^3) though... What is n? Cubic?! Yikes!

As compared / contrasted with Spirit? Qi? X3?

> I'm thinking of writing a Spirit-like library based on a Earley parser. Are
> there any reasons that would be a bad idea?
>
> Thanks,
> Tyler
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> Spirit-general mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/spirit-general
>

------------------------------------------------------------------------------
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Why doesn't Spirit use an Earley parser?

tyler

That Wikipedia page says it runs in linear time for most LR grammars. Since Spirit only supports LR grammars (or maybe a subset thereof), Earley would be equivalent for most current use cases.


------------------------------------------------------------------------------

_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Why doesn't Spirit use an Earley parser?

Joel de Guzman
On 6/3/15 10:02 AM, Tyler Hardin wrote:
> That Wikipedia page says it runs in linear time for most LR grammars. Since Spirit only
> supports LR grammars (or maybe a subset thereof), Earley would be equivalent for most
> current use cases.

Correction: Spirit is LL. There's always this debate on top-down vs.
bottom up. Recursive descent is top down.


Regards,
--
Joel de Guzman
http://www.ciere.com
http://boost-spirit.com
http://www.cycfi.com/


------------------------------------------------------------------------------
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Why doesn't Spirit use an Earley parser?

tyler
LL < LR, I think. I was (over?) simplifying. Since LR subsumes LL and it is linear for most LR, it will be linear for most LL.

I'm not really taking a stance on bottom-up vs top-down. I'm just saying that, for nearly equal performance and better capabilities, it would make sense to use Earley or GLR. I'm here to see if it was considered first and to ask why it wasn't used, given its seeming superiority. There's a lot of experience behind Spirit. If y'all chose not to take what seems like the obvious course of action, then I can only assume there must have been a good reason not to.

On Tue, Jun 2, 2015 at 10:16 PM, Joel de Guzman <[hidden email]> wrote:
On 6/3/15 10:02 AM, Tyler Hardin wrote:
> That Wikipedia page says it runs in linear time for most LR grammars. Since Spirit only
> supports LR grammars (or maybe a subset thereof), Earley would be equivalent for most
> current use cases.

Correction: Spirit is LL. There's always this debate on top-down vs.
bottom up. Recursive descent is top down.


Regards,
--
Joel de Guzman
http://www.ciere.com
http://boost-spirit.com
http://www.cycfi.com/


------------------------------------------------------------------------------
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general


------------------------------------------------------------------------------

_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Why doesn't Spirit use an Earley parser?

Joel de Guzman
On 6/3/15 11:25 AM, Tyler Hardin wrote:
> LL < LR, I think. I was (over?) simplifying. Since LR subsumes LL and it is linear for
> most LR, it will be linear for most LL.
>
> I'm not really taking a stance on bottom-up vs top-down. I'm just saying that, for nearly
> equal performance and better capabilities, it would make sense to use Earley or GLR. I'm
> here to see if it was considered first and to ask why it wasn't used, given its seeming
> superiority. There's a lot of experience behind Spirit. If y'all chose not to take what
> seems like the obvious course of action, then I can only assume there must have been a
> good reason not to.

Parser-combinators (like Spirit) tend to be PEG and RD. It is inherent.

(BTW: GCC is now using RD. GCC once used YACC, but LR proved to be
problematic in many aspects.) Interestingly, RD proves to be superior
in performance!)

Regards,
--
Joel de Guzman
http://www.ciere.com
http://boost-spirit.com
http://www.cycfi.com/


------------------------------------------------------------------------------
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Why doesn't Spirit use an Earley parser?

Richard-45

In article <mklvcr$7jm$[hidden email]>,
    Joel de Guzman <[hidden email]> writes:

> (BTW: GCC is now using RD. GCC once used YACC, but LR proved to be
> problematic in many aspects.) Interestingly, RD proves to be superior
> in performance!)

I think Clang is also recursive-descent using a hand-written parser.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
     The Computer Graphics Museum <http://ComputerGraphicsMuseum.org>
         The Terminals Wiki <http://terminals.classiccmp.org>
  Legalize Adulthood! (my blog) <http://LegalizeAdulthood.wordpress.com>

------------------------------------------------------------------------------
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Why doesn't Spirit use an Earley parser?

Joel de Guzman
On 6/4/15 1:08 AM, Richard wrote:
>
> In article <mklvcr$7jm$[hidden email]>,
>      Joel de Guzman <[hidden email]> writes:
>
>> (BTW: GCC is now using RD. GCC once used YACC, but LR proved to be
>> problematic in many aspects.) Interestingly, RD proves to be superior
>> in performance!)
>
> I think Clang is also recursive-descent using a hand-written parser.

Yes it is!

Regards,
--
Joel de Guzman
http://www.ciere.com
http://boost-spirit.com
http://www.cycfi.com/


------------------------------------------------------------------------------
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Why doesn't Spirit use an Earley parser?

Ben Hanson
In reply to this post by tyler
tyler wrote
I'm thinking of writing a Spirit-like library based on a Earley parser. Are there any reasons that would be a bad idea?
I'm very interested in this. I also found the following an interesting read: http://blogs.perl.org/users/jeffrey_kegler/2013/04/is-earley-parsing-fast-enough.html

To be blunt, it would be nice to have tools that go beyond LL and LALR(1). To quote Dick Grune and Ceriel J.H. Jacobs in PARSING TECHNIQUES A Practical Guide "In summary, LR(k) parsers are the strongest deterministic parsers possible and they are the strongest linear-time parsers known, with the exception of some non-canonical parsers; ... They react to errors immediately, are paragons of virtue and beyond compare, but even after 40 years they are not widely used."

Although the Earley algorithm is a little left field, it would be fascinating to see how it performs in reality and would be a lot easier to implement than LALR(k).

Regards,

Ben Hanson