Are there languages that can be parsed by an LR(k) parser but not by an LL(k′) parser for any k′?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Related: cs.stackexchange.com/q/43 $\endgroup$– Jozef MikušinecJun 10 at 14:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, $\{a^i b^j c \mid i \ge j \ge 0\}$ can be parsed by a $LR(0)$ parser but not by any $LL(k')$ parser for any $k'$. See How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?.
See also https://stackoverflow.com/q/36652221/781723 and Language theoretic comparison of LL and LR grammars.