**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 startFor this exercise, this copies test data for each part ( 1.data , 2.data , 3.data , 4.data , 5.data , 6.data ) and the

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 ./infix 1+2*3;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.

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

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

UP PREVIOUS NEXT