MODULE; IMPORT PDATrans; IMPORT PDATransList; IMPORT PDATransListF; IMPORT PDATransListIntTbl; IMPORT IntIntTbl; IMPORT Term, Fmt; CONST (* can this action be performed by default? *) Defable = SET OF PDATrans.ActKind{PDATrans.ActKind.Reduce, PDATrans.ActKind.Accept}; PROCEDURE PDATransListOp Simplify (a: T): T = VAR scores := NEW(IntIntTbl.Default).init(); cur := a; tr: PDATrans.T; score: INTEGER; hiScorer: PDATrans.T; hiScore: INTEGER := 0; result: T; BEGIN WHILE cur # NIL DO tr := cur.head; IF tr.kind IN Defable THEN score := 0; EVAL scores.get(tr.target, score); INC(score); EVAL scores.put(tr.target, score); IF score > hiScore THEN hiScorer := tr; hiScore := score; END; END; cur := cur.tail; END; IF hiScore = 0 THEN RETURN PDATransList.ReverseD(a); END; hiScorer.code := -1; cur := a; WHILE cur # NIL DO tr := cur.head; IF (NOT tr.kind IN Defable) OR tr.target # hiScorer.target THEN result := PDATransList.Cons(tr, result); END; cur := cur.tail; END; result := PDATransList.Cons(hiScorer, result); RETURN result; END Simplify; PROCEDUREPrintArray (a: REF ARRAY OF T; len: INTEGER := 0) = VAR actual := len; BEGIN IF actual = 0 THEN actual := LAST(a^); END; FOR i := 1 TO actual DO Term.WrLn(Fmt.Int(i) & ": " & PDATransListF.Format(a[i])); END; END PrintArray; PROCEDURECollapsable (a: T): BOOLEAN = BEGIN RETURN a.tail = NIL AND a.head.kind IN Defable; END Collapsable; PROCEDUREMergeStates (VAR a: REF ARRAY OF T) = VAR cur: T; result: REF ARRAY OF T; numStates: INTEGER := LAST(a^); newNumStates: INTEGER; renumber := NEW(REF ARRAY OF INTEGER, numStates+1); ID, i, iOriginal: INTEGER; canonID: PDATransListIntTbl.T; fixed: BOOLEAN; PROCEDURE ReNumberShifts() = BEGIN numStates := newNumStates; FOR i := 1 TO numStates DO cur := a[i]; WHILE cur # NIL DO IF cur.head.kind = PDATrans.ActKind.Shift THEN cur.head.target := renumber[cur.head.target]; END; cur := cur.tail; END; END; (* Term.WrLn("renumbered: ");PrintArray(a, numStates); *) END ReNumberShifts; BEGIN (* Term.WrLn("start with: ");PrintArray(a, numStates); *) REPEAT fixed := TRUE; canonID := NEW(PDATransListIntTbl.Default).init(); newNumStates := numStates; i := 1; iOriginal := 1; WHILE i <= newNumStates DO ID := i; IF canonID.get(a[i], ID) THEN fixed := FALSE; (* Term.WrLn("found " & PDATransListF.Format(a[i]) & " with ID = " & Fmt.Int(ID)); *) ELSE EVAL canonID.put(a[i], ID); (* Term.WrLn("putting " & PDATransListF.Format(a[i]) & " with ID = " & Fmt.Int(ID)); *) END; renumber[iOriginal] := ID; IF i = ID THEN INC(i); iOriginal := i; ELSE
Term.Wr(
); IF iOriginal # i THEN Term.Wr(
re-
); END; Term.WrLn(renumber
& Fmt.Int(iOriginal) &->
& Fmt.Int(ID) &. Delete: renumber
& Fmt.Int(newNumStates) &->
& Fmt.Int(i));
iOriginal := newNumStates; a[i] := a[iOriginal]; DEC(newNumStates); END; END; ReNumberShifts(); UNTIL fixed; (* make anonymous reductions *) FOR i := 1 TO numStates DO cur := a[i]; WHILE cur # NIL DO IF cur.head.kind = PDATrans.ActKind.Shift THEN WITH targ = a[cur.head.target] DO IF Collapsable(targ) THEN cur.head := PDATrans.PreShift(targ.head, cur.head.code); END; END; END; cur := cur.tail; END; END; newNumStates := numStates; i := 2; (* don't eliminate the start state! *) WHILE i <= newNumStates DO IF Collapsable(a[i]) THEN a[i] := a[newNumStates]; renumber[newNumStates] := i; DEC(newNumStates); ELSE INC(i); END; END; ReNumberShifts(); result := NEW(REF ARRAY OF T, numStates+1); result^ := SUBARRAY(a^, 0, numStates+1); (* PrintArray(result, numStates); *) a := result; END MergeStates; BEGIN END PDATransListOp.