# IRC log for #marpa, 2015-05-13

All times shown according to UTC.

Time Nick Message
01:45 jeffreykegler joined #marpa
01:48 ilbot3 joined #marpa
01:48 Topic for #marpa is now Start here: http://savage.net.au/Marpa.html - Pastebin: http://scsys.co.uk:8002/marpa - Jeffrey's Marpa site: http://jeffreykegler.github.io/Marpa-web-site/ - IRC log: http://irclog.perlgeek.de/marpa/today
01:48 jeffreykegler Ok, the logging bot is back.
01:48 jeffreykegler As I just said "off the record", I want to give a quick cheat sheet on Marpa-flavored Leo implementation
01:49 jeffreykegler I was re-reading Leo's paper recently and it hit me that I made a number of serious changes to his algorithm.
01:49 jeffreykegler Leo's algorithm in his paper goes out of its way to be "lazy" -- never adding a Leo item unless it's about to use it.
01:50 jeffreykegler This involves, potentially, at each Earley set, going backward over the entire parse.  From a complexity point of view, this is very much under control, so Leo 1991 does deliver on complexity,
01:51 jeffreykegler but the implementation is awkward, and I took an eager approach -- if any Leo item *might* be added at an Earley set, then Marpa adds it when the Earley set is first built.
01:54 jeffreykegler That is, if there is a transition over a quasi-final symbol, and it is deterministic, then I add the Earley
01:54 jeffreykegler (Quasi-final) means final if you ignore nulling symbols.
01:55 jeffreykegler Second change: In Leo 1991, Leo items are created for all symbols, even those which are not right-recursive.
01:56 jeffreykegler These can chain, so there can be some payoff, but the payoff is eliminating a chain which is at most less than some finite constant in length.
01:58 jeffreykegler Only if a right recursion is involved, does the chain of Leo-memoized items grow beyond constant size.
01:59 jeffreykegler So Marpa in its precomputations, determines which symbol right recurse and which do not.
01:59 jeffreykegler And if the transition symbol of a Leo item is not right recursive, Marpa does not create a Leo item.
02:00 jeffreykegler Note these two changes are complementary -- eager Leo-memoization raises the cost of the Leo logic, imposing it in cases where it will not be used.
02:01 jeffreykegler Limiting Leo-memoization to right-recursion, however, means Leo items are only created where the potential payoff is big.
02:02 jeffreykegler This grew beyond "quick cheat sheet" size, but hopefully it would still fit into mini-talk format. :-)
02:02 jeffreykegler Glad I waited for the bot. :-)
02:58 jeffreykegler http://ppm4.activestate.com/x86_64-​linux/5.20/2000/J/JK/JKEGL/Marpa-R2​-3.000000.d/log-20150511T082248.txt
02:58 jeffreykegler A build report from Activestate -- their one error with Marpa::R2 3.0
02:59 jeffreykegler I think the key line is "Perl API version v5.20.0 of threads does not match v5.14.0 at /home/fly2000/var/megalib/XSLoader.pm line 92."
02:59 jeffreykegler which suggests that it's an issue with their configuration.
04:27 rns In http://www.linuxquestions.org/questio​ns/slackware-14/perl-broken-in-curren​t-automake-fails-to-start-4175418402/ -- "Perl API version ... " explained by 2 perls on the same system.
05:15 koo8 joined #marpa
06:13 ronsavage joined #marpa
06:44 koo6 joined #marpa
07:18 rns re http://irclog.perlgeek.de/m​arpa/2015-05-08#i_10570019 -- fast recognizer creations can be used to write parser combinators which work in linear, rather than polynomial, time.
10:37 ilbot3 joined #marpa
10:37 Topic for #marpa is now Start here: http://savage.net.au/Marpa.html - Pastebin: http://scsys.co.uk:8002/marpa - Jeffrey's Marpa site: http://jeffreykegler.github.io/Marpa-web-site/ - IRC log: http://irclog.perlgeek.de/marpa/today
11:30 lwa joined #marpa
13:01 koo6 joined #marpa
13:20 ceridwen rns, Can you expand on your last comment?
13:23 jeffreykegler joined #marpa
13:26 jeffreykegler Anyone out there who knows about Config::Autoconf -- I am a bit puzzled by this: https://github.com/jeffreykegler/Marpa​--R2/issues/178#issuecomment-101525453
13:27 rns ceridwen: Sure, what in particular would be interesting to you?
13:27 jeffreykegler There had been a discussion of a Config::Autoconf change, which ended (if I read the issue correctly) with an assurance there'd be plenty of notice on the release, ...
13:28 jeffreykegler and a promise to send me a list of methods to check for -- methods, which if Marpa::R2 used them, might mean it was affected.
13:29 jeffreykegler I never got the list, so had no way of knowing if I was affected, and just kept the issue on my Github list.
13:29 jeffreykegler I think what I've just been told is that the change took place 6 months ago.
13:31 jeffreykegler If I got notice, I missed it.  But if indeed the change came down without prep, we dodged the bullet, because there've been no problems.
13:32 jeffreykegler So, anyway, if there's someone who can help me figure out what's happened, and what (if anything at this point) Marpa::R2 should do, I'd appreciate it.
14:28 ceridwen rns, Parser combinators in general use recursive descent, which is worst-case exponential on general CFGs.  There are ways to build parser combinators with other CFG algorithms that are worst-case O(n^3).  How would you get linear time?  Are you restricting the grammar choice?
14:29 rns joined #marpa
14:36 rns Well, Marpa grammars are composable (if lexeme-compatible) and Marpa has linear time for those of them, which are in practical use, so parser combinators (which form an algebra), if backed by Marpa grammar composition, would be also linear?
14:42 ceridwen Are LR-regular grammars closed under composition?  I'd suspect not just because LL, LR, and the deterministic grammars aren't, but I could easily be wrong.
14:47 ceridwen But yes, if you restrict the set of grammars under consideration, you can easily write parser combinators that run in worst-case linear time.  PEG parser combinators are popular, though they have the usual problems of PEGs.  I've been exploring parser combinators based on GLL, which runs in linear time on deterministic grammars.  (I don't know about LR-regular grammars, and I wonder if it doesn't, if it would be possible to modify it so it does run
14:47 ceridwen in linear time on LR-regular grammars, but I haven't had time to spend time thinking carefully about it.)
14:54 rns Me too, yet. I was exploring composability for Kollos and remembered what Jeffrey said about recognizers.
14:55 ceridwen Random curiosity: have you seen the paper "efficient earley parsing with regular right-hand sides", http://trevorjim.com/papers/ldta-2009.pdf ?
14:56 rns Anyway, Marpa parses a rather broad class of grammars, so Marpa-backed parsers can well be closed under composition even if grammars aren't. :)
14:56 ceridwen Well, CFGs are closed under composition.
14:57 ceridwen That's one of their big advantages compared to other classes of grammars.
14:57 Aria Yesss
14:57 rns re http://irclog.perlgeek.de/m​arpa/2015-05-13#i_10596710 -- nope, looks interesting, thanks.
15:04 ceridwen For general context: I'm working on trying to create a modern, efficient parser library for Python, trying to incorporate some ideas from the literature that are either new or old and neglected.  I'm not sure if using Marpa as my backend is viable.  (I originally started out thinking GLL, I've been studying Earley lately along with Marpa.)  In particular, I want to combine Richter's non-correcting error handling, Jim and Mandelbaum's data-dependent
15:04 ceridwen grammars (related to attribute grammars), and Yellin's attribute grammar inversion into one project.
16:55 Cheery ceridwen: https://gist.github.com/ch​eery/99b5d82d09aa88b80199
16:58 Cheery jeffreykegler: I'm not sure my implementation is correct, but it turned out to be quite simple to just check if same rule is reduced twice, then react on that.
17:02 Cheery I have figured out a semi-satisfying way to handle indentation heh
17:02 Cheery but would like something on precedence rules and arithmetic
17:03 jeffreykegler Cheery: my apologies if I don't review the code -- in the unhappy old days when Marpa was ignored, I had lots of time and re-read anything written in or about Marpa carefully, several times.
17:03 Cheery no problem. I'll figure if it works soon enough :)
17:03 jeffreykegler Now I read very little of it, about which I am sorry.
17:04 jeffreykegler Perhaps some other folks working on the same problem might want to look at Cheery's stuff?
17:05 Cheery haven't implemented that indentation parsing yet.. Though I figured I can use the ruby slippers -approach there.
17:05 Cheery if the parser expects for indentation marker and it can be given, the tokenizer gives it.
17:07 Cheery anyway I'm looking at arithmetic parsing right now. I'm looking at the output my parser gives and concluding grammar rewriting might be sufficient
17:07 Cheery but wouldn't like to do the grammar rewriting myself.
17:10 Cheery another thing bothers me is that all the operators and such tend to increase size of the gramar.
17:49 hobbs http://loup-vaillant.fr/tutorials/earley-parsing/ not sure if anyone's spotted this yet but it got posted on reddit this morning