23 Jan 1998 00:21:50 -0500

Related articles |
---|

LL(2) always factorable to LL(1)? aduncan@cs.ucsb.edu (Andrew M. Duncan) (1998-01-17) |

Re: LL(2) always factorable to LL(1)? clark@quarry.zk3.dec.com (Chris Clark USG) (1998-01-20) |

Re: LL(2) always factorable to LL(1)? bill@amber.ssd.csd.harris.com (1998-01-21) |

Re: LL(2) always factorable to LL(1)? mickunas@cs.uiuc.edu (1998-01-23) |

Re: LL(2) always factorable to LL(1)? cfc@world.std.com (Chris F Clark) (1998-01-23) |

Re: LL(2) always factorable to LL(1)? parrt@magelang.com (Terence Parr) (1998-01-23) |

Re: LL(2) always factorable to LL(1)? thetick@magelang.com (Scott Stanchfield) (1998-01-24) |

Re: LL(2) always factorable to LL(1)? parrt@magelang.com (Terence Parr) (1998-02-01) |

From: | Terence Parr <parrt@magelang.com> |

Newsgroups: | comp.compilers |

Date: | 23 Jan 1998 00:21:50 -0500 |

Organization: | MageLang Insitute |

References: | 98-01-071 |

Keywords: | parse, 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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.