Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-11-27

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

All times shown according to UTC.

Time Nick Message
00:15 ronsavage joined #marpa
02:02 ronsavage joined #marpa
05:31 ronsavage joined #marpa
05:46 jdurand joined #marpa
05:47 jdurand Re http://irclog.perlgeek.de/m​arpa/2015-11-23#i_11583612 - quite often forgortten; though the ECMAScript Marpa package has a full regexp parser, c.f. http://blogs.perl.org/users/jean-dami​en_durand/2014/02/a-marpa-use-case-ja​vascript-regexp-implementation.html
05:48 jdurand In this package, there is a single line saying where ECMAScript differs from Perl5' regexp - at closure implementation level, the parsing itself is unchanged between the two languages. Adding other perl5 specifics in the grammar is quite trivial
05:52 jdurand Correction: the semantics is in Pattern/Semantics.pm in the ECMAScript github repo
06:24 ronsavage joined #marpa
06:25 ronsavage jdurand: Thanx.
09:40 koo8 joined #marpa
10:06 Pursuit joined #marpa
11:48 ceridwen joined #marpa
14:48 iarna joined #marpa
14:48 iarna joined #marpa
16:10 ceridwen joined #marpa
16:10 ceridwen joined #marpa
16:31 Idiosyncrat http://act.yapc.eu/lpw2015/talk/6468
16:32 Idiosyncrat It looks like Maxim Vuets will give his Toki Pona/Marpa talk at the UK Perl workshop.
16:33 Idiosyncrat 12 Dec London, time not yet set
16:33 Idiosyncrat Be there or be square!
16:56 iarna joined #marpa
16:58 ceridwen joined #marpa
16:58 ceridwen joined #marpa
20:07 Idiosyncrat joined #marpa
20:09 Idiosyncrat joined #marpa
21:30 ceridwen Idiosyncrat, How does Marpa handle the case of infinitely-ambiguous grammars in the SPPF, data-structure-wise?
21:30 Idiosyncrat With great difficulty. :-)
21:31 Idiosyncrat Basically, you just keep track of everywhere there might be a cycle, and prevent it or make sure it is harmless.
21:31 Idiosyncrat In the future, I will either simply ban cycles, or eliminate them in the grammar rewrite ...
21:32 Idiosyncrat and eliminate the cycle-handling code from Libmarpa.
21:32 Idiosyncrat I'm writing the Marpa Book as if it did not handle cycles.
21:33 Idiosyncrat The great problem with previous parsers is they've been under-engineered ...
21:33 Idiosyncrat Arguably, I erred in the opposite direction, and I will be backing some of that out.
21:33 Idiosyncrat If you use the SLIF, it automatically bans cycles.
21:35 ceridwen Apparently this is a particularly painful problem, so it's no surprise I've been struggling with it.
21:39 ceridwen I'm most concerned about the case where an automatically-generated grammar creates an infinitely-ambiguous situation---an obvious case arises when trying to invert the grammar for a programming language that ignores whitespace, since all infinitely-many possible insertions of whitespace are valid.  The immediate problem is that I've been planning on using a hash table + immutable linked-list implementati
21:39 ceridwen on for the SPPF, but this does not play nicely with cycles in a language like Python with eager evaluation.
21:40 ceridwen My temptation is to stick with the design I have for now and then, when handling cycles, use lazy evaluation, but I don't know if that's going to get me into massive amounts of trouble.
21:44 Idiosyncrat Cycles can be detected ...
21:44 Idiosyncrat it's yet another use for a transitive closure algorithm.
21:45 Idiosyncrat That's what the SLIF current does -- it detects a cycle and prints a diagnostic.
21:47 ceridwen Since I want to deal with arbitrary CFGs and in some cases CSGs, I guess it's possible to automatically eliminate a cycle?
21:53 Idiosyncrat Consider what it means to handle an infinite cycle in the evalution phase.
21:54 Idiosyncrat That is, you cannot actually perform an infinitely long evaluation.
21:55 Idiosyncrat The usual thing to do is, when there is an infinite cycle, to refuse to do any processing.
21:55 ronsavage joined #marpa
21:56 Idiosyncrat Currently Libmarpa will follow rules which involve infinite cycles for a length of 1 -- that is, until they repeat.
21:56 Idiosyncrat Nobody every found a use for this.
21:56 Idiosyncrat If anybody ever does find a use for this, it is better handled as a grammar rewrite.
21:57 koo7 joined #marpa
21:57 Idiosyncrat The cases where Libmarpa follows infinite cycles is where they, in addition to infinite cycle, also reach a terminal ...
21:58 Idiosyncrat If a cycle is just simple A -> A where A is a non-terminal, then it's just an infinite loop, and Marpa does nothing with it.
21:59 Idiosyncrat But if you have A ::= x | A ...
21:59 Idiosyncrat that is an infinite cycle, but there is also a way to reach the terminal <x>, so Libmarpa (with the right options set) will do that
21:59 Idiosyncrat and silently ignore the cycle.
22:00 Idiosyncrat Most users are happiest if you just treat A ::= A | x as a fatal error.
22:02 ceridwen Infinite cycles like A -> A can be automatically eliminated without changing the language of the grammar, so I'm assuming that when I'm doing automatic grammar processing for inversion or error-handling, I will have to rewrite the grammars to avoid those.  The terminal cases are the ones that are tricky.  For inversion, they have to be disambiguated at some point.
22:05 ceridwen I was planning to have one ex-post-facto disambiguation system that runs during/after parsing, but I'm not sure that when dealing with an automatic inversion this is superior to forcing users to redefine the grammar to make it unambiguous.
22:05 Idiosyncrat To handle them as a grammar rewrite, just follow the paths, renaming symbols so they are unique per path ...
22:05 Idiosyncrat paths end when you reach a terminal, in which case you use the path ...
22:05 Idiosyncrat or when they cycle, in which case you do not use the path.
22:06 ceridwen For error-handling, it's not immediately clear to me what's right, though it's also not clear to me that the reverse grammar can even generate a cycle if one doesn't exist.  (I'm hoping not, honestly, but I haven't proven it yet.)
22:06 Idiosyncrat In some grammars this can lead to an explosion in the number of symbols and rules, but that's unavoidable.
22:07 ceridwen Right.  Can it be bounded?
22:07 Idiosyncrat It's bounded, yes.
22:07 Idiosyncrat But I think it may be exponential if the cycle is a plex --
22:08 Idiosyncrat something like A :: = B | C | D ; B ::= A | C | D; C ::= A | B | D; D ::= A | B | C
22:09 Idiosyncrat they are actually some of these in Marpa::R2's test suite.
22:09 Idiosyncrat Frankly, I'd love to have all the time I spent on them back to devote to other things. :-)
22:10 Idiosyncrat Unfolding all the symbols and rules of a plex is (I think) exponential in the number of symbols ...
22:10 ceridwen Your advice, then, would be to stick with my current SPPF design and defer the cycles issue, possibly indefinitely?
22:11 Idiosyncrat so it is easy to automatically create a grammar which takes an impractical amount of time to rewrite.
22:11 Idiosyncrat Y. E. S.
22:11 Idiosyncrat That's exactly my advice.
22:15 ceridwen It's useful to know that no one's ever used them.  Thanks for the advice and notes on grammar-rewriting---that's probably a better solution than using lazy evaluation to circumvent the problem.
22:18 Idiosyncrat Yes, no users AFAICT.  The best evidence is when I quietly yanked support for them which I created the SLIF.  No complaints.  None.
22:19 Idiosyncrat In fact, no evidence that anybody even noticed the absence of support of cycles.
22:23 ceridwen This is one of those highly-technical issues that no one without a background in parsing theory even thinks about, I'm sure.  I hope you don't mind my using #marpa for these sorts of questions, there aren't many places where asking them won't get me puzzled expressions.
22:36 ronsavage JK: Re http://irclog.perlgeek.de/m​arpa/2015-11-27#i_11615379. Yes, I remember when cycles got zapped. I didn't like the look of them, so was happy to see the go. But I /did/ notice!
22:43 Idiosyncrat ceridwen: I think it is useful for the Marpa community to be seen as the place to go for advice on leading edge parsing techniques.
22:44 Idiosyncrat So as low as my estimate of the value of cycles support to my community was, it may have been too high.
22:45 Idiosyncrat ronsavage: You probably were not the only one in the Marpa user community saying ...
22:45 Idiosyncrat "Finally, the idiosyncrat has gotten the cycle things out of his system!  Thank God and Greyhound!"
23:06 ronsavage Ha! I've never been to church, but I do have 2 Italian Greyhounds: https://en.wikipedia.org/wiki/Italian_Greyhound.
23:09 koo8 joined #marpa

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