Re: GLR Parsing Generator

Chris F Clark <cfc@world.std.com>
12 Jun 1999 21:25:08 -0400

          From comp.compilers

Related articles
GLR Parsing Generator puehler@uni-koblenz.de (Thomas =?iso-8859-1?Q?P=FChler?=) (1999-06-06)
Re: GLR Parsing Generator dwight@pentasoft.com (1999-06-12)
Re: GLR Parsing Generator cfc@world.std.com (Chris F Clark) (1999-06-12)
Re: GLR Parsing Generator bromage@cs.mu.OZ.AU (1999-06-12)
Re: GLR Parsing Generator adrian@dcs.rhbnc.ac.uk (1999-06-15)
| List of all articles for this month |

From: Chris F Clark <cfc@world.std.com>
Newsgroups: comp.compilers,comp.lang.c++
Date: 12 Jun 1999 21:25:08 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 99-06-033
Keywords: parse, C++

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)


Post a followup to this message

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