Re: Parsing fully context-free grammars

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

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