Re: A big easy subset of the CFGs

In an ongoing public discussion between "Matt Timmermans"
<mtimmerm@microstar.com> and me.


I said:
c>However, a second reason why we haven't pursued non-canonical parsing
c>more actively is that it actually complicates the conflict reporting
c>process. The types of conflicts which can occur in a non-canonical
c>parser are more subtle than in a simple LR parser. Our experiments
c>suggest that writting and debugging a non-canonical grammar may
c>actually be more difficult (once you get past trivial grammars).


And Matt Replied:
m>This is the part that bothers me. How sure are you that this is a
m>product of non-cannonical parsing, rather than the conflict report
m>itself?


I'm not certain. At some level it is hard to distinguish problems in
the implementation from problems in the theory. Particularly when 1)
you are looking at the implementation and trying to make it work and
2) there is little of no written theory (at your disposal) covering
the specific implementation issues you are looking at.


More of Matt's reply:
m>Non-bizarre ambiguity rules, however, should make it possible to do to
m>much friendlier conflict reporting, like "In an If-statement, IF x
m>THEN IF y THEN z ELSE ... could mean IF x THEN (IF y THEN z ELSE ...)
m>or IF x THEN ( IF y THEN z ) ELSE ...". That is to say, conflict
m>reporting by smallest possible example of alternate sentiential forms. . . .


That may work. If I remember right, the Cocktail system uses that
basic approach (even for the LALR cases which don't have the
non-bizarre ambiguity problems you desire).


BTW, just a personal foible of mine, but I think we should be a little
careful about terminology and reserve the term ambiguous for grammars
which cannot be resolved by any parsing method (i.e. there is more
than one legal parse tree representing some input) and use the term
conflict when any given (LL, LR, LR(term), LR-regular, ...) parsing
method cannot resolve the grammar (i.e. the generated parser doesn't
know how to construct the one valid parse tree for some input). I
think it is a little presumptuous of us parser generator writers to
elevate the problems that our particular parsing methodology cannot
handle to the level of general parsing problems.


One last note, if you really want to make translation easy, I would
suggest working on the following approach. Build a very general
parser (e.g. an Earley parser or even better the Lang-Tomita
variation--see Nigel Horspool's web page for some more ideas on this)
and have it simply build the appropriate see of potential parse trees.
Then, use the concept of coupled (or synchronized) [attribute]
grammars to match the parse tree with an output tree which you then
un-parse (or generate). The FNC-2 system has a nice write up on
coupled attribute grammars. A similar approach is used in the XTAG
system (I think they call them synchronized trees). Anyway, that
approach is very general and even the possibility of having an
ambiguous grammar won't cause it problems--there are simply two
choices, either the parser outputs all of the possible translations
when the choice is ambiguous or the parser generator selects one
output translation according to some set of rules.


-Chris Clark
************************************************************************
Compiler Resources, Inc. email: compres@world.std.com
3 Proctor St. http://world.std.com/~compres
Hopkinton, MA 01748 phone: (508) 435-5016
USA 24hr fax: (508) 435-4847
--

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