//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ // PLEASE DO NOT EDIT WITHOUT THE EXPLICIT CONSENT OF THE AUTHOR! \\ //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ package hlt.language.util; /** * This class is a concrete implementation of the abstract class RegExpTwo to represent alternation. * * @version Last modified on Mon Mar 26 10:45:54 2018 by hak * @author Hassan Aït-Kaci * @copyright © Hassan Aït-Kaci */ public class RegExpChoice extends RegExpTwo { /** * Constructs a RegExpChoice with the two specified * RegExp's. */ public RegExpChoice (RegExp left, RegExp right) { super(left,right); } public final int type () { return CHOICE_EXP; } public final RegExp shallowCopy () { return choice(_left,_right); } public final RegExp deepCopy () { return choice(_left.deepCopy(),_right.deepCopy()); } /** * This computes the normal form of this * RegExpChoice, and sets its _normalForm field to * it. This normal form is computed according to the following rewrite * rules. * *

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

    * *
  1. left() or right() is EMPTY; * *
  2. left() and right() forms are non-numeric * unary expressions forming a matching pair, or this is of the * form A|(B|C), where A and B form such a * (restricted) matching * pair; * *
  3. power/range rules (taking care of choices of numeric unary * expressions); * *
  4. commutation rules; * *
  5. the rest. * *
* * We simply refer to a rule in each group as (for lack of better * terms!): *
    * *
  1. an empty-rule, * *
  2. a matching-pair-rule, * *
  3. a power-rule, * *
  4. a swap-rule, * *
  5. 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 a choice involving EMPTY are: * * * ******************************************************************** * *

Matching-pair-rules

