Re: Parsing fully context-free grammars
- From: "Paul Mann" <paul@xxxxxxxxxxxx>
- Date: 4 Oct 2005 01:46:26 -0400
> "Paul Mann" <paul@xxxxxxxxxxxx> 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
.
- Follow-Ups:
- Re: Parsing fully context-free grammars
- From: Hannah Schroeter
- Re: Parsing fully context-free grammars
- Prev by Date: Re: Predicates
- Next by Date: Code generation tool
- Previous by thread: Re: Parsing fully context-free grammars
- Next by thread: Re: Parsing fully context-free grammars
- Index(es):
Relevant Pages
|
