Re: LR(k)-Parser wanted

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
--

Return to the comp.compilers page.
Search the comp.compilers archives again.