Sensible parsing with Flex and Bison

To build it:

The reason it prints non-matching words (such as “the”) is that there’s an
implicit rule matching any character (.) and echoing it. In most real parsers
we’ll want to override that.

Here’s what’s happening inside the scanner. Lex reads the regexes and generates
a state machine to consume input. Below is a visualization of the states, with
transitions labeled by input character. The circles with a double outline
indicate states that trigger actions.

Note there’s no notion of word boundaries in our lexer, it’s operating on
characters alone. For instance:

That sounds rather like an insult.

An important subtlety is how Lex handles multiple eligible matches. It picks
the longest possible match available, and in the case of a tie, picks the
matching pattern defined earliest.

To illustrate, suppose we add a looser regex, c.t, first.

Lex detects that the rule masks cat and cot, and outputs a warning:

catcot.l:10: warning, rule cannot be matched
catcot.l:11: warning, rule cannot be matched

It still compiles though, and behaves like this:

echo "the cat on the cot joined the cats" | ./catcot
the mumble mumble on the mumble mumble joined the anti-herd

Notice that it still matched cats, because cats is longer than c.t.

Compare what happens if we move the loose regex to the end of our rules. It can
then pick up whatever strings get past the others.

It acts like this:

echo "cut the cot" | ./catcot
mumble mumble the portable bed

Now’s a good time to take a detour and observe how our user-defined code acts
in the generated C file. Lex creates a function called yylex(), and inserts
the code blocks verbatim into a switch statement. When using lex with a parser,
the parser will call yylex() to retrieve tokens, named by integers. For now,
our user-defined code isn’t returning tokens to a parser, but doing simple
print statements.

As mentioned, a lex file is comprised of three sections:

DEFINITIONS

%%

RULES

%%

HELPER FUNCTIONS

The definitions section is where you can embed C code to include headers and
declare functions used in rules. The definitions section can also define
friendly names for regexes that can be reused in the rules.

The rules section, as we saw, contains a list of regexes and associated user
code.

The final section is where to put the full definitions of helper functions.
This is also where you’d put the main() function. If you omit main(), the
Lex library provides one that simply calls yylex(). This default main()
implementation (and implementations for a few other functions) is available by
linking your lex-generated C code with -ll compiler flag.

Let’s see a short, fun example: converting Roman numerals to decimal. Thanks to
lex’s behavior of matching longer strings first, it can read the single-letter
numerals, but look ahead for longer subtractive forms like “IV” or “XC.”

More realistic scanner

Now that we’ve seen Lex’s basic operation in the previous section, let’s
consider a useful example: syntax highlighting. Detecting keywords in syntax is
a problem that lex can handle by itself, without help from yacc.

Using a scanner as a library

One of the biggest areas of improvement between classic lex/yacc and flex/bison
is the ability of the latter to generate code that’s easier to embed into a
larger application. Lex and yacc are designed to create standalone programs,
with user-defined code blocks stuck inside. When classic lex and yacc work
together, they use a bunch of global variables.

Flex and Bison, on the other hand, can generate thread-safe functions with
uniquely prefixed names that can be safely linked into larger programs. To
demonstrate, we’ll do another scanner (with Flex this time).

The following Rube Goldberg contraption uses Flex to split words on whitespace
and call a user-supplied callback for each word. There’s certainly an easier
non-Flex way to do this task, but this example illustrates how to encapsulate
Flex code into a reusable library.

Build it like this:

%option noyyalloc noyyfree noyyrealloc

/* add in a code block by the %options */
#define YY_EXIT_FAILURE ((void)yyscanner, EXIT_FAILURE)

/* add definitions down by words_callback */

void *wordsalloc(size_t size, void *yyscanner)
{
    (void) yyscanner;
    return malloc(size);
}

void *wordsrealloc(void * ptr, size_t size, void *yyscanner)
{
    (void) yyscanner;
    return realloc(ptr, size);
}

void wordsfree(void *ptr, void *yyscanner)
{
    (void) yyscanner;
    free(ptr);
}

A calling program can use our library without seeing any Flex internals.

To build the program, just link it with words.o.

Parsing

Now that we’ve seen how to identify tokens with a scanner, let’s learn how a
parser can act on the tokens using recursive rules. Yacc/byacc/bison are LALR
(look-ahead left recursive) parsers, and Bison supports more powerful modes if
desired.

Mental model of LR parsing

