Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   *
   * Copyright 1997-2010 Oracle and/or its affiliates. All rights reserved.
   *
   * Oracle and Java are registered trademarks of Oracle and/or its affiliates.
   * Other names may be trademarks of their respective owners.
   *
   * The contents of this file are subject to the terms of either the GNU
  * General Public License Version 2 only ("GPL") or the Common
  * Development and Distribution License("CDDL") (collectively, the
  * "License"). You may not use this file except in compliance with the
  * License. You can obtain a copy of the License at
  * http://www.netbeans.org/cddl-gplv2.html
  * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
  * specific language governing permissions and limitations under the
  * License.  When distributing the software, include this License Header
  * Notice in each file and include the License file at
  * nbbuild/licenses/CDDL-GPL-2-CP.  Oracle designates this
  * particular file as subject to the "Classpath" exception as provided
  * by Oracle in the GPL Version 2 section of the License file that
  * accompanied this code. If applicable, add the following below the
  * License Header, with the fields enclosed by brackets [] replaced by
  * your own identifying information:
  * "Portions Copyrighted [year] [name of copyright owner]"
  *
  * Contributor(s):
  *
  * The Original Software is NetBeans. The Initial Developer of the Original
  * Software is Sun Microsystems, Inc. Portions Copyright 1997-2007 Sun
  * Microsystems, Inc. All Rights Reserved.
  *
  * If you wish your version of this file to be governed by only the CDDL
  * or only the GPL Version 2, indicate your decision by adding
  * "[Contributor] elects to include this software in this distribution
  * under the [CDDL or GPL Version 2] license." If you do not indicate a
  * single choice of license, a recipient has the option to distribute
  * your version of this file under either the CDDL, the GPL Version 2 or
  * to extend the choice of license to its licensees as provided above.
  * However, if you add GPL Version 2 code and therefore, elected the GPL
  * Version 2 license, then the option applies only if the new code is
  * made subject to such option by the copyright holder.
  */
 
 
 package org.netbeans.modules.i18n.regexp;
 
 import java.util.List;
Parser of regular expressions.

