Generating a parser and lexer with bison and flex

Manually constructing a lexer and a parser is not difficult and usually results in fast components. The disadvantage is that it is not easy to introduce changes, especially in the parser. This can be important if you are prototyping a new programming language. Using specialized tools can mitigate this issue.

There are many tools available that generate either a lexer or a parser from a specification file. In the Linux world, flex (https://github.com/westes/flex) and bison (https://www.gnu.org/software/bison/) are the most commonly used tools. Flex generates a lexer from a set of regular expressions, while bison generates a parser from a grammar description. Usually, both tools are used together.

Bison produces an LALR(1) parser from a grammar description. An LALR(1) parser is a bottom-up parser and is implemented using an automaton. The input for bison is a grammar file very similar to the one presented at beginning of this chapter...