Re: Parsing fully context-free grammars

"Paul Mann" <paul@parsetec.com>
4 Oct 2005 01:46:26 -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: 4 Oct 2005 01:46:26 -0400
Organization: Compilers Central
Keywords: parse
Posted-Date: 04 Oct 2005 01:46:26 EDT

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


Post a followup to this message

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