Re: LL(2) always factorable to LL(1)?

Andrew M. Duncan wrote:


> It's clear that some languages can be expressed in an LL(2)
> grammar, but the grammar can be further factored.


...


> Is this always possible?


Not in theory...there are languages that are inherently LL(k), but not
LL(k-1). However, most languages you run into are only terribly
inconvenient to left-factor in order to drop their lookahead
requirements. Any small grammar will mostly likely be factorable.


On the other hand, the introduction of actions can restrict your
ability to rewrite the grammar while preserving the semantics of the
translation, thus, making it impossible instead of inconvenient.


Please check out "LL and LR Translator Need k Tokens of Lookahead":


        http://www.antlr.org/Articles/needlook.html


for a practical lookahead discussion. We give a "practical" version
of Brosgol's proof that LR(k) is stronger than LR(1). There are some
examples of lookahead requirements for LL and LR.


The summary is that k>1 tokens of lookahead makes a difference for
both LL *and* LR because it makes the former stronger period and the
latter more flexible with regards to action placement. Lookahead is
your friend.


Unfortunately, k>1 lookahead is not computable in the general case due
to the exponential explosion of time/space (it's O(|T|^k) just to
store all possible lookahead sequences of length k with vocabulary of
size |T|).


The principle contribution of PCCTS/ANTLR is the notion of
linear-approximate lookahead:


o an approximation with nearly the strength of full LL(k) or LR(k).
o works for the majority of the cases.
o when it doesn't work, it attenuates the cost of doing full k
          lookahead!
o is effectively linear in k, so you can crank up k; just wrote a lexer
          last night with k=17.


The paper above describes its definition and implementation tersely.
For something dark and scary to read that tells you more than you
wanted to know about linear approximate lookahead (for LL and LR), see
my thesis listed at:


        http://www.antlr.org/articles.html


Note the groovy new http://www.antlr.org web site for PCCTS / ANTLR.


Best regards,
Terence
--

Return to the comp.compilers page.
Search the comp.compilers archives again.