Skip to Main Content
flex & bison
book

flex & bison

by John Levine
August 2009
Intermediate to advanced content levelIntermediate to advanced
292 pages
7h 31m
English
O'Reilly Media, Inc.
Content preview from 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 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Head First Design Patterns, 2nd Edition

Head First Design Patterns, 2nd Edition

Eric Freeman, Elisabeth Robson
Learning React, 2nd Edition

Learning React, 2nd Edition

Alex Banks, Eve Porcello

Publisher Resources

ISBN: 9780596805418Errata Page