CS 11: advanced C track: lab 4

Material to be covered for this lab

Parsing using bison

Overview of this lab

Last week, we started to implement a small interpreted computer language by writing a lexer to recognize the tokens that constitute the building blocks of expressions in the language. In this lab we will complete the job by writing a parser, which will take the stream of tokens, figure out what kind of expressions they correspond to, and execute the code corresponding to these expressions.

Parsing

OK, so you've run your source code through flex, and have a nice set of tokens to play with. Unfortunately, there are some kinds of language analysis that are too complex for lexers. One example is matching open parentheses with their corresponding close parentheses: it turns out to be impossible for a lexer (which only handles regular expressions) to match arbitrarily nested sets of parentheses, which is something you would want in a computer language. For this we need something more powerful, and that thing is a parser. A parser takes a sequences of tokens (provided by the lexer) and either

determines that a syntax error has occurred, or
determines the next valid expression in the language.

If a valid expression is found, the parser may execute it immediately (for simple languages like this week's exercise) or convert it into yet another representation (called an abstract syntax tree) which is then subjected to even more processing (this is how serious computer languages work; for details, see Jason Hickey's CS 134b course on compilers).

Writing parsers by hand is hard work (much harder than writing lexers). So, by analogy with lexers, there are programs called parser generators that take an input file representing the grammar of the language to be parsed and generate C code that implements the parser. Also by analogy with lexers, parser generators are written in a special language that is in some ways similar to C, but that is specialized to the task of parsing. The standard unix parser generator program is yacc, which stands for "yet another compiler-compiler". Again, we will be using an improved version called bison. The name bison is a pun on yacc and on "GNU" (which in turn stands for "GNU's not unix"). GNU is the name of software from the Free Software Foundation.

What the bison grammar description looks like is described in great detail here. You should read as much of this as you need to. Briefly, the main section of the grammar describes productions (valid expressions in the language) in terms of simpler expressions, finally bottoming out with tokens. When an expression is matched, you can define an action to execute. This may involve evaluating the expression (in our case), or generating part of an abstract syntax tree (for a more complex language).

Program to write

You are to implement a simple calculator program/language, which will have the following features:

Users can enter infix expressions involving the operators "+", "-", "*", "/", "**" (exponentiation), numbers (represented as doubles), and arbitrarily nested parentheses.
Users can enter function calls using the standard C syntax e.g. sqrt(2.0). There should be a built-in function called "print" which will print an expression to stdout, followed by a newline e.g.
```
    a = 2 + 2;
    print(a);
```
prints "4" to stdout. You can also add other built-in functions e.g. sqrt and exp. For the purposes of this lab, functions should take a single argument only, which will be a number. (Extra credit: extend this to functions that can take arbitrary numbers of arguments.)
Users can bind one-character variables with names from "a" to "z" to expressions using the syntax "var = expr;".
Statements end in a semicolon (";"); this tells the interpreter to evaluate the statement.
Comments in code that start with the "#" character and go to the end of the line. Comment removal should be done in the lexer.
Note that even though your lexer from last week could recognize integers, the calculator language will only work with doubles, so integers should always be converted to doubles. You should do this conversion by modifying your lexer appropriately.

Use the lexer you wrote in last week's lab to parse the tokens. Use bison to define the grammar. Your grammar should not have any shift-reduce or reduce-reduce conflicts (these indicate ambiguities in the grammar).

Your program should also be able to run scripts. This is done using the unix "sharp-bang" hack ("#!") as follows:

#! /usr/bin/env calculator
a = 2 + 2;
print(a);

When you put this into a file (called e.g. "print_4") and do this:

% chmod +x print_4
% print_4

it will print "4" to stdout.

To hand in

The calculator program.
A Makefile that will compile the program by typing "make". There should also be a "clean" target to get rid of all files generated during compilation.

References

The flex documentation.
The bison documentation.
Lex and Yacc by John R. Levine, Tony Mason, and Doug Brown (O'Reilly and Associates, 1992). This book is quite old, but it's still the best reference on lex and yacc (and by extension on flex and bison) out there.
Modern Compiler Implementation in C by Andrew Appel with Maia Ginsburg (Cambridge University Press, 1998). This book is a comprehensive introduction to compiler design. The first two chapters cover the theory behind lexers and parser generators in great detail. Compared to most tutorials on parser generators, the material here is useful for writing a scalable parser, not just a "toy" parser.
Brian Kernighan and Rob Pike, The Unix Programming Environment
This book contains as a project a miniature computer language which is a superset of this week's assignment. Thus, if you want to cheat, this will be a good place to look ;-) I recommend you avoid using this book unless you're really stuck. Instead, look at their solution after you're done and compare it with yours.