In today's lab, you will explore the standard Unix parser analyzer generator,
yacc, and its GNU implementation,
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
Bison, in its GNU implementation) is one
of the standard parser generators. You can use
to build parsers that construct parse trees. You can use
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.
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)
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.
Thursday, 22 September 2011 [Samuel A. Rebelsky]
Thursday, 29 September 2011 [Samuel A. Rebelsky]
I usually create these pages
on the fly, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Sat Nov 12 22:53:46 2011.
The source to the document was last modified on Thu Sep 29 12:42:29 2011.
This document may be found at