> For example, one can prove that any yacc-generated parser never infinite loops and runs in O(n)
Trivial when actually writing the code.
And your example of infinite left recursion is basics in parser theory. No one in their right mind would write a hanging program like that, at least not for long.
Left recursion is basic, sure, but it's not a problem for an (LA)LR parser generator like yacc. (Depending on your parse actions, you might even get slightly better memory consumption when using left recursion rather than right recursion.)
