DIRECTORY
BoolOps,
Commander USING [CommandProc, Register],
Atom USING [MakeAtom, GetPName],
RefTab,
Convert,
IO,
Rope;


BoolOpsImpl: CEDAR PROGRAM				
IMPORTS Commander, RefTab, IO, Rope, Atom EXPORTS BoolOps = BEGIN
OPEN BoolOps; 

TokenTypes: TYPE = {Id, SubTree, Not, And, Or, LParen, RParen, End, Null};

precedence: ARRAY TokenTypes OF Rope.ROPE _ [

-- Id -- "..>>>>>>.",
--Subt-- ".........",
--Not -- "<.<>><>>.",
--And -- "<.<=><>>.",
--Or  -- "<.<<=<>>.",
--LPar-- "<.<<<<=..",
--RPar-- "..>>>.>>.",
--End -- "<.<<<<...",
--Null-- "........."

];

tokenNames: ARRAY TokenTypes OF Rope.ROPE _ ["", "", "~", "AND", "OR", "(", ")", "", ""];

Error: PUBLIC ERROR[ec: ErrorCode, msg: Rope.ROPE] = CODE;

RopeToTree: PUBLIC PROC [expr: Rope.ROPE] RETURNS [tree: Tree] = BEGIN


Token: TYPE = RECORD [
type: TokenTypes,
name: Rope.ROPE _ NIL,
value: SubTree _ NIL
];

Input: TYPE = RECORD [
value: Rope.ROPE,
index: CARDINAL _ 0
];

Stack: TYPE = LIST OF Token;

NextToken: PROC [in: IO.STREAM] RETURNS[Token] = BEGIN
tok: Rope.ROPE;
eof: BOOL _ FALSE;
[ , tok, ] _ IO.GetCedarTokenRope[in !
IO.Error => {eof _ TRUE; CONTINUE}; 
IO.EndOfStream => {eof _ TRUE; CONTINUE}
]; 
IF eof THEN RETURN[[$End, ""]];
FOR t: TokenTypes IN TokenTypes DO
IF Rope.Equal[tok, tokenNames[t]] THEN RETURN[[t, tok]];
ENDLOOP;
RETURN[[$Id, tok]];
END;

Push: PROC [s: Stack, t: Token] RETURNS[Stack] = BEGIN
RETURN[CONS[t, s]];
END;

Pop: PROC [s: Stack] RETURNS[Stack, Token] = BEGIN
IF s = NIL THEN RETURN[NIL, [$Null, "(Stack underflow)", NIL]];
RETURN[s.rest, s.first];
END;

Peek: PROC [s: Stack] RETURNS[Token] = BEGIN
IF s = NIL THEN RETURN[[$Null, "(Stack underflow)", NIL]];
RETURN[s.first];
END;

PeekUnder: PROC [s: Stack] RETURNS[Token] = BEGIN
FOR tlist: Stack _ s, tlist.rest WHILE tlist # NIL DO
IF tlist.first.type # $SubTree THEN RETURN[tlist.first];
ENDLOOP;
RETURN[[$Null, "(Stack underflow)", NIL]];
END;

Precedence: PROC [tokl, tokr: TokenTypes] RETURNS[CHAR] = BEGIN
RETURN[Rope.Fetch[precedence[tokl], ORD[tokr]]];
END;

in: IO.STREAM _ IO.RIS[expr];
s: Stack _ NIL;
p, curToken: Token;
s _ Push[s, [$End, NIL]];
curToken _ [$Null, NIL, NIL];
DO 
IF curToken.type = $Null THEN curToken _ NextToken[in];
p _ PeekUnder[s];
SELECT Precedence[p.type, curToken.type] FROM
'<, '= => {  -- shift
s _ Push[s, curToken];
curToken.type _ $Null;
};
'> => {	-- reduce
top, rp: Token;
topOp: Token _ [$Null, NIL, NIL];
newt: Token;
haveOp: BOOL _ FALSE;
op: Operator;
opId: TokenTypes;
numArgs: CARDINAL _ 0;
newt.type _ $SubTree;
DO
[s, top] _ Pop[s];
IF top.type # SubTree THEN topOp _ top;
SELECT top.type FROM
$Id => {
newt.value _ NEW[Leaf];
NARROW[newt.value, REF Leaf].var _ Atom.MakeAtom[top.name];
};
$SubTree => {
IF newt.value = NIL THEN newt.value _ NEW[Expression];
NARROW[newt.value, REF Expression].children _ CONS[top.value, NARROW[newt.value, REF Expression].children];
numArgs _ numArgs + 1;
};
$Or, $And, $Not => {
newOp: Operator;
SELECT top.type FROM
$Or => newOp _ $Or;
$And => newOp _ $And;
$Not => newOp _ $Not;
ENDCASE => newOp _ $None;
IF haveOp THEN {
IF op # newOp OR op = $Not THEN ERROR Error[InternalError, "Parser screwup."];  
}
ELSE {
haveOp _ TRUE;
op _ newOp;
opId _ top.type;
};
};
ENDCASE;
rp _ Peek[s];
IF rp.type # $SubTree AND topOp.type # $Null THEN {
SELECT Precedence[rp.type, topOp.type] FROM
'< => EXIT;
'= => NULL;
'> => ERROR;
ENDCASE => GOTO syntax;
};
ENDLOOP;
IF haveOp THEN {
IF numArgs < 1 THEN GOTO syntax;
IF op = $Not AND numArgs > 1 THEN GOTO syntax;
NARROW[newt.value, REF Expression].op _ op;
}
ELSE {
IF numArgs > 1 THEN GOTO syntax;
IF ISTYPE[newt.value, REF Expression] THEN {
e: REF Expression _ NARROW[newt.value, REF Expression];
IF e # NIL AND e.children # NIL THEN
newt.value _ e.children.first;
};
};
IF curToken.type = $End AND Peek[s].type = $End THEN 
RETURN[newt.value];
s _ Push[s, newt];
};
ENDCASE => GOTO syntax;
ENDLOOP;
EXITS
syntax => ERROR Error[SyntaxError, "Syntax error in expression."];
END;

