//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ // PLEASE DO NOT EDIT WITHOUT THE EXPLICIT CONSENT OF THE AUTHOR! \\ //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ package hlt.language.util; import java.util.Iterator; /** * This class is a concrete implementation of the abstract class RegExpTwo to represent * concatenation. * * @version Last modified on Mon Mar 26 10:38:17 2018 by hak * @author Hassan Aït-Kaci * @copyright © Hassan Aït-Kaci */ public class RegExpConcat extends RegExpTwo { /** * Constructs a RegExpConcat with the two specified * RegExp's. */ public RegExpConcat (RegExp left, RegExp right) { super(left,right); } public final RegExp shallowCopy () { return concat(_left,_right); } public final RegExp deepCopy () { return concat(_left.deepCopy(),_right.deepCopy()); } public final int type () { return CONCAT_EXP; } /** * This returns this RegExpConcat's * normal form according to the following (conditional) rewrite rules. * *

* * These rules are categorized into three subgroups, depending on the * nature of this RegExpConcat's left() and * right() components, corresponding to the three following * cases: * *

left() or right() is EMPTY; * *
left() and right() form a matching * pair, or this is of the form A.(B.C), where * A and B form a matching pair; * *
the rest. * *

* * We simply refer to a rule in each group as (for lack of better * terms!): *

an empty-rule, * *
a matching-pair-rule, * *
an other-rule, * *

* * respectively. [In what follows, the "qualifier-rule" * notation will be used systematically and exclusively to qualify * these groups.] * ******************************************************************** * *

Empty-rules

* * The rules for concatenating EMPTY to anything, or * anything to EMPTY, are: * *

* * [CO:E_] * * * * * ().X * * * → * * * X * * * *
* * [CO:_E] * * * * * X.() * * * → * * * X * * * *

* ******************************************************************** * *

Matching-pair-rules

* * The rules for concatenating any two regular expressions forming a * "matching pair" are given * by the table below. Note that, although concatenation is not a * commutative operation on strings nor on regular expressions, its * restriction to such "matching * pairs" of regular expressions is commutative. Thus, the table * is symmetric in its rows and columns (i.e., it is invariant * when swapping any corresponding pair of row/column). * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* * _._ * * * * X * * * * X? * * * * X+ * * * * X\* * * * * X^q * * * * X_p^q * *

* * X * *

* * X^2 * *

* * [CO:XX] * *

* * X_1^2 * *

* * [CO:XO] * *

* * X_2~ * *

* * [CO:XP] * *

* * X+ * *

* * [CO:XS] * *

* * X^q+1 * *

* * [CO:XN] * *

* * X_p+1^q+1 * *

* * [CO:XR] * *

* * X? * *

* * X_1^2 * *

* * [CO:OX] * *

* * X_0^2 * *

* * [CO:OO] * *

* * X+ * *

* * [CO:OP] * *

* * X\* * *

* * [CO:OS] * *

* * X_q^q+1 * *

* * [CO:ON] * *

* * X_p^q+1 * *

* * [CO:OR] * *

* * X+ * *

* * X_2~ * *

* * [CO:PX] * *

* * X+ * *

* * [CO:PO] * *

* * X_2~ * *

* * [CO:PP] * *

* * X+ * *

* * [CO:PS] * *

* * X_q+1~ * *

* * [CO:PN] * *

* * X_p+1~ * *

* * [CO:PR] * *

* * X\* * *

* * X+ * *

* * [CO:SX] * *

* * X\* * *

* * [CO:SO] * *

* * X+ * *

* * [CO:SP] * *

* * X\* * *

* * [CO:SS] * *

* * X_q~ * *

* * [CO:SN] * *

* * X_p~ * *

* * [CO:SR] * *

* * X^n * *

* * X^n+1 * *

* * [CO:NX] * *

* * X_n^n+1 * *

* * [CO:NO] * *

* * X_n+1~ * *

* * [CO:NP] * *

* * X_n~ * *

* * [CO:NS] * *

* * X^n+q * *

* * [CO:NN] * *

* * X_n+p^n+q * *

* * [CO:NR] * *

* * X_m^n * *

* * X_m+1^n+1 * *

* * [CO:RX] * *

* * X_m^n+1 * *

* * [CO:RO] * *

* * X_m+1~ * *

* * [CO:RP] * *

