Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-06-02

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary

All times shown according to UTC.

Time Nick Message
00:12 sadmac jeffreykegler: so I wrote an Earley parser and it's incredibly slow and I can't figure out why.
01:00 jeffreykegler sadmac: there are a lot of things that can make an Earley implementation slow -- so many that it has been thought that Earley's *must* be slow
01:05 sadmac jeffreykegler: I'm seeing 100x as many states as there are AST nodes in the final tree. does that sound right?
01:06 jeffreykegler No, it doesn't
01:06 sadmac hmm
01:06 sadmac the traces look right, but they're massive, so eyeballing them may not be the best way
01:06 jeffreykegler Is this a implementation of the classic, pre-Leo, pre-Marpa Earley's
01:06 jeffreykegler ?
01:07 sadmac I don't exactly do leo, but I believe this grammar is right-recursion free. I have support for the kleene star, and basically rewriting right recursive rules to rules that use that is equivalent to leo.
01:07 sadmac I thought to go aycock-horspool when I saw the state numbers, but I know you said that wasn't worth it and ditched it for marpa
01:08 jeffreykegler No need to apologize for no Leo, I am just trying to understand the situation
01:08 sadmac naturally
01:08 jeffreykegler If it is classic Earley's then ...
01:08 jeffreykegler I suggest getting a text which describes the exact states for a small example.
01:08 jeffreykegler And seeing if yours match state-for-state.
01:09 jeffreykegler That's how I started Marpa, 8 years ago, parsing a textbook example and checking state by state.
01:09 sadmac alright. any idea where I can find examples that are particularly likely to be pathological?
01:10 jeffreykegler I used the one from the Aycock&Horspool paper a lot.
01:10 sadmac ok
01:10 jeffreykegler I think the Wikipedia article may have another.
01:11 sadmac I do have some other fancy features that may be interfering. I can look at those.
01:11 jeffreykegler Don't be afraid to go back to very small -- stupidly small - examples ...
01:11 jeffreykegler Marpa started with stupidly small examples.
01:11 sadmac naturally
01:13 jeffreykegler And come to think of it, don't the Loup Vailliant blog pieces have small examples?
01:14 sadmac I think so, if I'm thinking of the right blog
01:14 jeffreykegler http://loup-vaillant.fr/tutorials/earley-parsing/
01:17 sadmac excellent
04:12 rns joined #marpa
04:19 rns jeffreykegler: re http://irclog.perlgeek.de/m​arpa/2015-06-01#i_10685344 -- the prototype is mostly Direct-2-Lua (D2L) calls in https://github.com/rns/libmarpa-bind​ings/blob/master/lua/kollos/luif.lua, test is https://github.com/rns/libmarpa-binding​s/blob/master/lua/kollos/test/d2l.t.lua
04:24 rns Now it has iterators over rules, rhs alternatives and symbols and just print the data. The plan is to build xrule/xsym database for KHIL and, with the help of THIF for LUIF (mostly works -- https://github.com/rns/libmarpa-bindings​/blob/master/lua/kollos/test/json.t.lua) -- prototype luif.V values per https://github.com/rns/kollos-luif-​doc/issues/26#issuecomment-98681263.
04:24 jeffreykegler I'm looking it over now ...
04:24 rns ok
04:25 jeffreykegler I think now that I want to do semantics, rather than try to type it into the KIR format, it's best to tackle the pre-processing.
04:25 jeffreykegler Not much slower and it gets a task done that will eventually need doing, while I have a good test case for it.
04:26 jeffreykegler So I am thinking of doing a Marpa::R2 LUIF to KIR calculator example & then a JSON example
04:26 jeffreykegler That is, I will use Marpa::R2 for the LUIF parsing.
04:28 rns Ok, perhaps you can find MarpaX::Languages::Lua::AST useful -- it has a working Lua grammar sans precedence.
04:28 jeffreykegler Yes, I can start there.
04:29 jeffreykegler Re D2L, as I work out how I'd write the code ...
04:29 jeffreykegler I'm discovering something about adopting Roberto's syntax, which is bad news for the design so far.
04:30 jeffreykegler LPeG is procedural and we are declarative -- what we really need is an AST, not procedure calls.
04:31 jeffreykegler One transforms into the other, of course, but perhaps you understand what I am getting at.
04:34 rns Well, I do -- I tried those calls to build a grammar that was no impossible, but didn't feel right. On the other hand, i've find it to be good in trying to build a libmarpa binding with a lexer in libmarpa.
04:34 rns So I kind of see the point.
04:34 jeffreykegler I just forked MarpaX-Languages-Lua-AST -- I may diverge rapidly ...
04:35 jeffreykegler we can figure out later perhaps whether to re-integrate, or just stay forked. :-)
04:36 jeffreykegler re http://irclog.perlgeek.de/m​arpa/2015-06-02#i_10688193 , the D2L design -- I paid careful attention while you were creating it, and all seemed fine, but now that I am trying to pseudo-code in my head, I am seeing the issue.
04:37 jeffreykegler It's been an issue for Marpa throughout its history -- my intent originally was never (or almost never) to create a new interface, just leverage existing work ...
04:38 jeffreykegler which seemed reasonable given the literature is decades old and voluminous ...
04:39 jeffreykegler but it turns out Marpa breaks such new ground for a practical parser that there is almost nothing out there in the way of interfaces that I can just "lift" as is.
04:40 jeffreykegler It may look like I'm the kind of guy who just *loves* to invent new interfaces (and there are lots of that type of guy out there), but I'd really rather work on the algorithm ...
04:40 jeffreykegler and let someone else provide its "public face"
04:41 jeffreykegler rns: anyway, much thanks for your extensive and continuous assistance on Kollos ...
04:41 jeffreykegler I hope this will be something folks really, really like.
04:42 rns Me too. :) Working on Kollos is great in many ways.
04:43 rns And, with LUIF in Marpa::R2, D2L will not be much use anyway, but I have a couple ideas about it.
04:44 rns And now I think it'be be better for me to focus on kollos-luif-doc -- stripping D2L and specifying events?
04:45 jeffreykegler IF you can think of a good syntax, that'll be helpful.
04:46 jeffreykegler I
04:46 jeffreykegler 've thought of several syntaxes, but none of them excite me -- serviceable, but not elegant
04:47 * jeffreykegler is talking about syntax for events, if case he did not make it clear
04:47 jeffreykegler s/if case/in case/
04:47 rns Yeah, I see -- I did the sketch in https://github.com/rns/kollos-luif-doc/issues/32 will try to elaborate.
04:59 jeffreykegler Good night, folks!
05:03 rns Good night.
05:28 rns left #marpa
06:11 ronsavage joined #marpa
06:19 lwa joined #marpa
09:47 koo6 joined #marpa
17:45 lwa joined #marpa
18:55 ceridwen joined #marpa
22:15 jeffreykegler joined #marpa
22:29 ronsavage joined #marpa

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary