Re: Hand-written rec-descent parser of GCC-4.1 is WRONG!!!

[jc-nospam at jr-pizarro dot jazztel dot es]

| > Do you demonstrate that "C++ is not LALR(1)"?
| 
| I'll leave that to you as a homework assignment.  Actually, C++ is not
| LALR(N) for any N.  Get out the C++ grammar and figure it out, it's an
| easy proof.  Come back when you have proved it to your own satisfaction,
| and please refrain from giving advice in the meantime.

It's not an easy proof. To prove "not LALR(N)" is hard, there is not
known lemma that says
"there is not equivalent grammar of this grammar to be LALR(N)".

People only knows LALR(1),LR(1),LL(1),LL(k),LR(k),SLR,LR(0),LL(0),LALR(0),...
but the people doesn't know LALL(0),LALL(1),LALR(2),LALL(k),LALR(k),...
because it is not easy to understand the unknown theory.

Do you demonstrate that "C++ is not LALR(k) for any k"?

Or didn't you find the "C++ grammar, LR(k) for small k"?

1. LR(k) / k small IS MORE POWERFUL THAN LR(3)
2. LR(3) IS MORE POWERFUL THAN LR(2)    (and little bit slower)
3. LR(2) IS MORE POWERFUL THAN LR(1)    (and little bit slower)
4. LR(1) IS MORE POWERFUL THAN LALR(1)  (and little bit slower)
5. LR(1) IS EQUAL POWERFUL AS LL(1) BUT
   there are many differences in the aspects of programming language grammars
   (e.g., vertical programming of rules versus horizontal programming of rules).

| > | Bison remains a good solution in many cases, especially for languages
| > | specifically designed to be easy to parse with an LALR parser (that is,
| > | languages that don't look like C).
| > 
| > Why don't we develop a "LR(k) / k small" functions-written parser for this
| > complex grammar?
|
| Because C++ is not LR(k) for any k.  It really does require unbounded
| lookahead.

It's possible that C++ doesn't require unbounded lookahead
because you did not find this confirmation
"For each C++ grammar, LR(k) for small k IS IMPOSSIBLE!!!".