DIRECTORY
Basics USING[LongNumber],
GrammarBasic USING[GenProductionsForSymbol, GenTerminalSymbols, GetLength, Grammar, Production, Symbol, TestCanProduceEmpty, TestIfTerminal],
HashTable USING[Create, Insert, Table],
IO USING[int, STREAM, PutF],
LR0ItemSetsBasic USING[CreateEmptyTentativeLR0ItemSet, FreezeTentativeLR0ItemSet, GenItemsInLR0ItemSet, GenItemsInTentativeLR0ItemSet, InsertItemInTentativeLR0ItemSet, LR0Item, LR0ItemSet, NarrowLR0ItemSet, TentativeLR0ItemSet],
LR0Items USING[CompleteProduction, GenClose0Items, GenKernelGoTo0Items, GetFirstLR0Item, GetFirstSymbol, GetGrammarFromLR0Item, GetNextLR0Item, GetProductionAndPosition, GetStartLR0Item],
LR1ItemSetsBasic USING[ClearLR1ItemSetsAssociatedNodes, CreateEmptyLR1ItemSet, FreezeLR1ItemSet, GenerateItemsFromLR1ItemSet, GenerateSubsetsFromLR1ItemSet, InsertItemInLR1ItemSet, LR1Item, LR1ItemSet, LR1ItemSubset, NarrowLR1ItemSet],
LR1Items USING[GenCloseOfLR1ItemSubset, GenKernelGoTo1ItemSubsetsFromKernelItemSubset],
LR1ItemSets USING[GenReductionRulesFromKernel],
TerminalSequences USING[CreateEmptyTerminalSeqSet, FreezeTerminalSeqSet, GenFirstNonEmptyTerminalSeqs, GenTerminalSeqsFromSet, GetEmptyTerminalSeq, GetOneSymbolTerminalSeq, InsertTerminalSeqInSet, TerminalSeq, TerminalSeqSet, TestIfTerminalSeqInSet, TestIfTerminalSeqSetEmpty, TestNonEmptyIntersection],
ParserGraphAlgorithms USING[Event],
ParserGraphs USING[AppendAnArc, ClearAllUpperNodePointers, CreateEmptyGraph, CreateTentativeStage1Node, GenerateAllNodes, GenerateArcs, GetAnyStage1Node, GetAssociatedSet, GetBaseNode, GetGrammar, GetGraph, GetStartNode, GetUpperNode, Graph, InstallStage1Node, MarkAsStage2, MarkNodeToSplit, Node, SetUpperNode],
ParserDisplay USING[ShowLR0ItemSet, ShowLR1ItemSet, ShowNode, ShowTerminalSeq, ShowLR0Item, ShowLR1Item],
ConflictAnal USING[];
debug: BOOLEAN ← FALSE; -- Set TRUE for lots of debugging print out
This is the main driver procedure for this module.
For each node of the LALR1 graph (supplied as graph) it checks for conflicting pairs of LR1 items. A list of conflicts is prepared for each following terminal sequence. A conflict graph is prepared that describes all of the conflicting items. For each conflicting item, it describes from what items at earlier nodes that item may have been generated. Finally, for each pair of conflicting items, a graph is made describing how those items may be jointly generated. If any such pair may be jointly generated from the root node, then the grammar is not LR1. Such joint paths are printed out, showing successive productions.
SignalUnresolvableConflict: SIGNAL = CODE;
AnalyzeLALR1Conflicts: PUBLIC PROC[graph: Graph, on: IO.STREAM, noteEvent: PROC[Event]] RETURNS[--IsLR1-- BOOLEAN] =
BEGIN
grammar: Grammar ← GetGrammar[graph];
baseInfoGraph: Graph ← BuildBaseInfoGraph[graph];
conflictGraph: Graph ← CreateEmptyGraph[grammar, SplitNode]; -- SplitNode because there is no good class name at the moment
isLR1: BOOLEAN ← TRUE; -- tentative
seeOneNode: PROC[node: Node] RETURNS[BOOLEAN] =
BEGIN
terminalList: TerminalConflictList ← ObtainConflictsForOneNode[node];
IF debug AND terminalList # NIL THEN
BEGIN
IO.PutF[on, "\N\N\N\NThere are conflicting items at node "];
ShowNode[on, 5, node];
IO.PutF[on, "\N\N"];
FOR oneTerminal: TerminalConflictList ← terminalList, oneTerminal.next WHILE oneTerminal # NIL DO
IO.PutF[on, "\N There are conflicting items for terminal sequence "];
ShowTerminalSeq[on, 0, oneTerminal.terminalSeq];
FOR oneConflictItem: ConflictList ← oneTerminal.conflicts, oneConflictItem.next WHILE oneConflictItem # NIL DO
IO.PutF[on, "\N conflict item = \N"];
ShowLR1Item[on, 8, oneConflictItem.conflictItem];
ENDLOOP;
ENDLOOP;
END;
FOR oneTerminal: TerminalConflictList ← terminalList, oneTerminal.next WHILE oneTerminal # NIL DO
FOR oneConflictItem: ConflictList ← oneTerminal.conflicts, oneConflictItem.next WHILE oneConflictItem # NIL DO
conflictNode: Node ← ProcessOneConflictItem[on, node, oneConflictItem.conflictItem, baseInfoGraph, conflictGraph, noteEvent];
oneConflictItem.node ← conflictNode;
ENDLOOP;
-- now look for possible conflict pairs
FOR oneConflictItem: ConflictList ← oneTerminal.conflicts, oneConflictItem.next WHILE oneConflictItem # NIL DO
IF LR0Items.CompleteProduction[oneConflictItem.conflictItem.lr0Item] # NIL THEN
BEGIN -- we are looking at an item that produces a reduction
FOR secondConflictItem: ConflictList ← oneTerminal.conflicts, secondConflictItem.next WHILE secondConflictItem # NIL DO
IF oneConflictItem # secondConflictItem THEN VisitAccessableConflictPairs[grammar, on, oneConflictItem.conflictItem, oneConflictItem.node, secondConflictItem.conflictItem, secondConflictItem.node];
ENDLOOP;
END;
ENDLOOP;
ENDLOOP;
RETURN[TRUE];
END;
GenerateAllNodes[graph, seeOneNode
! SignalUnresolvableConflict => {isLR1 ← FALSE; RESUME}];
RETURN[isLR1];
END;
TerminalConflictList: TYPE = REF TerminalConflictListBody;
TerminalConflictListBody: TYPE = RECORD[
terminalSeq: TerminalSeq,
conflicts: ConflictList,
next: TerminalConflictList];
ConflictList: TYPE = REF ConflictListBody;
ConflictListBody: TYPE = RECORD[
conflictItem: LR1Item,
node: Node, -- from a conflict graph
next: ConflictList];
ObtainConflictsForOneNode: PROC[node: Node] RETURNS[TerminalConflictList] =
BEGIN
graph: Graph ← GetGraph[node];
grammar: Grammar ← GetGrammar[graph];
terminalList: TerminalConflictList ← NIL;
seeOneConflict: PROC[terminalSeq: TerminalSeq, conflictItem: LR1Item] =
BEGIN
FOR oneTerminal: TerminalConflictList ← terminalList, oneTerminal.next WHILE oneTerminal # NIL DO
IF oneTerminal.terminalSeq = terminalSeq THEN
BEGIN
we have a new conflict item for an existing terminal
oneTerminal.conflicts ← NEW[ConflictListBody←[conflictItem, NIL, oneTerminal.conflicts]];
RETURN;
END;
ENDLOOP;
must be a new terminal for this node
terminalList ← NEW[TerminalConflictListBody←[terminalSeq, NIL, terminalList]];
terminalList.conflicts ← NEW[ConflictListBody←[conflictItem, NIL]];
END;
GenConflictItemsForNode[graph, node, seeOneConflict];
RETURN[terminalList];
END;
ProdTermSeqCell: TYPE = REF ProdTermSeqCellBody;
ProdTermSeqCellBody: TYPE = RECORD[
termSeq: TerminalSeq,
production: Production,
next: ProdTermSeqCell];
Used as a subroutine by GenConflictSets
This procedure is adapted from ParserGraphAlgorithmsImpl.TestConsistencyOfNode
conflictItem is involved in a conflict for terminalSeq, and conflictItem is in the closure of kernelItem, where kernelItem is in the kernel of node.
GenConflictItemsForNode: PROC[graph: Graph, node: Node, for: PROC[terminalSeq: TerminalSeq, conflictItem: LR1Item]] =
BEGIN
consistent: BOOLEAN ← TRUE; -- tentative
grammar: Grammar ← GetGrammar[graph];
conflictingTerminals: TerminalSeqSet ← CreateEmptyTerminalSeqSet[grammar];
We first do a rough analysis to see if there are any conflicts, and record the terminal sequences involved
BEGIN
terminalsSeen: TerminalSeqSet ← CreateEmptyTerminalSeqSet[grammar];
pairsSeen: ProdTermSeqCell ← NIL;
NoteTheOutgoingArcs: PROC[s: Symbol, target: Node] RETURNS[--continue--BOOLEAN] =
BEGIN
IF TestIfTerminal[s] THEN
[] ← InsertTerminalSeqInSet[terminalsSeen, GetOneSymbolTerminalSeq[s]];
RETURN[TRUE];
END;
NoteTheReductionRules: PROC[terminalSeq: TerminalSeq, production: Production] =
BEGIN
IF GetLength[production] # 0 THEN
BEGIN
We are dealing with a non empty production, so it must be in the kernel, hence we will only see it once.
IF NOT InsertTerminalSeqInSet[terminalsSeen, terminalSeq] THEN
BEGIN
consistent ← FALSE;
[] ← InsertTerminalSeqInSet[conflictingTerminals, terminalSeq]
END;
END
ELSE
BEGIN
we are dealing with an empty production, hence not in the kernel, so there is danger of seeing the same <production, terminalSeq> pair more than once.
FOR cell: ProdTermSeqCell ← pairsSeen, cell.next WHILE cell # NIL DO
IF cell.termSeq = terminalSeq AND cell.production = production THEN RETURN; -- we have seen this pair before
ENDLOOP;
IF NOT InsertTerminalSeqInSet[terminalsSeen, terminalSeq] THEN
BEGIN
consistent ← FALSE;
[] ← InsertTerminalSeqInSet[conflictingTerminals, terminalSeq]
END;
pairsSeen ← NEW[ProdTermSeqCellBody←[terminalSeq, production, pairsSeen]];
END;
END;
GenerateArcs[node, NoteTheOutgoingArcs];
GenReductionRulesFromKernel[NarrowLR1ItemSet[GetAssociatedSet[node]], NoteTheReductionRules];
IF consistent THEN RETURN; -- all is well
END; -- of rough analysis
This node contains inconsistencies
Let us now more carefully generate the LR(1) items actually involved in the conflicts, and note the items involved with conflictingTerminals
Scheme: generate all lr1 items from the closure of the kernel. If the "next" symbol is one of the conflicting terminals then we have a conflicting item, or if the production is "complete" and one of the "following" terminal sequences is one of the conflicting terminals, then we also have a conflicting item.
BEGIN
for1: PROC[kernalItem: LR1Item] =
BEGIN
for2: PROC[subSet: LR1ItemSubset] =
BEGIN -- we are now looking at a subset of the closure of kernelItem
first see if we have a complete production on hand, and if the possible follower terminal sequences are of interest, or if not a complete production, if the "shift" terminal sequence is of interest
p: Production ← LR0Items.CompleteProduction[subSet.lr0Item];
IF p # NIL THEN
BEGIN
we have a complete production
so look for reduce conflicts
for3: PROC[tSeq: TerminalSeq] =
BEGIN
IF TestIfTerminalSeqInSet[conflictingTerminals, tSeq]
THEN for[tSeq, [subSet.lr0Item, tSeq]];
END;
GenTerminalSeqsFromSet[subSet.terminals, for3];
END
ELSE
BEGIN
we don't have a complete production
so look for shift conflicts
s: Symbol ← GetFirstSymbol[subSet.lr0Item]; -- the first symbol after the "dot"
tSeq: TerminalSeq ← IF TestIfTerminal[s] THEN GetOneSymbolTerminalSeq[s] ELSE NIL;
for4: PROC[ftSeq: TerminalSeq] =
{for[tSeq, [subSet.lr0Item, ftSeq]]};
IF tSeq # NIL AND TestIfTerminalSeqInSet[conflictingTerminals, tSeq]
THEN GenTerminalSeqsFromSet[subSet.terminals, for4];
END;
END;
kernelItemTermSeqSet: TerminalSeqSet ← CreateEmptyTerminalSeqSet[grammar];
[] ← InsertTerminalSeqInSet[kernelItemTermSeqSet, kernalItem.terminalSeq];
[kernelItemTermSeqSet, ] ← FreezeTerminalSeqSet[kernelItemTermSeqSet];
GenCloseOfLR1ItemSubset[[kernalItem.lr0Item, kernelItemTermSeqSet], for2];
END;
GenerateItemsFromLR1ItemSet[NarrowLR1ItemSet[GetAssociatedSet[node]], for1];
END;
END;
In ProcessOneConflictItem conflictingItem is an element of the LR1 closure of the kernal of the LALR(1) set associated with node.
ProcessOneConflictItem adds nodes and arcs to an existing conflict graph such that:
1) A node is a pair <S, T>, where S is a canonical LR0 set and T is a set of kernel LR1 items. The core of each item in T is in S. If all possible LR1 items with the same core are in T, we simply represent them with the corresponding LR0 item.
2) An arc is directed and labeled. It is a triple: <<S1, T1>, <S2, T2>, A>, where A is a symbol of the grammar and: 1) GOTO0(S1, A) = S2; 2) for all t1 in T1 there is a t2 in T2 such that t2 is in KernelGoTo1({t1}, A); and 3) if t1 is in Kernel(LALR1(S1)) and there is a t2 in T2 such that t2 is in KernelGoTO1({t1}, A), then t1 is in T1.
3) If t is a conflicting item that has been presented to ProcessOneConflictItem, then there will be a node <S, T> where S is the canonical LR0 set associated with the LALR(1) set containing the conflicting item, and were T is the set of kernel items in the LALR(1) set from which the conflicting item can be reached by LR(1) closure.
There are three graphs involved in the following procedure.
LALR is the original LALR graph
baseInfoGraph is the graph parallel to the LALR graph constructed by BuildBaseInfoGraph
conflictGraph is the graph constructed by calls on ProcessOneConflictItem.
ConflictGraphNodeInfo: TYPE = REF ConflictGraphNodeInfoBody;
ConflictGraphNodeInfoBody: TYPE = RECORD[
node: Node,
root: BOOLEAN,
lr1KernelSet: LR1ItemSet,
lr0KernelSet: LR0ItemSet,
prevNodes: LIST OF Node,
next: ConflictGraphNodeInfo];
ProcessOneConflictItem: PROC[on: IO.STREAM, initialLALRnode: Node, conflictingItem: LR1Item, baseInfoGraph: Graph, conflictGraph: Graph, noteEvent: PROC[Event]] RETURNS[initialConflictNodeForConflictingItem: Node] =
BEGIN
grammar: Grammar ← GetGrammar[baseInfoGraph];
rootLR0Item: LR0Item ← GetStartLR0Item[grammar];
-- following procedure is used for adding nodes to the conflict graph
BuildOneConflictGraphNode: PROC[baseNode: Node, tentativeLR1KernelSet: LR1ItemSet, tentativeLR0KernelSet: TentativeLR0ItemSet] RETURNS[node: Node] =
BEGIN
baseNodeInfo: BaseNodeInfo ← NARROW[GetAssociatedSet[baseNode]];
lr1KernelSet: LR1ItemSet ← IF tentativeLR1KernelSet = NIL THEN NIL ELSE FreezeLR1ItemSet[tentativeLR1KernelSet, TRUE];
lr0KernelSet: LR0ItemSet ← IF tentativeLR0KernelSet = NIL THEN NIL ELSE FreezeTentativeLR0ItemSet[tentativeLR0KernelSet];
node ← NIL; -- tentative
IF lr1KernelSet # NIL OR lr0KernelSet # NIL THEN
BEGIN
foundACandidate: BOOLEAN ← FALSE;
FOR candidateNodeInfo: ConflictGraphNodeInfo ← baseNodeInfo.kernelGraphNodeChain, candidateNodeInfo.next WHILE candidateNodeInfo # NIL DO
IF candidateNodeInfo.lr1KernelSet = lr1KernelSet AND candidateNodeInfo.lr0KernelSet = lr0KernelSet THEN
BEGIN -- we have a successful candidate
foundACandidate ← TRUE;
node ← candidateNodeInfo.node;
EXIT;
END;
ENDLOOP;
IF NOT foundACandidate THEN
BEGIN -- got to build a new one
newNodeInfo: ConflictGraphNodeInfo ← NEW[ConflictGraphNodeInfoBody←[
NIL, FALSE, lr1KernelSet, lr0KernelSet, NIL, baseNodeInfo.kernelGraphNodeChain]];
CheckForRoot: PROC[item: LR0Item] =
BEGIN
IF item = rootLR0Item AND GetProductionAndPosition[item].position = 0 THEN
newNodeInfo.root ← TRUE
END;
seeOneLR0Item: PROC[item: LR0Item] = {CheckForRoot[item]};
seeOneLR1Item: PROC[item: LR1Item] = {CheckForRoot[item.lr0Item]};
node ← CreateTentativeStage1Node[conflictGraph, newNodeInfo, baseNode];
newNodeInfo.node ← node;
baseNodeInfo.kernelGraphNodeChain ← newNodeInfo;
InstallStage1Node[node, FALSE];
IF lr0KernelSet # NIL THEN GenItemsInLR0ItemSet[lr0KernelSet, seeOneLR0Item];
IF NOT newNodeInfo.root AND lr1KernelSet # NIL THEN GenerateItemsFromLR1ItemSet[lr1KernelSet, seeOneLR1Item];
END;
END;
END;
-- following special terminal sequences are used in testing whether all LR1 items with the same LR0 component will go into a constructed set, and hence can be represented by a single LR0 item, rather than a collection of distinct LR1 items.
emptyTerminalSeq: TerminalSeq;
singletonEmptyTerminalSeq: TerminalSeqSet;
otherTerminalSeq: TerminalSeq ← NIL;
singletonOtherTerminalSeq: TerminalSeqSet;
-- set up the special terminal sequences
BEGIN
seeOneTerminal: PROC[t: Symbol] =
BEGIN
IF otherTerminalSeq = NIL THEN
otherTerminalSeq ← GetOneSymbolTerminalSeq[t];
END;
emptyTerminalSeq ← GetEmptyTerminalSeq[grammar];
singletonEmptyTerminalSeq ← CreateEmptyTerminalSeqSet[grammar];
[] ← InsertTerminalSeqInSet[singletonEmptyTerminalSeq, emptyTerminalSeq];
[singletonEmptyTerminalSeq, ] ← FreezeTerminalSeqSet[singletonEmptyTerminalSeq];
GenTerminalSymbols[grammar, seeOneTerminal];
singletonOtherTerminalSeq ← CreateEmptyTerminalSeqSet[grammar];
[] ← InsertTerminalSeqInSet[singletonOtherTerminalSeq, otherTerminalSeq];
[singletonOtherTerminalSeq, ] ← FreezeTerminalSeqSet[singletonOtherTerminalSeq];
END;
-- build the initialConflictNode
BEGIN
initialBaseInfoNode: Node ← GetUpperNode[initialLALRnode];
initialBaseInfo: BaseNodeInfo ← NARROW[GetAssociatedSet[initialBaseInfoNode]];
tentativeLR1KernelSet: LR1ItemSet ← NIL;
tentativeLR0KernelSet: TentativeLR0ItemSet ← NIL;
seeOneLR0Item: PROC[candidateLR0Item: LR0Item] =
BEGIN
candidateLR0ItemIsIn: BOOLEAN ← FALSE;
TryOneSyntheticLR1Item: PROC[trialItemSubset: LR1ItemSubset, trialItemSeq: TerminalSeq] =
BEGIN
seeOneClosureSubset: PROC[closureSubset: LR1ItemSubset] =
BEGIN
seeOneTerminalSeq: PROC[ts: TerminalSeq] =
BEGIN
IF candidateLR0ItemIsIn THEN RETURN;
IF ts = conflictingItem.terminalSeq THEN
BEGIN
IF tentativeLR0KernelSet = NIL THEN
tentativeLR0KernelSet ← CreateEmptyTentativeLR0ItemSet[grammar];
[] ← InsertItemInTentativeLR0ItemSet[tentativeLR0KernelSet, candidateLR0Item];
candidateLR0ItemIsIn ← TRUE;
END;
END;
IF candidateLR0ItemIsIn THEN RETURN;
IF closureSubset.lr0Item # conflictingItem.lr0Item THEN RETURN;
GenTerminalSeqsFromSet[closureSubset.terminals, seeOneTerminalSeq];
END;
GenCloseOfLR1ItemSubset[trialItemSubset, seeOneClosureSubset];
END;
IF emptyTerminalSeq = conflictingItem.terminalSeq THEN
TryOneSyntheticLR1Item[[candidateLR0Item, singletonOtherTerminalSeq], otherTerminalSeq]
ELSE
TryOneSyntheticLR1Item[[candidateLR0Item, singletonEmptyTerminalSeq], emptyTerminalSeq];
END;
seeOneLR1Item: PROC[candidateLR1Item: LR1Item] =
BEGIN
candidateLR1ItemIsIn: BOOLEAN ← FALSE;
seeOneClosureSubset: PROC[closureSubset: LR1ItemSubset] =
BEGIN
seeOneTerminalSeq: PROC[ts: TerminalSeq] =
BEGIN
IF candidateLR1ItemIsIn THEN RETURN;
IF ts = conflictingItem.terminalSeq THEN
BEGIN
IF tentativeLR1KernelSet = NIL THEN
tentativeLR1KernelSet ← CreateEmptyLR1ItemSet[grammar];
[] ← InsertItemInLR1ItemSet[tentativeLR1KernelSet, candidateLR1Item];
candidateLR1ItemIsIn ← TRUE;
END;
END;
IF candidateLR1ItemIsIn THEN RETURN;
IF closureSubset.lr0Item # conflictingItem.lr0Item THEN RETURN;
GenTerminalSeqsFromSet[closureSubset.terminals, seeOneTerminalSeq];
END;
GenCloseOfLR1Item[grammar, candidateLR1Item, seeOneClosureSubset];
END;
-- first, we see if we can put in a pure LR0Item that represents all LR1 items with the same terminalSeq
GenItemsInLR0ItemSet[initialBaseInfo.LR0Set, seeOneLR0Item];
-- now we try individual LR1 items
GenerateItemsFromLR1ItemSet[initialBaseInfo.LALR1set, seeOneLR1Item];
-- and we build the node
IF (initialConflictNodeForConflictingItem ← BuildOneConflictGraphNode[initialBaseInfoNode, tentativeLR1KernelSet, tentativeLR0KernelSet]) = NIL THEN ERROR;
END;
-- now we process stage1 nodes until there are no more, adding nodes as needed
FOR stage1Node: Node ← GetAnyStage1Node[conflictGraph],
GetAnyStage1Node[conflictGraph]
WHILE stage1Node # NIL DO
stage1NodeInfo: ConflictGraphNodeInfo ← NARROW[GetAssociatedSet[stage1Node]];
stage1BaseInfo: BaseNodeInfo ← NARROW[GetAssociatedSet[GetBaseNode[stage1Node]]];
FOR prevBaseInfoNodes: LIST OF Node ← stage1BaseInfo.predecessors, prevBaseInfoNodes.rest WHILE prevBaseInfoNodes # NIL DO
prevBaseInfoNode: Node ← prevBaseInfoNodes.first;
prevBaseInfo: BaseNodeInfo ← NARROW[GetAssociatedSet[prevBaseInfoNode]];
tentativeLR1KernelSet: LR1ItemSet ← NIL;
tentativeLR0KernelSet: TentativeLR0ItemSet ← NIL;
-- first we see if we shold make entries in tentativeLR0KernelSet, that is, if arbitrary LR1 items with the same core lead to items in the stage1 node. There are two cases, either "GoTo0" of an LR0 item leads to an LR0 item in the stage one node, or "GoTo1" of an "arbitrary" LR1 item (constructed from an lr0 item) leads to some LR1 item in the stage1 node.
-- here we tackle the first case: "GoTo0" of an LR0 item leads to an LR0 item in the stage one node.
BEGIN
seeOneLr0Item: PROC[item: LR0Item] =
BEGIN
lr0ItemIsIn: BOOLEAN ← FALSE;
seeOneKernelGoToItem: PROC[s: Symbol, goToItem: LR0Item] =
BEGIN
IF lr0ItemIsIn OR s # stage1BaseInfo.symbol THEN RETURN;
IF stage1NodeInfo.lr0KernelSet # NIL AND TestIfLR0ItemInSet[goToItem, stage1NodeInfo.lr0KernelSet] THEN
BEGIN
IF tentativeLR0KernelSet = NIL THEN
tentativeLR0KernelSet ← CreateEmptyTentativeLR0ItemSet[grammar];
[] ← InsertItemInTentativeLR0ItemSet[tentativeLR0KernelSet, item];
lr0ItemIsIn ← TRUE;
END;
END;
seeOneClosureItem: PROC[closureItem: LR0Item] =
{GenKernelGoTo0Items[closureItem, seeOneKernelGoToItem]};
GenClose0Items[item, seeOneClosureItem];
END;
GenItemsInLR0ItemSet[prevBaseInfo.LR0Set, seeOneLr0Item];
END;
-- and now the second case: "GoTo1" of an "arbitrary" LR1 item (constructed from an lr0 item) leads to some LR1 item in the stage1 node. The scheme is to generate the goto1 items from some specific lr1item and if there is a resulting terminal seq that wasn't the terminal seq of the trial item then "arbitrary" items will also generate the observed item. We need only try for two trial items.
BEGIN
seeOneLr0Item: PROC[lr0Item: LR0Item] =
BEGIN
lr0ItemIsIn: BOOLEAN ← FALSE;
TryOneItem: PROC[trialItemSubset: LR1ItemSubset, trialItemSeq: TerminalSeq] =
BEGIN
seeOneGoToSubset: PROC[s: Symbol, goTo1Subset: LR1ItemSubset] =
BEGIN
-- now, we see if some element of goTo1Subset (whose follow terminalSeq is not the unique seq in trialItemSubset.terminals) is in stage1NodeInfo.lr1KernelSet
seeOneTargetSubset: PROC[tSubset: LR1ItemSubset] =
BEGIN
seeOneTerminalSeq: PROC[tseq: TerminalSeq] =
BEGIN
IF lr0ItemIsIn THEN RETURN;
IF tseq = trialItemSeq THEN RETURN;
IF TestIfTerminalSeqInSet[tSubset.terminals, tseq] THEN
BEGIN -- this lr0 item passes muster
IF tentativeLR0KernelSet = NIL THEN
tentativeLR0KernelSet ← CreateEmptyTentativeLR0ItemSet[grammar];
[] ← InsertItemInTentativeLR0ItemSet[tentativeLR0KernelSet, lr0Item];
lr0ItemIsIn ← TRUE;
END;
END;
IF lr0ItemIsIn THEN RETURN;
IF tSubset.lr0Item # goTo1Subset.lr0Item THEN RETURN;
GenTerminalSeqsFromSet[goTo1Subset.terminals, seeOneTerminalSeq];
END;
IF lr0ItemIsIn THEN RETURN;
IF s # stage1BaseInfo.symbol THEN RETURN;
GenerateSubsetsFromLR1ItemSet[stage1NodeInfo.lr1KernelSet, seeOneTargetSubset];
END;
GenKernelGoTo1ItemSubsetsFromKernelItemSubset[trialItemSubset, seeOneGoToSubset];
END;
IF TestIfLR0ItemInTentativeSet[lr0Item, tentativeLR0KernelSet] THEN RETURN;
TryOneItem[[lr0Item, singletonEmptyTerminalSeq], emptyTerminalSeq];
IF lr0ItemIsIn THEN RETURN;
TryOneItem[[lr0Item, singletonOtherTerminalSeq], otherTerminalSeq];
END;
GenItemsInLR0ItemSet[prevBaseInfo.LR0Set, seeOneLr0Item];
END;
-- we look for specific lr1 items that should be in the set we are building
BEGIN
seeOneLR1Item: PROC[lr1Item: LR1Item] =
BEGIN
lr1ItemIsIn: BOOLEAN ← FALSE;
seeOneGenSubset: PROC[s: Symbol, subset: LR1ItemSubset] =
BEGIN
seeOneTargetSubset: PROC[tSubset: LR1ItemSubset] =
BEGIN
IF lr1ItemIsIn THEN RETURN;
IF tSubset.lr0Item # subset.lr0Item THEN RETURN;
IF TestNonEmptyIntersection[subset.terminals, tSubset.terminals] THEN
BEGIN
IF tentativeLR1KernelSet = NIL THEN
tentativeLR1KernelSet ← CreateEmptyLR1ItemSet[grammar];
[] ← InsertItemInLR1ItemSet[tentativeLR1KernelSet, lr1Item];
lr1ItemIsIn ← TRUE;
END;
END;
IF lr1ItemIsIn THEN RETURN;
IF s # stage1BaseInfo.symbol THEN RETURN;
GenerateSubsetsFromLR1ItemSet[stage1NodeInfo.lr1KernelSet, seeOneTargetSubset];
END;
IF TestIfLR0ItemInTentativeSet[lr1Item.lr0Item, tentativeLR0KernelSet] THEN RETURN;
GenGoTo1KernelSubsetsFromKernelItem[grammar, lr1Item, seeOneGenSubset];
END;
GenerateItemsFromLR1ItemSet[prevBaseInfo.LALR1set, seeOneLR1Item];
END;
-- now, if at least one of the sets is non empty, check to see if we have already built a node that satisfies the requirements, or build one.
BEGIN
node: Node ← BuildOneConflictGraphNode[prevBaseInfoNode, tentativeLR1KernelSet, tentativeLR0KernelSet];
IF node # NIL THEN
stage1NodeInfo.prevNodes ← CONS[node, stage1NodeInfo.prevNodes];
END;
ENDLOOP;
MarkAsStage2[stage1Node];
ENDLOOP;
END;
BaseNodeInfo: TYPE = REF BaseNodeInfoBody;
BaseNodeInfoBody: TYPE = RECORD[
predecessors: LIST OF Node ← NIL,
symbol: Symbol ← NIL,
LALR1set: LR1ItemSet ← NIL,
LR0Set: LR0ItemSet ← NIL,
kernelGraphNodeChain: ConflictGraphNodeInfo ← NIL];
BuildBaseInfoGraph: PROC[baseGraph: Graph] RETURNS[Graph] =
BEGIN
baseStart: Node ← GetStartNode[baseGraph];
grammar: Grammar ← GetGrammar[baseGraph];
newGraph: Graph ← CreateEmptyGraph[grammar, LALR1]; -- LALR1 because there is no good class name at the moment
CreateOneNewNode: PROC[baseNode: Node] RETURNS[--continue--BOOLEAN] =
BEGIN
info: BaseNodeInfo ← NEW[BaseNodeInfoBody];
newNode: Node ← CreateTentativeStage1Node[newGraph, info, baseNode];
InstallStage1Node[newNode, baseNode=baseStart];
SetUpperNode[baseNode, newNode];
info.LALR1set ← NarrowLR1ItemSet[GetAssociatedSet[baseNode]];
info.LR0Set ← NarrowLR0ItemSet[GetAssociatedSet[GetBaseNode[baseNode]]];
RETURN[TRUE];
END;
-- first clean up any set associations
ClearLR1ItemSetsAssociatedNodes[grammar];
ClearAllUpperNodePointers[baseGraph];
-- next, we copy the structure of the given LR0Parser graph
GenerateAllNodes[baseGraph, CreateOneNewNode];
FOR stage1Node: Node ← GetAnyStage1Node[newGraph],
GetAnyStage1Node[newGraph]
WHILE stage1Node # NIL DO
baseSourceNode: Node ← GetBaseNode[stage1Node];
InstallNewArc: PROC[s: Symbol, baseArcTarget: Node]RETURNS[--continue-- BOOLEAN] =
BEGIN
target: Node ← GetUpperNode[baseArcTarget];
targetInfo: BaseNodeInfo ← NARROW[GetAssociatedSet[target]];
IF GetBaseNode[target] # baseArcTarget THEN ERROR;
IF targetInfo.symbol # NIL AND targetInfo.symbol # s THEN ERROR;
targetInfo.symbol ← s;
AppendAnArc[stage1Node, s, target];
targetInfo.predecessors ← CONS[stage1Node, targetInfo.predecessors];
RETURN[TRUE];
END;
GenerateArcs[baseSourceNode, InstallNewArc];
MarkAsStage2[stage1Node];
ENDLOOP;
RETURN[newGraph];
END;
following code builds the graph of accessable pairs
ConflictPair: TYPE = REF ConflictPairBody;
ConflictPairBody: TYPE = RECORD[
a, b: ConflictGraphNodeInfo];
AnUnresolvableConflict: SIGNAL = CODE;
VisitAccessableConflictPairs: PROC[grammar: Grammar, showOn: IO.STREAM, itemA: LR1Item, nodeA: Node, itemB: LR1Item, nodeB: Node] =
BEGIN
firstPair: ConflictPair ← NEW[ConflictPairBody←[NARROW[GetAssociatedSet[nodeA]], NARROW[GetAssociatedSet[nodeB]]]];
visitedPairs: HashTable.Table ← HashTable.Create[equal: EqualPairs, hash: PairHash];
nEqualPairs: INT ← 0;
nDifPairs: INT ← 0;
conflicts: LIST OF LIST OF ConflictPair ← NIL;
NoShow: PROC[tail: LIST OF ConflictPair] RETURNS[LIST OF ConflictPair] = {RETURN[tail]};
VisitPair: PROC[pair: ConflictPair, showChain: PROC[LIST OF ConflictPair] RETURNS[LIST OF ConflictPair]] =
BEGIN
ShowChain: PROC[tail: LIST OF ConflictPair] RETURNS[LIST OF ConflictPair] =
BEGIN
IF debug THEN ShowPair[showOn, pair];
RETURN[showChain[CONS[pair,tail]]];
END;
UnresolvableConflict: PROC =
BEGIN
IO.PutF[showOn, "\N\N\NAn unresolvable conflict\N"];
IO.PutF[showOn, "between "];
ShowLR1Item[showOn, 0, itemA];
IO.PutF[showOn, "\N and "];
ShowLR1Item[showOn, 0, itemB];
IO.PutF[showOn, "\N\N"];
conflicts ← CONS[ShowChain[NIL], conflicts];
SignalUnresolvableConflict[];
END;
IF HashTable.Insert[visitedPairs, pair, pair] THEN
BEGIN
MarkNodeToSplit[GetBaseNode[GetBaseNode[pair.a.node]]];
IF pair.a = pair.b THEN
BEGIN
nEqualPairs ← nEqualPairs + 1;
IF pair.a.root THEN UnresolvableConflict[]
ELSE
BEGIN
FOR prevAs: LIST OF Node ← pair.a.prevNodes, prevAs.rest WHILE prevAs # NIL DO
prevA: Node ← prevAs.first;
prevAInfo: ConflictGraphNodeInfo ← NARROW[GetAssociatedSet[prevA]];
VisitPair[NEW[ConflictPairBody←[prevAInfo, prevAInfo]], ShowChain];
ENDLOOP;
END;
END
ELSE
BEGIN
nDifPairs ← nDifPairs + 1;
IF pair.a.root AND pair.b.root THEN UnresolvableConflict[]
ELSE
FOR prevAs: LIST OF Node ← pair.a.prevNodes, prevAs.rest WHILE prevAs # NIL DO
prevA: Node ← prevAs.first;
prevAInfo: ConflictGraphNodeInfo ← NARROW[GetAssociatedSet[prevA]];
prevABase: Node ← GetBaseNode[prevA];
FOR prevBs: LIST OF Node ← pair.b.prevNodes, prevBs.rest WHILE prevBs # NIL DO
prevB: Node ← prevBs.first;
prevBInfo: ConflictGraphNodeInfo ← NARROW[GetAssociatedSet[prevB]];
prevBBase: Node ← GetBaseNode[prevB];
IF prevABase = prevBBase THEN
VisitPair[NEW[ConflictPairBody←[prevAInfo, prevBInfo]], ShowChain];
ENDLOOP;
ENDLOOP;
END;
END;
END;
VisitPair[firstPair, NoShow];
IF debug THEN IO.PutF[showOn, "\Nvisited %g pairs of unequals, and %g pairs of equals\N", IO.int[nDifPairs], IO.int[nEqualPairs]];
IF conflicts # NIL THEN
BEGIN -- lets see if we can print more details
FOR someConflicts: LIST OF LIST OF ConflictPair ← conflicts, someConflicts.rest WHILE someConflicts # NIL DO
ShowConflictList[grammar, showOn, itemA, itemB, someConflicts.first];
ENDLOOP;
END;
END;
It is assumed that itemA and itemB are conflicting lr1 items at some node. list is a seq of conflict pairs (i.e. pairs of nodes from the conflict graph with the same underlying LR0 node) reached along the same path in the lr0 graph. Here we compute two sequences of productions, one for itemA and one for itemB, that reproduces the common path in the lr0 graph.
ShowConflictList: PROC[grammar: Grammar, on: IO.STREAM, itemA, itemB: LR1Item, list: LIST OF ConflictPair] =
BEGIN
targetA: LIST OF Precursor ← NIL;
targetB: LIST OF Precursor ← NIL;
precListA: LIST OF Precursor ← NIL;
precListB: LIST OF Precursor ← NIL;
ConcatTruncatedPrecList: PROC[a, b: LIST OF Precursor] RETURNS[LIST OF Precursor] =
{IF a.rest = NIL THEN RETURN[b] ELSE RETURN[CONS[a.first, ConcatTruncatedPrecList[a.rest, b]]]};
we first find kernel items in the final LALR(1) nodes from which the conflicting items are reached by a closure operation, and construct the lists of LR1 items related by close(1) operations.
BEGIN
TestItemA: PROC[candidate: Precursor] RETURNS[BOOLEAN] =
{RETURN[candidate = [lr1[itemA]]]};
TestItemB: PROC[candidate: Precursor] RETURNS[BOOLEAN] =
{RETURN[candidate = [lr1[itemB]]]};
listA: LIST OF Precursor ← FindPrecursors[grammar, list.first.a.lr0KernelSet, list.first.a.lr1KernelSet, TestItemA];
listB: LIST OF Precursor ← FindPrecursors[grammar, list.first.b.lr0KernelSet, list.first.b.lr1KernelSet, TestItemB];
--PrintPrecursorList[on, listA];
--PrintPrecursorList[on, listB];
targetA ← listA;
targetB ← listB;
precListA ← listA;
precListB ← listB;
END;
Now we iterate back through the graph. At each step, targetA and targetB are kernel items in a single LALR1 node. The goal is to find corresponding kernel items in the precursor node from which targetA and targetB can be reached by a series of closure operations followed by a single GOTO1 operation. (This differs from the computation above in that there was no final GOTO1 step.) We also attempt to replace LR1 items by LR0 items as soon as possible.
FOR pairs: LIST OF ConflictPair ← list.rest, pairs.rest WHILE pairs # NIL DO
TestItemA: PROC[candidate: Precursor] RETURNS[BOOLEAN] =
BEGIN
WITH candidate SELECT FROM
c: lr0 Precursor =>
WITH targetA.first SELECT FROM
t: lr0 Precursor => RETURN[t.item = GetNextLR0Item[c.item]];
t: lr1 Precursor => RETURN[FALSE];
ENDCASE => ERROR;
c: lr1 Precursor =>
WITH targetA.first SELECT FROM
t: lr0 Precursor => RETURN[FALSE];
t: lr1 Precursor =>
RETURN[t.item.lr0Item = GetNextLR0Item[c.item.lr0Item] AND t.item.terminalSeq = c.item.terminalSeq];
ENDCASE => ERROR;
ENDCASE => ERROR;
END;
TestItemB: PROC[candidate: Precursor] RETURNS[BOOLEAN] =
BEGIN
WITH candidate SELECT FROM
c: lr0 Precursor =>
WITH targetB.first SELECT FROM
t: lr0 Precursor => RETURN[t.item = GetNextLR0Item[c.item]];
t: lr1 Precursor => RETURN[FALSE];
ENDCASE => ERROR;
c: lr1 Precursor =>
WITH targetB.first SELECT FROM
t: lr0 Precursor => RETURN[FALSE];
t: lr1 Precursor =>
RETURN[t.item.lr0Item = GetNextLR0Item[c.item.lr0Item] AND t.item.terminalSeq = c.item.terminalSeq];
ENDCASE => ERROR;
ENDCASE => ERROR;
END;
listA: LIST OF Precursor ← FindPrecursors[grammar, pairs.first.a.lr0KernelSet, pairs.first.a.lr1KernelSet, TestItemA];
listB: LIST OF Precursor ← FindPrecursors[grammar, pairs.first.b.lr0KernelSet, pairs.first.b.lr1KernelSet, TestItemB];
--PrintPrecursorList[on, listA];
--PrintPrecursorList[on, listB];
targetA ← listA;
targetB ← listB;
precListA ← ConcatTruncatedPrecList[listA, precListA];
precListB ← ConcatTruncatedPrecList[listB, precListB];
ENDLOOP;
ShowLR1Item[on, 0, itemA];
IO.PutF[on, "\N\Tcan be reached by\N\N"];
PrintPrecursorList[on, precListA];
IO.PutF[on, "\Nand \N"];
ShowLR1Item[on, 0, itemB];
IO.PutF[on, "\N\Tcan be reached by along the same path by\N\N"];
PrintPrecursorList[on, precListB];
IO.PutF[on, "\N\N\N"];
END;
ShowPair: PROC[on: IO.STREAM, pair: ConflictPair] =
BEGIN
IO.PutF[on, "one conflicting pair\N"];
ShowConflictNode[on, pair.a];
ShowConflictNode[on, pair.b];
END;
ShowConflictNode: PROC[on: IO.STREAM, info: ConflictGraphNodeInfo] =
BEGIN
IF info.lr1KernelSet = NIL THEN IO.PutF[on, " no lr1 items\N"]
ELSE
BEGIN
IO.PutF[on, " lr1 items = \N"];
ShowLR1ItemSet[on, 10, info.lr1KernelSet];
IO.PutF[on, "\N"];
END;
IF info.lr0KernelSet = NIL THEN IO.PutF[on, " no lr0 items\N"]
ELSE
BEGIN
IO.PutF[on, " lr0 items = \N"];
ShowLR0ItemSet[on, 10, info.lr0KernelSet];
IO.PutF[on, "\N"];
END;
IO.PutF[on, "\N"];
END;
EqualPairs: PROC[a, b: REF ANY] RETURNS[BOOLEAN] =
BEGIN
pairA: ConflictPair ← NARROW[a];
pairB: ConflictPair ← NARROW[b];
RETURN[pairA.a = pairB.a AND pairA.b = pairB.b];
END;
PairHash: PROC[a: REF ANY] RETURNS[CARDINAL] =
BEGIN
pairA: ConflictPair ← NARROW[a];
lna: Basics.LongNumber ← [lp[LOOPHOLE[pairA.a]]];
lnb: Basics.LongNumber ← [lp[LOOPHOLE[pairA.b]]];
RETURN[lna.lo+lna.hi+lnb.lo+lnb.hi];
END;
Precursor: TYPE = RECORD[
SELECT case: * FROM
lr0 => [item: LR0Item],
lr1 => [item: LR1Item],
ENDCASE];
FindPrecursors: PROC[grammar: Grammar, lr0KernelSet: LR0ItemSet, lr1KernelSet: LR1ItemSet, testOne: PROC[candidateImmediatePrecursor: Precursor] RETURNS[BOOLEAN]] RETURNS[LIST OF Precursor] =
BEGIN
visitedLR1Items: LR1ItemSet ← CreateEmptyLR1ItemSet[grammar];
visitedLR0Items: TentativeLR0ItemSet ← CreateEmptyTentativeLR0ItemSet[grammar];
returnChain: LIST OF Precursor ← NIL;
found: BOOLEAN ← FALSE; -- initial
SeeKernelLR0Item: PROC[kernelLR0Item: LR0Item] =
{IF NOT found THEN [] ← ExploreFromLR0Item[kernelLR0Item]};
ExploreFromLR0Item: PROC[lr0Item: LR0Item] RETURNS[--stopGeneration-- BOOLEAN] =
BEGIN
IF found THEN RETURN[TRUE];
IF InsertItemInTentativeLR0ItemSet[visitedLR0Items, lr0Item] THEN
BEGIN -- we havn't seen this one before
IF testOne[[lr0[lr0Item]]] THEN -- we now have the immediate precursor
BEGIN
found ← TRUE;
returnChain ← LIST[[lr0[lr0Item]]];
RETURN[TRUE]
END
ELSE
BEGIN
SeeItemWithEmptySeq: PROC[LR1Item] = {NULL};
GenOneSimpleLR0LR0CloseStep[lr0Item, ExploreFromLR0Item];
IF NOT found THEN BasicGenOneSimpleLR0LR1CloseStep[lr0Item, ExploreFromLR1Item, SeeItemWithEmptySeq];
IF found THEN -- this one belongs in the chain
BEGIN
returnChain ← CONS[[lr0[lr0Item]], returnChain];
RETURN[TRUE];
END;
END;
END;
RETURN[FALSE];
END;
SeeKernelLR1Item: PROC[kernelLR1Item: LR1Item] =
{IF NOT found THEN [] ← ExploreFromLR1Item[kernelLR1Item]};
ExploreFromLR1Item: PROC[lr1Item: LR1Item] RETURNS[--stopGeneration-- BOOLEAN] =
BEGIN
IF found THEN RETURN[TRUE];
IF InsertItemInLR1ItemSet[visitedLR1Items, lr1Item] THEN
BEGIN -- we havn't seen this one before
IF testOne[[lr1[lr1Item]]] THEN -- we now have the immediate precursor
BEGIN
found ← TRUE;
returnChain ← LIST[[lr1[lr1Item]]];
RETURN[TRUE]
END
ELSE
BEGIN
GenOneSimpleLR1LR1CloseStep[lr1Item, ExploreFromLR1Item];
IF found THEN -- this one belongs in the chain
BEGIN
returnChain ← CONS[[lr1[lr1Item]], returnChain];
RETURN[TRUE];
END;
END;
END;
RETURN[FALSE];
END;
IF lr0KernelSet # NIL THEN GenItemsInLR0ItemSet[lr0KernelSet, SeeKernelLR0Item];
IF found THEN RETURN[returnChain];
IF lr1KernelSet # NIL THEN GenerateItemsFromLR1ItemSet[lr1KernelSet, SeeKernelLR1Item];
IF found THEN RETURN[returnChain];
ERROR;
END;
TestIfLR0ItemInSet: PROC[item: LR0Item, set: LR0ItemSet] RETURNS[BOOLEAN]=
BEGIN
found: BOOLEAN ← FALSE;
seeOneItem: PROC[setItem: LR0Item] =
{IF setItem = item THEN found ← TRUE};
GenItemsInLR0ItemSet[set, seeOneItem];
RETURN[found];
END;
TestIfLR0ItemInTentativeSet: PROC[item: LR0Item, set: TentativeLR0ItemSet] RETURNS[BOOLEAN]=
BEGIN
found: BOOLEAN ← FALSE;
seeOneItem: PROC[setItem: LR0Item] =
{IF setItem = item THEN found ← TRUE};
IF set = NIL THEN RETURN[FALSE];
GenItemsInTentativeLR0ItemSet[set, seeOneItem];
RETURN[found];
END;
TestIfLR1ItemInSet: PROC[item: LR1Item, set: LR1ItemSet] RETURNS[BOOLEAN] =
BEGIN
yes: BOOLEAN ← FALSE; -- tentative
seeOneSubset: PROC[subset: LR1ItemSubset] =
BEGIN
IF item.lr0Item # subset.lr0Item THEN RETURN;
IF TestIfTerminalSeqInSet[subset.terminals, item.terminalSeq] THEN yes ← TRUE;
END;
IF set # NIL THEN GenerateSubsetsFromLR1ItemSet[set, seeOneSubset, TRUE];
RETURN[yes];
END;
GenGoTo1KernelSubsetsFromKernelItem: PROC[grammar: Grammar, kernelItem: LR1Item, for: PROC[Symbol, LR1ItemSubset]] =
BEGIN
kernelItemTermSeqSet: TerminalSeqSet ← CreateEmptyTerminalSeqSet[grammar];
[] ← InsertTerminalSeqInSet[kernelItemTermSeqSet, kernelItem.terminalSeq];
[kernelItemTermSeqSet, ] ← FreezeTerminalSeqSet[kernelItemTermSeqSet];
GenKernelGoTo1ItemSubsetsFromKernelItemSubset[[kernelItem.lr0Item, kernelItemTermSeqSet], for];
END;
GenCloseOfLR1Item: PROC[grammar: Grammar, item: LR1Item, for: PROC[LR1ItemSubset]] =
BEGIN
itemTermSeqSet: TerminalSeqSet ← CreateEmptyTerminalSeqSet[grammar];
[] ← InsertTerminalSeqInSet[itemTermSeqSet, item.terminalSeq];
[itemTermSeqSet, ] ← FreezeTerminalSeqSet[itemTermSeqSet];
GenCloseOfLR1ItemSubset[[item.lr0Item, itemTermSeqSet], for];
END;
GenOneSimpleLR1LR1CloseStep: PROC[lr1Item: LR1Item, for: PROC[LR1Item] RETURNS[--stop-- BOOLEAN]] =
BEGIN
SeeItemWithEmptySeq: PROC[closureItem: LR1Item] =
{[] ← for[[closureItem.lr0Item, lr1Item.terminalSeq]]};
BasicGenOneSimpleLR0LR1CloseStep[lr1Item.lr0Item, for, SeeItemWithEmptySeq];
END;
A generated LR1 item with the empty terminal sequence must be treated specially by the client
This code is adapted from LR1ItemsImpl.GenOneCloseStep, at some future time they should be combined.
BasicGenOneSimpleLR0LR1CloseStep: PROC[lr0Item: LR0Item, for: PROC[LR1Item]RETURNS[--stop-- BOOLEAN], seeItemWithEmptySeq: PROC[LR1Item]] =
BEGIN
grammar: Grammar ← GetGrammarFromLR0Item[lr0Item];
emptySeq: TerminalSeq ← GetEmptyTerminalSeq[grammar];
terminalSet: TerminalSeqSet ← CreateEmptyTerminalSeqSet[grammar];
emptySeqOccurs: BOOLEAN;
-- first, build the terminal set that will follow each LR0 Item in the closure
BEGIN
remainder: LR0Item ← GetNextLR0Item[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;
emptySeqOccurs ← emptyInPrev;
END;
-- again, check for empty closure
IF TestIfTerminalSeqSetEmpty[terminalSet] AND NOT emptySeqOccurs THEN RETURN;
-- now generate the lr0 items for the closure, then generate the terminals.
BEGIN
stop: BOOLEAN ← FALSE; -- tentative
HandleOneLR0ClosureItem: PROC[closureItem: LR0Item] RETURNS[--stop-- BOOLEAN] =
BEGIN
HandleOneTerminalSeq: PROC[ts: TerminalSeq] =
{IF NOT stop AND for[[closureItem, ts]] THEN stop ← TRUE};
IF NOT stop THEN GenTerminalSeqsFromSet[terminalSet, HandleOneTerminalSeq];
IF stop THEN RETURN[TRUE];
IF emptySeqOccurs THEN seeItemWithEmptySeq[[closureItem, emptySeq]];
RETURN[FALSE];
END;
GenOneSimpleLR0LR0CloseStep[lr0Item, HandleOneLR0ClosureItem];
END;
END;
This code does the same thing as LR0ItemsImpl.GenOneLR0CloseStep
GenOneSimpleLR0LR0CloseStep: PROC[lr0Item: LR0Item, for: PROC[LR0Item] RETURNS[--stop-- BOOLEAN]] =
BEGIN
leftSide: Symbol ← GetFirstSymbol[lr0Item]; -- the first symbol after the "dot"
stop: BOOLEAN ← FALSE; -- tentative
HandleOneProduction: PROC[production: Production] =
{IF NOT stop AND for[GetFirstLR0Item[production]] THEN stop ← TRUE};
IF leftSide = NIL THEN RETURN;
GenProductionsForSymbol[leftSide, HandleOneProduction];
END;
GenElementsOfLR1ItemSubset: PROC[subset: LR1ItemSubset, for: PROC[LR1Item]] =
BEGIN
SeeOneTerminalSeq: PROC[ts: TerminalSeq] =
{for[[subset.lr0Item, ts]]};
GenTerminalSeqsFromSet[subset.terminals, SeeOneTerminalSeq];
END;
GenGoTo0KernelItemsFromKernelItem: PROC[kernelItem: LR0Item, for: PROC[Symbol, LR0Item]] =
BEGIN
seeCloseItem: PROC[closeItem: LR0Item] =
{GenKernelGoTo0Items[closeItem, for]};
GenClose0Items[kernelItem, seeCloseItem];
END;
DescribeConflictGraph: PROC[on: IO.STREAM, conflictGraph: Graph] =
BEGIN
nNodes: INT ← 0;
nLR0Items: INT ← 0;
nLR1Items: INT ← 0;
nRootNodes: INT ← 0;
seeOneNode: PROC[pnode: Node] RETURNS[BOOLEAN] =
BEGIN
info: ConflictGraphNodeInfo ← NARROW[GetAssociatedSet[pnode]];
seeOneLR1Item: PROC[item: LR1Item] =
{nLR1Items ← nLR1Items + 1};
seeOneLR0Item: PROC[item: LR0Item] =
{nLR0Items ← nLR0Items + 1};
IF info # NIL THEN
BEGIN
IF info.lr1KernelSet # NIL THEN GenerateItemsFromLR1ItemSet[info.lr1KernelSet, seeOneLR1Item];
IF info.lr0KernelSet # NIL THEN GenItemsInLR0ItemSet[info.lr0KernelSet, seeOneLR0Item];
nNodes ← nNodes + 1;
IF info.root THEN
BEGIN
nRootNodes ← nRootNodes + 1;
IO.PutF[on, "\NThis conflict graph contains a root node\N"];
ShowConflictNode[on, info];
END;
END;
RETURN[TRUE];
END;
GenerateAllNodes[conflictGraph, seeOneNode];
IO.PutF[on, "\Nthere are %g nodes containing a total of %g lr0 items, a total of %g lr1 items, and %g of the nodes are root nodes\N", IO.int[nNodes], IO.int[nLR0Items], IO.int[nLR1Items], IO.int[nRootNodes]];
END;
PrintPrecursorList: PROC[on: IO.STREAM, list: LIST OF Precursor] =
BEGIN
FOR items: LIST OF Precursor ← list, items.rest WHILE items # NIL DO
WITH items.first SELECT FROM
i: lr0 Precursor => ShowLR0Item[on, 5, i.item];
i: lr1 Precursor => ShowLR1Item[on, 5, i.item];
ENDCASE => ERROR;
IO.PutF[on, "\N"];
ENDLOOP;
END;
END.