Re: (long) conflict resolution in action table

Tim Newsham <newsham@lava.net> wrote:


> I have a comment about using precedence to disambiguate the
>actions in a shift-reduce parser. I've found two approaches so
>far:
...
> - Give priorities and associativities to terminals....
...
> - Use a set of conflict constraints when generating the LR0
> goto table and the follow set of each production ...
>... This method is outlined by Visser
> in the following two papers: ...


>I'd be interested in hearing of other approaches.


I have just (a few months ago) generalized the Visser approach to
"constrained grammars" for use with LR parsing. (I'll email you a copy
the paper.) The first method above should depend heavily on the
parsing algorithm used, but the point of this constrained grammars
extension of the Visser method is that it depends only on the
grammar. A constrained grammar can easily be rewritten to an ordinary
context free grammar.


> The end effect is that the resulting action tables [of the Visser
> method] will have many shift/reduce conflicts that the precedence
> rules imply should have been elimianted.


This is correct. If you need to have a low number of states, the first
method above should used. But then you loose the parsing algorithm
independence. In the quoted paper, I give an example, namely the
"dangling-else" problem which will be resolved by different precedence
rules in the two methods.


>My comment: Visser's method seems very elegant for completely
>disambiguating conflicts in a set of productions, but if you wish
>to partially disambiguate the productions, it may not do as much
>as you would hope.
>
>My question: Is there anyway to augment Visser's conflict resolution
>so that it can be more effective when resolving a subset of the
>conflicts that occur? For example, is there a method that could
>produce a parser for my simple expression grammar that only encountered
>a ambiguity when the "^" operator was present in an input sentance?


This is exactly what I do by the constrained grammars: One can for any
grammar variable argument in any rule specify exactly which expansions
to be admitted. For arguments that admit some such constraints, the LR
parsing table will instead of keeping track of the grammar variable
being reduced, have an entry for each reduction possible. If no
constrains is imposed, this is not needed, so it then reduces to
traditional parsing.


    Hans Aberg

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