DIRECTORY
GrammarBasic USING[Grammar, Symbol, Production, GenProductions, GenProductionsForSymbol, GetAssociatedLR1Closure, NoteAssociatedLR1Closure, TestCanProduceEmpty],
TerminalSequences USING[TerminalSeq, TerminalSeqSet, CreateEmptyTerminalSeqSet, GetEmptyTerminalSeq, GenFirstNonEmptyTerminalSeqs, GetSetOfExactlyTheEmptyTermSeq, GetWithEmptyTerminalSeqRemoved, InsertTerminalSeqInSet, InsertTermSeqSetInSet, TestIfEmptySeqInSet, TestIfTerminalSeqSetEmpty],
LR0ItemSetsBasic USING[LR0Item],
LR0Items USING[GetGrammarFromLR0Item, GetFirstSymbol, GetFirstLR0Item, GetNextLR0Item, GetProductionAndPosition, GetStartLR0Item, GenKernelGoTo0Items],
LR1ItemSetsBasic USING[LR1Item, LR1ItemSet, LR1ItemSubset, CreateEmptyLR1ItemSet, InsertItemInLR1ItemSet, GenerateDirtySubsetsFromLR1ItemSet, GenerateSubsetsFromLR1ItemSet, FreezeLR1ItemSet, InsertSubsetInLR1ItemSet, NarrowLR1ItemSet],
LR1Items USING[];
LR1ItemsImpl: CEDAR PROGRAM IMPORTS GrammarBasic, LR0Items, LR1ItemSetsBasic, TerminalSequences EXPORTS LR1Items =
BEGIN OPEN GrammarBasic, TerminalSequences, LR0ItemSetsBasic, LR0Items, LR1ItemSetsBasic;
GenKernelV1EpsilonItemSubsets: PUBLIC PROC[grammar: Grammar, for: PROC[LR1ItemSubset]] =
BEGIN
terminals: TerminalSeqSet ← CreateEmptyTerminalSeqSet[grammar];
[] ← InsertTerminalSeqInSet[terminals, GetEmptyTerminalSeq[grammar]];
for[[GetStartLR0Item[grammar], terminals]];
END;
GenKernelGoTo1ItemSubsetsFromKernelItemSubset: PUBLIC PROC[from: LR1ItemSubset, for: PROC[Symbol, LR1ItemSubset]] =
BEGIN
GenPreCloseGoTo1ItemSubsets: PROC[innerSubset: LR1ItemSubset, innerFor: PROC[Symbol, LR1ItemSubset]] =
BEGIN
SeeOneLR0Item: PROC[s: Symbol, lr0Item: LR0Item] =
{innerFor[s, [lr0Item, innerSubset.terminals]]};
GenKernelGoTo0Items[innerSubset.lr0Item, SeeOneLR0Item];
END;
HandleOneCloseSubset: PROC[closeSubset: LR1ItemSubset] =
{GenPreCloseGoTo1ItemSubsets[closeSubset, for]};
GenCloseOfLR1ItemSubset[from, HandleOneCloseSubset];
END;
-- this procedure depends on some precomputed info
GenCloseOfLR1ItemSubset: PUBLIC PROC[firstSubset: LR1ItemSubset, for: PROC[LR1ItemSubset]] =
BEGIN
grammar: Grammar ← GetGrammarFromLR0Item[firstSubset.lr0Item];
emptySeq: TerminalSeq ← GetEmptyTerminalSeq[grammar];
SecondStepOfClose: PROC[secondSubset: LR1ItemSubset] =
BEGIN
-- secondItem is always of the form [A ← .b, t], and it appears in the closure unless t = e.
-- and we have pre computed closure([A ← .b, e])
maskedSecondTerms: TerminalSeqSet;
ThirdStepOfClose: PROC[thirdSubset: LR1ItemSubset] =
BEGIN
maskedThirdTerms: TerminalSeqSet;
maskedThirdTerms ← GetWithEmptyTerminalSeqRemoved[thirdSubset.terminals];
IF maskedThirdTerms # NIL THEN for[[thirdSubset.lr0Item, maskedThirdTerms]];
IF NOT TestIfEmptySeqInSet[thirdSubset.terminals] THEN RETURN;
IF maskedSecondTerms # NIL THEN for[[thirdSubset.lr0Item, maskedSecondTerms]];
IF NOT TestIfEmptySeqInSet[secondSubset.terminals] THEN RETURN;
for[[thirdSubset.lr0Item, firstSubset.terminals]];
END;
production: Production ← GetProductionAndPosition[secondSubset.lr0Item].production; -- A ← b
subClosure: LR1ItemSet ← NarrowLR1ItemSet[GetAssociatedLR1Closure[production]]; -- close([A ← .b, e])
IF subClosure = NIL THEN -- they havn't been built yet
BEGIN
PreComputeClosures[grammar];
subClosure ← NarrowLR1ItemSet[GetAssociatedLR1Closure[production]];
END;
maskedSecondTerms ← GetWithEmptyTerminalSeqRemoved[secondSubset.terminals];
IF maskedSecondTerms # NIL THEN for[[secondSubset.lr0Item, maskedSecondTerms]];
GenerateSubsetsFromLR1ItemSet[subClosure, ThirdStepOfClose];
END;
for[firstSubset]; -- the input ItemSubset itself is in the closure
GenOneCloseStep[[firstSubset.lr0Item, GetSetOfExactlyTheEmptyTermSeq[grammar]], SecondStepOfClose]; -- here are the rest, with possible repetitions
END;
-- support code
-- this procedure pre-computes the closures of certain items, and associates one such closure with each production. It associates close([A←.b, e]) with the production A←b.
PreComputeClosures: PROC[grammar: Grammar] =
BEGIN
emptySeq: TerminalSeq ← GetEmptyTerminalSeq[grammar];
HandleOneProduction: PROC[production: Production] =
BEGIN
closure: LR1ItemSet ← ConstructFullClosure[[GetFirstLR0Item[production], emptySeq]];
NoteAssociatedLR1Closure[production, closure];
END;
GenProductions[grammar, HandleOneProduction];
END;
-- following procedure is used to generate a full closure using the basic close definition. The results are captured in an ItemSet. The caller will associated these item sets with the first position in each productions.
ConstructFullClosure: PROC[lr1Item: LR1Item] RETURNS[LR1ItemSet] =
BEGIN
grammar: Grammar ← GetGrammarFromLR0Item[lr1Item.lr0Item];
tentative: LR1ItemSet ← CreateEmptyLR1ItemSet[grammar];
moreToDo: BOOLEAN ← TRUE;
[] ← InsertItemInLR1ItemSet[tentative, lr1Item];
WHILE moreToDo DO
InstallOneSubset: PROC[closureItems: LR1ItemSubset] =
{IF InsertSubsetInLR1ItemSet[closureItems, tentative] THEN moreToDo ← TRUE};
HandleOneSubset: PROC[subsetToClose: LR1ItemSubset] =
{GenOneCloseStep[subsetToClose, InstallOneSubset]};
moreToDo ← FALSE;
GenerateDirtySubsetsFromLR1ItemSet[tentative, HandleOneSubset];
ENDLOOP;
RETURN[FreezeLR1ItemSet[tentative, FALSE]];
END;
-- this is the basic close definition, a closure is obtained by combining the input item with the result of the repeated application of this procedure.
GenOneCloseStep: PROC[lr1ItemSubset: LR1ItemSubset, for: PROC[LR1ItemSubset]] =
BEGIN
leftSide: Symbol ← GetFirstSymbol[lr1ItemSubset.lr0Item]; -- the first symbol after the "dot"
grammar: Grammar ← GetGrammarFromLR0Item[lr1ItemSubset.lr0Item];
emptySeq: TerminalSeq ← GetEmptyTerminalSeq[grammar];
terminalSet: TerminalSeqSet ← CreateEmptyTerminalSeqSet[grammar];
-- first check for obviously empty closure
IF leftSide = NIL THEN RETURN;
-- first, build the terminal set that will follow each LR0 Item in the closure
BEGIN
remainder: LR0Item ← GetNextLR0Item[lr1ItemSubset.lr0Item];
emptyInPrev: BOOLEAN ← TRUE; -- initial value, lets the loop go around once
WHILE remainder.ref # NIL AND emptyInPrev DO
firstOfRemainder: Symbol ← GetFirstSymbol[remainder];
IF firstOfRemainder # NIL THEN
BEGIN
noSeqsSeen: BOOLEAN ← TRUE; -- tentative;
SeeOneTerminalSeq: PROC[seq: TerminalSeq] =
BEGIN
IF seq # emptySeq THEN [] ← InsertTerminalSeqInSet[terminalSet, seq] ELSE emptyInPrev ← TRUE;
noSeqsSeen ← FALSE;
END;
emptyInPrev ← FALSE; -- tentative value
GenFirstNonEmptyTerminalSeqs[firstOfRemainder, SeeOneTerminalSeq];
IF noSeqsSeen THEN emptyInPrev ← TRUE;
IF TestCanProduceEmpty[firstOfRemainder] THEN emptyInPrev ← TRUE;
END
ELSE emptyInPrev ← TRUE;
remainder ← GetNextLR0Item[remainder];
ENDLOOP;
IF emptyInPrev THEN {[] ← InsertTermSeqSetInSet[add: lr1ItemSubset.terminals, to: terminalSet]};
END;
-- again, check for empty closure
IF TestIfTerminalSeqSetEmpty[terminalSet] THEN RETURN;
-- now generate the lr0 items for the closure, and present the combined result to the caller.
BEGIN
HandleOneProduction: PROC[production: Production] =
BEGIN
lr0Item: LR0Item ← GetFirstLR0Item[production];
for[[lr0Item, terminalSet]];
END;
GenProductionsForSymbol[leftSide, HandleOneProduction];
END;
END;
-- September 13, 1984 9:03:04 am PDT: this seems all wrong, and I am replacing it with new code. However, I am holding it around just in case I am confused at this time.
OldGenOneCloseStep: PROC[lr1ItemSubset: LR1ItemSubset, for: PROC[LR1ItemSubset]] =
BEGIN
leftSide: Symbol ← GetFirstSymbol[lr1ItemSubset.lr0Item]; -- the first symbol after the "dot"
grammar: Grammar ← GetGrammarFromLR0Item[lr1ItemSubset.lr0Item];
emptySeq: TerminalSeq ← GetEmptyTerminalSeq[grammar];
HandleOneProduction: PROC[production: Production] =
BEGIN
lr0Item: LR0Item ← GetFirstLR0Item[production];
remainder: LR0Item ← GetNextLR0Item[lr1ItemSubset.lr0Item];
emptyInPrev: BOOLEAN ← TRUE; -- initial value, lets the loop go around once
WHILE remainder.ref # NIL AND emptyInPrev DO
firstOfRemainder: Symbol ← GetFirstSymbol[remainder];
terminals: TerminalSeqSet ← CreateEmptyTerminalSeqSet[grammar];
SeeOneTerminalSeq: PROC[seq: TerminalSeq] =
BEGIN
IF seq # emptySeq THEN [] ← InsertTerminalSeqInSet[terminals, seq] ELSE emptyInPrev ← TRUE;
END;
IF firstOfRemainder # NIL THEN
BEGIN
maskedTerminals: TerminalSeqSet;
emptyInPrev ← FALSE; -- tentative value
GenFirstNonEmptyTerminalSeqs[firstOfRemainder, SeeOneTerminalSeq];
maskedTerminals ← GetWithEmptyTerminalSeqRemoved[terminals];
IF maskedTerminals # NIL THEN for[[lr0Item, maskedTerminals]];
END
ELSE emptyInPrev ← TRUE;
remainder ← GetNextLR0Item[remainder];
ENDLOOP;
IF emptyInPrev THEN for[[lr0Item, lr1ItemSubset.terminals]];
END;
IF leftSide # NIL THEN
GenProductionsForSymbol[leftSide, HandleOneProduction];
END;
END..
-- remark: September 14, 1984 11:02:33 am PDT: yet another bug in one close step. If a production has right side, then SeeOneTerminalSeq in the innermost loop never gets called. In this case, we must set emptyInPrev to TRUE, but we didn't.
-- remark: September 21, 1984 5:33:06 pm PDT: yet another bug in one close step. We must set emptyInPrev true if first of remainder can be empty. (This is because GenFirstNonEmptySeqs will not generate the empty seq (by design)).