flex & bison

Chapter 3. Using Bison

The previous chapter concentrated on flex alone. In this chapter we turn our attention to bison, although we use flex to generate our lexical analyzers. Where flex recognizes regular expressions, bison recognizes entire grammars. Flex divides the input stream into pieces (tokens), and then bison takes these pieces and groups them together logically. In this chapter we’ll finish the desk calculator we started in Chapter 1, starting with simple arithmetic and then adding built-in functions, user variables, and finally user-defined functions.

How a Bison Parser Matches Its Input

Bison takes a grammar that you specify and writes a parser that recognizes valid “sentences” in that grammar. We use the term sentence here in a fairly general way—for a C language grammar, the sentences are syntactically valid C programs. Programs can be syntactically valid but semantically invalid, for example, a C program that assigns a string to an int variable. Bison handles only the syntax; other validation is up to you. As we saw in Chapter 1, a grammar is a series of rules that the parser uses to recognize syntactically valid input. For example, here is a version of the grammar we’ll use later in this chapter in a calculator:

statement:   NAME '=' expression

expression:  NUMBER '+' NUMBER
           | NUMBER '−' NUMBER

The vertical bar, |, means there are two possibilities for the same symbol; that is, an expression can be either an addition or a subtraction. The symbol to the left of the : is ...