Take the 2-minute tour ×

I want to understand the relation between LL/LR grammars and the left-recursion problem (for any question I know parcially the answer, but I ask them as I don't know nothing, because I am a little confused now, and prefer complete answers) I'm happy with sintetized or short and direct answers (or just links solving it unambiguously):

  1. What type of context free-language isn't LL(∞) languages?
  2. LL(K) and LL(∞) have problems with left-recursion? Or only LL(k) parsers?
  3. LALR(1) parser have troubles with left or right recursion? What type of troubles?
  4. Only in terms of the LL/LALR comparision. What is better, Bison (LALR(1)) or Boost.Spirit (LL(∞))? (Let's suppose other features of them are irrelevant in this question)
  5. Why GCC use a (hand-made) LL(∞) parser? Only for the "handling-error" problem?
share|improve this question
Your questions should be reasonably scoped. If you can imagine an entire book that answers your question, you’re asking too much. programmers.stackexchange.com/faq#dontask –  Robert Harvey Nov 20 '12 at 16:54
These questions are related to formal languages and grammars. You probably aren't going to get the answers you want here. Most of our users have expertise with designing and building software-intensive systems. I'd highly recommend checking out Computer Science, where you'll find people who specialize in the concepts rooted in mathematics and theory of computation. However, you'll probably want to be a lot more specific in your questions and perhaps break them up into smaller chunks. –  Thomas Owens Nov 20 '12 at 19:51
Computer Science moderator here: your questions 1–3 would be ok for Computer Science. Ask them separately, don't combine three questions into one. Please do read the relevant chapter in your textbook first, or at least the Wikipedia articles. Question 4 is meaningless because you haven't defined “better” (can express more languages? faster to parse? easier to write a grammar? …); you could ask about specific aspects of LALR(1) and LL(∞) and others on Computer Science as well. Question 5 is an Stack Overflow topic, but the SO community at least dislikes “why” questions; you may have better luck on a GCC mailing list. –  Gilles Nov 20 '12 at 20:05
I think three of your questions are answered by this post: cs.stackexchange.com/a/48/92. For the rest I also recommend you start questions over at that site. Don't forget to specify 'better' more precisely. –  Alex ten Brink Nov 20 '12 at 22:48
add comment

closed as not a real question by maple_shaft Nov 20 '12 at 19:45


1 Answer

Often a bad answer will do more to generate good answers than a good question, so in that spirit here are answers from someone (ie me) who did not take CS and never really learned parsing.

  1. Off of the top of my head, consider the language consisting of as and bs with a appearing no more than sqrt(2) times as often as b. There's a nice simple language which can't be represented by any reasonable grammar! I'm sure there are much less pathological examples.
  2. Only the parsers. The problem is that the grammar asks, Does there exist a parse? The parser does a recursive search for the parse, and can get stuck in an infinite loop. But the question of whether the parse exists is still unambiguous. A smarter parser can handle this, see http://en.wikipedia.org/wiki/Top-down_parsing#cite_note-FrostHafiz2006-4 for a reference to research on how to automatically build such parsers.
  3. The parser can get into an infinite loop where it keeps on trying to recursively expand a production, each time winding up with the same production that it can try to expand again.
  4. In theory the Bison parser should be able to be faster while the Boost parser should be more flexible. I have no idea how this works out in practice.
  5. http://gcc.gnu.org/wiki/New_C_Parser would be a good place to start on that question.
share|improve this answer
add comment
