Re: Bison Question: Ambiguous Grammar?

[Hans Aberg]

At 19:21 +0200 2005/05/06, Claus Brabrand wrote:
> Yes, I realize there's no parse tree beyond what I may chose to 
> construct in the action code myself.
>
> What I meant is: is there a way for Bison to take the actions 
> according to one (any) of the parses?

The current Bison GLR parsers work so that when parsing an ambiguous 
rule, the parser splits, and parses without executing any actions 
until the ambiguous rule has finished parsing. Then the actions of 
the successful parses, if any, are executed. There is currently no 
way to get actions executed immediately, even though Paul Hilfinger, 
who wrote %glr, is considering this as a feature.

> I am using Bison in GLR-mode for code-generating syntax-directed 
> transformations (executed in
> the action code). The grammars are highly ambiguous which is fine: I 
> just want to execute actions
> for one (any) of the parses.

Then you have to choose one of the parses according to the methods 
indicated in the Bison manual. I do not know if there is a way to 
avoid actions to be executed in the unwanted parses, if there is more 
than one successful parses; possibly you have to write the actions, 
so that they are not harmful in such a case.

> I have a grammar which is capable of parsing a string (and returning 
> a transformed string which is
> just the result of executing the corresponding action code). Now, 
> when I add a certain production to
> this grammar, I get a parse error in the middle of the string it was 
> able to parse without this
> extra production(?!?) What I don't understand is how adding a 
> production to a grammar G can cause it
> to reject the string - it should just enlarge the language induced 
> by the grammar - and so, that if it was
> capable of parsing my string before, it should also be able to do so 
> after (with the extra production).
>
> This really puzzles me(?)

If the parser constructed all parse trees, that would be the case, 
but in LALR(1), and scans the rules in order. So then funny things 
can happen. I do not know if this is the case; you give no details. 
Also, you might ask this question in the newsgroup comp.compiles, 
providing the details.

> Is Bison's GLR algorithm intended for ambiguous grammars or will it 
> only work on the subset of
> grammars that are unambiguous (LALR(1) or not)? Maybe this 
> particular production renders the
> grammar ambiguous (at least wrt. my input string - i.e. that my 
> string has two parses).

When making this GLR extension, it should work with all ambiguous 
grammars. The drawback, though, is that it only splits the ambiguous 
rules, and then merges them when finished. Of one then wants to keep 
track of all parses, then one will have to do that via the actions. 
Thus, there is a difference between GLR based on LALR(1) or on LR(1). 
The advantage of this approach, though, over a genuinely 
non-deterministic parsing, is that the latter is very slow.
--
  Hans Aberg