Re: Parsing fully context-free grammars

Thanks for all of your comments. I've found them all to be interesting and
useful.


paul@parsetec.com (Paul Mann) (2005-10-02) wrote:
>This is one of the problems with GLR parsers.


However, I would like to point out again that APG generates
recursive-decent, not GLR parsers. Albeit, not the same
recursive-decent algorithm as defined in the Dragon Book and not
limited to LL grammars. However, even though it currently
disambiguates to a single parse tree, it could easily be modified to
branch out and generate all parse trees in parallel as GLR does. The
question I'm interested in is, is there any reason to do so?


>When you have a grammar that is ambiguous, such as this case of the
>dangling 'else' problem, then you get a parser that is ambiguous
>also.


Not necessarily. It depends on how you write the semantic actions. I
did a little experimentation with the "dangling else" problem and
developed a fairly simple C-language program that demonstrates four
different approaches to dealing with it. The fourth strategy is to
develop semantic actions which get the translation you want
independent of which parse tree you use. The four strategies are:


1) The "classical" multiple parse tree strategy. The semantic actions
stay fixed and you get different translations from the different parse
trees


haberg@math.su.se (2005-10-02) wrote:
>> It seems to me that this could be generalized to say, in effect, that
>> any tree from the forest can be emulated by any other. Does anyone
>> know of a contradiction to this?
>So there are indeed situations where this is useful and used. But I do not
>know of any general exploration of the topic.


2) The simulated parse tree strategy. This is what I was referring to
in my original post in this thread. This strategy assumes that you can
get any translation you like from any parse tree. The example shows
"cross" translations. That is, generating translation 2 from parse
tree 1 and vice versa.


paul@parsetec.com (Paul Mann) (2005-10-02) wrote:
>This problem can be resolved at the grammar level and avoid the
>ambiguity at the parsing level.


3) The unambiguous grammar strategy. The translation here is similar
to the first, multiple parse tree strategy except you write an
unambiguous grammar which gives the only the parse tree you want and
nothing more. (The example gives an unambiguous grammar for each of
the two parse trees in this demonstration.)


4) The universal translation strategy. In this example semantic
actions are developed which give the translation you want independent
of which parse tree you use. I like this one best. But this is a
simple problem. I hope it proves to have some durability as I become
more experienced with tougher problems.


You can find a copy of the source code for the demonstration program
and more detailed discussion at
http://www.coasttocoastresearch.com/CompCompilersDEDemo.htm/.


Lowell Thomas

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