BEGIN OPEN GrammarBasic, ParserGraphs;
Graph: TYPE = REF GraphBody;
GraphBody: PUBLIC TYPE = RECORD[
class: GraphClass,
grammar: Grammar,
start: Node ← NIL,
first: Node ← NIL,
firstStage1: Node ← NIL,
firstDirty: Node ← NIL,
indexed: BOOLEAN ← FALSE];
Node: TYPE = REF NodeBody;
NodeBody: PUBLIC TYPE = RECORD[
graph: Graph,
s: REF ANY,
index: CARDINAL ← 0, --used by print code
upper: Node ← NIL,
base: Node,
ring: CARDINAL ← LAST[CARDINAL],
split: BOOLEAN ← FALSE,
dirty: BOOLEAN ← FALSE,
arcs: Arc ← NIL,
recentArc: Arc ← NIL,
next: Node ← NIL,
stage: Stage ← stage1,
installed: BOOLEAN ← FALSE,
prevStage1, nextStage1: Node ← NIL,
nextDirty: Node ← NIL];
Stage: TYPE = {stage1, stage2};
Arc: TYPE = REF ArcBody;
ArcBody: TYPE = RECORD[
s: Symbol,
target: Node,
next: Arc];
-- interface procedures
CreateEmptyGraph: PUBLIC PROC[grammar: Grammar, class: GraphClass] RETURNS[Graph] =
BEGIN
graph: Graph ← NEW[GraphBody ← [class, grammar]];
RETURN[graph];
END;
GetGraphStats: PUBLIC PROC[g: Graph] RETURNS[nNodes, nArcs, nNodesMarkedToSplit: INT] =
BEGIN
SeeOneNode: PROC[n: Node] RETURNS[BOOLEAN] =
BEGIN
nNodes ← nNodes + 1;
IF n.split THEN nNodesMarkedToSplit ← nNodesMarkedToSplit + 1;
GenerateArcs[n, SeeOneArc];
RETURN[TRUE]
END;
SeeOneArc: PROC[s: Symbol, t: Node] RETURNS[BOOLEAN] =
{nArcs ← nArcs + 1; RETURN[TRUE]};
nNodes ← nArcs ← nNodesMarkedToSplit ← 0;
GenerateAllNodes[g, SeeOneNode];
END;
GetClass: PUBLIC PROC[graph: Graph] RETURNS[GraphClass] =
{RETURN[graph.class]};
GetGrammar: PUBLIC PROC[graph: Graph] RETURNS[Grammar] =
{RETURN[graph.grammar]};
GetStartNode: PUBLIC PROC[graph: Graph] RETURNS[Node] =
{RETURN[graph.start]};
GetAnyStage1Node: PUBLIC PROC[graph: Graph] RETURNS[Node] =
{RETURN[graph.firstStage1]};
GetAnyDirtyNode: PUBLIC PROC[graph: Graph] RETURNS[Node] =
BEGIN
dirty: Node ← graph.firstDirty;
IF dirty # NIL THEN
BEGIN
graph.firstDirty ← dirty.nextDirty;
dirty.nextDirty ← NIL;
dirty.dirty ← FALSE;
END;
RETURN[dirty];
END;
GenerateAllNodes: PUBLIC PROC[graph: Graph, viewNode: PROC[Node] RETURNS[--continue--BOOLEAN]] =
BEGIN -- nodes added during iteration will not be generated.
FOR node: Node ← graph.first, node.next WHILE node # NIL DO
IF NOT viewNode[node] THEN EXIT;
ENDLOOP;
END;
ClearAllUpperNodePointers: PUBLIC PROC[graph: Graph] =
BEGIN
FOR node: Node ← graph.first, node.next WHILE node # NIL DO
node.upper ← NIL;
ENDLOOP;
END;
IndexTheNodes: PUBLIC PROC[graph: Graph] =
BEGIN
nextIndex: CARDINAL ← 0;
IF graph.indexed THEN ERROR;
graph.indexed ← TRUE;
FOR node: Node ← graph.first, node.next WHILE node # NIL DO
node.index ← nextIndex;
nextIndex ← nextIndex+1;
ENDLOOP;
END;
CleanTheGraph: PUBLIC PROCEDURE[graph: Graph] RETURNS[Graph] =
BEGIN
nextNode: Node;
nextArc: Arc;
IF graph = NIL THEN RETURN[NIL];
FOR node: Node ← graph.first, nextNode WHILE node # NIL DO
nextNode ← node.next;
FOR arc: Arc ← node.arcs, nextArc WHILE arc # NIL DO
nextArc ← arc.next;
arc.target ← NIL;
arc.next ← NIL;
ENDLOOP;
node.graph ← NIL;
node.upper ← node.base ← node.next ← node.prevStage1 ← node.nextStage1 ← node.nextDirty ← NIL;
node.arcs ← node.recentArc ← NIL;
ENDLOOP;
RETURN[NIL];
END;
CreateTentativeStage1Node: PUBLIC PROC[g: Graph, s: REF ANY, base: Node] RETURNS[Node] =
BEGIN
newNode: Node ← NEW[NodeBody ← [graph: g, s: s, base: base, next: NIL, nextStage1: NIL]];
RETURN[newNode];
END;
InstallStage1Node: PUBLIC PROC[n: Node, startNode: BOOLEAN] =
BEGIN
g: Graph ← n.graph;
IF n.installed THEN RETURN;
n.installed ← TRUE;
n.nextStage1 ← g.firstStage1;
IF g.firstStage1 # NIL THEN g.firstStage1.prevStage1 ← n;
g.firstStage1 ← n;
n.next ← g.first;
g.first ← n;
IF startNode THEN
BEGIN
IF g.start # NIL THEN ERROR;
g.start ← n;
END;
END;
SetUpperNode: PUBLIC PROC[n: Node, upper: Node] =
BEGIN
IF n.upper # NIL THEN ERROR;
n.upper ← upper;
END;
SetRingNumber: PUBLIC PROC[n: Node, ring: CARDINAL] =
{n.ring ← ring};
AppendAnArc: PUBLIC PROC[source: Node, s: Symbol, target: Node] =
BEGIN
newArc: Arc;
IF source.recentArc # NIL AND source.recentArc.s = s THEN ERROR;
FOR a: Arc ← source.arcs, a.next WHILE a # NIL DO
IF a.s = s THEN ERROR;
ENDLOOP;
newArc ← NEW[ArcBody ← [s: s, target: target, next: source.arcs]];
source.arcs ← newArc;
END;
ResetArcTarget: PUBLIC PROC[source: Node, s: Symbol, newTarget: Node] =
BEGIN
IF source.recentArc = NIL OR source.recentArc.s # s THEN
FOR a: Arc ← source.arcs, a.next WHILE a # NIL DO
IF a.s = s THEN {source.recentArc ← a; EXIT};
ENDLOOP;
IF source.recentArc = NIL THEN ERROR;
source.recentArc.target ← newTarget;
END;
SetAssociatedSet: PUBLIC PROC[node: Node, s: REF ANY, oldValue: REF ANY] =
BEGIN
IF node.s # oldValue THEN ERROR;
node.s ← s;
END;
MarkAsStage2: PUBLIC PROC[node: Node] =
BEGIN
IF NOT node.stage = stage1 THEN ERROR;
node.stage ← stage2;
IF node.prevStage1 # NIL THEN node.prevStage1.nextStage1 ← node.nextStage1 ELSE node.graph.firstStage1 ← node.nextStage1;
IF node.nextStage1 # NIL THEN node.nextStage1.prevStage1 ← node.prevStage1;
node.prevStage1 ← node.nextStage1 ← NIL;
END;
MarkNodeDirty: PUBLIC PROC[node: Node] =
BEGIN
IF node.dirty THEN RETURN;
node.dirty ← TRUE;
node.nextDirty ← node.graph.firstDirty;
node.graph.firstDirty ← node;
END;
MarkNodeToSplit: PUBLIC PROC[node: Node] =
{node.split ← TRUE};
SetNodeIndex: PUBLIC PROC[node: Node, x: CARDINAL] =
{node.index ← x};
GetGraph: PUBLIC PROC[node: Node] RETURNS[Graph] =
{RETURN[node.graph]};
GenerateArcs: PUBLIC PROC[node: Node, p: PROC[Symbol, Node] RETURNS[--continue-- BOOLEAN]] =
BEGIN
FOR a: Arc ← node.arcs, a.next WHILE a # NIL DO
IF NOT p[a.s, a.target] THEN EXIT;
ENDLOOP;
END;
FollowSymbol: PUBLIC PROC[node: Node, s: Symbol] RETURNS[Node] =
BEGIN
IF node.recentArc # NIL AND node.recentArc.s = s THEN RETURN[node.recentArc.target];
FOR a: Arc ← node.arcs, a.next WHILE a # NIL DO
IF a.s = s THEN
BEGIN
node.recentArc ← a;
RETURN[a.target];
END;
ENDLOOP;
RETURN[NIL];
END;
GetAssociatedSet: PUBLIC PROC[node: Node] RETURNS[REF ANY] =
{RETURN[node.s]};
GetBaseNode: PUBLIC PROC[node: Node] RETURNS[Node] =
{RETURN[node.base]};
GetUpperNode: PUBLIC PROC[node: Node] RETURNS[Node] =
{RETURN[node.upper]};
GetRingNumber: PUBLIC PROC[node: Node] RETURNS[CARDINAL] =
{RETURN[node.ring]};
GetSplittingMark: PUBLIC PROC[node: Node] RETURNS[BOOLEAN] =
{RETURN[node.split]};
NarrowNode: PUBLIC PROC[ref: REF ANY] RETURNS[Node] =
{RETURN[NARROW[ref]]};
GetNodeIndex: PUBLIC PROC[node: Node] RETURNS[CARDINAL] =
{RETURN[node.index]};
END..