FileDocCategorySizeDatePackage
RECompiler.javaAPI DocJava SE 5 API50957Fri Aug 26 14:55:28 BST 2005com.sun.org.apache.regexp.internal

RECompiler

public class RECompiler extends Object
A regular expression compiler class. This class compiles a pattern string into a regular expression program interpretable by the RE evaluator class. The 'recompile' command line tool uses this compiler to pre-compile regular expressions for use with RE. For a description of the syntax accepted by RECompiler and what you can do with regular expressions, see the documentation for the RE matcher class.
see
RE
see
recompile
author
Jonathan Locke
version
$Id: RECompiler.java,v 1.2 2000/05/14 21:04:17 jon Exp $

Fields Summary
char[]
instruction
int
lenInstruction
String
pattern
int
len
int
idx
int
parens
static final int
NODE_NORMAL
static final int
NODE_NULLABLE
static final int
NODE_TOPLEVEL
static final char
ESC_MASK
static final char
ESC_BACKREF
static final char
ESC_COMPLEX
static final char
ESC_CLASS
static final int
maxBrackets
static int
brackets
static int[]
bracketStart
static int[]
bracketEnd
static int[]
bracketMin
static int[]
bracketOpt
static final int
bracketUnbounded
static final int
bracketFinished
static Hashtable
hashPOSIX
Constructors Summary
public RECompiler()
Constructor. Creates (initially empty) storage for a regular expression program.

    
    
        hashPOSIX.put("alnum",     new Character(RE.POSIX_CLASS_ALNUM));
        hashPOSIX.put("alpha",     new Character(RE.POSIX_CLASS_ALPHA));
        hashPOSIX.put("blank",     new Character(RE.POSIX_CLASS_BLANK));
        hashPOSIX.put("cntrl",     new Character(RE.POSIX_CLASS_CNTRL));
        hashPOSIX.put("digit",     new Character(RE.POSIX_CLASS_DIGIT));
        hashPOSIX.put("graph",     new Character(RE.POSIX_CLASS_GRAPH));
        hashPOSIX.put("lower",     new Character(RE.POSIX_CLASS_LOWER));
        hashPOSIX.put("print",     new Character(RE.POSIX_CLASS_PRINT));
        hashPOSIX.put("punct",     new Character(RE.POSIX_CLASS_PUNCT));
        hashPOSIX.put("space",     new Character(RE.POSIX_CLASS_SPACE));
        hashPOSIX.put("upper",     new Character(RE.POSIX_CLASS_UPPER));
        hashPOSIX.put("xdigit",    new Character(RE.POSIX_CLASS_XDIGIT));
        hashPOSIX.put("javastart", new Character(RE.POSIX_CLASS_JSTART));
        hashPOSIX.put("javapart",  new Character(RE.POSIX_CLASS_JPART));
    
        // Start off with a generous, yet reasonable, initial size
        instruction = new char[128];
        lenInstruction = 0;
Methods Summary
voidallocBrackets()
Allocate storage for brackets only as needed

        // Allocate bracket stacks if not already done
        if (bracketStart == null)
        {
            // Allocate storage
            bracketStart = new int[maxBrackets];
            bracketEnd   = new int[maxBrackets];
            bracketMin   = new int[maxBrackets];
            bracketOpt   = new int[maxBrackets];

            // Initialize to invalid values
            for (int i = 0; i < maxBrackets; i++)
            {
                bracketStart[i] = bracketEnd[i] = bracketMin[i] = bracketOpt[i] = -1;
            }
        }
intatom()
Absorb an atomic character string. This method is a little tricky because it can un-include the last character of string if a closure operator follows. This is correct because *+? have higher precedence than concatentation (thus ABC* means AB(C*) and NOT (ABC)*).