* * X_m~ * *

* * [CO:RS] * *

* * X_m+q^n+q * *

* * [CO:RN] * *

* * X_m+p^n+q * *

* * [CO:RR] * *

* * * Each entry in this table is labeled [CO:AB] where A and B are a pair of letters * in the set {X O P S N * R}. Each letter is a mnemonic for the case it * stands for: X = * "eXpression", O = * "Option", P = * "Plus", S = * "Star", N = "N-th * power", R = "power * Range". To each entry in the above table labeled [CO:AB], there * correspond two rules, labeled [CO:AB1] and [CO:AB2]: the first one * covers the simple case and the second one the nested case. They are * listed again below for the sake of clarity. * *

* * The entries marked "(redundant)" are * never used as they are systematically preempted earlier by the * X/X case. Indeed, it is never * possible for matchingPairCode() * to return any of the values OO, PP, SS, * NN, nor RR. Therefore, the 10 corresponding rules * [CO:OO1], [CO:OO2], [CO:PP1], [CO:PP2], [CO:SS1], [CO:SS2], [CO:NN1], [CO:NN2], [CO:RR1], and [CO:RR2] are redundant and could be * eliminated altogether. As a matter of fact, each is confluent with * the effect of applying the CO:XX rule followed by the * appropriate PW:_ rule. This can be trivially verified by * looking at the appropriate rules. The redundant rules are given * here for the sake of completeness and for the justification of * correctness of this specification. * ******************************************************************** *

