Re: Parsing fully context-free grammars

"Evangelos Drikos" <drikosv@otenet.gr>
3 Oct 2005 00:30:24 -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: "Evangelos Drikos" <drikosv@otenet.gr>
Newsgroups: comp.compilers
Date: 3 Oct 2005 00:30:24 -0400
Organization: An OTEnet S.A. customer
References: 05-10-008
Keywords: parse

Hi Paul,
Hi all,


"Paul Mann" <paul@parsetec.com> wrote
> It's just plain ambiguous and shows one of the pitfalls of GLR systems.


I don't see why this is pitfall of GLR parsers; rather I think is a
pitfall of the grammar notation we use.


If the grammar is ambiguous but we always mean shift 'else' and not
reduce the <if-statement> then the problem is profoundly that we have
not stated it in the grammar.


If we always prefer to solve a shift/reduce conflict by favoring shift
we mean match "else" to the last "if".




Given this grammar:


  <stmt> ::= <if-stmt>


  <if-stmt> ::= if ( cond ) <stmt>
                                  | if ( cond ) <stmt> else <stmt>


The following text causes an ambiguity:


if ( aa > bb ) if ( aaa > bbbb ) aaa = bbb else bbb = cccc


We could disambiguate by restating the grammar as:


<stmt> ::=
                      <if-stmt>
          | <if-else-stmt>




<if-stmt> ::=
                      if ( cond ) <stmt>




<if-else-stmt> ::=
                      if ( cond ) <non-if-stmt> else <stmt>


<non-if-stmt> ::=
                    <if-else-stmt>


One could argue that it is not always convenient and I could also agree;


The reason is that the grammar notation "doesn't support" what we "always"
want to say in a convenient manner.


The additional rule is used to emphasize that the <non-if-stmt> is any
<stmt> "but not" the <if-stmt>.


That is one thing probably missing from the grammar notation, the operator
"but not". Then we could say:


<if-else-stmt> ::= if ( cond ) <stmt> "but not" <if-stmt> else <stmt>


Another solution, a third solution, would be to execute a semantic check.


Actually, I'd prefer the "but not" operator.




>This problem can be resolved at the grammar level and avoid the
>ambiguity at the parsing level.


I agree, as long as one states it in the grammar.


Thanks,


Ev. Drikos


Post a followup to this message

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