Full LL(k) (was: [antlr-interest] Can someone please explain)

Bogdan Mitu bogdan_mt at yahoo.com
Thu Jun 27 04:49:19 PDT 2002


--- Terence Parr <parrt at jguru.com> wrote:
> 
> On Tuesday, June 25, 2002, at 05:57  AM, Bogdan Mitu wrote:
> 
> >
> > --- Tom Moog <tmoog at polhode.com> wrote:
> >>
> >> Well, there's always pccts (aka antlr v1) for C++.
> >> It does full LL(k) when linear lookahead isn't sufficient.
> >
> > Just out of curiosity:
> > What is the difficulty of using full LL(k)? Is it just the space 
> > required to
> > store lookahead sets (trees?)?
> 
> Space and time go from O(n*k) to O(n^k) ;)  Obviously it can be done in 
> most cases (see PCCTS) ...

Well, theory is theory, and practice is practice. Most engineering problems
are exponentially bounded. Fortunately good solutions can be found in most
practical problems, otherwise they would be out of business ;-)

I was involved last year in a project dealing with formal verification of
digital circuits, and the big problem there is the exploration of all
possible future states starting from a given initial state. Note that I am
speaking of FSMs with states encoded on 100 bits or even more. The key in
the practical implementation was the use of Ordered Binary Decision Diagrams
(OBDD) to represent the state space. It is amazing how efficient this was
for practical cases. And all is due to the fact that all subtrees in BDD are
unique (reused).

I think that something similar can be used for lookaheads. Maybe not BDD but
Hex Decision Diagrams. Represent the lookahead as a tree where nodes have
(at most) 16 children. Each level of the tree "consumes" 4 bits from the
binary representation of the character/token. This won't be more efficient
than current implementation for *one* lookahead set, but when you consider
all lookaheads, a lot of subtree reusing can take place; I can bet many
lookaheads are similar (have common subtrees).

Best regards,
Bogdan

> with some tricks combining approx and full to 
> render full lookahead, but it can still generate land mines.  I'll be 
> using a thread to do the computations in the future so I can kill it if 
> it takes too long to compute and fall back on approx.
> 
> Ter
> 
> 
>  
> 
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
> 
> 
> 




__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com



More information about the antlr-interest mailing list