flex & bison

Chapter 7. Ambiguities and Conflicts

This chapter focuses on finding and correcting conflicts within a bison grammar. Conflicts occur when bison reports shift/reduce and reduce/reduce errors. Bison lists any errors in the listing file name.output, which we will describe in this chapter, but it can still be a challenge to figure out what’s wrong with the grammar and how to fix it. Before reading this chapter, you should understand the general way that bison parsers work, described in Chapter 3.

The Pointer Model and Conflicts

To describe what a conflict is in terms of the bison grammar, we introduce a model of bison’s operation. In this model, a pointer moves through the bison grammar as each individual token is read. When you start, there is one pointer (represented here as an up arrow, ↑) at the beginning of the start rule:

%token A B C
%%
start:     ↑ A B C;

As the bison parser reads tokens, the pointer moves. Say it reads A and B:

%token A B C
%%
start:     A B ↑ C;

At times, there may be more than one pointer because of the alternatives in your bison grammar. For example, suppose with the following grammar it reads A and B:

%token A B C D E F
%%
start:      x
     |      y;
x:    A B ↑ C D;
y:    A B ↑ E F;

(For the rest of the examples in this chapter, all capital letters are tokens, so we will leave out the %token and the %%.) There are two ways for pointers to disappear. One happens when a subsequent token doesn’t match a partially matched rule. If the next token that the parser reads is C, the second pointer ...