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