Terence Parr (author of ANTLR) pointed out a mistake I made when I was describing how ANTLR deals with non-LL(*) grammars. I said that ANTLR’s option for dealing with non-LL(*) grammars is to do a depth-first search which runs in exponential time. While I believe this is true if you enable “backtrack=true” alone, ANTLR also has a “memoize=true” option that you can use together with backtrack=true to reduce the time complexity to linear, at the expense of more space.
I also claimed that ANTLR can handle all grammars when backtrack=true is on. Terence corrected me and said that even with backtrack=true, ANTLR does not handle all grammars — for example left-recursive ones. I mistakenly thought that depth-first search parsing would be capable of handling left-recursion, but after some more thought and some time with my trusty Grune and Jacobs I understood why this is not the case. There are other top-down algorithms that can handle this, but backtracking depth-first search (with or without memoization) is not one of them.
Apologies to Terence for my misstatements about ANTLR!