[antlr-interest] The power of backtracking in ANTLR

[Michael Bedward]

Hi Søren,

The section on backtracking parsers in Ter's "Language Implementation
Patterns" book really helped me to understand this issue better:
http://www.pragprog.com/titles/tpdsl/language-implementation-patterns

Stealing a relevant example from the book involving C++ function
definitions and declarations...

void bar() {...} // a function definition
void bar();	// a function declaration (forward declaration)

"Because C++ function headers can be arbitrarily long, the
distinguishing token does not appear at a fixed lookahead position
from the left side of the statement. Consequently, Pattern 4, LL(k)
Recursive-Descent Parser, on page 59 is too weak to distinguish
function definitions from declarations using a natural grammar."

So, in this example you can't refactor the grammar to LL(k) but you
can have a simple, readable grammar for this part of the language if
you work with a back-tracking parser.

Hope this helps.

Michael