TreeToRope: PUBLIC PROC [tree: Tree] RETURNS [Rope.ROPE] = BEGIN
result: Rope.ROPE _ NIL;
IF tree = NIL THEN RETURN[""];
WITH tree SELECT FROM
l: REF Leaf => {
IF l.neg THEN
RETURN[Rope.Concat[tokenNames[$Not], Atom.GetPName[l.var]]]
ELSE
RETURN[Atom.GetPName[l.var]];
};
e: REF Expression => {
opName: Rope.ROPE;
haveArg: BOOL _ FALSE;
SELECT e.op FROM
$Not => opName _ tokenNames[$Not];
$Or => opName _ tokenNames[$Or];
$And => opName _ tokenNames[$And];
$None => opName _ "";
ENDCASE => ERROR Error[UnknownOperator, "Unknown operator in expression tree."];
IF e.op = $Not THEN
result _ opName
ELSE
result _ "";
FOR st: LIST OF SubTree _ e.children, st.rest WHILE st # NIL DO
stName: Rope.ROPE;
stName _ TreeToRope[st.first];
IF ~ISTYPE[st.first, REF Leaf] THEN
stName _ Rope.Cat["(", stName, ")"];
IF e.op = $Not THEN 
result _ Rope.Cat[result, " ", stName]
ELSE {
IF haveArg THEN
result _ Rope.Cat[result, " ", opName, " ", stName]
ELSE
result _ Rope.Cat[result, stName];
};
haveArg _ TRUE;
ENDLOOP;
RETURN[result];
};
ENDCASE => ERROR Error[BadPointer, "Tree is malformed, a pointer points to something other than a subtree or a node."];
END;
AppendTreeLists: PROC [l1, l2: LIST OF SubTree] RETURNS [LIST OF SubTree] = BEGIN
t: LIST OF SubTree _ l1;
FOR tl: LIST OF SubTree _ l2, tl.rest WHILE tl # NIL DO
t _ CONS[tl.first, t];
ENDLOOP;
RETURN[t];
END;

SOPNot: PUBLIC PROC [tree: Tree] RETURNS [Tree] = BEGIN
IF tree = NIL THEN ERROR Error[TreeIsNil, "Tree is NIL."];
WITH tree SELECT FROM
l: REF Leaf => {
l2: REF Leaf _ NEW[Leaf _ l^];
l2.neg _ ~l2.neg;
RETURN[l2];
};
e: REF Expression => {
finalt: Tree _ NIL;
IF e.children = NIL OR e.children.first = NIL THEN ERROR Error[EmptyExpression, "Empty expression."];
SELECT e.op FROM
$Not => {
RETURN[e.children.first];
};
$Or, $And => {
finalt: Tree _ NIL;
FOR tl: LIST OF Tree _ e.children, tl.rest WHILE tl # NIL DO
t: SubTree;
t _ TreeToSOP[tl.first];
t _ SOPNot[t];
IF e.op = $And THEN
finalt _ SOPOr[finalt, t]
ELSE
finalt _ SOPAnd[finalt, t];
ENDLOOP;
RETURN[finalt];
};
$None => {
RETURN[SOPNot[e.children.first]];
};
ENDCASE => ERROR Error[UnknownOperator, "Unknown operator."];
};
ENDCASE => ERROR Error[BadPointer, "Tree is malformed, a pointer points to something other than a subtree or a node."];
END;

SOPAnd: PUBLIC PROC [tree1, tree2: Tree] RETURNS [Tree] = BEGIN
e: REF Expression _ NEW[Expression];
l1, l2: LIST OF SubTree;
IF tree1 = NIL THEN RETURN[tree2];
IF tree2 = NIL THEN RETURN[tree1];
e.op _ $Or;
e.children _ NIL;
IF ISTYPE[tree1, REF Expression] AND NARROW[tree1, REF Expression].op = $Or THEN
l1 _ NARROW[tree1, REF Expression].children
ELSE
l1 _ CONS[tree1, NIL];
IF ISTYPE[tree2, REF Expression] AND NARROW[tree2, REF Expression].op = $Or THEN
l2 _ NARROW[tree2, REF Expression].children
ELSE
l2 _ CONS[tree2, NIL];
FOR list1: LIST OF SubTree _ l1, list1.rest WHILE list1 # NIL DO
FOR list2: LIST OF SubTree _ l2, list2.rest WHILE list2 # NIL DO
and: REF Expression _ NEW[Expression];
and.op _ $And;
IF ISTYPE[list1.first, REF Expression] AND NARROW[list1.first, REF Expression].op = $And THEN {
and.children _ AppendTreeLists[NARROW[list1.first, REF Expression].children, and.children];
}
ELSE {
and.children _ CONS[list1.first, and.children];
};
IF ISTYPE[list2.first, REF Expression] AND NARROW[list2.first, REF Expression].op = $And THEN {
and.children _ AppendTreeLists[NARROW[list2.first, REF Expression].children, and.children];
}
ELSE {
and.children _ CONS[list2.first, and.children];
};
e.children _ CONS[and, e.children];
ENDLOOP;
ENDLOOP;
RETURN[e];
END;

