[antlr-interest] Help with pesky Lexer determinism
parrt at cs.usfca.edu
Mon Jun 6 16:44:10 PDT 2005
On Jun 6, 2005, at 4:31 PM, Lloyd Dupont wrote:
>> But wait...there's MORE! The v3 version wouldn't even need the
>> predicates and any order would be ok. ;)
> WoW, Awesome!
> Is there Any Such Thing as a Limit to the Power of ANTLR v3?!?!
Well, to be honest, that is something that any old lex/flex lookalike
(or even JavaCC) could do. The trick is that now you can do it in
ANTLR without losing the ability to do recursion in the lexer.
LL(k) parsers are basically using DFAs of fixed depth, k, to decide
which among n alternatives will succeed in matching. LL(*) allows
cyclic DFA, hence, arbitrarily deep lookahead to make parsing
decisions. The same algorithm will be used for lexers, parsers, and
The really cool thing is that hoisted semantic predicates come
essentially for free, piggybacking on the LL(*) algorithm. Oh, the
academic papers I shall write...not that anybody gives a damn about
parsing anymore in the US. Have to start going to European
conferences I guess.
> sorry, just looking for some distraction while working...
Me too...i've been stuck in administration hell all day. :( I did
just get my visa to go to India this summer though! A nice distraction.
CS Professor & Grad Director, University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
More information about the antlr-interest