Thu, 30 Sep 1993 19:00:57 GMT

Related articles |
---|

LR(k) parsers nandu@cs.clemson.edu (1993-09-21) |

Re: LR(k) parsers parrt@s1.arc.umn.edu (Terence Parr) (1993-09-30) |

Newsgroups: | comp.compilers |

From: | "Terence Parr" <parrt@s1.arc.umn.edu> |

Keywords: | parse, LR(1) |

Organization: | Compilers Central |

Date: | Thu, 30 Sep 1993 19:00:57 GMT |

Nandakumar Sankaran writes:

*> I am looking for LR(k) parsers that are publicly available. I have*

*> rummaged thru the compilers list and have been unable to find one.*

This is because computing k-token lookahead is an exponential problem in

theory. As usual, much can be done in practice, but requires what can be

termed "polynomial approximations to exponential k-token lookahead" to get

anything beyond 1-token lookahead. My Ph.D. thesis describes how this can

be done (paper coming soon to a theatre near you). Also, ANTLR applies

this theory to build LL(k) for k>1 if you want to take a look (send mail

to pccts@ecn.purdue.edu).

*> [Isn't the usual approach to mangle the grammar until it's LR(1)? -John]*

Unfortunately, yes, this is the case. However, my techniques for

approximating k-token lookahead are equally valid for LL and LR based

parsing; it's just that I don't use LR parsers and don't want to code up a

LR(k)-based parser generator.

Terence Parr

U of MN

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.