Lab: Yacc and Bison

Summary: In today's lab, you will explore the standard Unix parser analyzer generator, yacc, and its GNU implementation, boson.

Collaboration: Feel free to work on this lab in pairs or trios.

Turning It In: Submit on P'Web a tarball of your new .l file, your new .y file, your Makefile, and a script of a session with your new program.

Background: Yacc (or Bison, in its GNU implementation) is one of the standard parser generators. You can use Yacc to build parsers that construct parse trees. You can use Yacc to build parsers that translate to assembly (of some form or another). You can also use Yacc more generally, to do computation related to the parsed structure of the input.

In this lab, we will focus on the last use as we build an interactive expression evaluator.

You can get more information on Bison from the man page, the info page, or on the Web.

You should have section 4.9 available as you do this lab.

Preparation

In the directory for this lab, you can find a simple expression evaluator, similar to the one in the book, but using f?lex. Make a copy of the important files (example.l, example.y, and Makefile)

Exercises

1. Scan through the files to understand the basic setup.

2. Using make, built the program example. Then, verify that it can evaluate expressions, paying attention to precedence. E.g.,

$ echo '2 + 3 * 5' | ./example

3. If you try to run example from the command line and give it multiple lines of input, you will find that it creates an error.

$ ./example
2 + 3
5
2 + 3
syntax error

Modify the grammar so that it can accept multiple lines of input, including blank lines. (Hint: You'll want to create a new top-level nonterminal.)

4. Extend the grammar to support logical 'or' (which you can implement with ||) and 'and' (which you can implement with &&). 'or' should have the same precedence as the addition operations. 'and' should have have the same precedence as the multiplication operations.

5. Extend the grammar to support the comparison operations (lower precedence than addition operations), so that I can write things like

2 + 3 < 7

You can use 1 for true and 0 for false.

6. Extend the grammar to support negation and not, both which have high precedence.

7. Extend the grammar to support assignments of the form

_IDENTIFIER := expression

which does assignment. You should support the identifiers 'i0' ... 'i9'. Initially, your assignments need do nothing.

8. Extend your grammar so that you can use identifiers in expressions. You'll need to set up an array of ten integers which you fill in when you see an assignment. Then, you'll need to reference that array when you see an identifier.