Bison is a parser generator that’s backwards compatable with yacc. You give it a lexer and a grammar in a .y file, and it gives you a parser.
Bison’s manual includes examples of grammars for different kinds of calculators. The Lispy calculator below is based on those examples.
The manual’s calculators are REPLs if you run them without sending anything to stdin. They print the values of valid expressions when the user presses return.
Using a Lispy calculator would look like this in your terminal:
The grammar rules section for the .y file looks like this.
The simplicity of this grammar is due to Lisp’s prefix notation. Operator precedence is not a concern. This is unlike grammars with infix notation, where precedence makes parser generators and the automata they create more complex.
The parser gets lookahead tokens by invoking a lexer contained in the
yylex function. Lexers can be built with
lex or other tools that export
yylex function for yacc-like generators.
yylex can also be
designed by hand. Our calculator can use the Bison manual’s lexer for
its reverse polish notation
The complete lispcalc.y file can be found here. That gist includes a Makefile that assumes version 3.0.4 of Bison installed via Homebrew on OSX.
Discussing parser generators is unsatisfying when not talking about exactly what they generate. For example, Bison’s default is to generate bottom-up, LALR(1) parsers that use a shift-reduce algorithm. But I’ll talk about all of that in other blog posts.Tweet