DIRECTORY
GrammarBasic USING[Grammar, Symbol, Production, GetRightSideSymbol, GetStartProduction, GetLength, GenProductions, GenProductionsForSymbol, GetFirstLR0Item, GetLR0ItemCollection, NoteAssociatedLR0Closure, GetAssociatedLR0Closure, NoteFirstLR0Item, NoteLR0ItemCollection],
LR0ItemSetsBasic USING[CreateEmptyTentativeLR0ItemSet, GenItemsInLR0ItemSet, InsertItemInTentativeLR0ItemSet, FreezeTentativeLR0ItemSet, GenItemsInTentativeLR0ItemSet, LR0Item, LR0ItemSet, NarrowLR0ItemSet, TentativeLR0ItemSet],
LR0Items USING[];
LR0ItemsImpl: CEDAR PROGRAM IMPORTS GrammarBasic, LR0ItemSetsBasic EXPORTS LR0ItemSetsBasic, LR0Items =
BEGIN OPEN GrammarBasic, LR0ItemSetsBasic;
LR0ItemCollection: TYPE = REF LR0ItemCollectionBody;
LR0ItemCollectionBody: TYPE = RECORD[
grammar: Grammar,
nextIndex: CARDINAL];
LR0ItemRef: TYPE = REF LR0ItemBody;
LR0ItemBody: PUBLIC TYPE = RECORD[
collection: LR0ItemCollection,
production: Production,
position: CARDINAL,
limit: CARDINAL, -- 0 <= position <= limit
x: CARDINAL,-- item1.x = item2.x => item1 = item2
next: LR0ItemRef];
CompleteProduction: PUBLIC PROC[item: LR0Item] RETURNS[Production] = -- NIL unless the LR0Item refers to a complete production, in which case returns the production; used for generating reduction steps.
BEGIN
itemRef: LR0ItemRef ← item.ref;
IF itemRef.position = itemRef.limit THEN RETURN[itemRef.production] ELSE RETURN[NIL];
END;
GetGrammarFromLR0Item: PUBLIC PROC[item: LR0Item] RETURNS[Grammar] =
BEGIN
itemRef: LR0ItemRef ← item.ref;
RETURN[itemRef.collection.grammar];
END;
GetStartLR0Item: PUBLIC PROC[grammar: Grammar] RETURNS[LR0Item] =
BEGIN
production: Production ← GetStartProduction[grammar];
RETURN[GetFirstLR0Item[production]];
END;
GetFirstLR0Item: PUBLIC PROC[production: Production] RETURNS[LR0Item] =
BEGIN
ref: LR0ItemRef ← NARROW[GrammarBasic.GetFirstLR0Item[production]];
RETURN[[ref, ref.x]];
END;
GetNextLR0Item: PUBLIC PROC[item: LR0Item] RETURNS[LR0Item] =
BEGIN
ref: LR0ItemRef ← item.ref;
nextRef: LR0ItemRef ← ref.next;
IF nextRef # NIL THEN RETURN[[nextRef, nextRef.x]] ELSE RETURN[[NIL, 0]];
END;
GetFirstSymbol: PUBLIC PROC[item: LR0Item] RETURNS[Symbol] =
BEGIN
ref: LR0ItemRef ← item.ref;
IF ref.position = ref.limit THEN RETURN[NIL];
RETURN[GetRightSideSymbol[ref.production, ref.position]];
END;
GetProductionAndPosition: PUBLIC PROC[item: LR0Item] RETURNS[production: Production, position: CARDINAL] =
BEGIN
ref: LR0ItemRef ← item.ref;
RETURN[ref.production, ref.position];
END;
GenV0EpsilonKernelItems: PUBLIC PROC[grammar: Grammar, for: PROC[LR0Item]] =
BEGIN
itemRef: LR0ItemRef ← NARROW[GrammarBasic.GetFirstLR0Item[GetStartProduction[grammar]]];
IF itemRef = NIL THEN
BEGIN
[] ← GetCollection[grammar];
itemRef ← NARROW[GrammarBasic.GetFirstLR0Item[GetStartProduction[grammar]]];
IF itemRef = NIL THEN ERROR;
END;
for[[itemRef, itemRef.x]];
END;
GenKernelGoTo0Items: PUBLIC PROC[item: LR0Item, for: PROC[Symbol, LR0Item]] =
BEGIN
itemRef: LR0ItemRef ← item.ref;
IF itemRef.position # itemRef.limit THEN for[
GetRightSideSymbol[itemRef.production, itemRef.position],
[itemRef.next, itemRef.next.x]];
END;
GenClose0Items: PUBLIC PROC[item: LR0Item, for: PROC[LR0Item]] =
BEGIN -- this procedure uses precomputed closures for the first lr0items for each production.
ExploreFirstCloseItem: PROCEDURE[firstCloseItem: LR0Item] =
BEGIN -- this must be the first item of some production
production: Production;
position: CARDINAL;
subClosure: LR0ItemSet;
[production, position] ← GetProductionAndPosition[firstCloseItem];
IF position # 0 THEN ERROR;
subClosure ← NarrowLR0ItemSet[GetAssociatedLR0Closure[production]];
GenItemsInLR0ItemSet[subClosure, for];
END;
for[item];
GenOneLR0CloseStep[item, ExploreFirstCloseItem];
-- support code
GetCollection: PROCEDURE[grammar: Grammar] RETURNS[LR0ItemCollection] =
BEGIN
collection: LR0ItemCollection ← NARROW[GetLR0ItemCollection[grammar]];
IF collection = NIL THEN
BEGIN
ExpandOneProduction: PROC[production: Production] =
BEGIN
size: CARDINAL ← GetLength[production];
next: LR0ItemRef ← NIL;
FOR I: CARDINAL DECREASING IN [0..size] DO
item: LR0ItemRef ← NEW[LR0ItemBody ← [collection, production, I, size, collection.nextIndex, next]];
next ← item;
collection.nextIndex ← collection.nextIndex + 1;
ENDLOOP;
NoteFirstLR0Item[production, next];
END;
CloseTheFirst: PROC[production: Production] =
BEGIN
first: LR0Item ← GetFirstLR0Item[production];
tentativeClosure: TentativeLR0ItemSet ← CreateEmptyTentativeLR0ItemSet[grammar];
changed: BOOLEAN ← TRUE;
closure: LR0ItemSet;
PossibleAddOneNewMember: PROC[possibleNewMember: LR0Item] =
BEGIN
IF InsertItemInTentativeLR0ItemSet[tentativeClosure, possibleNewMember] THEN
changed ← TRUE;
END;
ConsiderOneOldMember: PROC[oldItem: LR0Item] =
{GenOneLR0CloseStep[oldItem, PossibleAddOneNewMember]};
[] ← InsertItemInTentativeLR0ItemSet[tentativeClosure, first];
WHILE changed DO
changed ← FALSE;
GenItemsInTentativeLR0ItemSet[tentativeClosure, ConsiderOneOldMember];
ENDLOOP;
closure ← FreezeTentativeLR0ItemSet[tentativeClosure];
NoteAssociatedLR0Closure[production, closure];
END;
-- first create all the LR0Items, and record the first one for each production
collection ← NEW[LR0ItemCollectionBody ← [grammar, 0]];
NoteLR0ItemCollection[grammar, collection];
GenProductions[grammar, ExpandOneProduction];
-- now record the closure of the first LR0Item for each production
GenProductions[grammar, CloseTheFirst];
END;
RETURN[collection];
GenOneLR0CloseStep: PROC[lr0Item: LR0Item, for: PROC[LR0Item]] =
BEGIN -- DOES NOT include the original item
itemRef: LR0ItemRef ← lr0Item.ref;
symbol: Symbol;
ExploreOneProduction: PROC[production: Production] =
BEGIN
closureItemRef: LR0ItemRef ← NARROW[GrammarBasic.GetFirstLR0Item[production]];
for[[closureItemRef, closureItemRef.x]];
END;
IF itemRef.position = itemRef.limit THEN RETURN;
symbol ← GetRightSideSymbol[itemRef.production, itemRef.position];
GenProductionsForSymbol[symbol, ExploreOneProduction];
END;
END..