Re: Parsing fully context-free grammars

> Also, APG always disambiguates to a single parse tree. However,
> looking at the "dangling else", I've found that is easy to get either
> translation from the single parse tree. That is,
>
> if(expr) then {if(expr) then {stmt} else {stmt}}
> or
> if(expr) then {if(expr) then {stmt}} else {stmt}.
>
> Lowell Thomas

This is one of the problems with GLR parsers. When you have a grammar
that is ambiguous, such as this case of the dangling 'else' problem,
then you get a parser that is ambiguous also.

This problem can be resolved at the grammar level and avoid the
ambiguity at the parsing level. This creates a shift-reduce conflict
which is resolved by chosing the shift action by most parser generators
of the non-GLR type.

The problem is the ambiguity in the grammar, which cannot be solved by
later symbol-table lookup's and discarding subtrees with semantic errors.

It's just plain ambiguous and shows one of the pitfalls of GLR systems.

Paul Mann
http://parsetec.com
.

Relevant Pages

  • Re: Parsing ambiguities
    ... elegant way to generate parsers that can deal with ambiguity. ... Error Correcting Parser Combinators: ... If yours is "the same" as Parsec (no way ... prepositional phrases just plain aren't in the grammar ...
    (comp.lang.misc)
  • Re: BNF notation needed
    ... The parser uses a grammar that relies on the category associated with ... do not fit the natural categories required by the parser and its ... deal well with context sensitive grammars. ... In automatic parsers the ambiguity is normally not ...
    (comp.lang.fortran)
  • Re: Is pyparsing really a recursive descent parser?
    ... The important part is what it recurses through... ... of that grammar meant. ... ambiguity doesn't have to do with recognizing the language. ... PyParsing is parser. ...
    (comp.lang.python)
  • Re: Parsing ambiguities
    ... I found a paper on "limited repair" of parse trees, ... obvious way to deal with ambiguity is to generate all the (combinatorial ... A standard technique for this is to parse using a context-free parser, ... An efficient method for doing this is GLR parsing, ...
    (comp.lang.misc)
  • Re: "Order by" clause
    ... While there is no actual ambiguity, the parser is not so sure. ... explicitly as the first column and once again in the *. ... parser does not try to figure out the meaning of the query. ...
    (microsoft.public.sqlserver.mseq)