Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-11-17

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

All times shown according to UTC.

Time Nick Message
02:03 ronsavage joined #marpa
03:18 ceridwen joined #marpa
03:18 ceridwen joined #marpa
05:01 ernimril joined #marpa
08:53 ronsavage joined #marpa
09:02 ronsavage joined #marpa
09:17 ronsavage JK: Re http://irclog.perlgeek.de/marpa/2015-11-12#i_11523369. There was one action sub which just returned $t1, so I've switched to ::first. Thanx. That sub was not mentioned in the article, which helps.
15:15 Idiosyncrat joined #marpa
15:32 JPGainsborough joined #marpa
16:39 ceridwen joined #marpa
16:39 ceridwen joined #marpa
20:52 Cheery Idiosyncrat: if you're rewriting your paper, you've got the point about adding leo items too?
20:54 Cheery so far I've understood: if I've got the grammar without null rules..
20:54 Cheery then it's easy to compute transitive items while I am memoizing transitions.
20:55 Cheery and apparently I am going to add leo item when I encounter rule such as: X -> a.A
20:56 Cheery two conditions: it's the only rule that has postdot A
20:56 Cheery and after the postdot it will be complete
20:58 Cheery .. still really hard to wrap my head around how it actually goes.
20:58 Cheery I'll try few parses today night or tmr. and see if I figure it out.
22:08 ronsavage joined #marpa
22:15 ronsavage joined #marpa
23:12 Idiosyncrat joined #marpa
23:14 Idiosyncrat Also, don't do Leo memoization unless the rule is a right recursion, is my suggestion.
23:15 Idiosyncrat Another lesson learned from many hours of experience -- I first implemented for all rules, as in Leo's paper, ...
23:15 Idiosyncrat and then based on experience, changed it.
23:15 Idiosyncrat But it looks like you have the rest right.
23:18 Idiosyncrat The reason for only doing right recursions is that with other rules, the cost of not doing Leo memoization is limited, ...
23:18 Idiosyncrat but with right recursions the cost of not Leo memoizing in unlimited and in practice can get very large.
23:20 Cheery right recursion such as: A -> a.A ?
23:20 Idiosyncrat Yup.
23:21 Idiosyncrat Don 't forget indirect right recursions.
23:21 Idiosyncrat A ::= x B ; B ::= y A
23:22 Cheery there's algorithm to identify those forms of recursion?
23:22 Idiosyncrat By doing a transitive closure, you can figure out which rules are right recursvie.
23:24 Idiosyncrat Yes
23:26 Idiosyncrat Use Warshall's algorithm for the transitive closure.
23:31 Idiosyncrat If you search the back log of the Google group and this channel, there is a lot of talk about Warshall's
23:31 Cheery I feel that may be the simple part still.
23:33 Cheery I understood that if the program finds a leo item when it is reducing, it copies the earley -part of that item.
23:34 Cheery but the leo item appears at memoization part.. and apparently the conditions are:
23:35 Cheery there's a penultimate right-recursive earley item, and it has unique postdot in that set.
23:37 Cheery so when I reduce, but get that penultimate right-recursive item, I will drop it in as-it.
23:38 Idiosyncrat Yes, right.
23:38 Cheery so in this part, they come for 'free'
23:38 Idiosyncrat I am now calling the EIM based on which the memo is created the "basis" of the Leo memo.
23:39 Idiosyncrat And I now say the requirement is that the basis be a "quasi-penult", where "quasi-" means that nulling symbols are ignored.
23:39 Idiosyncrat Working on the paper, I am nailing down the terminology.
23:41 Idiosyncrat Cheery: anyway, so note in this you wind up starting with the bottom of what I now call the "Leo silo"
23:42 Idiosyncrat and using the Leo memo, you create the top of the Leo silo.
23:42 Idiosyncrat So that you need to be able to recreate everything in the silo between bottom and top.
23:43 Idiosyncrat That's why the requirement that the basis EIM's be "postdot-unique"
23:43 Idiosyncrat That way everything about the Leo silo is determined, even if you know only it bottom and top.
23:43 Cheery okay.
23:43 Idiosyncrat s/it bottom/its bottom/
23:45 Idiosyncrat The chapter of the theory paper I am working on defines all this terminology, and connects it together with proofs.
23:45 Cheery I checked at the profiling of the current parser I got running.. It appears to spend considerable time in constructing the parse trees, after the recognizer has run.
23:46 Idiosyncrat I know it took some care for me to get the parse tree construction to be linear.
23:46 Idiosyncrat Btw, have you looked at Elizabeth Scott's article re SPFF's for Earley's algorithm?
23:46 Cheery heh. I just read it small while ago
23:46 Idiosyncrat What she describes is basically the way Libmarpa does it.
23:47 Idiosyncrat Except I say "bocage" instead of SPFF.
23:47 Cheery so at reduction you add links around.
23:47 Idiosyncrat Yes, links.
23:47 Idiosyncrat Aycock&Horspool talk a bit about links.
23:47 Cheery and that's compatible with the leo memoization.
23:48 Idiosyncrat You need a system of links for the Leo memoization as well.
23:49 Idiosyncrat And, just to make things interesting, in an ambiguous grammar an EIM can have multiple sets of both normal and Leo links.
23:49 Idiosyncrat All this is why it took 8 years to get Marpa to the state it is in.
23:50 Idiosyncrat Various people had done pieces of it, often very big, important pieces.
23:50 Idiosyncrat But other pieces were missing and nobody had tried to figure out how to put them together.
23:51 Idiosyncrat Originally, for the interface, I thought I would "borrow" an existing one, so I didn't have solve the interface issues ...
23:52 Idiosyncrat but it turned out nobody had ever really tried to create a full production-quality general parser system before, so there was no place I could borrow from.
23:57 Cheery I feel I could actually manage to implement this now.
23:58 Cheery It'll require few tries to get some things right.
23:58 Cheery but I'm looking at this one and the parser I have right now. I have a hunch that it's worth it.

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