MODULE; IMPORT NFA; IMPORT NFANode; IMPORT NFANodeList; IMPORT NFANodeListF; IMPORT NFANodeListSort; IMPORT Word; IMPORT Fmt,Term,Text; REVEAL T = BRANDED REF RECORD s: NFANodeList.T := NIL; out: INTEGER := NFANode.NoOutput; markedNodes: NFANodeList.T := NIL; END; PROCEDURE NFAState DeleteRedundant (s: NFANodeList.T) = VAR cur := s; BEGIN WHILE cur # NIL DO WHILE cur.tail # NIL AND cur.head = cur.tail.head DO cur.tail := cur.tail.tail; END; cur := cur.tail; END; END DeleteRedundant; PROCEDUREUnmarkNodes (nodes: NFANodeList.T) = VAR cur := nodes; BEGIN WHILE cur # NIL DO <* ASSERT cur.head.marked *> cur.head.marked := FALSE; cur := cur.tail; END; END UnmarkNodes; PROCEDURECanonical (s: T) = BEGIN IF s.s # NIL THEN s.s := NFANodeListSort.SortD(s.s); DeleteRedundant(s.s); END; UnmarkNodes(s.markedNodes); s.markedNodes := NIL; END Canonical; PROCEDUREAddNodeChasingEpsilons (s: T; node: NFANode.T) = BEGIN IF node = NIL OR node.marked THEN ELSIF node.keyBegin = NFANode.Epsilon THEN node.marked := TRUE; s.markedNodes := NFANodeList.Cons(node, s.markedNodes); AddNodeChasingEpsilons(s, node.targ1); AddNodeChasingEpsilons(s, node.targ2); s.out := MIN(s.out, node.output);
IF s.out # NFANode.NoOutput THEN
Term.WrLn(NFAState outputs
& Fmt.Int(s.out));
END;
ELSE s.s := NFANodeList.Cons(node, s.s); END; END AddNodeChasingEpsilons; PROCEDURENew (n: NFA.T): T = VAR result := NEW(T); BEGIN AddNodeChasingEpsilons(result, n.start); Canonical(result); RETURN result; END New; PROCEDUREStep (from: T; key: CHAR; VAR keyEnd: CHAR): T = VAR result := NEW(T); cur := from.s; node: NFANode.T; BEGIN keyEnd := LAST(CHAR); WHILE cur # NIL DO node := cur.head; <* ASSERT node.keyBegin # NFANode.Epsilon *> IF key < node.keyBegin THEN keyEnd := MIN(keyEnd, VAL(ORD(node.keyBegin) - 1, CHAR)); ELSIF key <= node.keyEnd THEN keyEnd := MIN(keyEnd, node.keyEnd); result.out := MIN(result.out, node.output); AddNodeChasingEpsilons(result, node.targ1); AddNodeChasingEpsilons(result, node.targ2); END; cur := cur.tail; END; Canonical(result); RETURN result; END Step;
PROCEDURE Steps(from: T): Targets = VAR to: T; result := NEW(Targets); cur := from.s; node: NFANode.T; matches: ARRAY CHAR OF NFANodeList.T; BEGIN FOR i := FIRST(CHAR) TO LAST(CHAR) DO matches[i] := NIL; END; WHILE cur # NIL DO node := cur.head; <* ASSERT node.key # NFANode.Epsilon *> matches[node.key] := NFANodeList.Cons(node, matches[node.key]); cur := cur.tail; END; FOR i := FIRST(CHAR) TO LAST(CHAR) DO cur := matches[i]; IF cur = NIL THEN result[i] := NIL; ELSE to := NEW(T); result[i] := to; WHILE cur # NIL DO node := cur.head; to.out := MIN(to.out, node.output); AddNodeChasingEpsilons(to, node.targ1); AddNodeChasingEpsilons(to, node.targ2); cur := cur.tail; END; Canonical(result[i]); END; END; RETURN result; END Steps;
PROCEDUREDead (s: T): BOOLEAN = BEGIN RETURN s=NIL OR (s.s = NIL AND s.out = NFANode.NoOutput); END Dead; PROCEDUREOutput (s: T): INTEGER = BEGIN IF s = NIL OR s.out = NFANode.NoOutput THEN RETURN 0; ELSE RETURN s.out; END; END Output; PROCEDUREEqual (s, t: T): BOOLEAN = BEGIN IF s.out # t.out THEN RETURN FALSE; END; RETURN NFANodeListF.Equal(s.s, t.s); END Equal; PROCEDUREHash (s: T): Word.T = BEGIN RETURN NFANodeListF.Hash(s.s)*5 + s.out; END Hash; PROCEDUREFormat (s: T): TEXT = VAR result: TEXT; BEGIN result := NFANodeListF.Format(s.s); IF s.out # NFANode.NoOutput THEN result := result & "." & Fmt.Int(s.out); END; RETURN result; END Format; PROCEDURETest (a: NFA.T) = VAR curState: T; input, t: TEXT := ""; c: CHAR; BEGIN EVAL NFA.AssignIDs(a); curState := New(a); Term.MakeRaw(TRUE); Term.WrLn("NFA Test."); WHILE NOT Dead(curState) DO Term.WrLn("curState = " & Format(curState)); IF curState.out # NFANode.NoOutput THEN Term.WrLn("Output: " & Fmt.Int(curState.out)); END; Term.Wr(input); c := Term.GetCharD(); t := Text.FromChar(c); input := input & t; Term.WrLn(t); curState := Step(curState, c, c); END; Term.WrLn("Reject."); END Test; BEGIN END NFAState.