**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 infix 1+2*3;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 <dataIf your code is correct, the output from your three programs should be the same. Try saving the outputs, and using

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

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

UP PREVIOUS NEXT