SOPOr: PUBLIC PROC [tree1, tree2: Tree] RETURNS [Tree] = BEGIN
e: REF Expression _ NEW[Expression];
IF tree1 = NIL THEN RETURN[tree2];
IF tree2 = NIL THEN RETURN[tree1];
e.op _ $Or;
e.children _ NIL;
IF ISTYPE[tree1, REF Expression] AND NARROW[tree1, REF Expression].op = $Or THEN {
e.children _ AppendTreeLists[NARROW[tree1, REF Expression].children, e.children];
}
ELSE {
e.children _ CONS[tree1, e.children];
};
IF ISTYPE[tree2, REF Expression] AND NARROW[tree2, REF Expression].op = $Or THEN {
e.children _ AppendTreeLists[NARROW[tree2, REF Expression].children, e.children];
}
ELSE {
e.children _ CONS[tree2, e.children];
};
RETURN[e];
END;


TreeToSOP: PUBLIC PROC [tree: Tree] RETURNS [Tree] = BEGIN
IF tree = NIL THEN ERROR Error[TreeIsNil, "Tree is NIL."];
WITH tree SELECT FROM
l: REF Leaf => RETURN[tree];
e: REF Expression => {
IF e.children = NIL OR e.children.first = NIL THEN ERROR Error[EmptyExpression, "Empty expression."];
SELECT e.op FROM
$Not => {
t: Tree;
t _ TreeToSOP[e.children.first];
t _ SOPNot[t];
RETURN[t];
};
$Or, $And => {
finalt: Tree _ NIL;
FOR tl: LIST OF Tree _ e.children, tl.rest WHILE tl # NIL DO
t: SubTree;
t _ TreeToSOP[tl.first];
IF e.op = $Or THEN
finalt _ SOPOr[finalt, t]
ELSE
finalt _ SOPAnd[finalt, t];
ENDLOOP;
RETURN[finalt];
};
$None => {
RETURN[TreeToSOP[e.children.first]];
};
ENDCASE => ERROR Error[UnknownOperator, "Unknown operator."];
};
ENDCASE => ERROR Error[BadPointer, "Tree is malformed, a pointer points to something other than a subtree or a node."];
END;

SOPOptimize: PUBLIC PROC [equations: LIST OF Tree] RETURNS [LIST OF Tree] = BEGIN
RETURN[equations];
END;

ptermHashSize: INT = 150;
ptermHashEntry: TYPE = RECORD [
pterm: REF PTerm _ NIL,
position: INT _ 0
];
ptermHashTab: TYPE = RECORD [
numEntries: INT _ 0,
vals: ARRAY [0..ptermHashSize) OF LIST OF ptermHashEntry
];

TempTruthTable: PUBLIC TYPE = RECORD [
numInputs, numOutputs: INT _ 0,
atomTab: RefTab.Ref _ RefTab.Create[150],		-- maps ATOMS -> input positions
ptermTab: REF ptermHashTab _ NEW[ptermHashTab]
];

InsertHashedPTerm: PROC [h: REF ptermHashTab, term: REF PTerm, ins, outs: INT] RETURNS[BOOL, REF PTerm] = BEGIN
pt: LIST OF ptermHashEntry;
hash: INT _ 0;
FOR i: INT IN [0 .. ins) DO
hash _ hash * 3 + ORD[term[i]];
ENDLOOP;
hash _ ABS[hash] MOD ptermHashSize;
FOR pt _ h.vals[hash], pt.rest WHILE pt # NIL DO
match: BOOL _ TRUE;
FOR i: INT IN [0 .. ins) DO
IF pt.first.pterm[i] # term[i] THEN match _ FALSE;
ENDLOOP;
IF match THEN {
FOR k: INT IN [ins .. ins + outs) DO
IF term.bits[k] = $One THEN pt.first.pterm.bits[k] _ $One;
ENDLOOP;
RETURN[FALSE, pt.first.pterm];
};
ENDLOOP;
h.vals[hash] _ CONS[[term, h.numEntries], h.vals[hash]];
h.numEntries _ h.numEntries + 1;
RETURN[TRUE, term];
END;

FillTableFromHash: PROC [tt: TruthTable, h: REF ptermHashTab] = BEGIN
tt.numPTerms _ 0;
FOR i: INT IN [0..ptermHashSize) DO
FOR pt: LIST OF ptermHashEntry _ h.vals[i], pt.rest WHILE pt # NIL DO
tt.pterms[pt.first.position] _ pt.first.pterm;
IF pt.first.position >= h.numEntries THEN ERROR;   -- position not in range
tt.numPTerms _ tt.numPTerms + 1;
IF tt.numPTerms > h.numEntries THEN ERROR;  -- more items than indicated by h.numEntries
ENDLOOP;
ENDLOOP;
END;

