[antlr-interest] Help with pesky Lexer determinism

[Terence Parr]

On Jun 6, 2005, at 4:31 PM, Lloyd Dupont wrote:
>> Hooray!
>> 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  
tree parsers.

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.

Terence
--
CS Professor & Grad Director, University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Cofounder, http://www.jguru.com