> 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.