Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-11-18

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

All times shown according to UTC.

Time Nick Message
00:38 Cheery the warshall algorithm has worst-case cubic time run, in relation to amount of nonterminals
00:39 Cheery but I guess it's less in practice because our rules aren't all-to-everything
00:43 Idiosyncrat Go back through the IRC log and you'll see that I came up with a bit vector driven implementation that is
00:44 Idiosyncrat really fact.
00:44 Idiosyncrat I think Aria reimplemented it in Javascript.
00:44 Idiosyncrat It's a pecular implementation, because the bit matrix in implemented assymmetrically, but it is blazingly fast in C.
00:45 Aria Not completely yet but getting there.
00:45 Idiosyncrat And in any case if you look in the Libmarpa code for "Warshall", there it is, ...
00:45 Idiosyncrat though you'll have to look up all the bit vector/matrix macros.
00:46 Idiosyncrat Anyway, you are doing your transitive closures on the *grammar*, which is treated as constant size in this context.
00:46 Idiosyncrat And usually the time comes closer to O(n**2)
00:47 Idiosyncrat Libmarpa does bunches of transitive closures every time you create a grammar, and the cost is not even noticeable.
00:48 Idiosyncrat A bit of history -- very few actual mistakes of mine passed through in the implementations, but transitive closure algorithms were one.
00:48 Idiosyncrat I was misled by Grune & Jacobs who, in one of their rare errors, stated that Warshall's is *always* O(n**3)
00:49 Idiosyncrat So I rolled my own transitive closure implementation, and when Jean-Damien started using Libmarpa to crunch big grammars,
00:49 Idiosyncrat speed became a real issue.
00:50 Idiosyncrat So I replace my "roll my own" algorithm with Warshall's, and the result as literally a 100x speed-up.
00:50 Idiosyncrat TL;DR -- Marpa's experience is that Warshall's is fast.
01:07 Cheery so it's good idea to use the bit-matrix -approach, but I got to exploit the idea that I only need to go through columns and rows where [i,k] or [k,j] is 1
01:07 Cheery ?
01:09 Cheery so if [i,k] = 0, I can skip
01:09 Cheery oh.. and since I'm going through a small subset of values in the matrix.. it's fast.
01:10 Cheery as long as the worst case doesn't happen, and it probably doesn't happen on grammars.
01:11 Cheery simple and clean.
01:18 Idiosyncrat The implementation in Libmarpa skips rows when they are all zeroes.
05:36 ronsavage joined #marpa
15:17 sadmac joined #marpa
16:29 black_ant joined #marpa
16:44 Idiosyncrat joined #marpa
21:06 ronsavage joined #marpa
22:08 VsyachePuz_ hi. Why wikipedia have a page for GLR, but have no page for GLL ?
22:09 VsyachePuz_ Is GLL the same as Earley + SPPF ?
22:09 VsyachePuz_ How GLL is different from ALL(*) which implemened by ANTLR ?
22:10 VsyachePuz_ Do I nead both structures - the markup of positions and SPPF during parsing, or SPPF replaces the Earley markup ?
22:14 VsyachePuz_ there is nonworking disambig for SPPF in wikipedia - https://en.wikipedia.org/wiki/SPPF
22:15 VsyachePuz_ the description of Graph Structured Stack is unclear on the page https://en.wikipedia.org/wiki/Graph-structured_stack
22:51 ernimril joined #marpa

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