Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-09-15

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

All times shown according to UTC.

Time Nick Message
00:18 idiosyncrat joined #marpa
01:29 idiosyncrat joined #marpa
01:30 idiosyncrat left #marpa
01:34 idiosyncrat1 joined #marpa
02:05 idiosyncrat joined #marpa
02:41 idiosyncrat joined #marpa
03:31 sadmac joined #marpa
03:53 Aria http://afroozeh.github.io/papers/cc15.pdf
04:03 idiosyncrat joined #marpa
04:04 sadmac joined #marpa
04:31 idiosyncrat joined #marpa
04:31 idiosyncrat left #marpa
04:48 idiosyncrat joined #marpa
05:06 idiosyncrat joined #marpa
05:30 pczarn joined #marpa
05:31 pczarn Aria: nice, their parsers have precedenced rules.
08:03 pczarn joined #marpa
09:06 rns Aria: good reading, thanks.
09:08 rns 5. Disambiguation filters for scannerless GLL parsing section describes what it calls precede/follow restrictions.
09:09 rns I wonder would such a thing be useful in Kollos seamless (character-based) mode.
09:10 rns On a first glance, they can be implemented using http://jeffreykegler.github.io/Marpa-we​b-site/libmarpa_api/stable/api_one_page​.html#Zero_002dwidth-assertion-methods or events with the former being arguably more efficient.
09:25 rns re their speed (and acceleration) claims -- they compare their own implementations of ‘original GLL’ and ‘new GLL’ (their improved version).
09:26 rns Comparison with ANTLR wouldn't hurt for a bigger picture.
10:27 idiosyncrat1 Re http://irclog.perlgeek.de/m​arpa/2015-09-15#i_11218736
10:27 idiosyncrat1 Since folks are reading this, maybe you know the answers to some things -- I just glanced at it very quickly.
10:28 idiosyncrat1 My impression is that it is top-down, restricted recursive descent, with backtracking.
10:28 idiosyncrat1 Did they say which grammars it is linear for?
10:29 idiosyncrat1 Also, I did see they claim n**3 worst case.  How do they keep the backtracking from going exponential?
10:30 idiosyncrat1 Finally, note that Marpa's rules are WYSIWYG -- you specify something, you get exactly that
10:31 idiosyncrat1 That behavior should match specification goes without saying with everything but parsers, where ...
10:32 idiosyncrat1 specifying a rule more often means "try to give me this, but if my specification does not mean some hard-to-apply criteria, silently give me something else and expect me to figure it out"
10:33 idiosyncrat1 Of which kind are the GLL rules?
10:33 idiosyncrat1 Good night!
10:33 idiosyncrat1 left #marpa
10:42 rns idiosyncrat: re http://irclog.perlgeek.de/m​arpa/2015-09-15#i_11220130 -- yes, ‘deterministic’ as they call it -- ‘Generalized parsing algorithms have the attractive property that they _can_ behave linearly on deterministic grammars.’
10:45 rns re http://irclog.perlgeek.de/m​arpa/2015-09-15#i_11220129 and http://irclog.perlgeek.de/m​arpa/2015-09-15#i_11220135 -- they consider backtracking solved to cubic citing [8] Scott, E., Johnstone, A.: GLL parse-tree generation. -- https://pure.royalholloway.ac.uk/p​ortal/files/25269152/GLLsubmit.pdf
10:47 idiosyncrat1 joined #marpa
10:49 idiosyncrat1 I did a 2nd skim and some answers ...
10:49 rns re rules -- they claim generality, so lhs ::= rhs, e.g. X ::= αA · β
10:49 rns also, they 'GLL parsers produce a binarized SPPF'
10:51 idiosyncrat1 Yes, they do claim generality, which I can believe, because unlike PEG/yacc they don't simply throw away non-determinism -- that's what you have to do to actually deliver on general BNF notation.
10:51 * idiosyncrat1 just completed a 2nd quick skim
10:52 idiosyncrat1 And, yes, they backtrack, but they memoize in binarized SPPF form (which is the same as Marpa uses in its bocages)
10:52 idiosyncrat1 So they can keep time complexity down to n**3
10:53 idiosyncrat1 Note this amounts to doing Earley parsing, only in a roundabout way.
10:53 idiosyncrat1 They'd have trouble implementing Leo's optimization that way.
10:54 idiosyncrat1 If they went the next step, and developed a faster way to create the SPPF, they'd have Earley's algorithm.
10:54 idiosyncrat1 If they went one further, and made it linear for all deterministic CFG's, they'd have Leo's algorithm.
10:55 idiosyncrat1 If they went one beyond that, and made it possible to stop, do procedural parsing, and restart, they'd have Marpa.
11:00 idiosyncrat1 The paper *is* an acknowlegement that the Earley's approach (really deliver on the BNF specification, and don't throw away non-determinism) is the way to go.
11:01 idiosyncrat1 But it sort of is trying to make Earley's look like recursive descent.
11:03 idiosyncrat1 I hate the name SPPF by the way.
11:03 idiosyncrat1 Since Scott almost certainly has priority ...
11:03 idiosyncrat1 I came up with them before reading her article, but almost certainly after her work ...
11:03 idiosyncrat1 maybe they could be called Scott forests.
11:04 idiosyncrat1 I prefer the name "bocage",
11:05 idiosyncrat1 and in the case of "America", the 2nd guy there did get to name the place,
11:05 idiosyncrat1 but usually that privilege goes to the first person to discover something. :-)
11:12 idiosyncrat1 I *do* notice some nice touches -- they know enough *not* to claim constant time for hashing.
11:12 idiosyncrat1 which means their *implementation* is not constant time.
11:13 idiosyncrat1 (If anybody wonders why I spend the time describing PSL's in my paper, that's why)
11:13 idiosyncrat1 They *describe* an constant-time way of doing their SPPF memoization.
11:16 idiosyncrat1 All the means their implementation is actually log n x n **3
11:19 idiosyncrat1 Good night, again!
11:19 idiosyncrat1 left #marpa
11:43 pczarn Exact complexity depends on the hash map they use. Some implementations with open addressing have O(log_2 log_2 n) lookup on average. I'm not sure about insertion, though.
12:24 pczarn idiosyncrat: Which fast deterministic parsers have WYSIWG behavior for well-defined classes of grammars?
15:38 Aria Doesn't Scott call them SPPFs?
15:40 pczarn joined #marpa
15:41 pczarn Aria: She does.
15:41 Aria Aah, okay.
15:41 Aria But yeah. Scott forests ++
16:58 pczarn Found it. I can check whether a given grammar is strict deterministic. If so, I'll use canonical LR or its equivalent.
19:00 djns joined #marpa
23:09 idiosyncrat joined #marpa
23:10 idiosyncrat Aria: Frank De Remer's classic paper is on-line -- http://web.archive.org/web/20120405124​425/http://computer-refuge.org/bitsave​rs/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf
23:10 idiosyncrat May I suggest it for the collection?
23:11 * idiosyncrat doesn't mention, but he's never actually read it.
23:25 idiosyncrat xdg
23:26 idiosyncrat Sorry, wrong window

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