O'Reilly logo

lex & yacc, 2nd Edition by Tony Mason, John Levine, Doug Brown

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required