RegExpConcat (API documentation of hlt.language packages)
Date: 2013-01-30

hlt.language.util

## Class RegExpConcat

- java.lang.Object
- - hlt.language.util.RegExp
  - - hlt.language.util.RegExpTwo
    - - hlt.language.util.RegExpConcat

-     public class RegExpConcat
      extends RegExpTwo

  This class is a concrete implementation of the abstract class `RegExpTwo` to represent concatenation.
  Version:
    Last modified on Fri Oct 19 17:35:13 2012 by hak
  Author:
    Hassan Aït-Kaci
  Copyright:
    © Hassan Aït-Kaci

- - ### Field Summary

    - ### Fields inherited from class hlt.language.util.RegExpTwo

      `NN, NO, NP, NR, NS, NX, ON, OO, OP, OR, OS, OX, PN, PO, PP, PR, PS, PX, RN, RO, RP, RR, RS, RX, SN, SO, SP, SR, SS, SX, XN, XO, XP, XR, XS, XX`

    - ### Fields inherited from class hlt.language.util.RegExp

      `BINARY_EXP, CHOICE_EXP, CONCAT_EXP, EMPTY, EMPTY_EXP, OPTION_EXP, PLUS_EXP, POWER_EXP, RANGE_EXP, STAR_EXP, SYMBOL_EXP, UNARY_EXP`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `RegExpConcat(RegExp left, RegExp right)` Constructs a `RegExpConcat` with the two specified `RegExp`'s.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `RegExp` | `deepCopy()` This returns a deep copy of this `RegExp`.
    `RegExp` | `normalize()` This returns this `RegExpConcat`'s normal form according to the following (conditional) rewrite rules.
    `RegExp` | `shallowCopy()` This returns a shallow copy of this `RegExp`.
    `java.lang.String` | `toString()` Returns a printable form for this `RegExpConcat`.
    `int` | `type()` This returns the specific type identifying this `RegExp`.

    - ### Methods inherited from class hlt.language.util.RegExpTwo

      `equals, getLeft, getRight, normalLeft, normalRight`

    - ### Methods inherited from class hlt.language.util.RegExp

      `cleanup, isBinary, isChoice, isConcat, isEmpty, isLexLess, isOption, isPlus, isPower, isRange, isStar, isSymbol, isUnary, normEquals, noTrace, tag, toggleTrace, toNormalString, trace, tracing`

    - ### Methods inherited from class java.lang.Object

      `getClass, hashCode, notify, notifyAll, wait, wait, wait`

- - ### Constructor Detail

    - #### RegExpConcat

          public RegExpConcat(RegExp left,
                      RegExp right)

      Constructs a `RegExpConcat` with the two specified `RegExp`'s.

  - ### Method Detail

    - #### shallowCopy

          public final RegExp shallowCopy()

      Description copied from class: `RegExp`
      This returns a shallow copy of this `RegExp`.
      Specified by:
        `shallowCopy` in class `RegExp`

    - #### deepCopy

          public final RegExp deepCopy()

      Description copied from class: `RegExp`
      This returns a deep copy of this `RegExp`.
      Specified by:
        `deepCopy` in class `RegExp`

    - #### type

          public final int type()

      Description copied from class: `RegExp`
      This returns the specific type identifying this `RegExp`.
      Specified by:
        `type` in class `RegExp`

    - #### normalize

          public RegExp normalize()

      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:

      1. `left()` or `right()` is `EMPTY`;
      2. `left()` and `right()` form a matching pair, or this is of the form `A.(B.C)`, where `A` and `B` form a matching pair;
      3. the rest.
      We simply refer to a rule in each group as (for lack of better terms!):
      1. an empty-rule,
      2. a pair-rule,
      3. 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`

      ### 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`

      ### 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 in `red` are 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`, `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`

      - (redundant) `[CO:OO1]` `X?.X?` → `X_0^2`
      - (redundant) `[CO:OO2]` `X?.(X?.Y)` → `X_0^2.Y`

      - `[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`

      - (redundant) `[CO:PP1]` `X+.X+` → `X_2~`
      - (redundant) `[CO:PP2]` `X+.(X+.Y)` → `X_2~.Y`

      - `[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`

      - (redundant) `[CO:SS1]` `X\*.X\*` → `X\*`
      - (redundant) `[CO:SS2]` `X\*.(X\*.Y)` → `X\*.Y`

      - `[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`

      - (redundant) `[CO:NN1]` `X^n.X^q` → `X^n+q`
      - (redundant) `[CO:NN2]` `X^n.(X^q.Y)` → `X^n+q.Y`

      - `[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`

      - (redundant) `[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` ********************************************************************
      Specified by:
        `normalize` in class `RegExp`

    - #### toString

          public final java.lang.String toString()

      Returns a printable form for this `RegExpConcat`.
      Overrides:
        `toString` in class `java.lang.Object`