# IRC log for #marpa, 2015-11-19

All times shown according to UTC.

Time Nick Message
00:10 Idiosyncrat joined #marpa
00:24 Idiosyncrat VsyachePuz_: re some of those questions
00:24 Idiosyncrat GLR was very much in fashion at one point, while GLL has not been.
00:24 Idiosyncrat GLL is very different from Earley + SPFF
00:25 Idiosyncrat Yes create Earley tables, then SPFF.  If, once you have the bocage (SPFF), you have stored all the odds and ends (token values, etc.), you can discard the Earley tables.
00:38 VsyachePuz_ Idiosyncrat: what is SPFF, is it the same as SPPF ?
00:39 Idiosyncrat s/SPFF/SPPF/ -- sorry
00:41 VsyachePuz_ Idiosyncrat: In my understanding, Earley is the best algorithm in terms of number of restrictions on grammar. How GLL is different from it? Does it sacrifice something to achieve some unnecessary performance?
00:42 Idiosyncrat Don't know much about GLL ...
00:42 VsyachePuz_ Idiosyncrat: me too, it's the reason why i am asking
00:43 VsyachePuz_ I more ore less understood, how to keep earley structure of markup in my program, but have difficulties with understanding of SPPF
00:43 Idiosyncrat If it's LL, that means it's top-down, and I think GLL is a kind of systematic backtracking.
00:47 Idiosyncrat OK, looked it up.
00:47 Idiosyncrat GLL is top-down, and solves ambiguity using a forked stack.
00:47 VsyachePuz_ SPPF is variation of forked stack
00:47 Idiosyncrat So it's the LL analog of GLR.
00:48 VsyachePuz_ so, I don't see, why Earley+SPPF is not a GLL
00:49 Idiosyncrat SPPF is a data structure that represents an ambiguous parse -- it's an efficient form of a parse forest.
00:50 Idiosyncrat You could draw an analogy with forked stacks, but I do not think it's helpful -- they both look like trees when you draw them, and that's about all they have in common AFAICT
00:51 VsyachePuz_ so, "Graph Structured Stack" and SPPF are two different things, which should be used in the same program at the same time for different goals?
00:51 Idiosyncrat "Graph Structured Stack"?
00:52 VsyachePuz_ i gave a like above - https://en.wikipedia.org/wiki/Graph-structured_stack
00:53 Idiosyncrat OK, I see the analogy, they use similar data structures.
00:53 VsyachePuz_ As I understood, there 2 papers. the paper of Earley with his markup, And the paper of Tomita with directed graph of stacks
00:54 Idiosyncrat But my reaction is, like, Perl uses hashes, Python uses hashes, so Perl = Python?
00:54 VsyachePuz_ I need to implement the parser. Do I need 3 things - Earley markup, GSS and SPPF, or 2 thing - just Earley markup and SPPF
00:55 Idiosyncrat You don't need the forked stacks == GSS
00:55 Idiosyncrat I experimented with forked stacks once, and they are not as hard as they look ...
00:56 Idiosyncrat in fact they are far, far, far worse
00:57 Idiosyncrat A way of looking a general parsers, is to consider them as dividing the task between "parsing" (a mathematical method of parsing) and "hacks" (everything else)
00:57 Idiosyncrat Hacks are backtracking, forked stacks, lookahead, etc.
00:58 Idiosyncrat With Earley you do whole hog on parsing, so that you don't need hacks.
00:58 black_ant joined #marpa
00:58 Idiosyncrat With top-down based methods, you do almost no parsing, and rely heavily on hacks
00:59 Idiosyncrat With GLR, it's sort of in-between.
00:59 VsyachePuz_ I already read a lot of such walking around explainations... They all say about common properties of algorithms, but don't dive into details
01:01 Idiosyncrat VsyachePuz_: what is your project?
01:01 VsyachePuz_ i want to join https://github.com/coonsta/earley
01:02 VsyachePuz_ but need more understanding of algorithm itself
01:02 VsyachePuz_ (i mean SPPF building algorithm)
01:03 VsyachePuz_ and then tru to rewrite it on language with built in proover (like F*)
01:04 Idiosyncrat Scott's paper describes the method I use.
01:05 Idiosyncrat I was not aware of her work when I did mine, but what I produced was essentially a copy of her work.
01:06 Idiosyncrat The coonsta repo was last touched 5 years ago.
01:07 VsyachePuz_ Idiosyncrat: the sources are available, that is enough for me
01:07 Idiosyncrat By the way, a point I'll probably repeat ... a number of folks are looking at Earley/Marpa reimplementations.
01:07 Idiosyncrat Which is cool,
01:08 Idiosyncrat but I don't see people getting into applications, like syntax macros, etc.
01:09 Idiosyncrat It's kind of like we're in the early days of aviation, and a lot of people want to build airplanes, but nobody wants to be Lindberg, Exupery or Earhardt
01:10 VsyachePuz_ I recently implemented parser for git config files for some utilities for portage package manager for gentoo and sabayon linux. I used Eto.Parse, which is LL(k). No i want to use something different
01:10 VsyachePuz_ *now
01:11 Idiosyncrat I see
01:12 VsyachePuz_ If you have Marpa implemented with C# according requirements of my religion, I will happily use existing implementation
01:13 Idiosyncrat Well, there is Libmarpa, which is in C, if you can use C libraries.
01:13 black_ant joined #marpa
01:14 VsyachePuz_ My religion is based on MOSA toolchain project (https://github.com/mosa/MOSA-Project), which generates C# to bare metal
01:14 VsyachePuz_ So, I can't use C libraries
01:14 Idiosyncrat I understand the "religion" thing.  In a lot of situations, you are tied to a specific language, so that arguing language is like arguing religion.
01:15 Idiosyncrat People come to languages for their own reasons, which often are fundamental, and it's rude to simply tell them to switch.
01:16 Idiosyncrat Reimplementing Marpa from scratch in C# would not be easy.
01:16 Idiosyncrat It wouldn't take the 8 years it took me, because you can leverage my work. :-)
01:16 Idiosyncrat But it's probably not something that can be done is a few weeks.
01:26 VsyachePuz joined #marpa
01:38 VsyachePuz Idiosyncrat: 8 years is much shorter, than 25 years of ANTLR
01:38 VsyachePuz Idiosyncrat: that give me base to expect implementation time of 3 years for my project :)
01:39 Idiosyncrat Probably as good an estimate as any. :-)
02:34 ronsavage joined #marpa
02:47 ilbot3 joined #marpa
02:47 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
05:27 Cheery https://bpaste.net/show/108912cb50dd
05:31 Cheery sometimes it's no wonder that it's impossible to determine how long a program takes.
05:34 Cheery heh. my transitive closure code had a bug
08:39 Cheery https://bpaste.net/show/1778515e556e
08:45 koo7 joined #marpa
08:53 black_ant joined #marpa
09:46 Cheery once you have the SPPF parse tree, what's the nicest error report you can give to ambiguity?
09:52 Cheery or...
09:52 Cheery maybe I'm just messing this up
09:53 Cheery even if the result would be quarranteed to be ambiguous, the parse forest necessarily isn't just single link everywhere.
09:54 Cheery or hm.
09:56 Cheery oh wait. it is just single links if the parse is ambiguous.
09:57 Cheery because the reductions are plotted by origin. the reduction into that origin cannot appear if the beginning of the rule isn't there.
15:50 koo8 joined #marpa
15:58 koo8 left #marpa
16:04 VsyachePuz https://github.com/JetBrains/Nitra
16:05 VsyachePuz there is class ParseResult in Nitra.Runtime.dll
16:08 VsyachePuz https://github.com/JetBrains/Nitra/blob/b6fb950b112d57be268f4177efde7dede71fbc48/Nitra/Nitra.Runtime/Parsing/ParseResult.n#L28
16:25 Idiosyncrat joined #marpa
16:26 Idiosyncrat Cheery: For how to report ambiguities, so Marpa::R2's solution -- this is one of the innovations that I claim ...
16:27 Idiosyncrat it was a hard problem to solve and I am pleased with how the solution came out.
16:28 Idiosyncrat By default, Marpa::R2's \$grammar->parse() routine treats ambiguity as an error and reports it.
16:30 Idiosyncrat The theory behind it is in part new -- to get started on it look at http://search.cpan.org/~jkegl/Marpa-R2-3.000000/
16:30 Idiosyncrat Ooops!  I meant http://search.cpan.org/~jkegl/Marpa-R2-3.000000/pod/ASF.pod
16:31 Idiosyncrat And, for the level under the ASF's, http://search.cpan.org/~jkegl/Marpa-R2-3.000000/pod/Glade.pod
17:05 VsyachePuz Idiosyncrat: you asked about applications of parser generators - http://blog.jetbrains.com/blog/2013/11/12/an-introduction-to-nitra/
17:09 Idiosyncrat VsyachePuz: looks interesting
18:20 JPGainsborough joined #marpa
20:03 black_ant joined #marpa
21:27 ronsavage joined #marpa