Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-05-24

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

All times shown according to UTC.

Time Nick Message
00:35 ronsavage I've updated http://savage.net.au/Marpa/html/Marpa.R2.DSL.Structure.html with min/max, and a note for the Start rule. Also, to make the ticks stand out, I've removed the '-' chars in non-ticked cells.
01:13 sivoais_ joined #marpa
01:17 KotH_ joined #marpa
01:23 sivoais joined #marpa
01:33 sivoais joined #marpa
03:05 ceridwen jeffreykegler, Two requests for citations for two things you say in your most recent blog post.  "Some of the PEG literature looks at techniques for extending this as far as LL-regular, but there are no implementations, and it remains to be seen if the algorithms described are practical."  "LR-regular also includes LL-regular."
03:08 jeffreykegler ceridwen: that "some of the PEG literature" is those papers ( Mascarenhas, Redziejowski ) cited in the blog post.
03:10 ceridwen The papers in the previous post?  Thanks!
03:11 jeffreykegler Googling for LL-regular and LR-regular, produces "Any LL-regular grammars is an LR-regular grammar"
03:12 jeffreykegler from this abstract http://www.tandfonline.com/doi/abs/10.1080/00207168008803216?journalCode=gcom20
03:14 ceridwen Darn.  That's the one paper I haven't been able to find a copy of online.
03:15 jeffreykegler I think it's a standard result (and not a hard one, though I don't care to prove it :-) ) that, for any lookahead, call it look, ...
03:15 jeffreykegler The LL(look) grammar are a subset of the LR(look) grammars
03:16 jeffreykegler ceridwen: Is http://cs.stackexchange.com/questions/43/language-theoretic-comparison-of-ll-and-lr-grammars helpful?
03:18 ceridwen Yes.  That said, I'm not sure the logic for LL(k) < LR(k) obviously extends to LL-regular and LR-regular.  (It's possible it does and I'm just not seeing it.)
03:20 jeffreykegler http://doc.utwente.nl/66932/1/fct1981.pdf , p. 209
03:21 jeffreykegler Oops, no, misread it.
03:22 ceridwen I'd seen the StackExchange link.  Do you know how they're using "LL(∗)×LR" there?  Because I'm used to that always being Cartesian product in set theory, which doesn't make any sense in that context.
03:22 jeffreykegler It was not immediately obvious to me either.
03:23 ceridwen That is exactly the paper I misread earlier that sent me on this wild goose chase.
03:27 ceridwen (Also, thanks again for fielding my questions on parsing theory.  If they ever get to be too much, just tell me.)
03:36 jeffreykegler Showing that a LL(k) grammar is always a LR(k) grammar is exercise 5.2.25 in Aho&Ullman 1972
03:36 jeffreykegler It has 2 stars, their highest rating, which means the proof is *not* easy.
03:38 jeffreykegler Aho&Ullman IMHO share a common fault of the textbooks of time in making too many things exercises, and the exercises too hard.
03:38 jeffreykegler Part of this was the need to save paper.
03:39 ceridwen I would agree.
03:40 jeffreykegler ceridwen: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.82.997 -- read that abstract -- the plot thickens!
03:43 ceridwen It's a well-known result but clearly not an elementary one.
03:43 jeffreykegler More well-known than well-proven, apparently
03:45 jeffreykegler That page also has a link to the paper which has a proof for LL(k) in LR(k) ... I leave it as your assignment to extend that result to LL-regular and LR-regular :-)
03:52 ceridwen Oh goody :).  I'm asking primarily because I'm trying to sort out exactly what grammars GLL parses in linear time, and if I instead need to move to Earley, which has some complications for a combinator approach.
05:23 ronsavage joined #marpa
08:47 lwa joined #marpa
09:42 ronsavage joined #marpa
13:56 koo6 joined #marpa
18:53 jeffreykegler joined #marpa
18:54 jeffreykegler It's a bit off-topic but Paul Bennett has been a long time supporter of Marpa, and who knows he may eventually be using Marpa in pursuing this interest:
18:55 jeffreykegler https://plus.google.com/+PaulBennett/posts/SewLZyteMDW
18:55 jeffreykegler Paul's question is addressed to native Russian speakers.
19:13 jeffreykegler ceridwen: the proof in http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=033B37B84E4FC20A2E3CADE1969A0987?doi=10.1.1.82.997&amp;rep=rep1&amp;type=pdf --
19:13 jeffreykegler it entends readily to LL- and LR-regular, I believe
19:14 jeffreykegler The property of the First(k) sets that it uses are that they are left-congruent partitions --
19:14 jeffreykegler the proof could be written to assume a left-congruent partition and then the application to First(k) derived as a corollary
19:15 jeffreykegler Any, any regular partition can be rewritten as a left-congruent partition, and the same proof method would go through.
19:15 jeffreykegler I've not studied it in full detail, but that's the way it looks to me.
19:16 jeffreykegler Aria: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=033B37B84E4FC20A2E3CADE1969A0987?doi=10.1.1.82.997&amp;rep=rep1&amp;type=pdf
19:16 jeffreykegler I think this is another one that merits inclusion in the collection.
22:14 jeffreykegler joined #marpa
22:26 ronsavage joined #marpa

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