help-bison
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: how does bison detect conflicts?


From: Hans Aberg
Subject: Re: how does bison detect conflicts?
Date: Wed, 13 Nov 2002 13:58:52 +0100

At 15:35 +0100 2002/11/12, SainTiss wrote:
>I've just read the bison manual online, and there's one thing that isn't
>really clear:
>
>I got the impression that conflicts, like shift/reduce can be detected
>when the actual input is being parsed by yyparse()...
>
>yet it seems that bison already tells me that there are such conflicts
>during the generation of the parser code!
>
>How does it do that? Surely bison doesn't "try" every possible input
>combination?

Bison uses the LALR(1) algorithm which is described in many books, for
example the widespread Aho, Sethi, Ullman, "Compilers...".

Roughly, such algorithms compute, given an input grammar, all possible
lookaheads, and detect conflicts via that analysis.

It generates an output for a so called push-down automaton state machine.
The states correspond in LR(n) algorithm to a set of rules each which a dot
in the RHS indicates how far the parsing has reached at that point, plus
some extra information when one can reduce.

  Hans Aberg






reply via email to

[Prev in Thread] Current Thread [Next in Thread]