parser-generators for RRPGs: summary

Michael Dyck <>
Mon, 22 Feb 1993 23:35:04 GMT

          From comp.compilers

Related articles
parser-generators for RRPGs (Michael Dyck) (1993-01-28)
parser-generators for RRPGs: summary (Michael Dyck) (1993-02-22)
Re: parser-generators for RRPGs: summary (1993-02-25)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Michael Dyck <>
Keywords: parse, summary, EBNF
Organization: Compilers Central
References: 93-01-206
Date: Mon, 22 Feb 1993 23:35:04 GMT

I wrote:
> Regular right-part grammars (RRPGs) are a kind of phrase structure
> grammar akin to context-free grammars (CFGs). In each production of an
> RRPG, the LHS is a single non-terminal (as in a CFG), but the RHS is a
> regular expression (or finite automaton) over the symbol set (rather
> than simply a sequence of symbols, as in a CFG).
> There are various notations for writing RRPGs (or slight restrictions
> thereof), many called "extended BNF".
> ...
> What parser-generators are available that accept some form of RRPG?

Here's a summary of the replies. Thanks to:

Kiong Beng Kee
Karsten Nyblad
Anton Ertl
Todd Jonker
Tim Channon
Paul Oude-Luttighuis
Taylor Hutt
Terence J Parr
Thomas Reid
Judith Grass
Xorian Technologies

I have divided RRPG parser-generators into three categories, according
to the approach taken.

Convert the RRPG to a CFG and use a 'conventional' parser generator:

Lalr, Ell (in Cocktail toolkit [formerly called Toolbox?])
    GMD Forschungsstelle an der Universitaet Karlsruhe

ESP (Extensible Syntax Parser)
    Todd Jonker at CMU
    (uses a Tomita parallel parser to do the parsing)

Generate a top-down parser directly from the RRPG:

    Barrett, Bates, Gustafson, and Couch
    "Compiler Construction - Theory and Practice, 2nd Edition",
    pp. 167-173
    (see article 93-02-024)

ANTLR, the parser-generator in PCCTS
    (Purdue Compiler Construction Tool Set)
    (see article 93-02-009)

    written in Forth
    available from
    (see article 92-05-111)

Generate a bottom-up parser directly from the RRPG:

LADE (LAnguage Definition Environment)
    Xorian Technologies Pte. Ltd
    (see article 92-05-061)

    ProSoft (formerly LALR Research)
    (see article 93-02-005)

    Compiler Resources, Inc.
    (see articles 92-06-142, 91-12-061, 91-09-005, 91-08-132, 91-04-071,
      and 91-03-095)

    Judith Grass at AT&T Bell Labs
    in-house research prototype
    Has "several (hefty) papers on Ryacc that are distributable."
    (see article 91-05-069)

    Karsten Nyblad at TFL, A Danish telecommunications research lab
    (see article 91-05-076)


Also, there are lists of references on RRPGs in

-Michael Dyck,

Post a followup to this message

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