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.)

  1. 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.
  2. Want docs for bison? There's the official Bison manual, and a nice intro to Bison at the University of Utah.
  3. Make a directory called "bison" and save calculator.y, main.cpp, calculator.lex, and calculator.h, Makefile, and expression.txt in it.
  4. Open a Terminal window and cd to your bison directory.
  5. Look at calculator.y, main.c, calculator.lex, Makefile, and expression.txt.
  6. Build the program by executing the "make" command.
  7. 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.)
  8. Take another look at calculator.y, and make sure you understand which context-free grammar it is parsing.
  9. 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?
  10. Modify the grammar in calculator.y and the tokenizer in calculator.lex to handle division and subtraction with proper precedence behavior.
  11. Modify the grammar and tokenizer to deal correctly with parentheses.
  12. 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.