Re: parsers for ambiguous grammars?

dekker@dutiws.twi.tudelft.nl (Rene Dekker) writes:


  >I am looking for parsing techniques that can handle a highly ambiguous
  >grammar and are able to generate partial parses. I am aware that
  >chart-parsers can do such a thing, but I am looking for other techniques
  >also.


  >I am particularly interested in parsers that aply these techniques to
  >graphs. Any pointer to literature or ideas on this matter are welcome.


Tabular parsing and graphs? One paper comes to mind:


Hemerik and Katoen: Bottom-up tree acceptors
Science of Computer Programming 13, 51-72


PS. Chart parsing is a particular view of tabular parsing, with specific
terminology and notation (which I very much dislike). Other examples of
tabular parsing are graph-structured stacks (e.g. Tomita's algorithm) and
dynamic programming for parsing (see the papers by Bernard Lang) and even
memo functions (applied to e.g. functional recursive-descent parsers).


Mark-Jan Nederhof
University of Nijmegen
--

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