CS 254: Automata and Computability
Bison lab
Do the following. At the end of the hour, for 10, 11, and 12,
print out or e-mail me your modified copies of calculator.y and
calculator.lex along with notes on
what worked, what didn't, and any questions you have. (By the way,
since I haven't ever run this lab before, I don't
have any idea of how much you're likely to get done
in 70 minutes. So don't worry if you haven't completed
the whole thing.)
- If you don't have experience with C or C++, work with a partner who does.
Ask your partner questions when you don't understand something
in the code.
- Want docs for bison? There's the
official
Bison manual, and
a nice intro
to Bison at the University of Utah.
- Make a directory called "bison" and save
calculator.y,
main.cpp,
calculator.lex,
and calculator.h,
Makefile,
and expression.txt
in it.
- Open a Terminal window and cd to your bison directory.
- Look at calculator.y, main.c, calculator.lex, Makefile, and expression.txt.
- Build the program by executing the "make" command.
- Run the program by executing "calculator < expression.txt". (Alternatively,
you can run something like "echo '2*3+4' | calculator" to specify your
expression on the command line.)
- Take another look at calculator.y, and make sure you understand which
context-free grammar it is parsing.
- Insert print statements into calculator.y's rules to see when each
rule is invoked when you try various input expressions. How do you
think calculator.y is causing the */+ precedence rule to be followed
correctly?
- Modify the grammar in calculator.y and the tokenizer in
calculator.lex to handle division and subtraction
with proper precedence behavior.
- Modify the grammar and tokenizer to deal correctly with parentheses.
- Try to modify the rule code in calculator.y to print out a parse tree
for the expression rather than a final value. This is tricky,
and you may need to poke around in the bison documentation.