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.


On successful completion of this exercise a student will:
Be able to use byacc to recognise patterns in a piece of text
Be aware that the patterns recognised by byacc can be much more complex than those that flex is able to recognise.
Be aware that it is possible to use byacc without also using flex, but that to do so can make simple things like ignoring spaces much more complicated.
Be able to use byacc to write a simple calculator i.e. an interpreter for a tiny computer language with sequential flow of control.
Be aware of the concepts of associativity and precedence of operators in expressions, and be able to implement them in byacc in two completely different ways.
Be aware that it is possible, albeit tedious, to describe simple computations - such as a boolean calculator - purely using grammars (as well as by using programming languages such as C) but also to be aware that it may not be feasible to describe slightly more complex computations - such as an integer calculator - using grammars like those of byacc.


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

Note: a boolean logic calculator manipulates truth values, such as "true" and "false", using logical operators like "and" and "or". It is not a binary calculator, performing arithmetic operations on binary numbers.


Just like the previous exercise, get started using the "makefile" but this time from "$CS2121/p*/ex3" i.e. make sure you are in your directory CS2121/ex3, and then type:

        cp $CS2121/p*/ex3/makefile .
	make start
For this exercise, this copies test data for each part ( 1.data , 2.data , 3.data , 4.data , 5.data , 6.data ) and the byacc program for the integer calculator given in the lecture.

You can compile the given program (infix.y) by typing "make infix". You can then run it by typing "./infix" followed by an expression, without any spaces, on a single line. e.g.:

	make infix
After it has told you the result (e.g. "result is 7") you should stop the program using ctrl-D. If you make a mistake in typing the expression, such as including a space, the program will output "syntax error" and stop.

a) Simple use of yacc

Part 1 You are going to replace the integer numbers and operations by boolean values and operations.

Start by copying "infix.y" to "1y.y". You can test the program by typing "make 1". (If you do this before modifying the program as described below, you will see "syntax error" and be told about lots of missing answers.)

You need to 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 "~"). Note: the symbols used for operators are not those used in C or Java: "&&", "||" and "!". A simple method of doing this is to start by discarding the rules for "number" and "digit" completely. Then change "exp" to deal with "|", "term" to deal with "&", and "factor" to deal with "~", "T", "F" and brackets.

Add a grammar rule to recognise one or more "line"s, and change the "%start" to be this rule. (hint: lectures section 4.1)
If you test your program at this point, it should recognise all the data, and so not output "syntax error", but get all the answers wrong. You will probably also get warning messages saying things like: "the default action assigns an undefined value to $$"
and: "the symbol number is undefined"

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). This should deal with the warning messages mentioned above.

Part 2 You are going to use "%left" and "%right" to give the correct precedence and associativity to the operators (notes and examples available via the web pages).

Start by copying "1y.y" to "2y.y". Combine your rules for "exp", "term" and "factor" into a single rule for "exp". Then, use "%left", "%right" or "%nonassoc" to give the correct precedence and associativity to the operators. Remember to modify your %type declarations. (see lectures section 4.4) You can test the program by typing "make 2".

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.

Part 3 You are going to use the grammar itself to calculate the results of the expressions, instead of using actions (i.e. the code in "{ }" ).

Start by copying "2y.y" to "3y.y", and then edit the new file to 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.

b) Bonus work

This section contains problems that are more difficult than those in the previous section, and where marks are harder to obtain. You should complete section (a) before attempting this section. If you are running out of time, you would do better to start exercise 4.

Part 4 Modify a copy of your answer to part 1 to ignore spaces, tabs and newlines, without generating any shift-reduce or reduce-reduce conflicts. You should still check that there is at least one newline at the end of each expression. Do not modify the code for "yylex" to ignore any white-space characters. Start by copying "1y.y" to "4y.y".

Part 5 Modify a copy of your answer to part 3 to allow for three logic values (True, False and Don't know). Start by copying "3y.y" to "5y.y".

Part 6 Modify a copy of your answer to part 1 to include the relational operators "<", "==", ">", "<=", ">=" and "!=", and add actions to calculate the correct results. (Use the same associativity and precedence as for C or Java.) Start by copying "1y.y" to "6y.y".


This exercise is worth 10 marks in total. It is necessary to produce working programs to demonstrate that you have achieved the Learning Outcomes of this exercise. However, it is also important that you are able to show that you understand the details of what you have written. You are therefore required to demonstrate your work to a member of the laboratory staff.


Demonstrate your working programs to a demonstrator or lab supervisor by typing "make marka" for section (a) and "make markb" for section (b).

You should labmail the file "labmail_me", containing all your yacc code, which you should create by typing "make labmail".

Your program for part 1 will be marked as follows:
1 mark - modifying program to deal with multiple lines
1 mark - rewriting grammar rules for expressions
1 mark - rewriting actions for expressions

Your program for part 2 will be marked as follows:
1 mark - correct use of %left, %right and %nonassoc
1 mark - rewriting grammar rules for expressions

Your program for part 3 will be marked as follows:
2 marks - rewriting grammar rules for expressions

Section (b) will be marked as follows:
1 mark - part 4 working correctly
1 mark - part 5 working correctly
1 mark - part 6 working correctly