lex & yacc, 2nd Edition

Chapter 8. Yacc Ambiguities and Conflicts

This chapter focuses on finding and correcting conflicts within a yacc grammar. Conflicts occur when yacc reports shift/reduce and reduce/reduce errors. Finding them can be challenging because yacc points to them in y.output,^[19] which we will describe in this chapter, rather than in your yacc grammar file. Before reading this chapter, you should understand the general way that yacc parsers work, described in in Chapter 3, Using Yacc .

The Pointer Model and Conflicts

To describe what a conflict is in terms of the yacc grammar, we introduce a model of yacc’s operation. In this model, a pointer moves through the yacc 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 yacc 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 yacc 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, we will leave out the %token and the %%.) There are two ways for pointers to disappear. One is for a token to eliminate one or more pointers because only one still matches the input. If the next token that yacc reads is C, the second pointer will disappear, and the first pointer ...