* * The rules for choosing among any two regular expressions forming a * "matching pair" are given * by the table below - but restricted to non-numeric unary * operators. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * _|_ * * * * X * * * * X? * * * * X+ * * * * X\* * * * * X^n * * * * X_m^n * *
* * X * *
* * * X * * *
* * [CH:XX] * *
* * * X? * * *
* * [CH:XO] * *
* * * X+ * * *
* * [CH:XP] * *
* * * X\* * * *
* * [CH:XS] * *
* * (see below) * *
* * [CH:XN] * *
* * (see below) * *
* * [CH:XR] * *
* * X? * *
* * * X? * * *
* * [CH:OX] * *
* * * X? * * *
* * [CH:OO] * *
* * * X\* * * *
* * [CH:OP] * *
* * * X\* * * *
* * [CH:OS] * *
* * (see below) * *
* * [CH:ON] * *
* * (see below) * *
* * [CH:OR] * *
* * X+ * *
* * * X+ * * *
* * [CH:PX] * *
* * * X\* * * *
* * [CH:PO] * *
* * * X+ * * *
* * [CH:PP] * *
* * * X\* * * *
* * [CH:PS] * *
* * * X+ * * *
* * [CH:PN] * *
* * * X+ * * *
* * [CH:PR] * *
* * X\* * *
* * * X\* * * *
* * [CH:SX] * *
* * * X\* * * *
* * [CH:SO] * *
* * * X\* * * *
* * [CH:SP] * *
* * * X\* * * *
* * [CH:SS] * *
* * * X\* * * *
* * [CH:SN] * *
* * * X\* * * *
* * [CH:SR] * *
* * X^n * *
* * (see below) * *
* * [CH:NX] * *
* * (see below) * *
* * [CH:NO] * *
* * * X+ * * *
* * [CH:NP] * *
* * * X\* * * *
* * [CH:NS] * *
* * (see below) * *
* * [CH:NN] * *
* * (see below) * *
* * [CH:NR] * *
* * X_m^n * *
* * (see below) * *
* * [CH:RX] * *
* * (see below) * *
* * [CH:RO] * *
* * * X+ * * *
* * [CH:RP] * *
* * * X\* * * *
* * [CH:RS] * *
* * (see below) * *
* * [CH:RN] * *
* * (see below) * *
* * [CH:RR] * *
*
* * Each entry in this table is labeled [CH: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 = "Nth power", * R = "power Range". To each entry in the above * table labeled [CH:AB], there correspond two * rules, labeled [CH:AB1] and * [CH: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. Entries in the table that are marked "(see below)" yield * several results depending on the nature of the exponents in the * power or range and are treated in the "Power-rules" and * "Swap-rules" sections following this "Matching-pair-rule" section. *

* * These above table entries are given as rules below. Those marked * "(redundant)" are in fact never used * as they are systematically preempted earlier by the the * X/X case. Indeed, it is never * possible for matchingPairCode() * to return any of the values OO, PP, nor * SS. Therefore, the 6 corresponding rules [CH:OO1], [CH:OO2], [CH:PP1], [CH:PP2], [CH:SS1], and [CH:SS2], are redundant and could be * eliminated altogether. As a matter of fact, each one reduces to the * corresponding [CH:XX] rule. This can * be trivially verified by looking at the rules (idempotence of * choice). The redundant rules are given here for the sake of * completeness and for the justification of correctness of this * specification. * ******************************************************************** *

*

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

Power-rules

* * The cases of N = "N-th * power" and R = "power * Range" missing in the table above need special attention and are * given here. * * *

Swap-rules

* * Although choice is a commutative operation on regular expressions, * we put it systematically in some predefined order based on the nature * of the operands. This is what the swap-rules do. * * * * * * * * * * *

Other-rules

* * ******************************************************************** */ public void normalize () { String rule = null; RegExp left = left(); RegExp right = right(); out: { // Empty-rules: if (left.isEmpty()) { rule = "[CH:E_] () | X --> X?"; _normalForm = option(right); break out; } if (right.isEmpty()) { rule = "[CH:_E] X | () --> X?"; _normalForm = option(left); break out; } // Matching-pair-rules: // 1st row: if (right.equals(left)) { rule = "[CH:XX1] X | X --> X"; _normalForm = left; break out; } // 2nd row: // 3rd row: // 4th row: // 5th row: // 6th row: // ... // ---------------------------------------------------------- // if (left.isOption()) { rule = "[CH:O_] X? | Y --> (X | Y)?"; _normalForm = option(choice(left.arg(), right)); break out; } if (right.isOption()) { rule = "[CH:_O] X | Y? --> (X | Y)?"; _normalForm = option(choice(left, right.arg())); break out; } if (left.isChoice()) { rule = "[CH:AS] (X | Y) | Z --> X | (Y | Z)"; _normalForm = choice(left.left(), choice(left.right(), right)); break out; } if (left.isSymbol()) { if (right.isSymbol()) { if (right.isLexLess(left)) { rule = "[CH:ba%1] b | a --> a | b\t(if a < b)"; _normalForm = choice(right,left); break out; } } if (right.isChoice()) { RegExp snd = right.left(); if (snd.isSymbol() && snd.isLexLess(left)) { rule = "[CH:ba%2] b | (a | X) --> a | (b | X)\t(if a < b)"; _normalForm = choice(snd, choice(left, right.right())); break out; } } } if (left.equals(right)) { rule = "[CH:XX1] X | X --> X"; _normalForm = left; break out; } if (right.isChoice() && left.equals(right.left())) { rule = "[CH:XX2] X | (X | Y) --> X | Y"; _normalForm = right; break out; } if (left.isConcat()) { if (left.right().isStar() && left.left().equals(right)) { rule = "[CH:XSX] X.Y* | X --> X.Y*"; _normalForm = left; break out; } if (left.left().isStar() && left.right().equals(right)) { rule = "[CH:SXX] Y*.X | X --> Y*.X"; _normalForm = left; break out; } if (left.right().isPlus() && left.left().equals(right)) { rule = "[CH:XPX] X.Y+ | X --> X.Y*"; _normalForm = concat(right, star(left.right().arg())); break out; } if (left.left().isPlus() && left.right().equals(right)) { rule = "[CH:PXX] Y+.X | X --> Y*.X"; _normalForm = concat(star(left.left().arg()), right); break out; } } if (right.isConcat()) { if (right.right().isStar() && right.left().equals(left)) { rule = "[CH:XXS] X | X.Y* --> X.Y*"; _normalForm = right; break out; } if (right.left().isStar() && right.right().equals(left)) { rule = "[CH:XSX] X | Y*.X --> Y*.X"; _normalForm = right; break out; } if (right.right().isPlus() && right.left().equals(left)) { rule = "[CH:XXP] X | X.Y+ --> X.Y*"; _normalForm = concat(left, star(right.right().arg())); break out; } if (right.left().isPlus() && right.right().equals(left)) { rule = "[CH:XPX] X | Y+.X --> Y*.X"; _normalForm = concat(star(right.left().arg()), left); break out; } } if (right.isPower() && right.power() == 2 && left.equals(right.arg())) { rule = "[CH:XN^2] X | X^2 --> X_1^2"; _normalForm = range(left,1,2); break out; } if (right.isRange() && right.lower() >= 0 && right.lower() <= 2 && left.equals(right.arg())) { switch (right.lower()) { case 0: rule = "[CH:XR0n] X | X_0^n --> X_0^n"; _normalForm = right; break out; case 1: rule = "[CH:XR1n] X | X_1^n --> X_1^n"; _normalForm = right; break out; case 2: rule = "[CH:XR2n] X | X_2^n --> X_1^n"; _normalForm = range(left, 1, right.upper()); break out; } } if (left.isPower()) { if (left.arg().equals(right)) { rule = "[CH:NX%1] X^n | X --> X | X^n"; _normalForm = choice(right,left); break out; } if (right.isPower()) { if (left.arg().equals(right.arg())) { if (left.power()+1 == right.power()) { rule = "[CH:NN_1] X^n | X^n+1 --> X_n^n+1"; _normalForm = range(left.arg(), left.power(), right.power()); break out; } if (right.power() < left.power()) { rule = "[CH:NN%1] X^n | X^m --> X^m | X^n\t(if mRegExpChoice. */ public final String toString () { return _left+" | "+_right; } public final String toNormalString () { if (!inNormalForm()) return _normalForm.toNormalString(); return _left.toNormalString()+" | "+_right.toNormalString(); } // // This prints with parentheses showing expicit nesting // // (for debugging purposes) // public final String toString () // { // String left = _left.toString(); // String right = _right.toString(); // if (_left.isChoice()) // 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()) // left = "("+left+")"; // if (_right.isChoice()) // right = "("+right+")"; // return left+" | "+right; // } }