Re: GLR Parsing Generator

Thomas P=FChler asked for pointers to GLR parser generators to use for
building a C++ parser.


If I read the advertising blurbs right, the "Natural Language
Processing" of VisualParse++ is GLR parsing.


There are also several free implementations on the net. A search with
for keywords like GLR and Tomita should get you references to "TOM"
written by Mark Hopkins. Nigel Horspool also has a paper mentioning a
GLR implmentation.


The ASF+SDF tools appear to be GLR based also. (Jan Rekers et. al. at
CWI(?))


However, with GLR parsing and an ambiguous grammar like C++, in the
end you are going to have to prune the shared parse forest down to the
correct parse. You want the pruning to be automatic and to always
yield the correct parse. My impression is that the choice between
different ambiguous parse trees can require user interaction in a GLR
system.


To my mind, predicated grammars are a better choice (than GLR) for
that. The reason is that with a predicated grammar, you specify in
the grammar how you want the ambiguity resolved and it becomes
embedded in the generated parser. The grammar designer knows in
advance that there will be no unresolved ambiguities. There are
several options for predicated parsing: Yacc++, ANTLR, and PCCTS. (I
don't recall whether RDP does predicated parsing or not, but it may be
a 4th candidate.) {BTW, the fact that I helped write Yacc++ might
explain my bias in that regard.}


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

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