TerminalSequencesImpl: CEDAR PROGRAM IMPORTS GrammarBasic EXPORTS TerminalSequences =
BEGIN OPEN GrammarBasic;
-- note: terminal sequences are either a single terminal symbol, or empty. So, we represent a terminal sequence by a single cardinal, and a TerminalSequenceSet by a packed array of Booleans.
-- note: This is currently (August 25, 1984 12:47:44 pm PDT) coded to deal with individual terminal sequences in the terminalSeqSets. My old code loopholed into sequences of words, and dealt with whole words at a time. I should eventually loophole into words also. This will have two effects. An internal speed up, e.g. in freeze, but also other interfaces should change, so that instead of dealing in LR1Items (a pair of an LR0Item and a terminal sequence) I will deal with subsets of LR1Items, those subsets that involve the same LR0 item. Such a subset is a pair: an LR0Item, and a TerminalSeqSet. I will need new operations on the sets as a whole, union, difference etc.
TerminalSeq: TYPE = REF TerminalSeqBody;
TerminalSeqBody: PUBLIC TYPE = RECORD[x: CARDINAL, s: Symbol]; -- s is NIL for the empty sequence
-- note: the index for the empty terminal sequence is 0, this is assumed in assorted places
TerminalSeqSet: TYPE = REF TerminalSeqSetBody;
TerminalSeqSetBody: PUBLIC TYPE = RECORD[
ignoreAnyEmpties: BOOLEAN,
ref: REF TerminalSeqSetRealBody];
TerminalSeqSetRealBody: TYPE = RECORD[
collection: TerminalSeqCollection,
frozen: BOOLEAN,
nElements: CARDINAL,
next: TerminalSeqSet,
sequences: PACKED SEQUENCE maxSequences: CARDINAL OF BOOLEAN];
TerminalSeqCollection: TYPE = REF TerminalSeqCollectionBody;
TerminalSeqCollectionBody: TYPE = RECORD[
grammar: Grammar,
hashTable: TerminalSeqSetHashTable,
setOfTheEmptySeq: TerminalSeqSet,
sequences: SEQUENCE maxSequences: CARDINAL OF TerminalSeq];
TerminalSeqSetHashTable: TYPE = REF TerminalSeqSetHashTableBody;
TerminalSeqSetHashTableBody: TYPE = RECORD[
lists: SEQUENCE nLists: CARDINAL OF TerminalSeqSet];
CreateEmptyTerminalSeqSet: PUBLIC PROC[grammar: Grammar] RETURNS[TerminalSeqSet] =
BEGIN
collection: TerminalSeqCollection ← GetCollection[grammar];
realBody: REF TerminalSeqSetRealBody ← NEW[TerminalSeqSetRealBody[collection.maxSequences] ←[collection, FALSE, 0, NIL, ]];
set: TerminalSeqSet ← NEW[TerminalSeqSetBody ← [FALSE, realBody]];
FOR x: CARDINAL IN [0..set.ref.maxSequences) DO set.ref.sequences[x] ← FALSE ENDLOOP;
RETURN[set];
END;
TestIfTerminalSeqInSet: PUBLIC PROC[set: TerminalSeqSet, seq: TerminalSeq] RETURNS[BOOLEAN] =
BEGIN
IF set.ignoreAnyEmpties THEN ERROR;
RETURN[set.ref.sequences[seq.x]];
END;
InsertTerminalSeqInSet: PUBLIC PROC[set: TerminalSeqSet, seq: TerminalSeq] RETURNS[notPreviouslyPresent: BOOLEAN] =
BEGIN
IF set.ref.frozen THEN ERROR;
IF set.ignoreAnyEmpties THEN ERROR;
notPreviouslyPresent ← NOT set.ref.sequences[seq.x];
set.ref.sequences[seq.x] ← TRUE;
IF notPreviouslyPresent THEN set.ref.nElements ← set.ref.nElements + 1;
END;
RemoveTerminalSeqFromSet: PUBLIC PROC[set: TerminalSeqSet, seq: TerminalSeq] =
BEGIN
previouslyPresent: BOOLEAN ← set.ref.sequences[seq.x];
IF set.ref.frozen THEN ERROR;
IF set.ignoreAnyEmpties THEN ERROR;
set.ref.sequences[seq.x] ← FALSE;
IF previouslyPresent THEN set.ref.nElements ← set.ref.nElements - 1;
END;
TestIfTerminalSeqSetEmpty: PUBLIC PROC[set: TerminalSeqSet] RETURNS[BOOLEAN] =
BEGIN
IF set.ignoreAnyEmpties THEN ERROR;
RETURN[set.ref.nElements = 0];
END;
TestNonEmptyIntersection: PUBLIC PROC[a, b: TerminalSeqSet] RETURNS[BOOLEAN] =
BEGIN
IF NOT a.ignoreAnyEmpties AND NOT b.ignoreAnyEmpties AND a.ref.sequences[0] AND b.ref.sequences[0] THEN RETURN[TRUE];
FOR x: CARDINAL IN (0..a.ref.maxSequences) DO
IF a.ref.sequences[x] AND b.ref.sequences[x] THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
END;
GenTerminalSeqsFromSet: PUBLIC PROC[set: TerminalSeqSet, for: PROC[TerminalSeq]] =
BEGIN
IF NOT set.ignoreAnyEmpties AND set.ref.sequences[0] THEN for[set.ref.collection.sequences[0]];
FOR x: CARDINAL IN (0..set.ref.maxSequences) DO
IF set.ref.sequences[x] THEN for[set.ref.collection.sequences[x]];
ENDLOOP;
END;
FreezeTerminalSeqSet: PUBLIC PROC[set: TerminalSeqSet] RETURNS[frozenSet: TerminalSeqSet, hash: CARDINAL] =
BEGIN
collection: TerminalSeqCollection ← set.ref.collection;
hashCode: CARDINAL ← 0;
hashX: CARDINAL;
IF set.ref.frozen THEN ERROR;
IF set.ignoreAnyEmpties THEN ERROR;
FOR x: CARDINAL IN [0..set.ref.maxSequences) DO
IF set.ref.sequences[x] THEN hashCode ← hashCode+x;
ENDLOOP;
hashX ← hashCode MOD collection.hashTable.nLists;
FOR frozenSet: TerminalSeqSet ← collection.hashTable[hashX], frozenSet.ref.next WHILE frozenSet # NIL DO
found: BOOLEAN ← TRUE; -- tentative
IF frozenSet.ref.maxSequences # set.ref.maxSequences THEN ERROR;
FOR x: CARDINAL IN [0..set.ref.maxSequences) DO
IF frozenSet.ref.sequences[x] # set.ref.sequences[x] THEN {found ← FALSE; EXIT};
ENDLOOP;
IF found THEN
BEGIN
IF NOT frozenSet.ref.frozen THEN ERROR;
RETURN[frozenSet, hashCode];
END;
ENDLOOP;
-- not in the table, so put it in
set.ref.frozen ← TRUE;
set.ref.next ← collection.hashTable[hashX];
collection.hashTable[hashX] ← set;
RETURN[set, hashCode];
END;
TestIfEmptySeqInSet: PUBLIC PROC[set: TerminalSeqSet] RETURNS[BOOLEAN] =
BEGIN
IF set.ignoreAnyEmpties THEN RETURN[FALSE];
RETURN[set.ref.sequences[0]];
END;
GetOneSymbolTerminalSeq: PUBLIC PROC[s: Symbol] RETURNS[TerminalSeq] =
BEGIN
seq: TerminalSeq ← NARROW[GetTerminalSeq[s]];
IF seq = NIL THEN ERROR;
RETURN[seq];
END;
GetEmptyTerminalSeq: PUBLIC PROC[grammar: Grammar] RETURNS[TerminalSeq] =
BEGIN
collection: TerminalSeqCollection ← GetCollection[grammar];
RETURN[collection.sequences[0]];
END;
GetSymbolFromTerminalSeq: PUBLIC PROC[seq: TerminalSeq] RETURNS[Symbol] =
{RETURN[seq.s]};
-- this is a basic procedure, it implements First1(symbol).
-- the current implementation is crude. It should record the appropriate sets attached to the symbols. It should work in terms of sets.
GenFirstNonEmptyTerminalSeqs: PUBLIC PROC[s: Symbol, for: PROC[TerminalSeq]] =
BEGIN
TryOneSymbol: PROC[firstSymb: Symbol] =
{IF TestIfTerminal[firstSymb] THEN for[GetOneSymbolTerminalSeq[firstSymb]]};
IF TestIfTerminal[s] THEN for[GetOneSymbolTerminalSeq[s]]
ELSE GenCanBeFirst[s, TryOneSymbol];
END;
GetSetOfExactlyTheEmptyTermSeq: PUBLIC PROC[grammar: Grammar] RETURNS[TerminalSeqSet] =
BEGIN
collection: TerminalSeqCollection ← GetCollection[grammar];
RETURN[collection.setOfTheEmptySeq];
END;
GetWithEmptyTerminalSeqRemoved: PUBLIC PROC[set: TerminalSeqSet] RETURNS[TerminalSeqSet] =
BEGIN
newSet: TerminalSeqSet;
IF set.ignoreAnyEmpties OR NOT set.ref.sequences[0] THEN RETURN[set];
IF set.ref.nElements = 1 AND set.ref.sequences[0] THEN RETURN[NIL];
newSet ← NEW[TerminalSeqSetBody ← [TRUE, set.ref]];
RETURN[newSet];
END;
CompareTwoTerminalSeqSets: PUBLIC PROC[set1, set2: TerminalSeqSet] RETURNS[BOOLEAN] =
BEGIN
set1HasEmptySeq: BOOLEAN ← NOT set1.ignoreAnyEmpties AND set1.ref.sequences[0];
set2HasEmptySeq: BOOLEAN ← NOT set2.ignoreAnyEmpties AND set2.ref.sequences[0];
IF NOT set1.ref.frozen OR NOT set2.ref.frozen THEN ERROR;
IF set1.ref.maxSequences # set2.ref.maxSequences THEN RETURN[FALSE];
IF set1HasEmptySeq # set2HasEmptySeq THEN RETURN[FALSE];
FOR I: CARDINAL IN [1..set1.ref.maxSequences) DO
IF set1.ref.sequences[I] # set2.ref.sequences[I] THEN RETURN[FALSE];
ENDLOOP;
RETURN[TRUE];
END;
-- following support working with sets of terminal sequences as a whole
InsertTermSeqSetInSet: PUBLIC PROC[add: TerminalSeqSet, to: TerminalSeqSet] RETURNS[--some new ones-- BOOLEAN] =
BEGIN
someNewOnes: BOOLEAN ← FALSE; -- tentative
IF add.ref.maxSequences # to.ref.maxSequences THEN ERROR;
IF to.ref.frozen THEN ERROR;
IF to.ignoreAnyEmpties THEN ERROR;
FOR I: CARDINAL IN [0..add.ref.maxSequences) DO
IF I = 0 AND add.ignoreAnyEmpties THEN LOOP;
IF add.ref.sequences[I] THEN
BEGIN
IF NOT to.ref.sequences[I] THEN
BEGIN
to.ref.sequences[I] ← TRUE;
someNewOnes ← TRUE;
to.ref.nElements ← to.ref.nElements + 1;
END;
END;
ENDLOOP;
RETURN[someNewOnes];
END;
CompareTermSeqSetWithSet: PUBLIC PROC[testThese: TerminalSeqSet, with: TerminalSeqSet] RETURNS[--diff--TerminalSeqSet] = --diff are those elements in "test these" and not in "with", NIL if empty
BEGIN
diff: TerminalSeqSet ← NIL;
IF testThese.ref.maxSequences # with.ref.maxSequences THEN ERROR;
IF with.ignoreAnyEmpties THEN ERROR;
FOR I: CARDINAL IN [0..testThese.ref.maxSequences) DO
IF I = 0 AND testThese.ignoreAnyEmpties THEN LOOP;
IF testThese.ref.sequences[I] AND NOT with.ref.sequences[I] THEN
BEGIN
IF diff = NIL THEN diff ← CreateEmptyTerminalSeqSet[with.ref.collection.grammar];
diff.ref.sequences[I] ← TRUE;
END;
ENDLOOP;
RETURN[diff];
END;
-- support code
GetCollection: PROCEDURE[grammar: Grammar] RETURNS[TerminalSeqCollection] =
BEGIN
collection: TerminalSeqCollection ← NARROW[GetTerminalSeqCollection[grammar]];
IF collection = NIL THEN
BEGIN
nTerminalSequences: CARDINAL ← GetNTerminalSymbols[grammar]+1;
hashTable: TerminalSeqSetHashTable ← NEW[TerminalSeqSetHashTableBody[1000]];
nextTerminalSeqIndex: CARDINAL;
AddOneTerminalSeq: PROC[s: Symbol] =
BEGIN
seq: TerminalSeq ← NEW[TerminalSeqBody ← [nextTerminalSeqIndex, s]];
NoteTerminalSeq[s, seq];
collection.sequences[nextTerminalSeqIndex] ← seq;
nextTerminalSeqIndex ← nextTerminalSeqIndex + 1;
END;
FOR hx: CARDINAL IN [0..hashTable.nLists) DO hashTable.lists[hx] ← NIL ENDLOOP;
collection ← NEW[TerminalSeqCollectionBody[nTerminalSequences] ← [grammar, hashTable, NIL, ]];
NoteTerminalSeqCollection[grammar, collection];
collection.sequences[0] ← NEW[TerminalSeqBody ← [0, NIL]]; -- the empty sequence
nextTerminalSeqIndex ← 1;
GenTerminalSymbols[grammar, AddOneTerminalSeq];
collection.setOfTheEmptySeq ← CreateEmptyTerminalSeqSet[grammar];
[] ← InsertTerminalSeqInSet[collection.setOfTheEmptySeq, GetEmptyTerminalSeq[grammar]];
collection.setOfTheEmptySeq ← FreezeTerminalSeqSet[collection.setOfTheEmptySeq].frozenSet;
END;
RETURN[collection];
END;
END..
Remark: September 13, 1984 9:59:48 am PDT: bad bug in InsertTermSeqSetInSet, forgot to increment the membership count, which caused client code to think some sets were empty.
-- RTE: November 1, 1984 5:02:22 pm PST: was not setting the set.ref.frozen when placing in hash table. Not sure if this was a problem.