Re: Questions about Bison's implementation

[Hans Aberg]

At 13:11 +0000 2002/02/19, Carlos Javier Borges Villalba wrote:
>I have some question about Bison's implementation. I would like to know in
>deed how it converts the LR(0) automata into a LALR.

What do you mean by this? -- The stack machine is the same for all LR
bottom up (deterministic) state machines; only the states and transitions
differ.

> (Please do not tell me
>to read the Dragon Book. I cannot see any correspondence between Bison and
>the algoritm that I can find on the book).

You might check the REFERENCES file in the Bison distribution. Also Pete
Jinks <address@hidden> suggested me in comp.compilers:
>Hans Aberg wrote:
>>
>> Can somebody give a reference to a description of the LALR(1)
>> algorithm that Bison uses?
>>
>> The file state.h of the Bison sources says that first, a
>> non-deterministic finite state machine that parses the specified
>> grammar is created; it is then converted into a deterministic finite
>> state machine.
>
>I don't know what Bison uses, but your description sounds like the
>algorithm I first came across in:
>        Syntax Analysis and Software Tools
>        K.John Gough
>        Addison-Wesley 1988
>        chapter 9 Bottom-up parsing
>The references there point to
>        D.E.Knuth (1965)
>        On the translation of languages from left to right
>        Information and control v8 pp323-350
>which apparently covers both this and the "usual" form of the algorithm.

Perhaps the book at http://www.cs.vu.nl/~dick/PTAPG.html can give some input.

>About how Bison solves the conflicts we have the next question. Why have we
>differents results for the next grammar if we change the rules order?
>
>left a
>left b
>left c
>
>S->Ab
>S-> ABb
>S->ab
>A->a
>B-> %prec c

I do not know exactly how Bison resolves this. Aho et al "Compilers...",
sec 4.6 deals with operator precedences, but not merged into LR.

Here is suggestion: What one needs is a precedence function p(x, y), taking
the values "shift", "reduce", or "error" if they do not compare, to compare
token precedence when (essentially) x is on top of the stack and y is the
next token.

If precedence(x) < precedence(y), set p(x, y) = shift, if precedence(x) >
precedence(y), set p(x, y) = reduce. If precedence(x) = precedence(y):
  x, y left associative => p(x, y) = reduce
  x, y right associative => p(x, y) = shift
  x, y non-associative => p(x, y) = error

Then, as for Bison, I think it might merely first compute the LALR(1)
algorithm, keeping track of all conflicts. Then if conflicts arise, the
function p(x, y) is applied in order to resolve shift/reduce them, if
possible.

A brief look at one of my Bison .output examples suggests that if there is
say a reduce/shift conflict between the rule x -> x1 ... xn and the token
y, then Bison resolves this by looking at the topmost (= last) token xj of
x1 ... xn, and set the shift/reduce choice to p(xj, y). Then one may have
to refine that crude analysis.

  Hans Aberg