Well, here you are. Here is the free information you have all been waiting for, with some extra bits of advice:
I have this colleague in the Logic Department who is trying to set an exam at short notice,with questions on evaluating and simplifying Boolean expressions and building truth tables. He has suddenly realized that there are only 24 hours remaining before the students write, and that he hasn't yet solved all the problems himself, some of which have given rise to rather complicated Boolean expressions in many variables. So he is pleading for help.
My first idea was to offer him a little Cocol application that my CSC 301 students had developed very early one morning before sunrise, while they were learning about expressions and precedence and all that stuff. One of them had come up with something very promising, so I showed it to my friend. It is a Cocol description of a simple Boolean expression evaluator, with the addition of a memory of 26 cells, named by the 26 lower case letters of the standard alphabet. The evaluator would allow him to read and store values into these cells, and to compute values for expressions - which might either be printed or stored in variables. Typical input for this evaluator might read
a = true;
b = not a;
read(c);
read(d);
write(a or b and c or not(c == d));
And here is the Cocol grammar:
using Library;
COMPILER BoolCalc $CN
/* Simple Boolean expression evaluator with 26 memory cells - Coco/R for C#
The nameless 63T0844, Rhodes University, 2017 */
static bool[] mem = new bool[26];
CHARACTERS
digit = "0123456789" .
letter = "abcdefghijklmnopqrstuvwxyz" .
TOKENS
number = digit { digit } .
variable = letter .
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
BoolCalc (. int index = 0; bool value = false; .)
= { ( Variable<out index>
WEAK "="
Expression<out value> (. mem[index] = value; .)
| "write" "("
Expression<out value> (. IO.WriteLine(value); .)
{ ","
Expression<out value> (. IO.WriteLine(value); .)
} ")"
| "read" "("
Variable<out index> (. mem[index] = IO.ReadBool(); .)
")"
) SYNC ";"
} EOF .
Expression<out bool value> (. bool value1; .)
= AndExp<out value>
{ "or" AndExp<out value1> (. value = value || value1; .)
} .
AndExp<out bool value> (. bool value1; .)
= EqlExp<out value>
{ "and" EqlExp<out value1> (. value = value && value1; .)
} .
EqlExp<out bool value> (. bool value1; .)
= NotExp<out value>
{ "==" NotExp<out value1> (. value = value == value1; .)
| "!=" NotExp<out value1> (. value = value != value1; .)
} .
NotExp<out bool value> (. value = false; .)
= Factor<out value>
| "not" NotExp<out value> (. value = ! value; .) .
Factor<out bool value> (. int index;
value = false;.)
= "true" (. value = true; .)
| "false" (. value = false; .)
| Variable<out index> (. value = mem[index]; .)
| "(" Expression<out value> ")" .
Variable<out int index>
= variable (. index = token.val[0] - 'a'; .) .
END BoolCalc.
"That's nice", he said. "But it's going to take a lot of typing to get all the functions into the right format, expanding where needed. It would be fantastic if I could define some functions before I start manipulating them and using them as factors in larger expressions. Like this:"
Fun(w, x, y, z) returns (w or x and y or not(y == z));
a = true;
b = not a;
read(c);
read(d);
write(Fun(a, b, c, d);
write(Fun(true, false, c or d, b);
"Well", I said, "No problem. As it happens, my students have nothing better to do in the next 24 hours, so I am sure they will all be delighted to help you!"
One of them immediately suggested that the logical way to solve the problem was simply to teach my colleague how to add Cocol code for any functions into the grammar (by extending Factor). For example, to incorporate an XOR function:
Factor<out bool value> (. int index;
bool value1;
value = false;.)
= "true" (. value = true; .)
| "false" (. value = false; .)
| Variable<out index> (. value = mem[index]; .)
* | "XOR" "(" Expression<out value>
* "," Expression<out value1> ")" (. value = value && !value1 || !value && value1; .)
| "(" Expression<out value> ")" .
However, this did not appeal - my friend thinks it's illogical to have to learn Cocol and fiddle with make files and C# compilers. Like all people who leave things to the last minute he wants something very, very easy to use.
So I thought of trying a different approach: rather than obey each statement as it is analysed, and evaluate each expression as it occurs, how about a system that will generate PVM code for a simple program - which can then be executed on the PVM? That is, effectively write something like a very simple complete compiler/interpreter.
With this in mind, the first part of the exercise for today is to use Coco/R to build a system for compiling and executing a "program" like the following:
// User defined functions precede the statements that might require them
XOR(x, y) returns x and !y or y and !x;
AND3(x, y, z) returns x and y and z;
// definitions are followed by statements that use these functions (the "main" function in a sense)
read("Supply three values ", x, y, z);
a = AND3(x, y, z);
s = XOR(x, a);
write("and3 is ", a, " xor is ", s);
Showing this example to my friend in the Logic department provoked an interesting response (some people are never satisfied!)
"That's very helpful, but if those are the only statements you can use, creating truth tables is still going to be very tedious - evaluating the functions for all the combinations of w, x, y, z and so on. Can't your bright students allow me just one more feature - a simple loop structure that will allow me to cycle some variables through the values (false, true) - something like this?"
XOR(x, y) returns x and not y or y and not x;
// Produce a simple truth table
writeLine(" x y x|y x&y x⊕y)");
loop x {
loop y {
writeLine(x, y, x or y, x and y, XOR(x, y));
}
}
leading to output like
x y x|y x&y x⊕y
false false false false false
false true true false true
true false true false true
true true true true false
"That should be easy enough, surely!" (The trouble with my colleagues is that they will keep coming back with requests for "just one more feature", but we might draw the line here for the purposes of the exam.)
In adopting this approach you can make use of the files provided in the examination kit free1.zip which you will find on the course website. In particular, you will find
This CodeGen.cs and PVM.cs have also been copied to the directory LogicCom with a change of namespace, so that you will be able to make your system with the command CMAKE LogicCom if your grammar is held in the file LogicCom.atg.
Although you are free to modify CodeGen and PVM, it is not believed that this will be necessary. You may wish to modify LogicCom.frame.
In addition you will find, in the root folder and the LogicCom folder:
It is suggested that you proceed as follows:
The way in which the PVM handles function calls is described in chapter 14 of the text. Since you have not worked much with the new opcodes FHDR, CALL and RET before, it will not be giving too much away to illustrate the sort of code that should be generated for a simple function definition, and for a corresponding call of this function.
Allowing ourselves the luxury of using names and labels for illustration, rather than the numerical offsets that are required in the code proper:
Fun(x, y, z) returns (x or y) and z;
Fun LDL x Push value of argument x
LDL y Push value of argument y
OR Now have value of x + y at TOS
LDL z Push value of argument z
AND Now have value of (x or y) and z at TOS
STL 0 Store result on bottom of stack frame
RET Return to caller
a = not Fun(p, q, r);
FHDR Create standard stack frame
LDL p Push value of first argument onto frame header
LDL q Push value of second argument onto frame header
LDL r Push value of third argument onto frame header
CALL Fun Call function - returned value left at TOS
NOT Will now have the value of NOT * Fun(p, q, r) at TOS
STL a Store on variable a
b = Fun(true, x, y or z);
FHDR Create standard stack frame
LDC 1 Push value of first argument onto frame header
LDL x Push value of second argument onto frame header
LDL y
LDL z
OR Push value of third argument onto frame header
CALL Fun Call function - returned value left at TOS
STL b Store on variable b
Have fun, and good luck!
Sally and I would like to invite you to the traditional an informal end-of-course party at our house on Saturday 18 November (after the Compilers paper). There's a wonderful ASCII-art map below to help you find your way there. It would help if you could let me know whether you are coming so that we can borrow enough glasses, plates, etc. Please post the reply slip into the hand-in box during the course of the day. Time: from 18h30 onwards. Dress: Casual
\
PDT(8) \ <==================================== here!
\ \ |\
\ Bedford /--\ Constitution Street
\ \ / \
Cradock \ \ / \ ^
\────-\ / \ │ Hospital
\ Pear Lane \ │
\ Worcester St \ │
───────────┼────────────────────────────┤
DSG │ │
│ St Andrew's │ Milner Street
│ │
│ BP │
Somerset │ African Street Spar │
Street ├──────┬─────────────────────┴──┬──────────
│ │ The Mall │
│ │ PnP │
│ │ KFC Wimpy │
│ │ Spur │
│ Rat │ New Street │
───────────┼──────┴┬───────────────────────┼──────────
Hamilton │ │ │
Hell Hole │ │ Gino's│ Hill St
│ │ │
Rhodes │ │ Steers High Street │
──┴───────┴───────────────────────┴ Cathedral
(See also http://www.cs.ru.ac.za/courses/CSc301/Translators/map.htm )