LR1ItemSetsBasicImpl: CEDAR PROGRAM IMPORTS GrammarBasic, TerminalSequences EXPORTS LR1ItemSetsBasic =
BEGIN OPEN GrammarBasic, TerminalSequences, LR0ItemSetsBasic, LR1ItemSetsBasic;
LR1ItemSetCollection: TYPE = REF LR1ItemSetCollectionBody;
LR1ItemSetCollectionBody: TYPE = RECORD[
grammar: Grammar,
firstSet: LR1ItemSet,
hashTable: LR1HashTable];
LR1ItemSet: TYPE = REF LR1ItemSetBody;
LR1ItemSetBody: PUBLIC TYPE = RECORD[
collection: LR1ItemSetCollection,
frozen: BOOLEAN,
marked: BOOLEAN,
associatedNode: REF ANY,
firstClean: LR1ItemSetChainCell,
recentClean: LR1ItemSetChainCell ← NIL,
firstDirty: LR1ItemSetChainCell,
recentDirty: LR1ItemSetChainCell ← NIL,
nextSet: LR1ItemSet,
nextHashSet: LR1ItemSet ← NIL];
LR1ItemSetChainCell: TYPE = REF LR1ItemSetChainCellBody;
LR1ItemSetChainCellBody: TYPE = RECORD[
lr0Item: LR0Item,
next: LR1ItemSetChainCell,
terminals: TerminalSeqSet];
LR1HashTable: TYPE = REF LR1HashTableBody;
LR1HashTableBody: TYPE = RECORD[slots: SEQUENCE tableSize: CARDINAL OF LR1ItemSet];
ClearLR1ItemSetsAssociatedNodes: PUBLIC PROC[grammar: Grammar] =
BEGIN
collection: LR1ItemSetCollection ← GetCollection[grammar];
FOR set: LR1ItemSet ← collection.firstSet, set.nextSet WHILE set # NIL DO
set.associatedNode ← NIL;
ENDLOOP;
END;
MarkExistingLR1ItemSets: PUBLIC PROC[grammar: Grammar] =
BEGIN
collection: LR1ItemSetCollection ← GetCollection[grammar];
FOR set: LR1ItemSet ← collection.firstSet, set.nextSet WHILE set # NIL DO
set.marked ← TRUE;
ENDLOOP;
END;
ForgetUnmarkedLR1ItemSets: PUBLIC PROC[grammar: Grammar] =
BEGIN
collection: LR1ItemSetCollection ← GetCollection[grammar];
hashTable: LR1HashTable ← collection.hashTable;
prevSet: LR1ItemSet ← NIL;
nextSet: LR1ItemSet;
-- first remove unmarked sets from the main chain
FOR set: LR1ItemSet ← collection.firstSet, nextSet WHILE set # NIL DO
nextSet ← set.nextSet;
IF NOT set.marked THEN
BEGIN
IF prevSet = NIL THEN collection.firstSet ← set.nextSet ELSE prevSet.nextSet ← set.nextSet;
set.nextSet ← NIL;
END
ELSE prevSet ← set;
ENDLOOP;
-- now remove unmarked sets from the hash chains
FOR hashIndex: CARDINAL IN [0..hashTable.tableSize) DO
prevSet ← NIL;
FOR set: LR1ItemSet ← hashTable[hashIndex], nextSet WHILE set # NIL DO
nextSet ← set.nextHashSet;
IF NOT set.marked THEN
BEGIN
IF prevSet = NIL THEN hashTable[hashIndex] ← set.nextHashSet ELSE prevSet.nextHashSet ← set.nextHashSet;
set.nextHashSet ← NIL;
END
ELSE prevSet ← set;
ENDLOOP;
ENDLOOP;
END;
CreateEmptyLR1ItemSet: PUBLIC PROC[grammar: Grammar] RETURNS[LR1ItemSet] =
BEGIN
set: LR1ItemSet ← NEW[LR1ItemSetBody ← [collection: GetCollection[grammar], frozen: FALSE, marked: FALSE]];
RETURN[set];
END;
InsertItemInLR1ItemSet: PUBLIC PROC[set: LR1ItemSet, item: LR1Item] RETURNS[--newItem-- BOOLEAN]=
BEGIN
cleanCell: LR1ItemSetChainCell ← ObtainCleanCell[set, item.lr0Item];
dirtyCell: LR1ItemSetChainCell;
IF set.frozen THEN ERROR;
IF TestIfTerminalSeqInSet[cleanCell.terminals, item.terminalSeq] THEN RETURN[FALSE];
[] ← InsertTerminalSeqInSet[cleanCell.terminals, item.terminalSeq];
dirtyCell ← ObtainDirtyCell[set, item.lr0Item];
RETURN[InsertTerminalSeqInSet[dirtyCell.terminals, item.terminalSeq]];
END;
InsertSubsetInLR1ItemSet: PUBLIC PROC[insert: LR1ItemSubset, into: LR1ItemSet] RETURNS[--someNew-- BOOLEAN] =
BEGIN
cleanCell: LR1ItemSetChainCell ← ObtainCleanCell[into, insert.lr0Item];
dirtyCell: LR1ItemSetChainCell;
diff: TerminalSeqSet ← CompareTermSeqSetWithSet[testThese: insert.terminals, with: cleanCell.terminals];
IF into.frozen THEN ERROR;
IF diff = NIL THEN RETURN[FALSE];
[] ← InsertTermSeqSetInSet[add: insert.terminals, to: cleanCell.terminals];
dirtyCell ← ObtainDirtyCell[into, insert.lr0Item];
RETURN[InsertTermSeqSetInSet[add: insert.terminals, to: dirtyCell.terminals]];
END;
GenerateDirtyItemsFromLR1ItemSet: PUBLIC PROC[set: LR1ItemSet, for: PROC[LR1Item]] =
BEGIN -- and mark them clean
prevCell: LR1ItemSetChainCell ← NIL;
nextCell: LR1ItemSetChainCell;
IF set.frozen THEN ERROR;
FOR dirtyCell: LR1ItemSetChainCell ← set.firstDirty, dirtyCell.next WHILE dirtyCell # NIL DO
cleanCell: LR1ItemSetChainCell ← ObtainCleanCell[set, dirtyCell.lr0Item];
SeeTheTerminals: PROC[terminalSeq: TerminalSeq] =
BEGIN
RemoveTerminalSeqFromSet[dirtyCell.terminals, terminalSeq];
for[[dirtyCell.lr0Item, terminalSeq]];
END;
GenTerminalSeqsFromSet[dirtyCell.terminals, SeeTheTerminals];
ENDLOOP;
-- note, generation may have inserted new dirty items, which were not picked up during preceding scan, therefore, must make sure really is clean before discarding dirty item info. If there are new dirty items, the calling routine will have marked the appropriate node dirty for a later pass.
FOR dirtyCell: LR1ItemSetChainCell ← set.firstDirty, nextCell WHILE dirtyCell # NIL
DO
nextCell ← dirtyCell.next;
IF TestIfTerminalSeqSetEmpty[dirtyCell.terminals] THEN
BEGIN
IF prevCell # NIL THEN prevCell.next ← dirtyCell.next ELSE set.firstDirty ← dirtyCell.next;
dirtyCell.next ← NIL;
END
ELSE prevCell ← dirtyCell;
ENDLOOP;
set.recentDirty ← NIL;
END;
GenerateDirtySubsetsFromLR1ItemSet: PUBLIC PROC[from: LR1ItemSet, for: PROC[LR1ItemSubset]] =
BEGIN -- and make them clean
prevCell: LR1ItemSetChainCell ← NIL;
nextCell: LR1ItemSetChainCell;
IF from.frozen THEN ERROR;
FOR dirtyCell: LR1ItemSetChainCell ← from.firstDirty, dirtyCell.next WHILE dirtyCell # NIL DO
cleanCell: LR1ItemSetChainCell ← ObtainCleanCell[from, dirtyCell.lr0Item];
dirtySeqs: TerminalSeqSet ← dirtyCell.terminals;
dirtyCell.terminals ← CreateEmptyTerminalSeqSet[from.collection.grammar];
for[[dirtyCell.lr0Item, dirtySeqs]];
ENDLOOP;
-- note, generation may have inserted new dirty items, which were not picked up during preceding scan, therefore, must make sure really is clean before discarding dirty item info. If there are new dirty items, the calling routine will have marked the appropriate node dirty for a later pass.
FOR dirtyCell: LR1ItemSetChainCell ← from.firstDirty, nextCell WHILE dirtyCell # NIL
DO
nextCell ← dirtyCell.next;
IF TestIfTerminalSeqSetEmpty[dirtyCell.terminals] THEN
BEGIN
IF prevCell # NIL THEN prevCell.next ← dirtyCell.next ELSE from.firstDirty ← dirtyCell.next;
dirtyCell.next ← NIL;
END
ELSE prevCell ← dirtyCell;
ENDLOOP;
from.recentDirty ← NIL;
END;
FreezeLR1ItemSet: PUBLIC PROC[set: LR1ItemSet, allowDirty: BOOLEAN] RETURNS[LR1ItemSet] =
BEGIN
collection: LR1ItemSetCollection ← set.collection;
hashCode: CARDINAL ← 0;
hashIndex: CARDINAL;
possibleSet: LR1ItemSet;
IF set.frozen THEN ERROR;
IF set.firstDirty # NIL THEN
BEGIN
dummy: PROC[LR1ItemSubset] = {NULL};
IF NOT allowDirty THEN ERROR; -- all entries should be clean
GenerateDirtySubsetsFromLR1ItemSet[set, dummy]; -- cleans the set
END;
set.frozen ← TRUE;
IF set.firstDirty # NIL THEN ERROR;
-- WARNING: September 11, 1984 2:55:11 pm PDT: following comment was written to describe the old schem in which a copy was made. Must figure out how to correct for new scheme without a copy.
-- 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: LR1ItemSetChainCell ← set.firstClean, cell.next WHILE cell # NIL DO
subHash: CARDINAL;
[cell.terminals, subHash] ← FreezeTerminalSeqSet[cell.terminals];
hashCode ← hashCode + subHash;
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 subsets based on 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: LR1ItemSetChainCell ← set.firstClean;
possibleCell: LR1ItemSetChainCell ← possibleSet.firstClean;
WHILE newCell # NIL AND possibleCell # NIL DO
IF newCell.lr0Item # possibleCell.lr0Item THEN {match ← FALSE; EXIT};
IF newCell.terminals # possibleCell.terminals 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 use the input
set.nextHashSet ← collection.hashTable[hashIndex];
collection.hashTable[hashIndex] ← set;
set.nextSet ← collection.firstSet;
collection.firstSet ← set;
RETURN[set];
END;
TestIfLR1ItemSetFrozen: PUBLIC PROC[set: LR1ItemSet] RETURNS[BOOLEAN] =
{RETURN[set.frozen]};
GenerateItemsFromLR1ItemSet: PUBLIC PROC[set: LR1ItemSet, for: PROC[LR1Item]] =
BEGIN
IF NOT set.frozen THEN ERROR;
FOR cell: LR1ItemSetChainCell ← set.firstClean, cell.next WHILE cell # NIL DO
ShowOneTerminalSeq: PROC[seq: TerminalSeq] =
{for[[cell.lr0Item, seq]]};
GenTerminalSeqsFromSet[cell.terminals, ShowOneTerminalSeq];
ENDLOOP;
END;
GenerateSubsetsFromLR1ItemSet: PUBLIC PROC[set: LR1ItemSet, for: PROC[LR1ItemSubset], notFrozenOK: BOOLEAN] =
BEGIN
IF set = NIL THEN RETURN;
IF NOT set.frozen AND NOT notFrozenOK THEN ERROR;
FOR cell: LR1ItemSetChainCell ← set.firstClean, cell.next WHILE cell # NIL DO
for[[cell.lr0Item, cell.terminals]];
ENDLOOP;
END;
SetLR1AssociatedNode: PUBLIC PROC[set: LR1ItemSet, node: REF ANY] =
BEGIN
IF set.associatedNode # NIL THEN ERROR;
set.associatedNode ← node;
END;
GetLR1AssociatedNode: PUBLIC PROC[set: LR1ItemSet] RETURNS[REF ANY] =
{RETURN[set.associatedNode]};
NarrowLR1ItemSet: PUBLIC PROC[ref: REF ANY] RETURNS[LR1ItemSet] =
{RETURN[NARROW[ref]]};
CheckAnLR1ItemSet: PUBLIC PROC[ref: REF ANY] =
BEGIN
set: LR1ItemSet ← NARROW[ref];
FOR cell: LR1ItemSetChainCell ← set.firstClean, cell.next WHILE cell # NIL DO
IF cell.next # NIL AND cell.lr0Item.x >= cell.next.lr0Item.x THEN ERROR;
ENDLOOP;
END;
CompareTwoLR1ItemSets: PUBLIC PROC[ref1, ref2: REF ANY] RETURNS[BOOLEAN] =
BEGIN
set1: LR1ItemSet ← NARROW[ref1];
set2: LR1ItemSet ← NARROW[ref2];
cell1: LR1ItemSetChainCell ← set1.firstClean;
cell2: LR1ItemSetChainCell ← set2.firstClean;
IF NOT set1.frozen OR NOT set2.frozen THEN ERROR;
WHILE cell1 # NIL AND cell2 # NIL DO
IF cell1.lr0Item # cell2.lr0Item THEN RETURN[FALSE];
IF NOT CompareTwoTerminalSeqSets[cell1.terminals, cell2.terminals] THEN RETURN[FALSE];
cell1 ← cell1.next; cell2 ← cell2.next;
ENDLOOP;
IF cell1 = NIL AND cell2 = NIL THEN RETURN[TRUE];
RETURN[FALSE];
END;
-- support code
GetCollection: PROC[grammar: Grammar] RETURNS[LR1ItemSetCollection] =
BEGIN
collection: LR1ItemSetCollection ← NARROW[GetLR1ItemSetCollection[grammar]];
IF collection = NIL THEN
BEGIN -- no collection in existence yet
collection ← NEW[LR1ItemSetCollectionBody ← [grammar, NIL, NIL]];
collection.hashTable ← NEW[LR1HashTableBody[1000]];
FOR hx: CARDINAL IN[0..collection.hashTable.tableSize) DO
collection.hashTable.slots[hx] ← NIL;
ENDLOOP;
NoteLR1ItemSetCollection[grammar, collection];
END;
RETURN[collection];
END;
-- note: this code guarantees the order of the lr0Items to conform to lr0Item.x
ObtainCleanCell: PROCEDURE[set: LR1ItemSet, lr0Item: LR0Item] RETURNS[LR1ItemSetChainCell] =
BEGIN
IF set.recentClean # NIL AND set.recentClean.lr0Item = lr0Item THEN RETURN[set.recentClean];
FOR cell: LR1ItemSetChainCell ← set.firstClean, cell.next WHILE cell # NIL DO
IF cell.lr0Item = lr0Item THEN
{set.recentClean ← cell; RETURN[cell]};
IF cell.lr0Item.x > lr0Item.x THEN
BEGIN -- insert new cell at fron of list
newCell: LR1ItemSetChainCell ← NEW[LR1ItemSetChainCellBody←[lr0Item, cell, CreateEmptyTerminalSeqSet[set.collection.grammar]]];
set.firstClean ← set.recentClean ← newCell;
RETURN[newCell];
END;
IF cell.next = NIL OR cell.next.lr0Item.x > lr0Item.x THEN
BEGIN -- insert new cell following current cell
newCell: LR1ItemSetChainCell ← NEW[LR1ItemSetChainCellBody←[lr0Item, cell.next, CreateEmptyTerminalSeqSet[set.collection.grammar]]];
cell.next ← newCell;
set.recentClean ← newCell;
RETURN[newCell];
END;
ENDLOOP;
-- set must be empty, create first new cell
BEGIN
newCell: LR1ItemSetChainCell ← NEW[LR1ItemSetChainCellBody←[lr0Item, NIL, CreateEmptyTerminalSeqSet[set.collection.grammar]]];
IF set.recentClean # NIL THEN ERROR;
set.firstClean ← set.recentClean ← newCell;
RETURN[newCell];
END;
END;
ObtainDirtyCell: PROCEDURE[set: LR1ItemSet, lr0Item: LR0Item] RETURNS[LR1ItemSetChainCell] =
BEGIN
cell: LR1ItemSetChainCell;
IF set.recentDirty # NIL AND set.recentDirty.lr0Item = lr0Item THEN RETURN[set.recentDirty];
FOR cell: LR1ItemSetChainCell ← set.firstDirty, cell.next WHILE cell # NIL DO
IF cell.lr0Item = lr0Item THEN
{set.recentDirty ← cell; RETURN[cell]};
ENDLOOP;
cell ← set.recentDirty ← NEW[LR1ItemSetChainCellBody];
cell.lr0Item ← lr0Item;
cell.next ← set.firstDirty;
set.firstDirty ← cell;
cell.terminals ← CreateEmptyTerminalSeqSet[set.collection.grammar];
RETURN[cell];
END;
END..
-- Remark: September 8, 1984 12:11:53 pm PDT: There was a really nasty bug in GenerateDirtyItemsFromTentativeLR1ItemSet. I forgot to NIL out set.recentDirty, so a dirty cell could be removed, but still be pointed to by recentDirty. The result was the loss of subseqent items with the same LR0 part (as they would be placed into the dirty cell which would not be seen later.)
-- Remark: September 11, 1984 3:09:15 pm PDT: conversion to have only one kind of terminal and LR1 set, i.e. no "tentative" versions. Also generate, insert etc subsets.
-- Remark: September 12, 1984 3:38:39 pm PDT: really nasty bug in the insertion code. Obtaining clean cell did not put them in the correct order if the new item should go at the fron of the list. Same bug was in the LR0 code.
-- RTE: November 1, 1984 5:17:55 pm PST: FreezeLR1ItemSet was not correctly scanning the sub cells of the tentative set. (started with NIL). Effect was to never see a match, so all sets were treated as never before seen. Did not show up until ran into a loop in among the splitting nodes.