Re: LR(n) parsers (Stephen Adams)
14 Oct 91 08:41:48 GMT

          From comp.compilers

Related articles
LR(n) parsers (Steve Boswell) (1991-10-10)
Re: LR(n) parsers (Karsten Nyblad, TFL, Denmark) (1991-10-13)
Re: LR(n) parsers (1991-10-14)
Re: LR(n) parsers (1991-10-14)
Re: LR(n) parsers (1991-10-14)
Re: LR(n) parsers (1991-10-14)
Re: LR(n) parsers (1991-10-15)
Re: LR(n) parsers (Nick Haines) (1991-10-16)
Re: LR(n) parsers mtxinu!angular! (1991-10-18)
Re: LR(n) parsers (Raul Deluth Miller-Rockwell) (1991-10-19)
[7 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Stephen Adams)
Keywords: parse, LR(1), bibliography
Organization: Southampton University Computer Science
References: 91-10-036
Date: 14 Oct 91 08:41:48 GMT

In article 91-10-036 (Steve Boswell) writes:

  > What sort of easily-describable or commonly-occuring grammars are
  > ambiguous for any amount of lookahead? I'm implementing an
  > object-oriented parsing engine and I'd like to take all the work of
  > resolving ambiguity away from the end programmer. (Maybe wanting to do
  > this is naive, but then I gotta learn somehow. :-) Has there been any work
  > done on LR(n) parsing engines like this? My idea is to do a normal LR(1)
  > transition table & parse in parallel with all possibilities every time
  > there is more than one.
  > [What you're proposing is more or less Earley's parsing scheme, which is
  > quite slow. -John]

That is how Tomita's algorithm works. Any LR table generator is used
(e.g. LR(0), LALR(1), LR(1) etc). All conflicting actions are stored in
the table. The clever bit is to recognize when two of the parallel
parsers are doing the same thing and then reducing the number of parallel

The group at CWI in Amsterdam have produced an incremental parser
generator based on Tomita's technique.

Some references:

    AUTHOR = "Masaru Tomita",
    TITLE = "Efficient Parsing for Natural Language",
    PUBLISHER = "Kluwer Academic Publishers",
    YEAR = 1980,

    AUTHOR = "Masaru Tomita",
    TITLE = "An Efficient Augmented-Context-Free Parsing Algorithm",
    JOURNAL = "Computational Linguistics",
    YEAR = 1987,
    MONTH = "January--June",
    VOLUME = 13,
    NUMBER = "1--2",
    PAGES = "31-46",

    AUTHOR = "J. Heering and P. R. H. Hendriks and P. Klint and J. Rekers",
    TITLE = "The Syntax Definition Formalism {SDF}---Reference Manual",
    YEAR = 1989,
    NUMBER = "CS-R8926",

    AUTHOR = "J. G. Rekers",
    TITLE = "Modular Parser Generation",
    YEAR = 1989,
    MONTH = sep,
    NUMBER = "CS-R8933",

    AUTHOR = "J. Heering and P. Klint and J. Rekers",
    TITLE = "Principles of Lazy and Incremental Program Generation",
    YEAR = 1987,
    MONTH = nov,
    NUMBER = "CS-R8749",

Stephen Adams Email:
Electronics and Computer Science Tel: 0703 593649
University of Southampton Fax: 0703 593045
Southampton SO9 5NH, UK

Post a followup to this message

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