This takes me deeper into derivatives than I've every gone, and probably beyond where I can help you. I skimmed Might-Darais at the time, and then read Russ Cox's appreciation <http://research.swtch.com/yaccalive> carefully. Russ seemed to say everything that needed to be said [ except he didn't mention Marpa :-) ], and I moved on. I've never studied the derivatives method in detail.
Many data structures mix rule, location of rule & location within rule in a data structure, and they can seem all to look the same. The 2nd one you list seemed to be Earley tables. I'm not too clear on what the 1st is (I'm not good at reading LISP), but if I had to guess it is a state transition table, rather than a parse table. If so, they're quite different things. On Tue, Jan 12, 2016 at 2:26 PM, Anton Dyudin <[email protected]> wrote: > I was referring to the constant factor; O(n|G|) is claimed by the paper, > via "our grammars blew up exponentially so we had to compact them > continuously, now they seem not to though a pathological case can probably > be constructed". Which isn't the same as "complexity class has been > proven", sure. > > But my main goal here is to understand marpa, and in this case > specifically where the intuition that > start: (alt (cat 'a' 'b') (cat 'a' <start> 'b'))) > = D_a => (alt 'b' (cat <start> 'b')) > = D_a => (alt null (cat (alt 'b' (cat <start> 'b')) 'b')) > => (cat (alt 'b' (cat <start> 'b')) 'b') > = D_b => (alt 'b' (cat null 'b')) => 'b' > is equivalent to > 0. {[start -> a b]:0 [start ->•a start b]:0} > 1.a {[start -> a•b]:0 [start -> a•start b]:0 [start -> •a b]:1 [start -> > •a start b]:1} > 2.a {[start -> a•b]:1 [start -> a•start b]:1 [start -> •a b]:2 [start -> > •a start b]:2} > 3.b {[start -> a start•b]:0} > modulo tree/by-reference structure, is off base. > > On Tuesday, January 12, 2016, Jeffrey Kegler < > [email protected]> wrote: > >> I didn't study Might-Darais closely -- Russ Cox did, and I'm relying on >> his observations. >> >> You can (and I do) think of packratting and backtacking as the same >> approach, it's just deciding whether to take the efficiency hit in space or >> in time. >> >> My idea is that, if you want a strong parserr, you should use a parse >> engine designed (like Earley's) to be strong from the ground up. Almost >> everybody else starts with a more or less weak parser, and hacks on the >> power, knowing that's worst-case inefficient, but hoping it will work out >> in enough cases of interest. Since Earley's is O(n) for every >> deterministic CFG, I don't see why folks insist on going for the weaker >> algorithms. But my approach is definitely the minority one so far. >> >> Re "2 seconds to parse a 31-line Python file" -- I really don't pay much >> attention to specific speed claims in theoretical papers -- as opposed to >> big-O worse-case results. With Marpa, you don't have to hope your grammar >> is O(n) -- you can know for sure. Resorting to claims for specific >> grammars on specific processors to my mind shows the approach has run out >> of steam. >> >> Note that I *do* do benchmarks to compare implementations in my blog, but >> I don't report those in theoretical contexts. Readers of theory papers >> should care how fast your algorithm is, not how fast your current processor >> is. >> >> On Tue, Jan 12, 2016 at 9:53 AM, Anton Dyudin <[email protected]> >> wrote: >> >>> Would I be correct to infer that memoization is a form of backtracking, >>> and packratting is what the "fixpoint" computation is doing? And is the >>> issue with those being expensive on real-world size grammars/input? 2 >>> seconds to parse a 31-line Python file seems a bit steep, though not >>> exponential. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "marpa parser" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "marpa parser" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> For more options, visit https://groups.google.com/d/optout. >> > -- > You received this message because you are subscribed to the Google Groups > "marpa parser" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "marpa parser" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
