Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2014-03-17

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

All times shown according to UTC.

Time Nick Message
00:04 jeffreykegler1 joined #marpa
15:48 LLamaRider joined #marpa
16:30 LLamaRider joined #marpa
16:37 jeffreykegler joined #marpa
16:54 jeffreykegler I've been working on the revision of Marpa's theory paper.  This won't necessarily mean a lot to everyone, but let me report what I've found in reworking the proofs.
16:55 jeffreykegler The results in Leo's paper showed that his algorithm (and therefore Marpa) is O(n) for LR-left-congruent grammars (I call these LRLG).
16:56 jeffreykegler I have found that Marpa is O(n) for any finite union of LRLG grammars.
16:57 jeffreykegler Every LRLG grammar is unambiguous, but their finite unions may be ambiguous, so this result explains the linear behavior Marpa exhibits on a wide variety of ambiguous grammars.
18:03 jeffreykegler Expanding on that last a bit -- the LRLG grammars include all the LR-regular grammars.
18:04 jeffreykegler LR-regular in turn includes LR(k) for all k and LL(k) for all k.
18:05 jeffreykegler This means it includes regular expressions, LALR and in fact every class of grammar parsed by yacc or recursive descent.
18:25 LLamaRider joined #marpa
21:09 ronsavage joined #marpa
21:10 ronsavage The breadth of this result is remarkable. Still, there'll be situations where Marpa is not the most appropriate choice, won't there?
21:50 ronsavage joined #marpa
22:22 jeffreykegler joined #marpa
22:23 jeffreykegler ronsavage: re http://irclog.perlgeek.de/​marpa/2014-03-17#i_8451260 -- a very good question
22:24 jeffreykegler Throughout this, I've tried to be the one people can go to for the facts about parsing trade-offs, even when they indicate that Marpa is not the right choice.
22:24 jeffreykegler This very much breaks with the tradition in parsing, which is one of overclaiming and under-delivering
22:26 jeffreykegler We can divide the limits of Marpa's applicability into two kinds: practical and theoretical.
22:26 jeffreykegler Practical meaning, yes the algorithm can do it, but the support system is not mature.
22:26 jeffreykegler Theoretical means, however strong the support system becomes, Marpa is not the right tool for the job.
22:27 jeffreykegler Quick thoughts: if it's a reasonably sized regular expression in the strict sense (that is, not a regex), a regular expression engine is the right tool.
22:29 jeffreykegler 2.) yacc/LALR is a great tradition, but one whose useful life has ended.  I don't really need to say much here because, whatever the textbooks might say, this is what the practitioners have decided.
22:32 jeffreykegler 3.)  At the far end, where we are talking about NLP, chart parsing and CYK may still have advantages.  Marpa may be a very serious contender here, particularly with extensions.
22:36 jeffreykegler 4.) That leaves left parsing in its various incarnations,  most prominently recursive descent.  Despite left parsing's track record as an incinerator of time and effort, the programming community seems slow to show interest to alternatives to pushing this particular rope.
22:37 jeffreykegler I'll leave it at that for now -- but it is clearly a topic which won't go away.
22:57 jeffreykegler1 joined #marpa

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