most recent 30 from http://mathoverflow.net 2013-06-19T02:41:52Z http://mathoverflow.net/feeds/question/31733 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31733/can-i-have-an-ll-grammar-for-every-deterministic-context-free-language lvella 2010-07-13T16:36:13Z 2010-07-13T19:17:28Z

<p>Every deterministic context free grammar can be represented by a LR(1) grammar, so this question can be rephrased as: can I build an equivalent LL(k) grammar from every LR(k) grammar? Can I have an example of deterministic context free language that can not have an LL(k) grammar?</p>

http://mathoverflow.net/questions/31733/can-i-have-an-ll-grammar-for-every-deterministic-context-free-language/31746#31746 Antonio E. Porreca 2010-07-13T18:47:38Z 2010-07-13T19:17:28Z

<p>I’m not an expert on this topic, but I found these <a href="http://www.gdi.uni-bamberg.de/teaching/SS10/GdI-GTI-B/tomlect8.pdf" rel="nofollow">course notes</a> (including some bibliographical references) which state that the language <i>L</i> = {<i>xⁿ</i> : <i>n</i> &isin; &#8469;} &cup; {<i>xⁿyⁿ</i> : <i>n</i> &isin; &#8469;} has no LL(<i>k</i>) parser, while being deterministic context-free (see pp. 24 and 27).</p> <p>Edit: I found a better reference. The paper <a href="http://www.cs.uwaterloo.ca/research/tr/1978/CS-78-24.pdf" rel="nofollow">Two iteration theorems for the LL(<i>k</i>) languages</a> by J.C. Beatty contains a proof that the LR language <i>L</i> = {<i>aⁿbⁿ</i>, <i>aⁿcⁿ</i> : <i>n</i> &ge; 1} is not LL (see Theorem 5.2).</p>