* * [CO:XX1] * * * * * X.X * * * → * * * X^2 * * * *
* * [CO:XX2] * * * * * X.(X.Y) * * * → * * * X^2.Y * * * *
* *
* * [CO:XO1] * * * * * X.X? * * * → * * * X_1^2 * * * *
* * [CO:XO2] * * * * * X.(X?.Y) * * * → * * * X_1^2.Y * * * *
* *
* * [CO:XP1] * * * * * X.X+ * * * → * * * X_2~ * * * *
* * [CO:XP2] * * * * * X.(X+.Y) * * * → * * * X_2~.Y * * * *
* *
* * [CO:XS1] * * * * * X.X\* * * * → * * * X+ * * * *
* * [CO:XS2] * * * * * X.(X\*.Y) * * * → * * * X+.Y * * * *
* *
* * [CO:XN1] * * * * * X.X^q * * * → * * * X^q+1 * * * *
* * [CO:XN2] * * * * * X.(X^q.Y) * * * → * * * X^q+1.Y * * * *
* *
* * [CO:XR1] * * * * * X.X_p^q * * * → * * * X_p+1^q+1 * * * ******************************************************************** *
* * [CO:XR2] * * * * * X.(X_p^q.Y) * * * → * * * X_p+1^q+1.Y * * * ******************************************************************** *
* *
* * [CO:OX1] * * * * * X?.X * * * → * * * X_1^2 * * * *
* * [CO:OX2] * * * * * X?.(X.Y) * * * → * * * X_1^2.Y * * * *
* *
* * [CO:OO1] * * * * * * X?.X? * * * → * * * X_0^2 * * (redundant) * *
* * [CO:OO2] * * * * * * X?.(X?.Y) * * * → * * * X_0^2.Y * * (redundant) * *
* *
* * [CO:OP1] * * * * * X?.X+ * * * → * * * X+ * * * *
* * [CO:OP2] * * * * * X?.(X+.Y) * * * → * * * X+.Y * * * *
* *
* * [CO:OS1] * * * * * X?.X\* * * * → * * * X* * * * *
* * [CO:OS2] * * * * * X?.(X\*.Y) * * * → * * * X*.Y * * * *
* *
* * [CO:ON1] * * * * * X?.X^q * * * → * * * X_q^q+1 * * * *
* * [CO:ON2] * * * * * X?.(X^q.Y) * * * → * * * X_q^q+1.Y * * * *
* *
* * [CO:OR1] * * * * * X?.X_p^q * * * → * * * X_p^q+1 * * * ******************************************************************** *
* * [CO:OR2] * * * * * X?.(X_p^q.Y) * * * → * * * X_p^q+1.Y * * * ******************************************************************** *
* *
* * [CO:PX1] * * * * * X+.X * * * → * * * X_2~ * * * *
* * [CO:PX2] * * * * * X+.(X.Y) * * * → * * * X_2~.Y * * * *
* *
* * [CO:PO1] * * * * * X+.X? * * * → * * * X+ * * * *
* * [CO:PO2] * * * * * X+.(X?.Y) * * * → * * * X+.Y * * * *
* *
* * [CO:PP1] * * * * * * X+.X+ * * * → * * * X_2~ * * (redundant) * *
* * [CO:PP2] * * * * * * X+.(X+.Y) * * * → * * * X_2~.Y * * (redundant) * *
* *
* * [CO:PS1] * * * * * X+.X\* * * * → * * * X+ * * * *
* * [CO:PS2] * * * * * X+.(X\*.Y) * * * → * * * X+.Y * * * *
* *
* * [CO:PN1] * * * * * X+.X^q * * * → * * * X_q+1~ * * * *
* * [CO:PN2] * * * * * X+.(X^q.Y) * * * → * * * X_q+1~.Y * * * *
* *
* * [CO:PR1] * * * * * X+.X_p^q * * * → * * * X_p+1~ * * * ******************************************************************** *
* * [CO:PR2] * * * * * X+.(X_p^q.Y) * * * → * * * X_p+1~.Y * * * ******************************************************************** *
* *
* * [CO:SX1] * * * * * X\*.X * * * → * * * X+ * * * *
* * [CO:SX2] * * * * * X\*.(X.Y) * * * → * * * X+.Y * * * *
* *
* * [CO:SO1] * * * * * X\*.X? * * * → * * * X* * * * *
* * [CO:SO2] * * * * * X\*.(X?.Y) * * * → * * * X*.Y * * * *
* *
* * [CO:SP1] * * * * * X\*.X+ * * * → * * * X+ * * * *
* * [CO:SP2] * * * * * X\*.(X+.Y) * * * → * * * X+.Y * * * *
* *
* * [CO:SS1] * * * * * * X\*.X\* * * * → * * * X\* * * (redundant) * *
* * [CO:SS2] * * * * * * X\*.(X\*.Y) * * * → * * * X\*.Y * * (redundant) * *
* *
* * [CO:SN1] * * * * * X\*.X^q * * * → * * * X_q~ * * * *
* * [CO:SN2] * * * * * X\*.(X^q.Y) * * * → * * * X_q~.Y * * * *
* *
* * [CO:SR1] * * * * * X\*.X_p^q * * * → * * * X_p~ * * * ******************************************************************** *
* * [CO:SR2] * * * * * X\*.(X_p^q.Y) * * * → * * * X_p~.Y * * * ******************************************************************** *
* *
* * [CO:NX1] * * * * * X^n.X * * * → * * * X^n+1 * * * *
* * [CO:NX2] * * * * * X^n.(X.Y) * * * → * * * X^n+1.Y * * * *
* *
* * [CO:NO1] * * * * * X^n.X? * * * → * * * X_n^n+1 * * * *
* * [CO:NO2] * * * * * X^n.(X?.Y) * * * → * * * X_n^n+1.Y * * * *
* *
* * [CO:NP1] * * * * * X^n.X+ * * * → * * * X_n+1~ * * * *
* * [CO:NP2] * * * * * X^n.(X+.Y) * * * → * * * X_n+1~.Y * * * *
* *
* * [CO:NS1] * * * * * X^n.X\* * * * → * * * X_n~ * * * *
* * [CO:NS2] * * * * * X^n.(X\*.Y) * * * → * * * X_n~.Y * * * *
* *
* * [CO:NN1] * * * * * * X^n.X^q * * * → * * * X^n+q * * (redundant) * *
* * [CO:NN2] * * * * * * X^n.(X^q.Y) * * * → * * * X^n+q.Y * * (redundant) * *
* *
* * [CO:NR1] * * * * * X^n.X_p^q * * * → * * * X_n+p^n+q * * * ******************************************************************** *
* * [CO:NR2] * * * * * X^n.(X_p^q.Y) * * * → * * * X_n+p^n+q.Y * * * ******************************************************************** *
* *
* * [CO:RX1] * * * * * X_m^n.X * * * → * * * X_m+1^n+1 * * * *
* * [CO:RX2] * * * * * X_m^n.(X.Y) * * * → * * * X_m+1^n+1.Y * * * *
* *
* * [CO:RO1] * * * * * X_m^n.X? * * * → * * * X_m^n+1 * * * *
* * [CO:RO2] * * * * * X_m^n.(X?.Y) * * * → * * * X_m^n+1.Y * * * *
* *
* * [CO:RP1] * * * * * X_m^n.X+ * * * → * * * X_m+1~ * * * *
* * [CO:RP2] * * * * * X_m^n.(X+.Y) * * * → * * * X_m+1~.Y * * * *
* *
* * [CO:RS1] * * * * * X_m^n.X\* * * * → * * * X_m~ * * * *
* * [CO:RS2] * * * * * X_m^n.(X\*.Y) * * * → * * * X_m~.Y * * * *
* *
* * [CO:RN1] * * * * * X_m^n.X^q * * * → * * * X_m+q^n+q * * * *
* * [CO:RN2] * * * * * X_m^n.(X^q.Y) * * * → * * * X_m+q^n+q.Y * * * *
* *
* * [CO:RR1] * * * * * * X_m^n.X_p^q * * * → * * * X_m+p^n+q * * (redundant) * *
* * [CO:RR2] * * * * * * X_m^n.(X_p^q.Y) * * * → * * * X_m+p^n+q.Y * * (redundant) *