SetTerm: PROC [tt: REF TempTruthTable, outputNumber: INT, nv: LIST OF Leaf] = BEGIN
term: REF PTerm _ NEW[PTerm[tt.numInputs + tt.numOutputs]];
FOR i: INT IN [0 .. tt.numInputs + tt.numOutputs) DO
IF i < tt.numInputs THEN term[i] _ $NC ELSE term[i] _ $Zero;
ENDLOOP;
FOR var: LIST OF Leaf _ nv, var.rest WHILE var # NIL DO
val: REF;
num: REF INT;
found: BOOL;
[found, val] _ RefTab.Fetch[tt.atomTab, var.first.var];
IF ~found THEN ERROR Error[VariableNotAnInput, "Variable is not an input."]; 
num _ NARROW[val];
IF var.first.neg THEN 
term[num^] _ $Zero
ELSE 
term[num^] _ $One;
ENDLOOP;
term[tt.numInputs + outputNumber] _ $One;
[] _ InsertHashedPTerm[tt.ptermTab, term, tt.numInputs, tt.numOutputs];
END;

AddVar: PROC [t: Tree, v: LIST OF Leaf] RETURNS[LIST OF Leaf] = BEGIN
WITH t SELECT FROM
l: REF Leaf => {
RETURN[CONS[l^, v]];
};
ENDCASE => GOTO notSOP;
EXITS
notSOP => ERROR Error[NotSOP, "Expression is not in Sum-Of-Products form."];
END;

AddTerm: PROC [t: Tree, v: LIST OF Leaf] RETURNS[LIST OF Leaf] = BEGIN
WITH t SELECT FROM
l: REF Leaf => {
v _ AddVar[t, v];
};
e: REF Expression => {
IF e.children = NIL OR e.children.first = NIL THEN ERROR Error[EmptyExpression, "Empty expression."];
SELECT e.op FROM
$Not => {
v _ AddVar[t, v];
};
$And => {
FOR ch: LIST OF Tree _ e.children, ch.rest WHILE ch # NIL DO
v _ AddVar[ch.first, v];
ENDLOOP;
};
ENDCASE => GOTO notSOP;
};
ENDCASE => ERROR Error[BadPointer, "Tree is malformed, a pointer points to something other than a subtree or a node."];
RETURN[v];
EXITS
notSOP => ERROR Error[NotSOP, "Expression is not in Sum-Of-Products form."];
END;

SOPToTT: PUBLIC PROC [inputs: LIST OF ATOM, equations: LIST OF Tree] RETURNS [TruthTable] = BEGIN

tmp: REF TempTruthTable _ NEW[TempTruthTable];
outputNumber: INT _ 0;
tt: TruthTable _ NIL;
FOR inp: LIST OF ATOM _ inputs, inp.rest WHILE inp # NIL DO
tmp.numInputs _ tmp.numInputs + 1;
IF ~RefTab.Store[tmp.atomTab, inp.first, NEW[INT _ tmp.numInputs-1]] THEN
ERROR Error[DoubleInputs, "Same input appears more than once."]
ENDLOOP;
FOR out: LIST OF Tree _ equations, out.rest WHILE out # NIL DO
tmp.numOutputs _ tmp.numOutputs + 1;  ENDLOOP;
FOR out: LIST OF Tree _ equations, out.rest WHILE out # NIL DO
t: Tree _ out.first;
nv: LIST OF Leaf _ NIL;
WITH t SELECT FROM
l: REF Leaf => {
nv _ AddVar[t, NIL];
SetTerm[tmp, outputNumber, nv];
};
e: REF Expression => {
IF e.children = NIL OR e.children.first = NIL THEN ERROR Error[EmptyExpression, "Empty expression."];
SELECT e.op FROM
$And => {
nv _ AddTerm[t, nv];
SetTerm[tmp, outputNumber, nv];
};
$Or => {
FOR term: LIST OF Tree _ e.children, term.rest WHILE term # NIL DO
nv _ AddTerm[term.first, NIL];
SetTerm[tmp, outputNumber, nv];
ENDLOOP;
};
ENDCASE => GOTO notSOP;
};
ENDCASE => ERROR Error[BadPointer, "Tree is malformed, a pointer points to something other than a subtree or a node."];
outputNumber _ outputNumber + 1;
ENDLOOP;
tt _ NEW[TruthTableRec[tmp.ptermTab.numEntries]];
tt.numInputs _ tmp.numInputs;
tt.numOutputs _ tmp.numOutputs;
FillTableFromHash[tt, tmp.ptermTab];
RETURN[tt];

