|LL(2) always factorable to LL(1)? email@example.com (Andrew M. Duncan) (1998-01-17)|
|Re: LL(2) always factorable to LL(1)? firstname.lastname@example.org (Chris Clark USG) (1998-01-20)|
|Re: LL(2) always factorable to LL(1)? email@example.com (1998-01-21)|
|Re: LL(2) always factorable to LL(1)? firstname.lastname@example.org (1998-01-23)|
|Re: LL(2) always factorable to LL(1)? email@example.com (Chris F Clark) (1998-01-23)|
|Re: LL(2) always factorable to LL(1)? firstname.lastname@example.org (Terence Parr) (1998-01-23)|
|Re: LL(2) always factorable to LL(1)? email@example.com (Scott Stanchfield) (1998-01-24)|
|Re: LL(2) always factorable to LL(1)? firstname.lastname@example.org (Terence Parr) (1998-02-01)|
|From:||Terence Parr <email@example.com>|
|Date:||23 Jan 1998 00:21:50 -0500|
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":
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
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
The principle contribution of PCCTS/ANTLR is the notion of
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
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:
Note the groovy new http://www.antlr.org web site for PCCTS / ANTLR.
Return to the
Search the comp.compilers archives again.