DURATION 1 lab session


This exercise is designed to familiarise you with the use of byacc (manual available via the web pages) so that, when you come to use it later, you can concentrate on the important aspects of the problem.


Using byacc but not flex, write three versions of a simple boolean logic calculator (not a binary calculator), based on the integer calculator (available via the web pages) given in the lectures.

Version 1: replace the integer numbers and operations by boolean values and operations, performing the calculations in the actions.

Version 2: use "%left" and "%right" to give the correct precedence and associativity to the operators (notes and examples available via the web pages).

Version 3: instead of using actions, use the grammar itself to calculate the result.


Copy the starting files from "$CS2111/p*/ex3/*". The files include a makefile, some test data, and the byacc program for the integer calculator given in the lecture.
The makefile relies on make's built-in knowledge of how to compile certain kinds of program. You can type "make infix" and it will compile your "infix.y" file using byacc and gcc. You can then run it by typing "infix <data".
At first, this will give you a "syntax error" message, as the data file contains boolean expressions, not integer expressions. If you want to test infix before you start to edit it, type:

	make infix
After it has told you the result (e.g. "result is 7") you should stop the program - I use ctrl-D, but if this causes you problems you can just press return again (and get a "syntax error" message).
You could create three different files (e.g. "one.y", "two.y" and "three.y") for the three different versions of the program, and compile and run them by:
        make one
        one <data
        make two
        two <data
        make three
        three <data
If your code is correct, the output from your three programs should be the same. Try saving the outputs, and using diff to check this:
        make one two three
        one <data >out1
        two <data >out2
        diff out1 out2
        three <data >out3
        diff out2 out3

Version 1 (Keep a copy of each version of your program for marking.)

* Rewrite the grammar to recognise boolean expressions consisting of the values "T" (true) and "F" (false), brackets "(" and ")", and operators "&" (and), "|" (or) and "~" (not) with the usual precedence ("~" > "&" > "|") and associativity (left for "&" and "|", right for "~").
A simple method is to discard the rules for "number" and "digit" completely and change "exp" to deal with "|", "term" to deal with "&", and "factor" to deal with "~", "T", "F" and brackets.
The operators do not have the identical meanings to those as in C, as single characters are easier to deal with when we are not using flex, and "!" and "|" are easily confused. If we are simply trying to fit in with C, we should probably use "&&", "||" and "!".
* Rewrite the actions to calculate the corresponding truth values - "T" and "F" should be converted to 1 and 0 respectively by "factor", and "line" should print a "T" or "F" as the result. Remember to modify the %type declaration (and possibly the %union as well, but you shouldn't need to).
* Add a grammar rule to input one or more "line"s and change the "%start" to be this rule.

Version 2 (Keep a copy of each version of your program for marking.)

Modify the first version of your program by combining your rules for "exp", "term" and "factor" into a single rule for "exp", and instead using "%left", "%right" or "%nonassoc" to give the correct precedence and associativity to the operators. Remember to modify your %type declarations.

It is very common to get shift-reduce or reduce-reduce conflicts when you do this. If byacc reports any conflicts, you must get rid of them by modifying your grammar, otherwise some expressions will not be recognised correctly.

Version 3 (Keep a copy of each version of your program for marking.)

Modify the second version of your program: (e.g. keep your %left, %right and %nonassoc declarations)
* Discard all the actions and any %union and %type declarations.
* Rewrite "exp" as two rules, called e.g. "true_exp" and "false_exp", explicitly listing the relevant sub-expressions e.g.:

        true_exp :	'T'  |  '(' true_exp ')'  |  '~' false_exp  |  . . .
        false_exp :	'F'  |  '(' false_exp ')'  |  . . .
* Rewrite "line" so that instead of recognising an "exp" it recognises a "true_exp" (in which case it outputs a "T") or a "false_exp" (in which case it outputs an "F") - these outputs should be the only actions in your byacc code.

Bonus suggestions:
* Modify your grammar for version 3 to ignore spaces and tabs, without generating any conflicts. (This is probably only worth 1 mark.)
* Modify the grammar to accept any number of expressions followed by a single ';' (i.e. there is no ';' between each expression and the next) and output the values of all the expressions (preferably in the correct order) when the ';' is seen - this is similar to what the SML interpreter does. Don't use an extra stack to hold the values of the expressions for printing - use the built-in $/yyval stack. (This is probably only worth 1 mark.)
* Include other operators in your version 3 (e.g. < = > etc.). (This is probably only worth 1 mark.)
* Modify your version 3 to allow for three logic values (True, False and Don't know). You could also add extra operators. (This is probably only worth 1 or 2 marks.)
* Write a calculator that will accept more than one type of value (e.g. some of boolean, floating point, integer, character etc.), only permitting sensible combinations for each of the operations, and output the result in the correct form for its type. I suggest you use separate grammar rules for "int_exp", "float_exp", "bool_exp", etc., like version 3, but perform the calculations in the actions, like version 2.


Demonstrate your three working programs to a demonstrator or lab supervisor. You should also make version 2 or 3, to show that you have no shift-reduce or reduce-reduce conflicts. You must "labmail" the final version of your byacc code i.e. "infix.y" (you may need to rename your file before you call "labmail").