Re: LR(n) parsers

In article 91-10-036 whatis@ucsd.edu (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
parsers.


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


Some references:


@BOOK{to:effi,
    AUTHOR = "Masaru Tomita",
    TITLE = "Efficient Parsing for Natural Language",
    PUBLISHER = "Kluwer Academic Publishers",
    YEAR = 1980,
}




@ARTICLE{to:augm,
    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",
}


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


@TECHREPORT{re:modu,
    AUTHOR = "J. G. Rekers",
    TITLE = "Modular Parser Generation",
    INSTITUTION = CWI,
    YEAR = 1989,
    MONTH = sep,
    NUMBER = "CS-R8933",
}


@TECHREPORT{he:prin,
    AUTHOR = "J. Heering and P. Klint and J. Rekers",
    TITLE = "Principles of Lazy and Incremental Program Generation",
    INSTITUTION = CWI,
    YEAR = 1987,
    MONTH = nov,
    NUMBER = "CS-R8749",
}


--
Stephen Adams Email: S.R.Adams@ecs.soton.ac.uk
Electronics and Computer Science Tel: 0703 593649
University of Southampton Fax: 0703 593045
Southampton SO9 5NH, UK
--

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