EXITS
notSOP => ERROR Error[NotSOP, "Expression is not in Sum-Of-Products form."];
END;
TTToStream: PUBLIC PROC [tt: TruthTable, out: IO.STREAM] = BEGIN
IF tt = NIL THEN ERROR Error[TTIsNil, "NIL truth table."];
FOR i: INT IN [0..tt.numPTerms) DO
FOR j: INT IN [0..tt.numInputs+tt.numOutputs) DO
IF j = tt.numInputs THEN IO.PutRope[out, "  |  "];
SELECT tt.pterms[i].bits[j] FROM
$One => IO.PutChar[out, '1];
$Zero => IO.PutChar[out, '0];
$NC => IO.PutChar[out, '-];
ENDCASE => ERROR Error[UnknownTTBit, "Strange bit in truth table"];
ENDLOOP;
IO.PutChar[out, '\n];
ENDLOOP;
END;

StreamToTT: PUBLIC PROC [in: IO.STREAM] RETURNS [TruthTable] = BEGIN
ins, outs, pterms: INT _ 0;
r: Rope.ROPE;
tTable: TruthTable;
haveDotE: BOOL _ FALSE;
eof: BOOL _ FALSE;
ptermNum: INT _ 0;
hashTab: REF ptermHashTab _ NEW[ptermHashTab];
DO
index: INT;
term: REF PTerm;
r _ IO.GetLineRope[in ! IO.EndOfStream => {eof _ TRUE; CONTINUE}];
IF eof THEN EXIT;
IF Rope.Length[r] < 1 OR Rope.Fetch[r, 0] = '# THEN LOOP;
IF eof THEN EXIT;
pterms _ pterms + 1;
IF pterms = 1 THEN {  -- first pterm, count number of inputs and outputs
numBits: INT _ 0;
FOR j: INT IN [0..Rope.Length[r]) DO
ch: CHAR _ Rope.Fetch[r, j];
SELECT ch FROM
'| => ins _ numBits;
' , '\n, '\t => LOOP;
'0, '1, '-, 'x, 'X => numBits _ numBits + 1;
ENDCASE => GOTO badBit;
ENDLOOP;
outs _ numBits - ins;
IF ins < 1 OR outs < 1  THEN GOTO shortTerm;
};
term _ NEW[PTerm[ins + outs]];
index _ 0;
FOR j: INT IN [0..Rope.Length[r]) DO
ch: CHAR _ Rope.Fetch[r, j];
SELECT ch FROM
'| => {
IF ins < index THEN 
GOTO longTerm 
ELSE {
IF ins > index THEN
GOTO shortTerm;
};
LOOP;
};
' , '\n, '\t => LOOP;
'0 => {
IF index >= ins + outs THEN GOTO longTerm;
term.bits[index] _ $Zero;
};
'1 => {
IF index >= ins + outs THEN GOTO longTerm;
term.bits[index] _ $One;
};
'-, 'x, 'X => {
IF index >= ins + outs THEN GOTO longTerm;
term.bits[index] _ $NC;
};
ENDCASE => GOTO badBit;
index _ index + 1;
ENDLOOP;
IF index # ins + outs THEN GOTO shortTerm;
[] _ InsertHashedPTerm[hashTab, term, ins, outs];
ENDLOOP;
IF pterms < 1 THEN GOTO earlyEnd;
tTable _ NEW[TruthTableRec[hashTab.numEntries]];
tTable.numInputs _ ins;
tTable.numOutputs _ outs;
FillTableFromHash[tTable, hashTab];
RETURN[tTable];
EXITS
earlyEnd => ERROR Error[SyntaxError, "Truth table ends early."];
longTerm => ERROR Error[SyntaxError, "Product term is too long."];
shortTerm => ERROR Error[SyntaxError, "Product term is too short."];
badBit => ERROR Error[SyntaxError, "Bad character in truth table."];
END;

Test: Commander.CommandProc = BEGIN
ENABLE {
Error => {
cmd.out.PutF["\nError: '"];
cmd.out.PutF[msg];
cmd.out.PutF["'.\n"];
CONTINUE;
};
};

expr: Rope.ROPE;
tList: LIST OF Tree _ NIL;
t: Tree;
tTable: TruthTable;
abc: LIST OF ATOM;
abc _ LIST[$a, $b, $c];
DO
cmd.out.PutF["Expr? "];
expr _ cmd.in.GetLineRope[];
t _ RopeToTree[expr];
expr _ TreeToRope[t];
cmd.out.PutF["Expr: '"];
cmd.out.PutF[expr];
cmd.out.PutF["'.\n"];
t _ TreeToSOP[t];
expr _ TreeToRope[t];
cmd.out.PutF["SOP Expr: '"];
cmd.out.PutF[expr];
cmd.out.PutF["'.\n"];
tList _ CONS[t, tList];
tTable _ SOPToTT[abc, tList];
TTToStream[tTable, cmd.out];
ENDLOOP;
END;

Commander.Register[key: "BoolOpsImplTest", proc: Test, doc: "test program"];
END.
¨File: BoolOpsImpl.mesa			
Copyright c 1984 by Xerox Corporation.  All rights reserved.
Created by: Mayo, July 16, 1984 4:44:25 pm PDT
Last Edited by: Mayo, July 30, 1984 4:32:04 pm PDT
--        ISNAOLREN
--        duonrPPnu
--         btd aadl
Convert a rope into an expresion tree.
Use an operator precedence parser to parse our expressions: (straight out of Aho & Ullman)
E -> id
E -> NOT E
E -> (E)
E -> E AND E
E -> E OR E

-- return the first terminal token on the stack
newt.name _ "";
newt.name _ top.name;
newt.name _ Rope.Cat[" (", top.name, ")", newt.name];
-- parser design error: two $Nots or more than one operator for a set of variables
newt.name _ Rope.Cat[tokenNames[opId], newt.name];
Convert an expression tree into a rope.

Perform logical operations on SOP trees to produce another tree in SOP form.
-- use DeMorgan's law
-- create two lists of things to be ANDed together.
-- now form the cross product of the lists
-- create one AND term
Convert an arbitrary expression tree into sum-of-products form.
Optimize a set of boolean equations in SOP form.  Method used is tailored for PLAs.
-- not implemented yet
-- Returns TRUE if the term was added to the table, FALSE if it just needed to be ORed into an existing entry in the table.
-- In any case, returns a pointer to the term.
-- OR in the new term
-- create a new term