LR parsers build bottom-up toward a goal, shifting tokens onto a stack and
combining (“reducing”) them according to rules. It’s helpful to get a mental
model for this process, so let’s jump into a simple example and simulate what
yacc does.

Here’s a yacc grammar with a single rule to build a result called foo. We
specify that foo is comprised of lex tokens A, B, and C.

Yacc transforms the grammar into a state machine which looks like this:

The first rule in the file (and the only rule in our case) becomes yacc’s
goal. Yacc begins in state 0, with the implicit rule 0: $accept: • foo $end.
The parse will be accepted if we can produce a foo followed immediately by
the end of input. The bullet point indicates our progress reading the input. In
state 0 it’s at the beginning, meaning we haven’t read anything yet.

Initially there’s no lookahead token, so yacc calls yylex() to get one. If
lex produces an A, we follow the state transition to state 1. Because the arrow
is a solid line, not dashed, yacc “shifts” the token to its token stack. It also
pushes state 1 onto a state stack, which now holds states 0 and 1.

State 1 is trying to satisfy the rule which it calls rule 1, namely 1 foo: A • B C. The bullet point after the A indicates we’ve seen the A already. Don’t
confuse the state numbers and rule numbers – yacc numbers them independently.

Yacc continues processing input, shifting tokens and moving to states 3 and 5
if lex produces the expected tokens. If, at any point, lex produces a token not
matching any transitions in the current state, then yacc reports a syntax error
and terminates. (There’s a way to do error recovery, but that’s another topic.)

State 5 has seen all necessary tokens for rule 1: 1 foo: A B C •. Yacc
continues to the diamond marked “R1,” which is a reduction action. Yacc
“reduces” rule 1, popping the A, B, C terminal tokens off the stack and pushing
a single non-terminal foo token. When it pops the three tokens, it pops the
same number of states (states 5, 3, and 1). Popping three states lands us back
in state 0.

State 0 has a dashed line going to state 2 that matches the foo token that was
just reduced. The dashed line means “goto” rather than “shift,” because rule 0
doesn’t have to shift anything onto the token stack. The previous reduction
already took care of that.

Finally, state 2 asks lex for another token, and if lex reports EOF, that
matches $end and sends us to state 4, which ties a ribbon on it with the
Acc(ept) action.

From what we’ve seen so far, each state may seem to be merely tracking progress
through a single rule. However, states actually track all legal ways forward
from tokens previously consumed. A single state can track multiple candidate
rules. For instance:

For this grammar, yacc produces the following state machine:

In state 1 we’ve seen token A, and so rules 3 and 4 are both in the running to
reduce an x or y. On a B or C token, the possibilities narrow to a single rule
(in state 5 or 6).

Also notice that our rule foo : x | y doesn’t occur verbatim in any states.
Yacc separates it into 1 foo: x and 2 foo: y. Thus, the numbered rules
don’t always match the rules in the grammar one-to-one.

Yacc can also use peek ahead by one token to choose which rule to reduce,
without shifting the “lookahead” token. In the following grammar, rules x and y
match the same tokens. However, the foo rule can say to choose x when followed
by a B, or y when followed by a C:

Note multiple reductions coming out of state 1 in the generated state machine:

The presence of a bracketed token ([C]) exiting state 1 indicates that the
state uses lookahead. If the state sees token C, it reduces rule 4. Otherwise
it reduces rule 3. Lookahead tokens remain to be read when following a
dashed-line (goto) action, such as from state 0 to state 4.

Ambiguous grammars

While yacc is a powerful tool to transform a grammar into a state machine, it
may not operate the way you intend on ambiguous grammars. These are grammars
with a state that could proceed in more than one way with the same input.

As grammars get complicated, it’s quite possible to create ambiguities. Let’s
look at small examples that make it easier to see the mechanics of the
conflict. That way, when it happens in a real grammar, we’ll have a better
feeling for it.

In the following example, the input A B matches both x and y B. There’s
no reason for yacc to choose one construction over the other when reducing to
foo. So why does this matter, you ask? Don’t we get to foo either way? Yes,
but real parsers will have different user code assigned to run per rule, and it
matters which code block gets executed.

The state machine shows ambiguity at state 1:

At state 1, when the next token is B, the state could shift the token and
enter state 5 (attempting to reduce x). It could also reduce y and leave B as
lookahead. This is called a shift/reduce conflict. Yacc’s policy in such a
conflict is to favor a shift over a reduce.

