Re: Parsing fully context-free grammars

> "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.


There is nothing wrong with notation that allows a dangling else.
The problem is the dangling else, not the notation.


> 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.


Nope, shift-reduce conflicts are valid conflicts. To avoid these
additional notation could be added which would work like the PEG '/'
notation.


IfStmt -> if '(' Exp ')' Stmt else Stmt
                / if '(' Exp ')' Stmt


In PEG parser generators this will not cause a conflict,
because by definition it will choose the shift action. It will
not cause a conflict in an LR parser generator that has an option
to ignore all shift-reduce conflicts (like LRgen has).


> 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>


This grammar does not have the dangling else problem, so it is
a different grammar and different language.


BTW, this grammar is unworkable in LR/LALR parser generators.
<stmt> is unreducible. It is a circular grammar.


Paul Mann
http://parsetec.com

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