Tue, 25 Apr 1995 11:12:39 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 |

Organization: | CoCoLab, Karlsruhe, Germany |

References: | 95-04-133 |

Date: | Tue, 25 Apr 1995 11:12:39 GMT |

Bernd Holzmueller (holzmuel@kafka.informatik.uni-stuttgart.de) wrote:

*: Has anybody developed a parser-generator which generates parsers for the*

*: grammar class of LR(1), LR(k) for a fixed k > 1 or LR(k) for arbitrary k?*

The parser generator 'lark' of the Cocktail Toolbox can generate parsers for

LR(1) grammars. There are several options:

- full LR(1): is only practical for medium size grammars, otherwise huge

amounts of memory and runtime are needed.

- partial LR(1): uses LALR(1) by default and LR(1) at states where necessary.

I have implemented my own version of state splitting. This works well

in simple cases and tends to degenerate to full LR(1) in case of many

LR conflicts. Perhaps I should try the algorithm of Pager, however,

I am not sure whether this is worth the effort.

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. Again, conventional LR(k) for a even few states is expensive.

The analysis phase is more or less completed. A grammar for COBOL with more

than 100 LR(1) conflicts can be analyzed giving the result that half of

the conflicts can be solved using LR(2). The generation of parsers that

automatically use more than one lookahead token has to be finished.

For more information please contact

Josef Grosch

Mail: grosch@cocolab.sub.com

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.