Alternately, we can construct a grammar with a state that has more than one
eligible reduction for the same input. The purest toy example would be foo : A | A, generating:

In a reduce/reduce conflict, yacc chooses to reduce the conflicting rule
presented earlier in the grammar.

Constructing semantic values

While matching tokens, parsers typically build a user-defined value in memory
to represent features of the input. Once the parse reaches the goal state and
succeeds, then the user code will act on the memory value (or pass it along to
a calling program).

Yacc has stores the semantic values from parsed tokens in variables ($1,
$2, …) accessible to code blocks, and it provides a variable ($$) for
assigning the semantic result of the current code block.

Let’s see it in action. We won’t do a hackneyed calculator, but let’s still
make a parser that operates on integers. Integer values allow us to avoid
thinking about memory management.

We’ll revisit the roman numeral example, and this time let lex match the digits
while yacc combines them into a final result. It’s actually more cumbersome
than our earlier way, but illustrates how to work with semantic parse values.

The corresponding lexer matches individual numerals, and returns them with
their semantic values.

To review: lex generates a yylex() function, and yacc generates yyparse() that
calls yylex() repeatedly to get new token identifiers. Lex actions copy
semantic values to yylval which Yacc copies into $-variables accessible in
parser rule actions.

Building an executable roman from the input files roman.y and roman.l
requires explanation. With appropriate command line flags, yacc will create the
files roman.tab.c and roman.tab.h from roman.y. Lex will create
roman.lex.c from roman.l, using token identifiers in roman.tab.h.

In short, here are the build dependencies for each file:

And here’s how to express it all in a Makefile.

And now, the moment of truth:

Using a parser as a library

The parser does the bulk of the work. We just need to pair it with a scanner
that reads atoms and parens.

Finally, here’s how to call the parser from a regular program.

To build it, use the Makefile pattern from roman to create analogous
lisp.lex.o and lisp.tab.o. This example requires Flex and Bison, so set
LEX=flex and YACC=bison at the top of the Makefile to override whatever
system defaults are used for these programs. Finally, compile driver_lisp.c
and link with those object files.

Here’s the program in action:

Designing against an RFC

With FIELD out of the way, here’s what’s left to translate:

file = [header CRLF] record *(CRLF record) [CRLF]

header = name *(COMMA name)

record = field *(COMMA field)

name = field

Let’s also drop the designation of the first row as the “header.” The
application can choose to treat the first ordinary row as a header if desired.
This simplifies the grammar to:

file = record *(CRLF record) [CRLF]

record = field *(COMMA field)

At this point it’s easy to convert to yacc.

Matching blank fields is tricky. There are three fields in a,,b, no way
around it. That means we have to identify some value (either a non-terminal
symbol, or a terminal token) out of thin air between characters of input. As
a corollary, given that we have to honor blank fields as existing, we’re forced
to interpret e.g. a 0-byte file as one record with a single blank field.

We handled the situation with an empty yacc rule in field.opt. Empty rules
allow the parser to reduce when it sees unexpected lookahead tokens. Perhaps
it’s also possible to use fancy tricks in the lexer (like trailing context and
start conditions) to also match empty non-escaped fields. However, I think an
empty parser rule is more elegant.

Three notes about empty rules:

The complete parser below combines values from the lexer into full records,
using the vector type. It then prints each record and frees it.

#fields = 5
        Year
        Make
        Model
        Description
        Price
#fields = 5
        1997
        Ford
        E350
        ac, abs, moon
        3000.00
#fields = 5
        1999
        Chevy
        Venture "Extended Edition"
        
        4900.00
#fields = 5
        1999
        Chevy
        Venture "Extended Edition, Very Large"
        
        5000.00
#fields = 5
        1996
        Jeep
        Grand Cherokee
        MUST SELL!
air, moon roof, loaded
        4799.00

#fields = 2
        
        
#fields = 2
        
        

Parsing a more complicated RFC

We’ll revisit the lexer to fill in details for assigning yylval. First, let’s
see the parser and its data types.

Returning to the lexer, here is the code with all the details filled in
to construct yylval for the tokens.

Build irc.y and irc.l according to our typical pattern (and link with libderp).
Here’s an example of the IRCv3 parser in action:

Tags:
        'aaa'='bbb'
        'ccc'=''
        'example.com/ddd'='eee'
Prefix: Nick nick, User ident, Host host.com
Command: PRIVMSG
Params:
        me
        Hello

Further resources