//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ // PLEASE DO NOT EDIT WITHOUT THE EXPLICIT CONSENT OF THE AUTHOR! \\ //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ package hlt.language.util; import hlt.language.tools.Misc; /** * This abstract class defines a representation for a regular expression * (RE) on an alphabet of Object's (as opposed to just * char's as done in most RE representation packages meant for * character word pattern-matching such as java.util.regex). * *

* * The purpose of this class and its subclasses is to allow the symbolic * manipulation of RE's on any alphabet, providing methods for reading, * writing, equality, and normalization to canonical form. RE matching * is not the intended use, although it should be simple to have that as * well by encoding each Object in the alphabet with a * char and delegate the work to java.util.regex. * *

* * This is an abstract class. It has the following subclasses: * *

* *

* * @version Last modified on Mon Mar 26 10:05:16 2018 by hak * @author Hassan Aït-Kaci * @copyright © Hassan Aït-Kaci */ public abstract class RegExp { /** * Returns the canonical RegExpSymbol.EMPTY symbol. */ public static final RegExpSymbol empty () { return RegExpSymbol.EMPTY; } /** * This is a protected field inherited by all subclasses of * RegExp. It is initialized to null and meant to * hold the normal form of this RegExp which is computed by * the normalize() method the first time the * normalForm() method is invoked on this. The result is then * cached in this field so that any further calls to * normalForm() will simply return the expression computed * and saved once and for all in this field by the * normalize() method. */ protected RegExp _normalForm = null; /** * This returns this RegExp's normal form, which is computed * by the normalize() method the first time this * normalForm() method is invoked on a RegExp. The * result is then cached so that any further calls to * normalForm() will simply return the expression computed * and saved once and for all for this RegExp by the * normalize() method. * * @return this regular expression's normal form */ public final RegExp normalForm () { if (_normalForm == null) normalize(); return _normalForm; } /** * This checks whether this expression's normal form has been reached, * and if not proceeds to normalize it further. */ protected final void checkNormalForm () { if (_normalForm == null) // no rule applied: this was already in normal form _normalForm = this; else _normalForm = _normalForm.normalForm(); } /** * Returns true if this expression is in normal form. * N.B. This will compute its normal form as a side effet! */ public final boolean inNormalForm () { return this == normalForm(); } /** * This is the method that computes this RegExp's normal * form. It is implemented by each concrete subclass of * RegExp; namely,: * * * */ abstract public void normalize (); /** * Returns true iff the specified RegExp's normal * form is equal to this RegExp's normal form. */ public final boolean normEquals (RegExp other) { return normalForm().equals(other.normalForm()); } /** * This returns a shallow copy of this RegExp. */ abstract public RegExp shallowCopy (); /** * This returns a deep copy of this RegExp. */ abstract public RegExp deepCopy (); /** * This simply returns its argument, unless null - in which * case it returns RegExpSymbol.EMPTY. */ public final RegExp cleanup (RegExp e) { return e == null ? RegExpSymbol.EMPTY : e; } /** * Constants identifying each specific type of RegExp. */ public final static int EMPTY_EXP = 1<<0; public final static int SYMBOL_EXP = 1<<1; public final static int OPTION_EXP = 1<<2; public final static int PLUS_EXP = 1<<3; public final static int STAR_EXP = 1<<4; public final static int POWER_EXP = 1<<5; public final static int RANGE_EXP = 1<<6; public final static int CHOICE_EXP = 1<<7; public final static int CONCAT_EXP = 1<<8; public final static int UNARY_EXP = OPTION_EXP | PLUS_EXP | STAR_EXP | POWER_EXP | RANGE_EXP ; public final static int BINARY_EXP = CONCAT_EXP | CHOICE_EXP ; /** * This returns the specific type identifying this RegExp. */ abstract public int type (); /** * This returns a string identifying this RegExp's specific * type. */ final public String tag () { switch (type()) { case EMPTY_EXP: return "Empty"; case SYMBOL_EXP: return "Symbol"; case CHOICE_EXP: return "Choice"; case CONCAT_EXP: return "Concat"; case OPTION_EXP: return "Option"; case PLUS_EXP: return "Plus"; case POWER_EXP: return "Power"; case RANGE_EXP: return "PowerRange"; case STAR_EXP: return "Star"; } return "Unknown"; } //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// /** * Each of the following methods tests whether this is a specific * RegExp type or form (i.e., unary or binary). */ public final boolean isEmpty () { return this == RegExpSymbol.EMPTY; } public final boolean isSymbol () { return type() == SYMBOL_EXP; } public final boolean isChoice () { return type() == CHOICE_EXP; } public final boolean isConcat () { return type() == CONCAT_EXP; } public final boolean isOption () { return type() == OPTION_EXP; } public final boolean isPlus () { return type() == PLUS_EXP; } public final boolean isPower () { return type() == POWER_EXP; } public final boolean isRange () { return type() == RANGE_EXP; } public final boolean isStar () { return type() == STAR_EXP; } public final boolean isUnary () { return (type() & UNARY_EXP) == type(); } public final boolean isBinary () { return (type() & BINARY_EXP) == type(); } //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// /** * Each of the following methods is a convenient shorthand for its * specific corresponding constructor. There is none * for RegExpSymbol because * it has no public constructor: it relies on a factory. * *

* * These really are just shorthands to avoid cluttering the code of * the normalize() methods with a proliferation of lengthy * new constuctor expressions as required by Java. * *

* * N.B.: This * adds (a useless) level of indirection. Ideally, these should be * macros rather than methods! */ protected final RegExpOption option (RegExp arg) { return new RegExpOption(arg); } protected final RegExpPlus plus (RegExp arg) { return new RegExpPlus(arg); } protected final RegExpStar star (RegExp arg) { return new RegExpStar(arg); } protected final RegExpPower power (RegExp arg, int power) { return new RegExpPower(arg,power); } protected final RegExpPowerRange range (RegExp arg, int lower, int upper) { return new RegExpPowerRange(arg,lower,upper); } protected final RegExpPowerRange range (RegExp arg, int lower) { return new RegExpPowerRange(arg,lower); } protected final RegExpConcat concat (RegExp left, RegExp right) { return new RegExpConcat(left,right); } protected final RegExpChoice choice (RegExp left, RegExp right) { return new RegExpChoice(left,right); } //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// /** * Each of the following methods performs an appropriate type cast to * this RegExp before extracting a component from its normal * form. This compoment being defined only for the type used in the * cast, all these methods assume that this has been * ascertained to be of the appropriate type so that the cast is * garanteed to be correct. * *

* * These really are just shorthands to avoid cluttering the code of * the normalize() methods with a proliferation of type-cast * expressions as required by Java. * *

* * N.B.: This * adds (a useless) level of indirection. Ideally, these should be * macros rather than methods! */ /** * Assuming that this RegExp is a RegExpOne, * returns its argument. */ protected final RegExp arg () { return ((RegExpOne)this).getArg(); } /** * Assuming that this RegExp is a RegExpOne, * returns its normalized argument. */ protected final RegExp narg () { return ((RegExpOne)this).normalArg(); } /** * Assuming that this RegExp is a RegExpTwo, * returns its left part. */ protected final RegExp left () { return ((RegExpTwo)this).getLeft(); } /** * Assuming that this RegExp is a RegExpTwo, * returns its normalized left part. */ protected final RegExp nleft () { return ((RegExpTwo)this).normalLeft(); } /** * Assuming that this RegExp is a RegExpTwo, * returns its right part. */ protected final RegExp right () { return ((RegExpTwo)this).getRight(); } /** * Assuming that this RegExp is a RegExpTwo, * returns its normalized right part. */ protected final RegExp nright () { return ((RegExpTwo)this).normalRight(); } /** * Assuming that this RegExp is a RegExpPower, * returns its exponent. */ protected final int power () { return ((RegExpPower)this).getPower(); } /** * Assuming that this RegExp is a RegExpPowerRange, * returns its lower exponent. */ protected final int lower () { return ((RegExpPowerRange)this).getLower(); } /** * Assuming that this RegExp is a RegExpPowerRange, * returns its upper exponent. */ protected final int upper () { return ((RegExpPowerRange)this).getUpper(); } //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// /** * This is a constant representing the cardinality of the set of * natural numbers. */ protected static int OMEGA = Integer.MAX_VALUE; /** * This returns the sum of the two specified integers whenever this * sum does not exceed OMEGA; otherwise, returns * OMEGA. */ protected final int plus (int x, int y) { if (x <= OMEGA && y <= OMEGA-x) return x+y; return OMEGA; } /** * This returns the product of the two specified integers whenever * this product does not exceed OMEGA; otherwise, returns * OMEGA. */ protected final int times (int x, int y) { if (x == 0 || y == 0) return 0; if (x <= OMEGA && y <= OMEGA/x) return x*y; return OMEGA; } /** * Returns the printable form for this RegExp's normal form. */ public abstract String toNormalString (); // { // return normalForm().toString(); // } public final boolean isLexLess (RegExp other) { return this.toString().compareTo(other.toString()) < 0; } /** * This is a simple tracing facility printing on System.err * how this RegExp gets transformed into its normal form * using the specified rule. */ protected final void traceRule (String rule) { if (tracing() && rule != null) { System.err.println(Misc.repeat(70,'-')); System.err.println(tag()+" Rule: "+rule+"\n\n\t" +this+" --> "+_normalForm+"\n"); } } /** * A flag indicating whether tracing mode is on. */ private static boolean _tracing = false; /** * Tests whether tracing is on. */ public static final boolean tracing () { return _tracing; } /** * Enables tracing mode on. */ public static final void trace () { _tracing = true; } /** * Disables tracing mode. */ public static final void noTrace () { _tracing = false; } /** * Toggles tracing mode. */ public static final void toggleTrace () { _tracing = !_tracing; } }