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