-- record inputs

--  make the product terms 

-- create the truth table

-- get product terms
Κ	˜–

"Cedar" styleš
œ™Jšœ
Οm
œ1™<J™.J™2J˜—š
Οk	˜	J˜Jšœ
žœ˜(Jšœžœ˜ J˜J˜Jšžœ
˜š
œ˜J˜——J˜šΟbœžœ
žœ˜šžœžœ
žœž˜AJšžœ
˜—J˜JšŸ
œžœ:˜JJ˜šŸ
œžœžœžœ˜-J˜Jš
Οf™Jš
 ™Jš
 ™JšΠcf 
˜Jš‘ 
˜Jš‘ 
˜Jš‘ 
˜Jš‘ 
˜Jš‘ 
˜Jš‘ 
˜Jš‘ 
˜Jš‘ ˜J˜J˜—J˜JšŸ
œžœžœžœ0˜YJ˜Jš
Ÿœžœ
žœžœžœ
˜:J˜J™&šΟn
œžœ
žœ
žœžœž˜FJ˜™ZJ™J™
J™J™J™J™J˜—šœžœžœ˜Jš
œ˜Jšœžœžœ
˜Jšœž˜J˜J˜—šœžœžœ˜Jšœžœ
˜Jšœžœ˜J˜J˜—Jšœžœžœ
žœ˜J˜š’	œžœžœ
žœžœ
ž˜6Jšœ
žœ
˜Jšœžœžœ
˜šœ
žœ˜&Jšžœžœžœ˜$Jšžœžœžœ
˜(Jš
œ˜—Jšžœžœ
žœ
˜•StartOfExpansion[]šžœžœž˜"Jšžœ žœ
žœ˜8Jšžœ
˜—Jšžœ
˜Jšžœ
˜J˜—š’œžœžœ
ž˜6Jšžœ
žœ˜Jšžœ
˜J˜—š’œžœžœž˜2Jšžœžœ
žœ
žœ
žœžœ˜?Jšžœ˜Jšžœ
˜J˜—š’œžœžœ
ž˜,Jš
žœžœ
žœ
žœžœ˜:Jšžœ
˜Jšžœ
˜J˜—š’	œžœžœ
ž˜1J–[]™/šžœžœ	žœ
ž˜5Jšžœžœ
žœ˜8Jšžœ
˜—Jšžœžœ˜*Jšžœ
˜J˜—š	’
œžœžœ
žœž˜?Jšžœžœ	˜0Jšžœ
˜J˜—Jš	œžœ
žœžœ
žœ˜Jšœžœ
˜J˜Jšœžœ˜Jšœžœžœ˜šžœ
˜Jšžœžœ˜7J˜šžœ#ž˜-šœ
Οc˜Jš
œ˜Jš
œ˜J˜—šœ£	˜J˜Jšœžœžœ˜!J˜Jšœžœžœ
˜Jš
œ
˜
J˜Jšœ	žœ˜J˜J™š
ž˜J˜Jšžœžœ
˜'šžœ
ž˜š
œ˜Jšœ
žœ˜Jšžœ
žœ%˜;Jš
œ™J˜—š
œ
˜
Jšžœžœ
žœžœ
˜6Jš
žœ
žœžœžœ
žœ˜kJš
œ5™5J˜J˜—˜J˜šžœ
ž˜J˜J˜Jš
œ˜Jšžœ˜—šžœžœ˜Jš
£R™RJšžœžœžœ
žœ+˜PJ˜
—šžœ˜Jšœ	žœ
˜Jš
œ˜J˜J˜—J˜—Jšžœ
˜—J˜
šžœžœžœ˜3šžœ!ž˜+Jšœžœ
˜Jšœžœ
˜Jšœžœ
˜Jšžœžœ˜—J˜—Jšžœ
˜—šžœžœ˜Jšžœ
žœ
žœ˜ Jšžœžœ
žœ
žœ˜.Jš
œ2™2Jšžœ
žœ˜+J˜
—šžœ˜Jšžœ
žœ
žœ˜ šžœ
žœ
žœ
žœ˜,Jšœžœžœ
žœ
˜7š	žœžœ
žœžœ
ž˜$Jš
œ˜—J˜—J˜—šžœžœžœ
˜5Jšžœ
˜—Jš
œ˜J˜—Jšžœžœ˜—Jšžœ
˜—š
ž˜Jšœ
žœ3˜B—Jšžœ
˜—J˜J™'š’
œžœ
žœžœžœž˜@J–[]šœ
žœžœ
˜Jšžœžœ
žœ
žœ˜šžœžœ
ž˜šœžœ
˜šžœž˜
Jšžœ5˜;—š
ž˜Jšžœ˜—J˜—šœžœ˜Jšœ
žœ
˜Jšœ	žœžœ
˜šžœž˜Jš
œ"˜"Jš
œ ˜ Jš
œ"˜"J˜Jšžœžœ@˜P—šžœ
ž˜J˜—š
ž˜J˜—šžœžœ
žœžœžœ
ž˜?Jšœ
žœ
˜J˜šžœžœžœž˜#J˜$—šžœ
žœ
˜J˜&—šžœ˜šžœ	ž˜J˜3—š
ž˜J˜"—J˜—Jšœ
žœ
˜Jšžœ
˜—Jšžœ	˜J˜—Jšžœžœg˜w—Jšžœ
˜—J™–[]š’œžœ
žœ
žœ
žœžœ
žœž˜QJšœžœ
žœ˜šžœžœ
žœžœžœ
ž˜7Jšœžœ˜Jšžœ
˜—Jšžœ˜
Jšžœ
˜J˜—J™Lš	’œžœ
žœžœ
ž˜7Jšžœžœ
žœ
žœ"˜:šžœžœ
ž˜šœžœ
˜Jšœžœžœ˜J˜Jšžœ˜J˜—šœžœ˜Jšœžœ
˜Jšžœžœ
žœžœ
žœ
žœ-˜ešžœž˜š
œ	˜	Jšžœ˜Jš
œ˜—š
œ˜J–[]™Jšœžœ
˜šžœžœ
žœžœžœ
ž˜<J˜J˜J˜šžœ
ž˜J˜—š
ž˜J˜—Jšžœ
˜—Jšžœ	˜Jš
œ˜—š
œ
˜
Jšžœ˜!J˜—Jšžœžœ-˜=—J˜—Jšžœžœg˜w—Jšžœ
˜J˜—š	’œžœ
žœžœ
ž˜?Jšœžœžœ
˜$Jšœžœ
žœ	˜Jšžœ	žœ
žœ
žœ˜"Jšžœ	žœ
žœ
žœ˜"J˜Jšœ
žœ
˜J™3š
žœ
žœžœ
žœ
žœžœž˜PJšœžœžœ˜+—š
ž˜Jšœžœžœ˜—š
žœ
žœžœ
žœ
žœžœž˜PJšœžœžœ˜+—š
ž˜Jšœžœžœ˜—J™*šžœžœ
žœžœ	žœ
ž˜@šžœžœ
žœžœ	žœ
ž˜@J™Jšœžœžœ
˜&J˜šžœ
žœžœ
žœ
žœžœžœ˜_Jšœžœžœ%˜[J˜
—šžœ˜Jšœžœ˜/J˜—šžœ
žœžœ
žœ
žœžœžœ˜_Jšœžœžœ%˜[J˜
—šžœ˜Jšœžœ˜/J˜—Jšœ
žœ˜#Jšžœ
˜—Jšžœ
˜—Jšžœ˜
Jšžœ
˜J˜—š	’œžœ
žœžœ
ž˜>Jšœžœžœ
˜$Jšžœ	žœ
žœ
žœ˜"Jšžœ	žœ
žœ
žœ˜"J˜Jšœ
žœ
˜šžœ
žœžœ
žœ
žœžœžœ˜RJšœžœžœ#˜QJ˜
—šžœ˜Jšœ
žœ˜%J˜—šžœ
žœžœ
žœ
žœžœžœ˜RJšœžœžœ#˜QJ˜
—šžœ˜Jšœ
žœ˜%J˜—Jšžœ˜
Jšžœ
˜J˜—J˜J™?š	’	œžœ
žœžœ
ž˜:Jšžœžœ
žœ
žœ"˜:šžœžœ
ž˜Jšœžœ	žœ˜šœžœ˜Jšžœžœ
žœžœ
žœ
žœ-˜ešžœž˜š
œ	˜	J–[]š
œ˜Jš
œ ˜ J˜Jšžœ˜
Jš
œ˜—š
œ˜J–[]šœžœ
˜šžœžœ
žœžœžœ
ž˜<J˜J˜šžœž˜J˜—š
ž˜J˜—Jšžœ
˜—Jšžœ	˜Jš
œ˜—š
œ
˜
Jšžœ˜$J˜—Jšžœžœ-˜=—J˜—Jšžœžœg˜w—Jšžœ
˜—J˜J™Sš’œžœ
žœ
žœ
žœžœžœ
žœ	ž˜QJ™Jšžœ˜Jšžœ
˜—J˜Jšœžœ˜šœžœžœ˜Jšœžœ	žœ
˜Jšœ
žœ˜J˜—šœžœžœ˜Jšœžœ˜Jš	œžœžœ
žœ
žœ˜8J˜—J˜šœžœ
žœžœ˜&Jšœžœ˜Jšœ+£ ˜KJšœ
žœžœ˜.J˜—J˜š’œžœžœžœžœžœ
žœžœ
ž˜oJ™{J™.Jšœžœ
žœ˜Jšœžœ˜šžœžœ
žœž˜Jšœžœ
˜Jšžœ
˜—Jšœžœžœ˜#šžœžœžœ
ž˜0Jšœžœžœ
˜šžœžœ
žœž˜Jšžœžœ	žœ
˜2Jšžœ
˜—šžœžœ˜J™šžœžœ
žœž˜$Jšžœžœ˜:Jšžœ
˜—Jšžœ
žœ˜J˜—Jšžœ
˜—J™Jšœžœ%˜8Jš
œ ˜ Jšžœ
žœ˜Jšžœ
˜J˜—š’œžœžœž˜EJš
œ˜šžœžœ
žœž˜#šžœžœ
žœ%žœžœ
ž˜EJš
œ.˜.Jšžœ#žœ
žœ£˜KJš
œ ˜ Jšžœžœ
žœ£,˜XJšžœ
˜—Jšžœ
˜—Jšžœ
˜J˜—š
’œžœžœžœžœ
žœ	ž˜SJšœžœ	žœ&˜;šžœžœ
žœ%ž˜4Jšžœžœžœ˜<Jšžœ
˜—šžœžœ
žœžœžœ
ž˜7Jšœžœ
˜	Jšœžœ
žœ
˜
Jšœžœ
˜J˜7Jšžœžœ
žœ9˜MJšœžœ˜šžœžœ
˜J˜—šžœ
˜J˜—Jšžœ
˜—Jš
œ)˜)Jš
œG˜GJšžœ
˜J˜—š’œžœžœ
žœžœ
žœ
žœ	ž˜Ešžœžœ
ž˜šœžœ
˜Jšžœ
žœ	˜Jš
œ˜—Jšžœžœ˜—š
ž˜Jšœ
žœ=˜L—Jšžœ
˜J˜—š’œžœžœ
žœžœ
žœ
žœ	ž˜Fšžœžœ
ž˜šœžœ
˜Jš
œ˜Jš
œ˜—šœžœ˜Jšžœžœ
žœžœ
žœ
žœ-˜ešžœž˜˜	Jš
œ˜J˜—˜	šžœžœ
žœžœžœ
ž˜<Jš
œ˜Jšžœ
˜—J˜—Jšžœžœ˜—J˜—Jšžœžœg˜w—Jšžœ˜
š
ž˜Jšœ
žœ=˜L—Jšžœ
˜J˜—š’œžœ
žœ
žœ
žœ
žœ
žœ
žœžœž˜aJ˜Jšœžœžœ˜.Jšœžœ˜Jšœžœ
˜J™J™š
žœžœ
žœ
žœžœžœ
ž˜;J˜"šžœ'žœ
žœž˜IJšžœ:˜?—Jšžœ
˜—J™J™šžœžœ
žœžœžœ
ž˜>Jšœ&žœ
˜.—šžœžœ
žœžœžœ
ž˜>J˜Jšœžœ
žœžœ
˜šžœžœ
ž˜šœžœ
˜Jšœžœ˜Jš
œ˜Jš
œ˜—šœžœ˜Jšžœžœ
žœžœ
žœ
žœ-˜ešžœž˜˜	J˜Jš
œ˜J˜—˜šžœžœ
žœžœžœ
ž˜BJšœžœ˜Jš
œ˜Jšžœ
˜—J˜—Jšžœžœ˜—J˜—Jšžœžœg˜w—Jš
œ ˜ Jšžœ
˜—J™J™Jšœžœ)˜1Jš
œ˜Jš
œ˜Jš
œ$˜$Jšžœ˜J˜š
ž˜Jšœ
žœ=˜L—Jšžœ
˜J™—š’
œžœ
žœžœ
žœž˜@Jšžœžœ
žœ
žœ$˜:šžœžœ
žœž˜"šžœžœ
žœ!ž˜0Jšžœžœ
žœ˜2šžœž˜ Jšœžœ˜Jšœ	žœ˜Jšœžœ˜Jšžœžœ3˜C—Jšžœ
˜—Jšžœ˜Jšžœ
˜—Jšžœ
˜J˜—š
’
œžœ
žœžœ
žœžœž˜DJšœžœ˜Jšœžœ
˜
J˜Jšœ
žœžœ
˜Jšœžœžœ
˜Jšœ
žœ˜Jšœ	žœžœ˜.J™š
ž˜Jšœžœ
˜Jšœžœ˜Jš
œžœΠkrΟrœžœžœ˜BJšžœžœ
žœ
˜Jšžœžœžœ
žœ
˜9Jšžœžœ
žœ
˜J˜šžœžœ£2˜HJšœ	žœ˜šžœžœ
žœž˜$Jšœžœ˜šžœž˜Jš
œ˜Jšœžœ
˜Jš
œ,˜,Jšžœžœ˜—Jšžœ
˜—Jš
œ˜Jšžœ	žœžœ
žœ˜,J˜—Jšœžœ˜J˜
šžœžœ
žœž˜$Jšœžœ˜šžœž˜š
œ˜šžœ
žœ
˜Jšžœ
˜—šžœ˜šžœ
ž˜Jšžœ˜—J˜—Jšžœ
˜J˜—Jšœžœ
˜˜Jšžœžœ
žœ
˜*J˜J˜—˜Jšžœžœ
žœ
˜*J˜J˜—˜Jšžœžœ
žœ
˜*J˜J˜—Jšžœžœ˜—J˜Jšžœ
˜—Jšžœžœ
žœ˜*J˜1Jšžœ
˜—Jšžœžœ
žœ
˜!Jšœ	žœ$˜0J˜J˜J˜#Jšžœ	˜š
ž˜Jšœžœ/˜@Jšœžœ1˜BJšœ
žœ2˜DJšœ
žœ5˜D—Jšžœ
˜J˜—šŸœž˜#šžœ˜˜
J˜J˜J˜Jšžœ
˜	J˜—J˜J˜—Jšœžœ
˜Jšœžœ
žœžœ
˜J˜J˜Jšœžœ
žœ
žœ
˜Jšœžœ
˜š
ž˜Jš
œ˜Jš
œ˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜Jšœžœ˜J˜J˜Jšžœ
˜—Jšžœ
˜J˜—Jš
œL˜LJšžœ
˜——…—Bzd+