* ******************************************************************** * ******************************************************************** * *

Other-rules

* * These rules are essentially putting all nested concatenations into * right-associative form and expanding left and right distributivity. *

* * [CO:_A] * * * * * (X.Y).Z * * * → * * * X.(Y.Z) * * * *
* * [CO:D_] * * * * * (X | Y).Z * * * → * * * X.Z | Y.Z * * * *
* * [CO:_D] * * * * * X.(Y | Z) * * * → * * * X.Y | X.Z * * * *

*/ public void normalize () { String rule = null; RegExp left = left(); RegExp right = right(); out: { if (left.isEmpty()) { rule = "[CO:E_] ().X --> X"; _normalForm = right; break out; } if (right.isEmpty()) { rule = "[CO:_E] X.() --> X"; _normalForm = left; break out; } if (left.isConcat()) { rule = "[CO:_A] (X.Y).Z --> X.(Y.Z)"; _normalForm = concat(left.left(), concat(left.right(), right)); break out; } if (left.isChoice()) { rule = "[CO:D_] (X | Y).Z --> X.Z | Y.Z"; _normalForm = choice(concat(left.left(), right), concat(left.right(), right)); break out; } if (right.isChoice()) { rule = "[CO:_D] X.(Y | Z) --> X.Y | X.Z"; _normalForm = choice(concat(left, right.left()), concat(left, right.right())); break out; } /* **************************************** */ RegExp X,Y; int m,n,p,q; // int code = matchingPairCode(); // System.err.println("code for "+this+" = "+code(code)); switch (matchingPairCode()) { case XX: rule = "[CO:XX1] X.X --> X^2"; X = left; _normalForm = power(X,2); break out; case XO: rule = "[CO:XO1] X.X? --> X_1^2"; X = left; _normalForm = range(X,1,2); break out; case XP: rule = "[CO:XP1] X.X+ --> X_2~"; X = left; _normalForm = range(X,2); break out; case XS: rule = "[CO:XS1] X.X* --> X+"; X = left; _normalForm = plus(X); break out; case XN: rule = "[CO:XN1] X.X^q --> X^q+1"; X = left; q = right.power(); _normalForm = power(X,plus(q,1)); break out; case XR: rule = "[CO:XR1] X.X_p^q --> X_p+1^q+1"; X = left; p = right.lower(); q = right.upper(); _normalForm = range(left,plus(p,1),plus(q,1)); break out; case OX: rule = "[CO:OX1] X?.X --> X_1^2"; X = right; _normalForm = range(X,1,2); break out; case OO: // this is never reached rule = "[CO:OO1] X?.X? --> X_0^2"; X = left.arg(); _normalForm = range(X,0,2); break out; case OP: rule = "[CO:OP1] X?.X+ --> X+"; _normalForm = right; break out; case OS: rule = "[CO:OS1] X?.X* --> X*"; _normalForm = right; break out; case ON: rule = "[CO:ON1] X?.X^q --> X_q^q+1"; X = left.arg(); q = right.power(); _normalForm = range(X,q,plus(q,1)); break out; case OR: rule = "[CO:OR1] X?.X_p^q --> X_p^q+1"; X = left.arg(); p = right.lower(); q = right.upper(); _normalForm = range(X,p,plus(q,1)); break out; case PX: rule = "[CO:PX1] X+.X --> X_2~"; X = right; _normalForm = range(X,2); break out; case PO: rule = "[CO:PO1] X+.X? --> X+"; _normalForm = left; break out; case PP: // this is never reached rule = "[CO:PP1] X+.X+ --> X_2~"; X = left.arg(); _normalForm = range(X,2); break out; case PS: rule = "[CO:PS1] X+.X* --> X+"; _normalForm = left; break out; case PN: rule = "[CO:PN1] X+.X^q --> X_q+1~"; X = left.arg(); q = right.power(); _normalForm = range(X,plus(q,1)); break out; case PR: rule = "[CO:PR1] X+.X_p^q --> X_p+1~"; X = left.arg(); p = right.lower(); q = right.upper(); _normalForm = range(X,plus(p,1)); break out; case SX: rule = "[CO:SX1] X*.X --> X+"; X = right; _normalForm = plus(X); break out; case SO: rule = "[CO:SO1] X*.X? --> X*"; _normalForm = left; break out; case SP: rule = "[CO:SP] X*.X+ --> X+"; _normalForm = right; break out; case SS: // this is never reached rule = "[CO:SS1] X*.X* --> X*"; _normalForm = left; break out; case SN: rule = "[CO:SN] X*.X^q --> X_q~"; X = left.arg(); q = right.power(); _normalForm = range(X,q); break out; case SR: rule = "[CO:SR1] X*.X_p^q --> X_p~"; X = left.arg(); p = right.lower(); _normalForm = range(X,p); break out; case NX: rule = "[CO:NX1] X^n.X --> X^n+1"; X = right; n = left.power(); _normalForm = power(X,plus(n,1)); break out; case NO: rule = "[CO:NO1] X^n.X? --> X_n^n+1"; X = left.arg(); n = left.power(); _normalForm = range(X,n,plus(n,1)); break out; case NP: rule = "[CO:NP1] X^n.X+ --> X_n+1~"; X = left.arg(); n = left.power(); _normalForm = range(X,plus(n,1)); break out; case NS: rule = "[CO:NS1] X^n.X* --> X_n~"; X = left.arg(); n = left.power(); _normalForm = range(X,n); break out; case NN: // this is never reached rule = "[CO:NN1] X^n.X^q --> X^n+q"; X = left.arg(); n = left.power(); q = right.power(); _normalForm = power(X,plus(n,q)); break out; case NR: rule = "[CO:NR1] X^n.X_p^q --> X_n+p^n+q"; X = left.arg(); n = left.power(); p = right.lower(); q = right.upper(); _normalForm = range(X,plus(n,p),plus(n,q)); break out; case RX: rule = "[CO:RX1] X_m^n.X --> X_m+1^n+1"; X = right; m = left.lower(); n = left.upper(); _normalForm = range(X,plus(m,1),plus(n,1)); break out; case RO: rule = "[CO:RO1] X_m^n.X? --> X_m^n+1"; X = left.arg(); m = left.lower(); n = left.upper(); _normalForm = range(X,m,plus(n,1)); break out; case RP: rule = "[CO:RP1] X_m^n.X+ --> X_m+1~"; X = left.arg(); m = left.lower(); n = left.upper(); _normalForm = range(X,plus(m,1)); break out; case RS: rule = "[CO:RS1] X_m^n.X* --> X_m~"; X = left.arg(); m = left.lower(); n = left.upper(); _normalForm = range(X,m); break out; case RN: rule = "[CO:RN1] X_m^n.X^q --> X_m+q^n+q"; X = left.arg(); m = left.lower(); n = left.upper(); q = right.power(); _normalForm = range(X,plus(m,q),plus(n,q)); break out; case RR: // this is never reached rule = "[CO:RR1] X_m^n.X_p^q --> X_m+p^n+q"; X = left.arg(); m = left.lower(); n = left.upper(); p = right.lower(); q = right.upper(); _normalForm = range(X,plus(m,p),plus(n,q)); break out; } switch (matchingArgsCode()) { case XX: rule = "[CO:XX2] X.(X.Y) --> X^2.Y"; X = left; Y = right.right(); _normalForm = concat(power(X,2),Y); break out; case XO: rule = "[CO:XO2] X.(X?.Y) --> X_1^2.Y"; X = left; Y = right.right(); _normalForm = concat(range(X,1,2),Y); break out; case XP: rule = "[CO:XP2] X.(X+.Y) --> X_2~.Y"; X = left; Y = right.right(); _normalForm = concat(range(X,2),Y); break out; case XS: rule = "[CO:XS2] X.(X*.Y) --> X+.Y"; X = left; Y = right.right(); _normalForm = concat(plus(X),Y); break out; case XN: rule = "[CO:XN2] X.(X^q.Y) --> X^q+1.Y"; X = left; q = right.left().power(); Y = right.right(); _normalForm = concat(power(X,plus(q,1)),Y); break out; case XR: rule = "[CO:XR2] X.(X_p^q.Y) --> X_p+1^q+1.Y"; X = left; p = right.left().lower(); q = right.left().upper(); Y = right.right(); _normalForm = concat(range(left,plus(p,1),plus(q,1)),Y); break out; case OX: rule = "[CO:OX2] X?.(X.Y) --> X_1^2.Y"; X = right.left(); Y = right.right(); _normalForm = concat(range(X,1,2),Y); break out; case OO: // this is never reached rule = "[CO:OO2] X?.(X?.Y) --> X_0^2.Y"; X = left.arg(); Y = right.right(); _normalForm = concat(range(X,0,2),Y); break out; case OP: rule = "[CO:OP2] X?.(X+.Y) --> X+.Y"; _normalForm = right; break out; case OS: rule = "[CO:OS2] X?.(X*.Y) --> X*.Y"; _normalForm = right; break out; case ON: rule = "[CO:ON2] X?.(X^q.Y) --> X_q^q+1.Y"; X = left.arg(); q = right.left().power(); Y = right.right(); _normalForm = concat(range(X,q,plus(q,1)),Y); break out; case OR: rule = "[CO:OR2] X?.(X_p^q.Y) --> X_p^q+1.Y"; X = left.arg(); p = right.left().lower(); q = right.left().upper(); Y = right.right(); _normalForm = concat(range(X,p,plus(q,1)),Y); break out; case PX: rule = "[CO:PX2] X+.(X.Y) --> X_2~.Y"; X = right.left(); Y = right.right(); _normalForm = concat(range(X,2),Y); break out; case PO: rule = "[CO:PO2] X+.(X?.Y) --> X+.Y"; Y = right.right(); _normalForm = concat(left,Y); break out; case PP: // this is never reached rule = "[CO:PP2] X+.(X+.Y) --> X_2~.Y"; X = left.arg(); Y = right.right(); _normalForm = concat(range(X,2),Y); break out; case PS: rule = "[CO:PS2] X+.(X*.Y) --> X+.Y"; X = left.arg(); Y = right.right(); _normalForm = concat(plus(X),Y); break out; case PN: rule = "[CO:PN2] X+.(X^q.Y) --> X_q+1~.Y"; X = left.arg(); q = right.left().power(); Y = right.right(); _normalForm = concat(range(X,plus(q,1)),Y); break out; case PR: rule = "[CO:PR2] X+.(X_p^q.Y) --> X_p+1~.Y"; X = left.arg(); p = right.left().lower(); q = right.left().upper(); Y = right.right(); _normalForm = concat(range(X,plus(p,1)),Y); break out; case SX: rule = "[CO:SX2] X*.(X.Y) --> X+.Y"; X = right.left(); Y = right.right(); _normalForm = concat(plus(X),Y); break out; case SO: rule = "[CO:SO2] X*.(X?.Y) --> X*.Y"; Y = right.right(); _normalForm = concat(left,Y); break out; case SP: rule = "[CO:SP2] X*.(X+.Y) --> X+.Y"; _normalForm = right; break out; case SS: // this is never reached rule = "[CO:SS2] X*.(X*.Y) --> X*.Y"; _normalForm = right; break out; case SN: rule = "[CO:SN2] X*.(X^q.Y) --> X_q~.Y"; X = left.arg(); q = right.left().power(); Y = right.right(); _normalForm = concat(range(X,q),Y); break out; case SR: rule = "[CO:SR2] X*.(X_p^q.Y) --> X_p~.Y"; X = left.arg(); p = right.left().lower(); Y = right.right(); _normalForm = concat(range(X,p),Y); break out; case NX: rule = "[CO:NX2] X^n.(X.Y) --> X^n+1.Y"; X = right.left(); n = left.power(); Y = right.right(); _normalForm = concat(power(X,plus(n,1)),Y); break out; case NO: rule = "[CO:NO2] X^n.(X?.Y) --> X_n^n+1.Y"; X = left.arg(); n = left.power(); Y = right.right(); _normalForm = concat(range(X,n,plus(n,1)),Y); break out; case NP: rule = "[CO:NP2] X^n.(X+.Y) --> X_n+1~.Y"; X = left.arg(); n = left.power(); Y = right.right(); _normalForm = concat(range(X,plus(n,1)),Y); break out; case NS: rule = "[CO:NS2] X^n.(X*.Y) --> X_n~.Y"; X = left.arg(); n = left.power(); Y = right.right(); _normalForm = concat(range(X,n),Y); break out; case NN: // this is never reached rule = "[CO:NN2] X^n.(X^q.Y) --> X^n+q.Y"; X = left.arg(); n = left.power(); q = right.left().power(); Y = right.right(); _normalForm = concat(power(X,plus(n,q)),Y); break out; case NR: rule = "[CO:NR2] X^n.(X_p^q.Y) --> X_n+p^n+q.Y"; X = left.arg(); n = left.power(); p = right.left().lower(); q = right.left().upper(); Y = right.right(); _normalForm = concat(range(X,plus(n,p),plus(n,q)),Y); break out; case RX: rule = "[CO:RX2] X_m^n.(X.Y) --> X_m+1^n+1.Y"; X = right.left(); m = left.lower(); n = left.upper(); Y = right.right(); _normalForm = concat(range(X,plus(m,1),plus(n,1)),Y); break out; case RO: rule = "[CO:RO2] X_m^n.(X?.Y) --> X_m^n+1.Y"; X = left.arg(); m = left.lower(); n = left.upper(); Y = right.right(); _normalForm = concat(range(X,m,plus(n,1)),Y); break out; case RP: rule = "[CO:RP2] X_m^n.(X+.Y) --> X_m+1~.Y"; X = left.arg(); m = left.lower(); n = left.upper(); Y = right.right(); _normalForm = concat(range(X,plus(m,1)),Y); break out; case RS: rule = "[CO:RS2] X_m^n.(X*.Y) --> X_m~.Y"; X = left.arg(); m = left.lower(); n = left.upper(); Y = right.right(); _normalForm = concat(range(X,m),Y); break out; case RN: rule = "[CO:RN2] X_m^n.(X^q.Y) --> X_m+q^n+q.Y"; X = left.arg(); m = left.lower(); n = left.upper(); q = right.left().power(); Y = right.right(); _normalForm = concat(range(X,plus(m,q),plus(n,q)),Y); break out; case RR: // this is never reached rule = "[CO:RR2] X_m^n.(X_p^q.Y) --> X_m+p^n+q.Y"; X = left.arg(); m = left.lower(); n = left.upper(); p = right.left().lower(); q = right.left().upper(); Y = right.right(); _normalForm = concat(range(X,plus(m,p),plus(n,q)),Y); break out; } } // end of named block "out:" traceRule(rule); checkNormalForm(); } private RegExp concat (ArrayList list) { RegExp e = RegExpSymbol.EMPTY; for (Iterator i=list.iterator(); i.hasNext();) e = concat((RegExp)i.next(),e); return e; } private final boolean reOccursIn (RegExp exp, ArrayList path) { if (exp.type() != CONCAT_EXP) return false; path.add(left()); RegExpConcat seq = (RegExpConcat)exp; if (this == seq.right()) return true; return reOccursIn(seq.right(),path); } /** * Returns a printable form for this RegExpConcat. */ public final String toString () { String left = _left.toString(); String right = _right.toString(); // if (_left.isChoice()) if (_left.isBinary()) left = "("+left+")"; if (_right.isChoice()) right = "("+right+")"; return left+"."+right; } public final String toNormalString () { if (!inNormalForm()) return _normalForm.toNormalString(); String left = _left.toNormalString(); String right = _right.toNormalString(); // if (_left.isChoice()) if (_left.isBinary()) left = "("+left+")"; if (_right.isChoice()) right = "("+right+")"; return left+"."+right; } }