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 LRleftcongruent 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 LRregular grammars. 
18:04 
jeffreykegler 
LRregular 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/20140317#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 tradeoffs, 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 underdelivering 
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 