Re: LR(k)-Parser wanted (Jan Rekers)
Sat, 29 Apr 1995 04:55:41 GMT

          From comp.compilers

Related articles
LR(k)-Parser wanted (1995-04-21)
Re: LR(k)-Parser wanted (1995-04-29)
Re: LR(k)-Parser wanted (1995-04-25)
Re: LR(k)-Parser wanted (Terence John Parr) (1995-04-30)
Re: LR(k)-Parser wanted (Bob Buckley) (1995-05-11)
Re: LR(k)-Parser wanted (1995-06-05)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Jan Rekers)
Keywords: parse
Organization: Dept. of Math. & Comp. Sci., Leiden Univ., Leiden, the Netherlands
References: 95-04-133
Date: Sat, 29 Apr 1995 04:55:41 GMT

> 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?
> Any links would be very appreciated.

I kind-of did. By using the Generalized LR parsing method of Tomita,
is it possible to use parse table generation techniques such as LR(0),
SLR, LALR(1), LR(1), ... and still obtain a parser which is able to
work for arbitrary context free grammars, so LR(k) grammars can be
handled without a problem. The parser becomes more efficient by
applying a more elaborate parse table generation technique. This
parsing algorithm splits in several parsers if it encounters a
shift/reduce or reduce/reduce conflict. Have a look at the following
paper for more details:

    key = {HKR90},
    author = {J. Heering and P. Klint and J. Rekers},
    title = {Incremental generation of parsers},
    journal = {IEEE Transactions on Software Engineering},
    volume = {16},
    number = {12},
    pages = {1344-1351},
    year = {1990},
    note = {Also in: {\it SIGPLAN Notices}, 24(7):179-191, 1989}

Hope this helps,
Jan Rekers

<A HREF=> Jan Rekers </A>
Department of Computer Science, Leiden University
P.O. box 9512, 2300 RA Leiden, the Netherlands
email:, Phone: +31 71 277108

Post a followup to this message

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