Re: Parsing fully context-free grammars

"Paul Mann" <paul@parsetec.com>
2 Oct 2005 02:49:56 -0400

          From comp.compilers

Related articles
Parsing fully context-free grammars lowell@coasttocoastresearch.com (Lowell Thomas) (2005-09-17)
Re: Parsing fully context-free grammars haberg@math.su.se (2005-09-18)
Re: Parsing fully context-free grammars lowell@coasttocoastresearch.com (Lowell Thomas) (2005-09-22)
Re: Parsing fully context-free grammars haberg@math.su.se (2005-09-23)
Re: Parsing fully context-free grammars paul@parsetec.com (Paul Mann) (2005-10-02)
Re: Parsing fully context-free grammars haberg@math.su.se (2005-10-02)
Re: Parsing fully context-free grammars drikosv@otenet.gr (Evangelos Drikos) (2005-10-03)
Re: Parsing fully context-free grammars paul@parsetec.com (Paul Mann) (2005-10-04)
Re: Parsing fully context-free grammars hannah@schlund.de (2005-10-06)
Re: Parsing fully context-free grammars drikosv@otenet.gr (Evangelos Drikos) (2005-10-07)
Re: Parsing fully context-free grammars lowell@coasttocoastresearch.com (lowell@coasttocoastresearch.com) (2005-10-20)
| List of all articles for this month |

From: "Paul Mann" <paul@parsetec.com>
Newsgroups: comp.compilers
Date: 2 Oct 2005 02:49:56 -0400
Organization: Compilers Central
Keywords: parse
Posted-Date: 02 Oct 2005 02:49:56 EDT

> Also, APG always disambiguates to a single parse tree. However,
> looking at the "dangling else", I've found that is easy to get either
> translation from the single parse tree. That is,
>
> if(expr) then {if(expr) then {stmt} else {stmt}}
> or
> if(expr) then {if(expr) then {stmt}} else {stmt}.
>
> Lowell Thomas


This is one of the problems with GLR parsers. 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.


This problem can be resolved at the grammar level and avoid the
ambiguity at the parsing level. This creates a shift-reduce conflict
which is resolved by chosing the shift action by most parser generators
of the non-GLR type.


The problem is the ambiguity in the grammar, which cannot be solved by
later symbol-table lookup's and discarding subtrees with semantic errors.


It's just plain ambiguous and shows one of the pitfalls of GLR systems.


Paul Mann
http://parsetec.com


Post a followup to this message

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