Well, here you are. Here is the free information you have all been waiting for, with some extra bits of advice:
Please note that there is no obligation to produce a machine readable solution for this section. Coco/R and other files are provided so that you can enhance, refine, or test your solution if you desire. If you choose to produce a machine readable solution, you should create a working directory, unpack EXAMP.ZIP (Pascal) or EXAMC.ZIP (C++), modify any files that you like, and then copy all the files back to the blank diskette that will be provided.
We have a minor crisis in the Department. Because the experienced staff member who normally gives the Boolean Algebra section of our course has just been taken ill, we have had to ask a new lecturer to take over the course at very short notice, and he needs help ...
We assume that you are familiar with the basic concepts of Boolean algebra, which is defined on a set of operands, say B = {a, b, ... }, two binary infix operators . and + (AND and OR), and a unary postfix operator ' (NOT) .
As you will recall, these operators have a precedence ordering. NOT takes precedence over AND, which takes precedence over OR. This means that an expression written without parentheses, such as a.b + c (or, equivalently, a AND b OR c) means the same as the parenthesized expression (a.b) + c, and does not mean the same as the parenthesized expression a.(b + c). Sometimes the AND operation becomes implicit - as in simple algebra where "a b" can be read as "a times b", so in Boolean algebra "a b" can be read as "a AND b"
Other symbols are sometimes used for the operators. (Expressed as an apostrophe ' , the NOT operator is one of the very few mathematical operators that is written after its operand, as what is called a postfix operator. Another example of a postfix operator is the "factorial" one, as in n!). In computer language terms it is usual to find prefix operators preferred to postfix ones, and to avoid the use of . and +, which tend to get confused with decimal points and addition signs. Hence one finds the use of the full words (as in Pascal and Modula-2) or the use of other symbols entirely, such as & to mean AND, | to mean OR, and ! or ~ to mean NOT.
Here is the same Boolean expression written in several different ways, using these various notations, with parentheses used in the expressions on the right to make the precedence quite explicit:
A AND B OR NOT C AND D (A AND B) OR ((NOT C) AND D)
a.b + c'.d (a.b) + (c'.d)
a b + c' d (a b) + (c' d)
a & b | ~c & d (a & b) | ((~c) & d)
a & b | !c & d (a & b) | ((!c) & d)
A AND B OR NOT C AND D (A AND B) OR ((NOT C) AND D)
When beginners are taught Boolean algebra and combinational circuits in introductory Computer Science courses, they are often introduced to the concept of a truth table, like those given below (sometimes these tables are expressed in terms of 0's and 1's; sometimes in terms of TRUE and FALSE).
┌────────┬───────┐
│ X │ NOT X │
├────────┼───────┤
│ FALSE │ TRUE │
│ TRUE │ FALSE │
└────────┴───────┘
┌─────────────┬─────────────┐
│ ONE TWO │ ONE XOR TWO │
├─────────────┼─────────────┤
│ 0 0 │ 0 │
│ 0 1 │ 1 │
│ 1 0 │ 1 │
│ 1 1 │ 0 │
└─────────────┴─────────────┘
Such tables are easy enough to derive by hand, though it is tedious to do so for expressions that involve more than two inputs, and the process is error prone. On Monday the new lecturer is scheduled to teach students about truth tables, and he is desperately looking for a tool that will help him produce these in a hurry for arbitrarily complex expressions. He wants to be able to feed in a list of (independent) functions, for example
BOOLEAN F(x) = x'; BOOLEAN f(x, y) = x | y; xor(one, two) = one & two' or one' & two; CanReturn(S1, S2, S3, Excluded) = (S1 S2 OR S2 S3 + S3 S1) AND ~ Excluded; BOOLEAN Equality(x) = x ' ' & ! (NOT x); NUMERIC Silly(Twit) = 1 . 0' + Twit; BOOLEAN Silly(Twit) = TRUE AND NOT FALSE OR Twit
each one defining some function of its explicit arguments, and separated one from the next by the traditional semicolons. For each function a table should be produced showing the value of the function for each combination of the possible values of its parameters. If present, the keyword BOOLEAN indicates that the table should be produced in terms of combinations of TRUE and FALSE; the absence of a keyword, or the explicit keyword NUMERIC indicates that the table should be produced in terms of combinations of 0's and 1's. Notice that the expressions defining the functions:
(a) may only refer to variables in the parentheses of the function header (b) may refer to these variables more than once in an expression, as illustrated by CanReturn (c) may not refer to other functions and (d) must be able to accept any of the equivalent tokens for operators within an expression (as exemplified in CanReturn, where one sees word tokens AND and OR, the alternative ~ used for NOT, and the alternative + used for OR).
Of course, as a senior undergraduate well versed in the use of compiler generating tools such as Coco/R, and in spite of these incredible time constraints, you should have little trouble in producing a system for him to use by Saturday evening, well in advance of Monday morning. After all, you have learned to generate code for simple stack machines, and still have that copy of a Clang compiler to turn to for useful ideas! So take up the challenge.
Being human like the rest of us, the lecturer wants a tool that will check his expressions for syntactic and semantic correctness. He is prepared to accept a fairly simple-minded approach to generating the results - it will suffice to have a system where these are simply directed to the standard output file. And, since he has a licensed copy of both the C++ and Pascal versions of Coco/R, he is prepared to accept submissions in the form of a Cocol attribute grammar using either language, plus any support modules needed, either on diskette or simply written on paper.