Author(s):
Marian Petras
 
 public class Parser {

    
regular expression being parsed by this parser
 
     private String regexp;

    
names of string tokens {token-name} to be recognized by this parser. The array contains just the names (without '{' and '}').
 
     private String[] tokenNames;

    
length of the longest string token name

See also:
tokenNames
 
     private int maxTokenLength;

    
Parses the given regular expression.

Parameters:
regexp regular expression to parse
Returns:
root of a syntax tree of the regular expression
Throws:
java.lang.IllegalArgumentException if the regular expression is null
ParseException if the given expression contained a syntax error
 
     public static TreeNodeRoot parse(String regexp)
             throws IllegalArgumentExceptionParseException {
         return parse(regexpnull);
     }

    
Parses the given regular expression with tokens enclosed between { and }.

Parameters:
regexp regular expression to parse
tokenNames names of a tokens to be recognized; or null if no tokens should be recognized
Returns:
root of a syntax tree of the regular expression
Throws:
java.lang.IllegalArgumentException if the regular expression is null
ParseException if the given expression contained a syntax error
    public static TreeNodeRoot parse(String regexpString tokenNames[])
            throws IllegalArgumentExceptionParseException {
        Parser parser = new Parser(regexp);
        if (tokenNames != null && tokenNames.length != 0) {
            parser.setTokenNames(tokenNames);
        }
        return parser.parse();
    }

    
Constructs a parser for parsing a given regular expression.

Parameters:
regexp regular expression to parse
Throws:
java.lang.IllegalArgumentException if the argument is null
    Parser(String regexp) {
        if (regexp == null) {
            throw new IllegalArgumentException();
        }
        this. = regexp;
    }

    
    private void setTokenNames(String[] tokenNames) {
        if (tokenNames != null && tokenNames.length != 0) {
            this. = tokenNames;
             = tokenNames[0].length();
            for (int i = 1; i < tokenNames.lengthi++) {
                if (tokenNames[i].length() > ) {
                     = tokenNames[i].length();
                }
            }
        } else {
            this. = null;
             = 0;
        }
    }

    
Performs parsing of the regular expression.

Returns:
root of a syntax tree of the regular expression
Throws:
ParseException if the expression contained a syntax error
    TreeNodeRoot parse() throws ParseException {
        TreeNodeRoot result;
        TreeNode multiRegexpNode = null;
        int begin = 0;
        int end = .length();
        boolean initialPart = false;
        boolean finalPart = false;
        if (begin == end) {
            return null;
        }
        /* Handle regular expressions "^", "$" and "^$": */
        if (.charAt(0) == '^') {
            initialPart = true;
            begin++;
        }
        if ((end == begin + 1) && (.charAt(begin) == '$')) {
            finalPart = true;
            end--;
        }
        /*
         * The following special regular expressions are now handled:
         *
         *   <empty> ...  returned <null>
         *   ^   .......  begin=1, end=1, initialpart=true,  finalPart=false
         *   ^$  .......  begin=1, end=1, initialpart=true,  finalPart=true
         *   $   .......  begin=0, end=0, initialPart=false, finalPart=true
         *
         * In all the cases except for the empty regular expression,
         * it is true that (begin == end). So we know that if (begin != end),
         * there must be something between the optional characters '^' and '$'.
         * If nothing is found, it singals a syntax error.
         */
        if (begin != end) {
            multiRegexpNode = parseMultiRegexp(beginend);
            /*
             * If nothing was found between the (optional) initial '^'
             * and the (optional) final '$', it is a syntax error:
             */
            if (multiRegexpNode == null) {
                throwParseException(begin);
            }
            /*
             * If there is a single character pending after the recognized
             * regular expression and it is '$', it is the (optional) final '$':
             */
            if ((multiRegexpNode.end == end - 1)
                    && (.charAt(end - 1) == '$')) {
                finalPart = true;
                end--;
            }
            /*
             * If some characters between the (optional) initial '^'
             * and the (optional) final '$' have been left unrecognized,
             * it is a syntax error:
             */
            if (multiRegexpNode.end != end) {
                throwParseException(begin);
            }
        }
        String attribs = null;
        if (initialPart || finalPart) {
            StringBuilder buf = new StringBuilder(2);
            if (initialPart) {
                buf.append('^');
            }
            if (finalPart) {
                buf.append('$');
            }
            attribs = buf.toString();
        }
        result = new TreeNodeRoot(attribs);
        if (multiRegexpNode != null) {
            result.add(multiRegexpNode);
        }
        return result;
    }


    
    private void throwParseException(int positionthrows ParseException {
        throw new ParseException(position);
    }


    
    private TreeNode parseMultiRegexp(int startint end)
            throws ParseException {
        if (start == end) {
            return null;
        }
        TreeNode regexpSequenceNode = parseRegexpSequence(startend);
        if (regexpSequenceNode == null) {
            return null;
        }
        List<TreeNodealternatives = new ArrayList<TreeNode>(4);
        alternatives.add(regexpSequenceNode);
        while (regexpSequenceNode.end != end
                && .charAt(regexpSequenceNode.end) == '|') {
            int from = regexpSequenceNode.end + 1;
            regexpSequenceNode = parseRegexpSequence(fromend);
            if (regexpSequenceNode == null) {
                /* expected: regexp sequence */
                throwParseException(from);
            }
            alternatives.add(regexpSequenceNode);
        }
        TreeNode result = new TreeNode(.,
                                       start,
                                       regexpSequenceNode.end);
        for (TreeNode alt : alternatives) {
            result.add(alt);
        }
        return result;
    }

    
    
    private TreeNode parseRegexpSequence(int startint end)
            throws ParseException {
        if (start == end) {
            return null;
        }
        TreeNode result;
        List<TreeNodesequence = null;
        TreeNode lastChildNode = null;
        int from = start;
        while (true) {
            TreeNode qRegexpNode = parseQRegexp(fromend);
            if (qRegexpNode == null) {
                break;
            }
            if (sequence == null) {
                sequence = new ArrayList<TreeNode>(4);
            }
            sequence.add(qRegexpNode);
            /* remember the last added regexp: */
            lastChildNode = qRegexpNode;
            /* test - is parsing finished? */
            if (qRegexpNode.end == end) {
                break;
            }
            from = qRegexpNode.end;
        }
        if (sequence == null) {
            return null;
        }
        result = new TreeNode(.startlastChildNode.end);
        for (TreeNode seqPart : sequence) {
            result.add(seqPart);
        }
        return result;
    }


    
    private TreeNode parseQRegexp(int startint endthrows ParseException {
        if (start == end) {
            return null;
        }
        TreeNode result;
        TreeNode singleRegexpNode = parseSingleRegexp(startend);
        if (singleRegexpNode == null) {
            return null;
        }
        /* test - is parsing finished? */
        if (singleRegexpNode.end == end) {
            result = new TreeNode(.,
                                  start,
                                  singleRegexpNode.end);
            result.add(singleRegexpNode);
            return result;
        }
        TreeNode quantifierNode = parseQuantifier(singleRegexpNode.endend);
        if (quantifierNode == null) {
            result = new TreeNode(.,
                                  start,
                                  singleRegexpNode.end);
            result.add(singleRegexpNode);
        } else {
            result = new TreeNode(.,
                                  start,
                                  quantifierNode.end);
            result.add(singleRegexpNode);
            result.add(quantifierNode);
        }
        return result;
    }


    
    private TreeNode parseSingleRegexp(int startint end)
            throws ParseException {
        if (start == end) {
            return null;
        }
        TreeNode result;
        char ch = .charAt(start);
        switch (ch) {
            case '.':
                result = new TreeNode(.,
                                      start,
                                      start + 1,
                                      new Character(ch));
                break;
            case '[':
                TreeNode setNode = parseSet(startend);
                assert setNode != null;
                return setNode;
            case '(':
                TreeNode subexprNode = parseSubexpr(startend);
                assert subexprNode != null;
                return subexprNode;
            case '\\':
                if (end == start + 1) {
                    
                    /* unexpected end of regexp */
                    throwParseException(end);
                }
                char ch2 = .charAt(start + 1);
                switch (ch2) {
                    case 'b':
                    case 'B':
                        result = new TreeNode(.,
                                              start,
                                              start + 2,
                                              new Character(ch2));
                        break;
                    case 'u':
                        Integer unicode = parseUnicode(start + 2, end);
                        if (unicode == null) {
                            /* expected: 4-digit hexadecimal number */
                            throwParseException(start + 2);
                        }
                        result = new TreeNode(.,
                                              start,
                                              start + 6,
                                              unicode);
                        break;
                    default:
                        char parsedChar;
                        switch (ch2) {
                            case 't':
                                parsedChar = '\t';
                                break;
                            case 'n':
                                parsedChar = '\n';
                                break;
                            case 'r':
                                parsedChar = '\r';
                                break;
                            case 'f':
                                parsedChar = '\f';
                                break;
                            default:
                                parsedChar = ch2;
                                break;
                        }
                        result = new TreeNode(.,
                                              start,
                                              start + 2,
                                              new Character(parsedChar));
                        break;
                }
                break;
            case '{':
                String tokenName = getTokenName(startend);
                if (tokenName != null) {
                    result = new TreeNode(.,
                                          start,
                                          start + tokenName.length() + 2,
                                          tokenName);
                    break;
                }
                /* falls through */
            default:
                if ("^$|*+?)]{}".indexOf(ch) != -1) {                //NOI18N
                    return null;
                }
                result = new TreeNode(.,
                                      start,
                                      start + 1,
                                      new Character(ch));
                break;
        }
        return result;
    }


    
    private TreeNode parseQuantifier(int startint end)
            throws ParseException {
        if (start == end) {
            return null;
        }
        TreeNode result = null;
        char ch = .charAt(start);
        switch (ch) {
            case '*':
            case '+':
            case '?':
                result = new TreeNode(.,
                                      start,
                                      start + 1,
                                      new Character(ch));
                return result;
            case '{':
                break;
            default:
                return null;
        }
        if (end - start == 1) {
            
            /* expected: number or token */
            throwParseException(start + 1);
        }
        TreeNode numberNode1 = parseNumber(start + 1, end);
        if (numberNode1 == null) {
            /* it is not a number - maybe it is a token: */
            if (getTokenName(startend) != null) {
                /* if it is a token, it is not a quantifier: */
                return null;
            }
            /* expected: number */
            throwParseException(start + 1);
        }
        if (numberNode1.end == end) {
            /* expected: '}', ',' */
            throwParseException(numberNode1.end);
        }
        switch (.charAt(numberNode1.end)) {
            case '}':
                result = new TreeNode(.,
                                      start,
                                      numberNode1.end + 1,
                                      "{n}");                           //NOI18N
                result.add(numberNode1);
                return result;
            case ',':
                break;
            default:
                /* expected: '}' or ',' */
                throwParseException(numberNode1.end);
        }
        if (numberNode1.end + 1 == end) {
            
            /* expected: number or '}' */
            throwParseException(numberNode1.end + 1);
        }
        if (.charAt(numberNode1.end + 1) == '}') {
                result = new TreeNode(.,
                                      start,
                                      numberNode1.end + 2,
                                      "{n,}");                          //NOI18N
                result.add(numberNode1);
                return result;
        }
        TreeNode numberNode2 = parseNumber(numberNode1.end + 1, end);
        if (numberNode2 == null) {
            /* expected: number */
            throwParseException(numberNode1.end + 1);
        }
        if (numberNode2.end == end
                || .charAt(numberNode2.end) != '}') {
            /* expected: '}' */
            throwParseException(numberNode2.end);
        }
        int num1 = ((IntegernumberNode1.getAttribs()).intValue();
        int num2 = ((IntegernumberNode2.getAttribs()).intValue();
        if (num2 < num1) {
            throwParseException(numberNode2.start);
        }
        result = new TreeNode(.,
                              start,
                              numberNode2.end + 1,
                              "{n,n}");                                 //NOI18N
        result.add(numberNode1);
        result.add(numberNode2);
        return result;
    }
    

    
    private TreeNode parseNumber(int startint endthrows ParseException {
        if (start == end) {
            return null;
        }
        char[] chars = .substring(startend).toCharArray();
        int endIndex = chars.length;
        for (int i = 0; i < chars.lengthi++) {
            if (chars[i] < '0' || chars[i] > '9') {
                endIndex = i;
                break;
            }
        }
        if (endIndex == 0) {
            return null;
        } else if (endIndex > 3) {
            /* max 3 digits */
            throwParseException(start);
        }
        int number;
        if (endIndex == 1) {
            number = chars[0] - '0';
        } else {
            try {
                number = Integer.parseInt(.substring(start,
                                                           start + endIndex));
            } catch (NumberFormatException ex) {
                throw new AssertionError();                  //should not happen
            }
        }
        TreeNode result = new TreeNode(.,
                                       start,
                                       start + endIndex,
                                       new Integer(number));
        return result;
    }


    
    private String getTokenName(int startint end) {
        if ( == null) {
            return null;
        }
        int checkAreaLength = Math.min(end - start + 2);
        String substring = .substring(startstart + checkAreaLength);
        if (substring.charAt(0) != '{') {
            return null;
        }
        int rightBoundaryIndex = substring.indexOf('}', 1);
        if (rightBoundaryIndex == -1) {
            return null;
        }
        String tokenName = substring.substring(1, rightBoundaryIndex);
        for (int i = 0; i < .i++) {
            if (tokenName.equals([i])) {
                return tokenName;
            }
        }
        return null;
    }


    
    private Integer parseUnicode(int startint endthrows ParseException {
        if (start == end) {
            return null;
        }
        if (end - start < 4) {
            /* expected: 4-digit hexadecimal number */
            throwParseException(start);
        }
        char[] chars = .substring(startstart + 4).toCharArray();
        for (int i = 0; i < 4; i++) {
            char ch = chars[i];
            if ("01234567890abcdefABCDEF".indexOf(ch) == -1) {          //NOI18N
                if (i == 0) {
                    return null;
                } else {
                    throwParseException(start);
                }
            }
        }
        Integer integer;
        try {
            integer = Integer.valueOf(.substring(startstart + 4), 16);
        } catch (NumberFormatException ex) {
            throw new AssertionError();         //should not happen
        }
        return integer;
    }


    
    private TreeNode parseSubexpr(int startint endthrows ParseException {
        if (start == end) {
            return null;
        }
        if (.charAt(start) != '(') {
            return null;
        }
        if (end == start + 1) {
            throwParseException(start + 1);
        }
        TreeNode result;
        TreeNode multiRegexpNode = parseMultiRegexp(start + 1, end);
        if (multiRegexpNode == null) {
            /* expected: regular subexpression */
            throwParseException(start + 1);
        }
        if (multiRegexpNode.end == end
                || .charAt(multiRegexpNode.end) != ')') {
            throwParseException(multiRegexpNode.end);
        }
        result = new TreeNode(.startmultiRegexpNode.end + 1);
        result.add(multiRegexpNode);
        return result;
    }


    
    private TreeNode parseSet(int startint endthrows ParseException {
        if (start == end) {
            return null;
        }
        if (.charAt(start) != '[') {
            return null;
        }
        if (end == start + 1) {
            /* unexpected end of regexp: */
            throwParseException(start + 1);
        }
        /*
         * Test which of the three chars that may occur only in the beginning
         * of the set ('^', ']', '-') are present:
         */
        String setString = .substring(startend);
        String specials = getSpecials(setString);
        /* Find indices of the bounding square brackets: */
        int endIndex = setString.indexOf(']', 1 + specials.length());
        if (endIndex == -1) {
            /* matching bracket (']') not found: */
            throwParseException(start);
        } else {
            endIndex++;                 //index of the first character after ']'
        }
        endIndex += start;              //from the beginning of 'regexp'
        setString = .substring(startendIndex);
        int setLength = setString.length();
        TreeNode result;
        /* Test whether the set is a named character set: */
        if (setLength >= 5
                && setString.charAt(1) == ':'
                && setString.charAt(setLength - 2) == ':') {
            String charClassName = setString.substring(2, setLength - 2);
            if (isPosixCharClass(charClassName)) {
                result = new TreeNode(.,
                                               start,
                                               endIndex,
                                               charClassName);
                return result;
            } else {
                throwParseException(start + 2);
            }
        }
        result = new TreeNode(.,
                              start,
                              endIndex,
                              specials);
        int from = start + 1 + specials.length();
        int to = endIndex - 1;
        while (from != to) {
            TreeNode rangeNode = parseRangeOrChar(fromto);
            if (rangeNode == null) {
                /* expected: character or range of characters */
                throwParseException(from);
            }
            result.add(rangeNode);
            from = rangeNode.end;
        }
        return result;
    }


    
    private TreeNode parseRangeOrChar(int startint end)
            throws ParseException {
        if (start == end) {
            return null;
        }
        TreeNode rangeCharNode1 = parseRangeChar(startend);
        if (rangeCharNode1 == null) {
            return null;
        }
        if (rangeCharNode1.end == end
                || .charAt(rangeCharNode1.end) != '-') {
            return rangeCharNode1;
        }
        TreeNode rangeCharNode2 = parseRangeChar(rangeCharNode1.end + 1, end);
        if (rangeCharNode2 == null) {
            /* expected: range character */
            throwParseException(rangeCharNode1.end + 1);
        }
        Object charObject;
        charObject = rangeCharNode1.getAttribs();
        int char1 = charObject instanceof Character
                     ? Character.getNumericValue(
                            ((CharactercharObject).charValue())
                     : ((IntegercharObject).intValue();
        charObject = rangeCharNode2.getAttribs();
        int char2 = charObject instanceof Character
                     ? Character.getNumericValue(
                            ((CharactercharObject).charValue())
                     : ((IntegercharObject).intValue();
        if (!(char1 < char2)) {
            /* expected: range character */
            throwParseException(rangeCharNode1.end + 1);
        }
        TreeNode result = new TreeNode(.,
                                       start,
                                       rangeCharNode2.end);
        result.add(rangeCharNode1);
        result.add(rangeCharNode2);
        return result;
    }

    
    
    private TreeNode parseRangeChar(int startint endthrows ParseException {
        if (start == end) {
            return null;
        }
        TreeNode result;
        char ch = .charAt(start);
        switch (ch) {
            case ']':
            case '-':
                return null;
            case '\\':
                if (end == start + 1) {
                    /* expected: any character except ']', '-' */
                    throwParseException(start + 1);
                }
                char ch2 = .charAt(start + 1);
                char parsedChar;
                switch (ch2) {
                    case 'u':
                        Integer unicode = parseUnicode(start + 2, end);
                        if (unicode == null) {
                            
                            /* expected: 4-digit hexadecimal number */
                            throwParseException(start + 2);
                        }
                        int codeValue = unicode.intValue();
                        assert codeValue >= 0;
                        if (codeValue <= 0x007f) {
                            /* expected: unicode value >= 0080h */
                            throwParseException(start + 2);
                        }
                        return new TreeNode(.,
                                              start,
                                              start + 6,
                                              unicode);
                    case ']':
                    case '-':
                        /*
                         * characters ']' and '-' must be in the beginning
                         * of the definition of the set:
                         */
                        throwParseException(start + 2);
                    case 't':
                        parsedChar = '\t';
                        break;
                    case 'n':
                        parsedChar = '\n';
                        break;
                    case 'r':
                        parsedChar = '\r';
                        break;
                    case 'f':
                        parsedChar = '\f';
                        break;
                    default:
                        parsedChar = ch2;
                        break;
                }
                result = new TreeNode(.,
                                      start,
                                      start + 2,
                                      new Character(parsedChar));
                break;
            default:
                result = new TreeNode(.,
                                      start,
                                      start + 1,
                                      new Character(ch));
                break;
        }
        return result;
    }


    
    private String getSpecials(String setRegexp) {
        int index = 1;
        int maxIndex = 3;
        if (setRegexp.length() < 5) {
            maxIndex = setRegexp.length() - 2;
        }
        StringBuilder buf = new StringBuilder(maxIndex - index + 1);
        char ch = setRegexp.charAt(index);
        if (ch == '^') {
            buf.append(ch);
            if (index == maxIndex) {
                return buf.toString();
            }
            ch = setRegexp.charAt(++index);
        }
        if (ch == ']') {
            buf.append(ch);
            if (index == maxIndex) {
                return buf.toString();
            }
            ch = setRegexp.charAt(++index);
        }
        if (ch == '-') {
            buf.append(ch);
        }
        return buf.toString();
    }


    
    private boolean isPosixCharClass(String name) {
        /* "xdigit" is the only class name not having exactly 5 characters: */
        if (name.equals("xdigit")) {                                    //NOI18N
            return true;
        }
        if (name.length() != 5) {
            return false;
        }
        String classNames = "alnum alpha blank cntrl digit graph "      //NOI18N
                            + "lower print punct space upper";          //NOI18N
        StringTokenizer tokenizer
                = new StringTokenizer(classNames" ");                 //NOI18N
        while (tokenizer.hasMoreTokens()) {
            if (name.equals(tokenizer.nextToken())) {
                return true;
            }
        }
        return false;
    }
New to GrepCode? Check out our FAQ X