return
Index of new atom node
exception
RESyntaxException Thrown if the regular expression has invalid syntax.

        // Create a string node
        int ret = node(RE.OP_ATOM, 0);

        // Length of atom
        int lenAtom = 0;

        // Loop while we've got input

        atomLoop:

        while (idx < len)
        {
            // Is there a next char?
            if ((idx + 1) < len)
            {
                char c = pattern.charAt(idx + 1);

                // If the next 'char' is an escape, look past the whole escape
                if (pattern.charAt(idx) == '\\")
                {
                    int idxEscape = idx;
                    escape();
                    if (idx < len)
                    {
                        c = pattern.charAt(idx);
                    }
                    idx = idxEscape;
                }

                // Switch on next char
                switch (c)
                {
                    case '{":
                    case '?":
                    case '*":
                    case '+":

                        // If the next character is a closure operator and our atom is non-empty, the
                        // current character should bind to the closure operator rather than the atom
                        if (lenAtom != 0)
                        {
                            break atomLoop;
                        }
                }
            }

            // Switch on current char
            switch (pattern.charAt(idx))
            {
                case ']":
                case '^":
                case '$":
                case '.":
                case '[":
                case '(":
                case ')":
                case '|":
                    break atomLoop;

                case '{":
                case '?":
                case '*":
                case '+":

                    // We should have an atom by now
                    if (lenAtom == 0)
                    {
                        // No atom before closure
                        syntaxError("Missing operand to closure");
                    }
                    break atomLoop;

                case '\\":

                    {
                        // Get the escaped character (advances input automatically)
                        int idxBeforeEscape = idx;
                        char c = escape();

                        // Check if it's a simple escape (as opposed to, say, a backreference)
                        if ((c & ESC_MASK) == ESC_MASK)
                        {
                            // Not a simple escape, so backup to where we were before the escape.
                            idx = idxBeforeEscape;
                            break atomLoop;
                        }

                        // Add escaped char to atom
                        emit(c);
                        lenAtom++;
                    }
                    break;

                default:

                    // Add normal character to atom
                    emit(pattern.charAt(idx++));
                    lenAtom++;
                    break;
            }
        }

        // This "shouldn't" happen
        if (lenAtom == 0)
        {
            internalError();
        }

        // Emit the atom length into the program
        instruction[ret + RE.offsetOpdata] = (char)lenAtom;
        return ret;
voidbracket()
Match bracket {m,n} expression put results in bracket member variables

exception
RESyntaxException Thrown if the regular expression has invalid syntax.

        // Current character must be a '{'
        if (idx >= len || pattern.charAt(idx++) != '{")
        {
            internalError();
        }

        // Next char must be a digit
        if (idx >= len || !Character.isDigit(pattern.charAt(idx)))
        {
            syntaxError("Expected digit");
        }

        // Get min ('m' of {m,n}) number
        StringBuffer number = new StringBuffer();
        while (idx < len && Character.isDigit(pattern.charAt(idx)))
        {
            number.append(pattern.charAt(idx++));
        }
        try
        {
            bracketMin[brackets] = Integer.parseInt(number.toString());
        }
        catch (NumberFormatException e)
        {
            syntaxError("Expected valid number");
        }

        // If out of input, fail
        if (idx >= len)
        {
            syntaxError("Expected comma or right bracket");
        }

        // If end of expr, optional limit is 0
        if (pattern.charAt(idx) == '}")
        {
            idx++;
            bracketOpt[brackets] = 0;
            return;
        }

        // Must have at least {m,} and maybe {m,n}.
        if (idx >= len || pattern.charAt(idx++) != ',")
        {
            syntaxError("Expected comma");
        }

        // If out of input, fail
        if (idx >= len)
        {
            syntaxError("Expected comma or right bracket");
        }

        // If {m,} max is unlimited
        if (pattern.charAt(idx) == '}")
        {
            idx++;
            bracketOpt[brackets] = bracketUnbounded;
            return;
        }

        // Next char must be a digit
        if (idx >= len || !Character.isDigit(pattern.charAt(idx)))
        {
            syntaxError("Expected digit");
        }

        // Get max number
        number.setLength(0);
        while (idx < len && Character.isDigit(pattern.charAt(idx)))
        {
            number.append(pattern.charAt(idx++));
        }
        try
        {
            bracketOpt[brackets] = Integer.parseInt(number.toString()) - bracketMin[brackets];
        }
        catch (NumberFormatException e)
        {
            syntaxError("Expected valid number");
        }

        // Optional repetitions must be > 0
        if (bracketOpt[brackets] <= 0)
        {
            syntaxError("Bad range");
        }

        // Must have close brace
        if (idx >= len || pattern.charAt(idx++) != '}")
        {
            syntaxError("Missing close brace");
        }
intbranch(int[] flags)
Compile one branch of an or operator (implements concatenation)

param
flags Flags passed by reference
return
Pointer to branch node
exception
RESyntaxException Thrown if the regular expression has invalid syntax.

        // Get each possibly closured piece and concat
        int node;
        int ret = node(RE.OP_BRANCH, 0);
        int chain = -1;
        int[] closureFlags = new int[1];
        boolean nullable = true;
        while (idx < len && pattern.charAt(idx) != '|" && pattern.charAt(idx) != ')")
        {
            // Get new node
            closureFlags[0] = NODE_NORMAL;
            node = closure(closureFlags);
            if (closureFlags[0] == NODE_NORMAL)
            {
                nullable = false;
            }

            // If there's a chain, append to the end
            if (chain != -1)
            {
                setNextOfEnd(chain, node);
            }

            // Chain starts at current
            chain = node;
        }

        // If we don't run loop, make a nothing node
        if (chain == -1)
        {
            node(RE.OP_NOTHING, 0);
        }

        // Set nullable flag for this branch
        if (nullable)
        {
            flags[0] |= NODE_NULLABLE;
        }
        return ret;
intcharacterClass()
Compile a character class

return
Index of class node
exception
RESyntaxException Thrown if the regular expression has invalid syntax.

        // Check for bad calling or empty class
        if (pattern.charAt(idx) != '[")
        {
            internalError();
        }

        // Check for unterminated or empty class
        if ((idx + 1) >= len || pattern.charAt(++idx) == ']")
        {
            syntaxError("Empty or unterminated class");
        }

        // Check for POSIX character class
        if (idx < len && pattern.charAt(idx) == ':")
        {
            // Skip colon
            idx++;

            // POSIX character classes are denoted with lowercase ASCII strings
            int idxStart = idx;
            while (idx < len && pattern.charAt(idx) >= 'a" && pattern.charAt(idx) <= 'z")
            {
                idx++;
            }
            
            // Should be a ":]" to terminate the POSIX character class
            if ((idx + 1) < len && pattern.charAt(idx) == ':" && pattern.charAt(idx + 1) == ']")
            {
                // Get character class
                String charClass = pattern.substring(idxStart, idx);

                // Select the POSIX class id
                Character i = (Character)hashPOSIX.get(charClass);
                if (i != null)
                {
                    // Move past colon and right bracket
                    idx += 2;

                    // Return new POSIX character class node
                    return node(RE.OP_POSIXCLASS, i.charValue());
                }
                syntaxError("Invalid POSIX character class '" + charClass + "'");
            }
            syntaxError("Invalid POSIX character class syntax");
        }

        // Try to build a class.  Create OP_ANYOF node
        int ret = node(RE.OP_ANYOF, 0);

        // Parse class declaration
        char CHAR_INVALID = Character.MAX_VALUE;
        char last = CHAR_INVALID;
        char simpleChar = 0;
        boolean include = true;
        boolean definingRange = false;
        int idxFirst = idx;
        char rangeStart = Character.MIN_VALUE;
        char rangeEnd;
        RERange range = new RERange();
        while (idx < len && pattern.charAt(idx) != ']")
        {

            switchOnCharacter:

            // Switch on character
            switch (pattern.charAt(idx))
            {
                case '^":
                    include = !include;
                    if (idx == idxFirst)
                    {
                        range.include(Character.MIN_VALUE, Character.MAX_VALUE, true);
                    }
                    idx++;
                    continue;

                case '\\":
                {
                    // Escape always advances the stream
                    char c;
                    switch (c = escape ())
                    {
                        case ESC_COMPLEX:
                        case ESC_BACKREF:

                            // Word boundaries and backrefs not allowed in a character class!
                            syntaxError("Bad character class");

                        case ESC_CLASS:

                            // Classes can't be an endpoint of a range
                            if (definingRange)
                            {
                                syntaxError("Bad character class");
                            }

                            // Handle specific type of class (some are ok)
                            switch (pattern.charAt(idx - 1))
                            {
                                case RE.E_NSPACE:
                                case RE.E_NDIGIT:
                                case RE.E_NALNUM:
                                    syntaxError("Bad character class");

                                case RE.E_SPACE:
                                    range.include('\t", include);
                                    range.include('\r", include);
                                    range.include('\f", include);
                                    range.include('\n", include);
                                    range.include('\b", include);
                                    range.include(' ", include);
                                    break;

                                case RE.E_ALNUM:
                                    range.include('a", 'z", include);
                                    range.include('A", 'Z", include);
                                    range.include('_", include);

                                    // Fall through!

                                case RE.E_DIGIT:
                                    range.include('0", '9", include);
                                    break;
                            }

                            // Make last char invalid (can't be a range start)
                            last = CHAR_INVALID;
                            break;

                        default:

                            // Escape is simple so treat as a simple char
                            simpleChar = c;
                            break switchOnCharacter;
                    }
                }
                continue;

                case '-":

                    // Start a range if one isn't already started
                    if (definingRange)
                    {
                        syntaxError("Bad class range");
                    }
                    definingRange = true;

                    // If no last character, start of range is 0
                    rangeStart = (last == CHAR_INVALID ? 0 : last);

                    // Premature end of range. define up to Character.MAX_VALUE
                    if ((idx + 1) < len && pattern.charAt(++idx) == ']")
                    {
                        simpleChar = Character.MAX_VALUE;
                        break;
                    }
                    continue;

                default:
                    simpleChar = pattern.charAt(idx++);
                    break;
            }

            // Handle simple character simpleChar
            if (definingRange)
            {
                // if we are defining a range make it now
                rangeEnd = simpleChar;

                // Actually create a range if the range is ok
                if (rangeStart >= rangeEnd)
                {
                    syntaxError("Bad character class");
                }
                range.include(rangeStart, rangeEnd, include);

                // We are done defining the range
                last = CHAR_INVALID;
                definingRange = false;
            }
            else
            {
                // If simple character and not start of range, include it
                if ((idx + 1) >= len || pattern.charAt(idx + 1) != '-")
                {
                    range.include(simpleChar, include);
                }
                last = simpleChar;
            }
        }

        // Shouldn't be out of input
        if (idx == len)
        {
            syntaxError("Unterminated character class");
        }

        // Absorb the ']' end of class marker
        idx++;

        // Emit character class definition
        instruction[ret + RE.offsetOpdata] = (char)range.num;
        for (int i = 0; i < range.num; i++)
        {
            emit((char)range.minRange[i]);
            emit((char)range.maxRange[i]);
        }
        return ret;
intclosure(int[] flags)
Compile a possibly closured terminal

param
flags Flags passed by reference
return
Index of closured node
exception
RESyntaxException Thrown if the regular expression has invalid syntax.

        // Before terminal
        int idxBeforeTerminal = idx;

        // Values to pass by reference to terminal()
        int[] terminalFlags = { NODE_NORMAL };

        // Get terminal symbol
        int ret = terminal(terminalFlags);

        // Or in flags from terminal symbol
        flags[0] |= terminalFlags[0];

        // Advance input, set NODE_NULLABLE flag and do sanity checks
        if (idx >= len)
        {
            return ret;
        }
        boolean greedy = true;
        char closureType = pattern.charAt(idx);
        switch (closureType)
        {
            case '?":
            case '*":

                // The current node can be null
                flags[0] |= NODE_NULLABLE;

            case '+":

                // Eat closure character
                idx++;

            case '{":

                // Don't allow blantant stupidity
                int opcode = instruction[ret + RE.offsetOpcode];
                if (opcode == RE.OP_BOL || opcode == RE.OP_EOL)
                {
                    syntaxError("Bad closure operand");
                }
                if ((terminalFlags[0] & NODE_NULLABLE) != 0)
                {
                    syntaxError("Closure operand can't be nullable");
                }
                break;
        }

        // If the next character is a '?', make the closure non-greedy (reluctant)
        if (idx < len && pattern.charAt(idx) == '?")
        {
            idx++;
            greedy = false;
        }

        if (greedy)
        {
            // Actually do the closure now
            switch (closureType)
            {
                case '{":
                {
                    // We look for our bracket in the list
                    boolean found = false;
                    int i;
                    allocBrackets();
                    for (i = 0; i < brackets; i++)
                    {
                        if (bracketStart[i] == idx)
                        {
                            found = true;
                            break;
                        }
                    }
                    
                    // If its not in the list we parse the {m,n}
                    if (!found)
                    {
                        if (brackets >= maxBrackets)
                        {
                            syntaxError("Too many bracketed closures (limit is 10)");
                        }
                        bracketStart[brackets] = idx;
                        bracket();
                        bracketEnd[brackets] = idx;
                        i = brackets++;
                    }
                    
                    // If there's a min, rewind stream and reparse
                    if (--bracketMin[i] > 0)
                    {
                        // Rewind stream and run it through again
                        idx = idxBeforeTerminal;
                        break;
                    }
                    
                    // Do the right thing for maximum ({m,})
                    if (bracketOpt[i] == bracketFinished)
                    {
                        // Drop through now and closure expression.
                        // We are done with the {m,} expr, so skip rest
                        closureType = '*";
                        bracketOpt[i] = 0;
                        idx = bracketEnd[i];
                    }
                    else
                        if (bracketOpt[i] == bracketUnbounded)
                        {
                            idx = idxBeforeTerminal;
                            bracketOpt[i] = bracketFinished;
                            break;
                        }
                        else
                            if (bracketOpt[i]-- > 0)
                            {
                                // Drop through to optionally close and then 'play it again sam!'
                                idx = idxBeforeTerminal;
                                closureType = '?";
                            }
                            else
                            {
                                // We are done. skip the rest of {m,n} expr
                                idx = bracketEnd[i];
                                break;
                            }
                }
                
                // Fall through!
                
                case '?":
                case '*":
                    
                    if (!greedy)
                    {
                        break;
                    }
                    
                    if (closureType == '?")
                    {
                        // X? is compiled as (X|)
                        nodeInsert(RE.OP_BRANCH, 0, ret);                 // branch before X
                        setNextOfEnd(ret, node (RE.OP_BRANCH, 0));        // inserted branch to option
                        int nothing = node (RE.OP_NOTHING, 0);            // which is OP_NOTHING
                        setNextOfEnd(ret, nothing);                       // point (second) branch to OP_NOTHING
                        setNextOfEnd(ret + RE.nodeSize, nothing);         // point the end of X to OP_NOTHING node
                    }
                    
                    if (closureType == '*")
                    {
                        // X* is compiled as (X{gotoX}|)
                        nodeInsert(RE.OP_BRANCH, 0, ret);                         // branch before X
                        setNextOfEnd(ret + RE.nodeSize, node(RE.OP_BRANCH, 0));   // end of X points to an option
                        setNextOfEnd(ret + RE.nodeSize, node(RE.OP_GOTO, 0));     // to goto
                        setNextOfEnd(ret + RE.nodeSize, ret);                     // the start again
                        setNextOfEnd(ret, node(RE.OP_BRANCH, 0));                 // the other option is
                        setNextOfEnd(ret, node(RE.OP_NOTHING, 0));                // OP_NOTHING
                    }
                    break;
                    
                case '+":
                {
                    // X+ is compiled as X({gotoX}|)
                    int branch;
                    branch = node(RE.OP_BRANCH, 0);                   // a new branch
                    setNextOfEnd(ret, branch);                        // is added to the end of X
                    setNextOfEnd(node(RE.OP_GOTO, 0), ret);           // one option is to go back to the start
                    setNextOfEnd(branch, node(RE.OP_BRANCH, 0));      // the other option
                    setNextOfEnd(ret, node(RE.OP_NOTHING, 0));        // is OP_NOTHING
                }
                break;
            }
        }
        else
        {
            // Add end after closured subexpr
            setNextOfEnd(ret, node(RE.OP_END, 0));

            // Actually do the closure now
            switch (closureType)
            {
                case '?":
                    nodeInsert(RE.OP_RELUCTANTMAYBE, 0, ret);
                    break;
                    
                case '*":       
                    nodeInsert(RE.OP_RELUCTANTSTAR, 0, ret);
                    break;

                case '+":
                    nodeInsert(RE.OP_RELUCTANTPLUS, 0, ret);
                    break;
            }

            // Point to the expr after the closure
            setNextOfEnd(ret, lenInstruction);          
        }
        return ret;
public REProgramcompile(java.lang.String pattern)
Compiles a regular expression pattern into a program runnable by the pattern matcher class 'RE'.

param
pattern Regular expression pattern to compile (see RECompiler class for details).
return
A compiled regular expression program.
exception
RESyntaxException Thrown if the regular expression has invalid syntax.
see
RECompiler
see
RE

        // Initialize variables for compilation
        this.pattern = pattern;                         // Save pattern in instance variable
        len = pattern.length();                         // Precompute pattern length for speed
        idx = 0;                                        // Set parsing index to the first character
        lenInstruction = 0;                             // Set emitted instruction count to zero
        parens = 1;                                     // Set paren level to 1 (the implicit outer parens)
        brackets = 0;                                   // No bracketed closures yet

        // Initialize pass by reference flags value
        int[] flags = { NODE_TOPLEVEL };

        // Parse expression
        expr(flags);

        // Should be at end of input
        if (idx != len)
        {
            if (pattern.charAt(idx) == ')")
            {
                syntaxError("Unmatched close paren");
            }
            syntaxError("Unexpected input remains");
        }

        // Return the result
        char[] ins = new char[lenInstruction];
        System.arraycopy(instruction, 0, ins, 0, lenInstruction);
        return new REProgram(ins);
voidemit(char c)
Emit a single character into the program stream.

param
c Character to add

        // Make room for character
        ensure(1);

        // Add character
        instruction[lenInstruction++] = c;
voidensure(int n)
Ensures that n more characters can fit in the program buffer. If n more can't fit, then the size is doubled until it can.

param
n Number of additional characters to ensure will fit.

        // Get current program length
        int curlen = instruction.length;

        // If the current length + n more is too much
        if (lenInstruction + n >= curlen)
        {
            // Double the size of the program array until n more will fit
            while (lenInstruction + n >= curlen)
            {
                curlen *= 2;
            }

            // Allocate new program array and move data into it
            char[] newInstruction = new char[curlen];
            System.arraycopy(instruction, 0, newInstruction, 0, lenInstruction);
            instruction = newInstruction;
        }
charescape()
Match an escape sequence. Handles quoted chars and octal escapes as well as normal escape characters. Always advances the input stream by the right amount. This code "understands" the subtle difference between an octal escape and a backref. You can access the type of ESC_CLASS or ESC_COMPLEX or ESC_BACKREF by looking at pattern[idx - 1].

return
ESC_* code or character if simple escape
exception
RESyntaxException Thrown if the regular expression has invalid syntax.

        // "Shouldn't" happen
        if (pattern.charAt(idx) != '\\")
        {
            internalError();
        }

        // Escape shouldn't occur as last character in string!
        if (idx + 1 == len)
        {
            syntaxError("Escape terminates string");
        }

        // Switch on character after backslash
        idx += 2;
        char escapeChar = pattern.charAt(idx - 1);
        switch (escapeChar)
        {
            case RE.E_BOUND:
            case RE.E_NBOUND:
                return ESC_COMPLEX;

            case RE.E_ALNUM:
            case RE.E_NALNUM:
            case RE.E_SPACE:
            case RE.E_NSPACE:
            case RE.E_DIGIT:
            case RE.E_NDIGIT:
                return ESC_CLASS;

            case 'u":
            case 'x":
                {
                    // Exact required hex digits for escape type
                    int hexDigits = (escapeChar == 'u" ? 4 : 2);

                    // Parse up to hexDigits characters from input
                    int val = 0;
                    for ( ; idx < len && hexDigits-- > 0; idx++)
                    {
                        // Get char
                        char c = pattern.charAt(idx);

                        // If it's a hexadecimal digit (0-9)
                        if (c >= '0" && c <= '9")
                        {
                            // Compute new value
                            val = (val << 4) + c - '0";
                        }
                        else
                        {
                            // If it's a hexadecimal letter (a-f)
                            c = Character.toLowerCase(c);
                            if (c >= 'a" && c <= 'f")
                            {
                                // Compute new value 
                                val = (val << 4) + (c - 'a") + 10;
                            }
                            else
                            {
                                // If it's not a valid digit or hex letter, the escape must be invalid
                                // because hexDigits of input have not been absorbed yet.
                                syntaxError("Expected " + hexDigits + " hexadecimal digits after \\" + escapeChar);
                            }
                        }
                    }
                    return (char)val;
                }

            case 't":
                return '\t";

            case 'n":
                return '\n";

            case 'r":
                return '\r";

            case 'f":
                return '\f";

            case '0":
            case '1":
            case '2":
            case '3":
            case '4":
            case '5":
            case '6":
            case '7":
            case '8":
            case '9":

                // An octal escape starts with a 0 or has two digits in a row
                if ((idx < len && Character.isDigit(pattern.charAt(idx))) || escapeChar == '0")
                {
                    // Handle \nnn octal escapes
                    int val = escapeChar - '0";
                    if (idx < len && Character.isDigit(pattern.charAt(idx)))
                    {
                        val = ((val << 3) + (pattern.charAt(idx++) - '0"));
                        if (idx < len && Character.isDigit(pattern.charAt(idx)))
                        {
                            val = ((val << 3) + (pattern.charAt(idx++) - '0"));
                        }
                    }
                    return (char)val;
                }

                // It's actually a backreference (\[1-9]), not an escape
                return ESC_BACKREF;

            default:

                // Simple quoting of a character
                return escapeChar;
        }
intexpr(int[] flags)
Compile an expression with possible parens around it. Paren matching is done at this level so we can tie the branch tails together.

param
flags Flag value passed by reference
return
Node index of expression in instruction array
exception
RESyntaxException Thrown if the regular expression has invalid syntax.

        // Create open paren node unless we were called from the top level (which has no parens)
        boolean paren = false;
        int ret = -1;
        int closeParens = parens;
        if ((flags[0] & NODE_TOPLEVEL) == 0 && pattern.charAt(idx) == '(")
        {
            idx++;
            paren = true;
            ret = node(RE.OP_OPEN, parens++);
        }
        flags[0] &= ~NODE_TOPLEVEL;

        // Create a branch node
        int branch = branch(flags);
        if (ret == -1)
        {
            ret = branch;
        }
        else
        {
            setNextOfEnd(ret, branch);
        }

        // Loop through branches
        while (idx < len && pattern.charAt(idx) == '|")
        {
            idx++;
            branch = branch(flags);
            setNextOfEnd(ret, branch);
        }

        // Create an ending node (either a close paren or an OP_END)
        int end;
        if (paren)
        {
            if (idx < len && pattern.charAt(idx) == ')")
            {
                idx++;
            }
            else
            {
                syntaxError("Missing close paren");
            }
            end = node(RE.OP_CLOSE, closeParens);
        }
        else
        {
            end = node(RE.OP_END, 0);
        }

        // Append the ending node to the ret nodelist
        setNextOfEnd(ret, end);

        // Hook the ends of each branch to the end node
        for (int next = -1, i = ret; next != 0; next = instruction[i + RE.offsetNext], i += next)
        {
            // If branch, make the end of the branch's operand chain point to the end node.
            if (instruction[i + RE.offsetOpcode] == RE.OP_BRANCH)
            {
                setNextOfEnd(i + RE.nodeSize, end);
            }
        }

        // Return the node list
        return ret;
voidinternalError()
Throws a new internal error exception

exception
Error Thrown in the event of an internal error.

        throw new Error("Internal error!");
intnode(char opcode, int opdata)
Adds a new node

param
opcode Opcode for node
param
opdata Opdata for node (only the low 16 bits are currently used)
return
Index of new node in program

        // Make room for a new node
        ensure(RE.nodeSize);

        // Add new node at end
        instruction[lenInstruction + RE.offsetOpcode] = opcode;
        instruction[lenInstruction + RE.offsetOpdata] = (char)opdata;
        instruction[lenInstruction + RE.offsetNext] = 0;
        lenInstruction += RE.nodeSize;

        // Return index of new node
        return lenInstruction - RE.nodeSize;
voidnodeInsert(char opcode, int opdata, int insertAt)
Inserts a node with a given opcode and opdata at insertAt. The node relative next pointer is initialized to 0.

param
opcode Opcode for new node
param
opdata Opdata for new node (only the low 16 bits are currently used)
param
insertAt Index at which to insert the new node in the program

        // Make room for a new node
        ensure(RE.nodeSize);

        // Move everything from insertAt to the end down nodeSize elements
        System.arraycopy(instruction, insertAt, instruction, insertAt + RE.nodeSize, lenInstruction - insertAt);
        instruction[insertAt + RE.offsetOpcode] = opcode;
        instruction[insertAt + RE.offsetOpdata] = (char)opdata;
        instruction[insertAt + RE.offsetNext] = 0;
        lenInstruction += RE.nodeSize;
voidsetNextOfEnd(int node, int pointTo)
Appends a node to the end of a node chain

param
node Start of node chain to traverse
param
pointTo Node to have the tail of the chain point to

        // Traverse the chain until the next offset is 0
        int next;
        while ((next = instruction[node + RE.offsetNext]) != 0)
        {
            node += next;
        }

        // Point the last node in the chain to pointTo.
        instruction[node + RE.offsetNext] = (char)(short)(pointTo - node);
voidsyntaxError(java.lang.String s)
Throws a new syntax error exception

exception
RESyntaxException Thrown if the regular expression has invalid syntax.

        throw new RESyntaxException(s);
intterminal(int[] flags)
Match a terminal node.

param
flags Flags
return
Index of terminal node (closeable)
exception
RESyntaxException Thrown if the regular expression has invalid syntax.

        switch (pattern.charAt(idx))
        {
        case RE.OP_EOL:
        case RE.OP_BOL:
        case RE.OP_ANY:
            return node(pattern.charAt(idx++), 0);

        case '[":
            return characterClass();

        case '(":
            return expr(flags);

        case ')":
            syntaxError("Unexpected close paren");

        case '|":
            internalError();

        case ']":
            syntaxError("Mismatched class");

        case 0:
            syntaxError("Unexpected end of input");

        case '?":
        case '+":
        case '{":
        case '*":
            syntaxError("Missing operand to closure");

        case '\\":
            {
                // Don't forget, escape() advances the input stream!
                int idxBeforeEscape = idx;

                // Switch on escaped character
                switch (escape())
                {
                    case ESC_CLASS:
                    case ESC_COMPLEX:
                        flags[0] &= ~NODE_NULLABLE;
                        return node(RE.OP_ESCAPE, pattern.charAt(idx - 1));

                    case ESC_BACKREF:
                        {
                            char backreference = (char)(pattern.charAt(idx - 1) - '0");
                            if (parens <= backreference)
                            {
                                syntaxError("Bad backreference");
                            }
                            flags[0] |= NODE_NULLABLE;
                            return node(RE.OP_BACKREF, backreference);
                        }

                    default:

                        // We had a simple escape and we want to have it end up in
                        // an atom, so we back up and fall though to the default handling
                        idx = idxBeforeEscape;
                        flags[0] &= ~NODE_NULLABLE;
                        break;
                }
            }
        }

        // Everything above either fails or returns.
        // If it wasn't one of the above, it must be the start of an atom.
        flags[0] &= ~NODE_NULLABLE;
        return atom();