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 nonticked 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 LLregular, but there are no implementations, and it remains to be seen if the algorithms described are practical." "LRregular also includes LLregular." 
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 LLregular and LRregular, produces "Any LLregular grammars is an LRregular 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/languagetheoreticcomparisonofllandlrgrammars helpful? 
03:18 
ceridwen 
Yes. That said, I'm not sure the logic for LL(k) < LR(k) obviously extends to LLregular and LRregular. (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 wellknown result but clearly not an elementary one. 
03:43 
jeffreykegler 
More wellknown than wellproven, 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 LLregular and LRregular :) 
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 offtopic 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&rep=rep1&type=pdf  
19:13 
jeffreykegler 
it entends readily to LL and LRregular, I believe 
19:14 
jeffreykegler 
The property of the First(k) sets that it uses are that they are leftcongruent partitions  
19:14 
jeffreykegler 
the proof could be written to assume a leftcongruent partition and then the application to First(k) derived as a corollary 
19:15 
jeffreykegler 
Any, any regular partition can be rewritten as a leftcongruent 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&rep=rep1&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 