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