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

Terence Parr parrt at jguru.com
Thu Jun 27 12:49:43 PDT 2002


On Thursday, June 27, 2002, at 04:49  AM, Bogdan Mitu wrote:

> --- Terence Parr <parrt at jguru.com> wrote:
>> 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 ;-)

Yup.  That was my dissertation in a nutshell--finding the linear 
approximate lookahead and using it to reduce complexity even of full 
lookahead.  Your BDD may be applicable, but pretty hard to beat the 
simple k sets of tokens of linear approximate lookahead. ;)

> I think that something similar can be used for lookaheads. Maybe not 
> BDD but

It's really the computation...yes, storage is important to reduce as 
well, but I use that concept only because the worst case is obvious as 
O(n^k).  In reality, grammar analysis is a function of grammar size, 
vocabulary size, and k so it's even worse to compute than O(n^k).  You 
have to traverse O(n^k) paths at each decision point in the worst case 
even if you don't store the data ;)

Ter
--
Co-founder, http://www.jguru.com
Creator, ANTLR Parser Generator: http://www.antlr.org


 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 



More information about the antlr-interest mailing list