LR0ItemSetsBasicImpl: CEDAR PROGRAM IMPORTS GrammarBasic EXPORTS LR0ItemSetsBasic =
BEGIN OPEN GrammarBasic, LR0ItemSetsBasic;
LR0ItemSetCollection: TYPE = REF LR0ItemSetCollectionBody;
LR0ItemSetCollectionBody: TYPE = RECORD[
grammar: Grammar,
firstSet: LR0ItemSet,
hashTable: LR0HashTable];
TentativeLR0ItemSet: TYPE = REF TentativeLR0ItemSetBody;
TentativeLR0ItemSetBody: PUBLIC TYPE = RECORD[
collection: LR0ItemSetCollection,
firstCell: TentativeLR0ItemSetChainCell,
recentCell: TentativeLR0ItemSetChainCell ← NIL];
TentativeLR0ItemSetChainCell: TYPE = REF TentativeLR0ItemSetChainCellBody;
TentativeLR0ItemSetChainCellBody: TYPE = RECORD[
lr0Item: LR0Item,
next: TentativeLR0ItemSetChainCell];
LR0ItemSet: TYPE = REF LR0ItemSetBody;
LR0ItemSetBody: PUBLIC TYPE = RECORD[
associatedNode: REF ANY,
firstChainCell: LR0ItemSetChainCell,
nextSet: LR0ItemSet,
nextHashSet: LR0ItemSet ← NIL];
LR0ItemSetChainCell: TYPE = REF LR0ItemSetChainCellBody;
LR0ItemSetChainCellBody: TYPE = RECORD[
lr0Item: LR0Item,
next: LR0ItemSetChainCell];
LR0HashTable: TYPE = REF LR0HashTableBody;
LR0HashTableBody: TYPE = RECORD[slots: SEQUENCE tableSize: CARDINAL OF LR0ItemSet];
ClearLR0ItemSetsAssociatedNodes: PUBLIC PROC[grammar: Grammar] =
BEGIN
collection: LR0ItemSetCollection ← GetCollection[grammar];
FOR set: LR0ItemSet ← collection.firstSet, set.nextSet WHILE set # NIL DO
set.associatedNode ← NIL;
ENDLOOP;
END;
CreateEmptyTentativeLR0ItemSet: PUBLIC PROC[grammar: Grammar] RETURNS[TentativeLR0ItemSet] =
BEGIN
collection: LR0ItemSetCollection ← GetCollection[grammar];
set: TentativeLR0ItemSet ← NEW[TentativeLR0ItemSetBody ← [collection, NIL]];
RETURN[set];
END;
-- note: this code guarantees the order of the lr0Items to conform to lr0Item.x
InsertItemInTentativeLR0ItemSet: PUBLIC PROC[set: TentativeLR0ItemSet, item: LR0Item] RETURNS[newItem: BOOLEAN] =
BEGIN
newItem ← FALSE;
IF set.recentCell # NIL AND set.recentCell.lr0Item = item THEN RETURN;
FOR cell: TentativeLR0ItemSetChainCell ← set.firstCell, cell.next WHILE cell # NIL DO
IF cell.lr0Item = item THEN
{set.recentCell ← cell; RETURN};
IF cell.lr0Item.x > item.x THEN
BEGIN -- insert new cell at front of list
newCell: TentativeLR0ItemSetChainCell ← NEW[TentativeLR0ItemSetChainCellBody←[item, cell]];
set.firstCell ← set.recentCell ← newCell;
RETURN[TRUE];
END;
IF cell.next = NIL OR cell.next.lr0Item.x > item.x THEN
BEGIN -- insert new cell following current cell
newCell: TentativeLR0ItemSetChainCell ← NEW[TentativeLR0ItemSetChainCellBody←[item, cell.next]];
cell.next ← newCell;
set.recentCell ← newCell;
RETURN[TRUE];
END;
ENDLOOP;
-- set must be empty, create first new cell
BEGIN
newCell: TentativeLR0ItemSetChainCell ← NEW[TentativeLR0ItemSetChainCellBody←[item, NIL]];
set.firstCell ← set.recentCell ← newCell;
RETURN[TRUE];
END;
END;
GenItemsInTentativeLR0ItemSet: PUBLIC PROC[tentativeSet: TentativeLR0ItemSet, for: PROC[LR0Item]] =
BEGIN
FOR cell: TentativeLR0ItemSetChainCell ← tentativeSet.firstCell, cell.next WHILE cell # NIL DO
for[cell.lr0Item];
ENDLOOP;
END;
FreezeTentativeLR0ItemSet: PUBLIC PROC[tentativeSet: TentativeLR0ItemSet] RETURNS[LR0ItemSet] =
BEGIN
collection: LR0ItemSetCollection ← tentativeSet.collection;
chain: LR0ItemSetChainCell ← NIL;
hashCode: CARDINAL ← 0;
hashIndex: CARDINAL;
possibleSet: LR0ItemSet;
-- note: following loop guarantees that the order of the lr0Items will be exactly the reverse of the order constructed in ObtainCleanCell, so that the order now conforms to the inverse of lr0Item.x
FOR cell: TentativeLR0ItemSetChainCell ← tentativeSet.firstCell, cell.next WHILE cell # NIL DO
hashCode ← hashCode + cell.lr0Item.x;
chain ← NEW[LR0ItemSetChainCellBody ← [cell.lr0Item, chain]];
ENDLOOP;
hashIndex ← hashCode MOD collection.hashTable.tableSize;
FOR possibleSet ← collection.hashTable[hashIndex], possibleSet.nextHashSet WHILE possibleSet # NIL DO
match: BOOLEAN ← TRUE; -- tentative
-- we are about to scan through the lr0Items, since the possibleSet just found, and the chain just constructed, have their lr0items in the same order, we need mearly look for the first difference.
newCell: LR0ItemSetChainCell ← chain;
possibleCell: LR0ItemSetChainCell ← possibleSet.firstChainCell;
WHILE newCell # NIL AND possibleCell # NIL DO
IF newCell.lr0Item # possibleCell.lr0Item THEN {match ← FALSE; EXIT};
newCell ← newCell.next; possibleCell ← possibleCell.next;
ENDLOOP;
IF match AND newCell = NIL AND possibleCell = NIL THEN
BEGIN -- we have a match
RETURN[possibleSet];
END;
ENDLOOP;
-- existing one not found, so create one
possibleSet ← NEW[LR0ItemSetBody ← [NIL, chain, collection.firstSet, collection.hashTable[hashIndex]]];
collection.firstSet ← possibleSet;
collection.hashTable[hashIndex] ← possibleSet;
RETURN[possibleSet];
END;
GenItemsInLR0ItemSet: PUBLIC PROC[set: LR0ItemSet, for: PROC[LR0Item]] =
BEGIN
FOR cell: LR0ItemSetChainCell ← set.firstChainCell, cell.next WHILE cell # NIL DO
for[cell.lr0Item];
ENDLOOP;
END;
GetLR0AssociatedNode: PUBLIC PROC[set: LR0ItemSet] RETURNS[REF ANY] =
{RETURN[set.associatedNode]};
SetLR0AssociatedNode: PUBLIC PROC[set: LR0ItemSet, node: REF ANY] =
{set.associatedNode ← node};
NarrowLR0ItemSet: PUBLIC PROCEDURE[ref: REF ANY] RETURNS[LR0ItemSet] =
{RETURN[NARROW[ref]]};
NarrowTentativeLR0ItemSet: PUBLIC PROCEDURE[ref: REF ANY] RETURNS[TentativeLR0ItemSet] =
{RETURN[NARROW[ref]]};
-- support code
GetCollection: PROC[grammar: Grammar] RETURNS[LR0ItemSetCollection] =
BEGIN
collection: LR0ItemSetCollection ← NARROW[GetLR0ItemSetCollection[grammar]];
IF collection = NIL THEN
BEGIN
hashTable: LR0HashTable ← NEW[LR0HashTableBody[1024]];
FOR x: CARDINAL IN [0..hashTable.tableSize) DO hashTable.slots[x] ← NIL ENDLOOP;
collection ← NEW[LR0ItemSetCollectionBody ← [grammar, NIL, hashTable]];
NoteLR0ItemSetCollection[grammar, collection];
END;
RETURN[collection];
END;
END..
-- remark: September 12, 1984 3:33:31 pm PDT: nasty bug in insert code, the items did not end up in order if the new cell should have been at front of the list.