Mon, 5 Jun 1995 02:28:48 GMT

Related articles |
---|

LR(k)-Parser wanted holzmuel@kafka.informatik.uni-stuttgart.de (1995-04-21) |

Re: LR(k)-Parser wanted rekers@wi.leidenuniv.nl (1995-04-29) |

Re: LR(k)-Parser wanted grosch@cocolab.sub.com (1995-04-25) |

Re: LR(k)-Parser wanted parrt@parr-research.com (Terence John Parr) (1995-04-30) |

Re: LR(k)-Parser wanted cisreb@cis.unisa.edu.au (Bob Buckley) (1995-05-11) |

Re: LR(k)-Parser wanted grosch@cocolab.sub.com (1995-06-05) |

Newsgroups: | comp.compilers |

From: | grosch@cocolab.sub.com (Josef Grosch) |

Keywords: | parse, tools |

Organization: | CoCoLab, Karlsruhe, Germany |

References: | 95-05-007 |

Date: | Mon, 5 Jun 1995 02:28:48 GMT |

Status: | RO |

Terence John Parr (parrt@parr-research.com) wrote:

*: Josef Grosch at CoCoLab writes:*

*: > Also, I started to work on an LR(k) version of 'lark'. It should be called*

*: > partial LR(k), because again LALR(1) is used by default and LR(k) only where*

*: > necessary. It tries LR(2), LR(3), etc. up to a given limit. Before trying*

*: > LR(k) an approximation of LR(k) is tried which is much more efficient to*

*: > compute.*

*: This wouldn't happen to be the linear approximate lookahead described*

*: in my thesis and used in ANTLR would it? Just curious to see if*

*: anybody had deciphered my thesis yet ;)*

Oh yes, I have deciphered the thesis of Terence, at least to some

degree. What I have implemented follows the idea of the linear

approximate lookahead, although the details are different: I

implemented it for LALR(k). I used my existing data structures which

worked as well as a GLA. I am using my own caching mechanism, because

I did not understand the one of Terence. And I combined the

computation with the digraph algorithm published by F. DeRemer and T.

Pennello: Efficient Computation of LALR(1) Look-Ahead Sets, TOPLAS 4,

4 (Oct. 1982), 615-649.

I consider the idea of the linear approximate lookahead to be a

brilliant invention. Especially, I do appreciate the underlying

principle of what Terence has done. At least I and probably others

have been caught by the existing definition of LR(k) grammars, many

attempts to implement LR(k) failed. Now, Terence just disregarded the

existing definition and he defined something new in between of LR(1)

and LR(k). This can be computed efficiently and it is a valuable

progress.

Josef Grosch

grosch@cocolab.sub.com

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.