| /* |
| * [The "BSD license"] |
| * Copyright (c) 2010 Terence Parr |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. The name of the author may not be used to endorse or promote products |
| * derived from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| package org.antlr.analysis; |
| |
| import org.antlr.misc.IntSet; |
| import org.antlr.misc.IntervalSet; |
| import org.antlr.tool.Grammar; |
| |
| /** A state machine transition label. A label can be either a simple |
| * label such as a token or character. A label can be a set of char or |
| * tokens. It can be an epsilon transition. It can be a semantic predicate |
| * (which assumes an epsilon transition) or a tree of predicates (in a DFA). |
| * Special label types have to be < 0 to avoid conflict with char. |
| */ |
| public class Label implements Comparable, Cloneable { |
| public static final int INVALID = -7; |
| |
| public static final int ACTION = -6; |
| |
| public static final int EPSILON = -5; |
| |
| public static final String EPSILON_STR = "<EPSILON>"; |
| |
| /** label is a semantic predicate; implies label is epsilon also */ |
| public static final int SEMPRED = -4; |
| |
| /** label is a set of tokens or char */ |
| public static final int SET = -3; |
| |
| /** End of Token is like EOF for lexer rules. It implies that no more |
| * characters are available and that NFA conversion should terminate |
| * for this path. For example |
| * |
| * A : 'a' 'b' | 'a' ; |
| * |
| * yields a DFA predictor: |
| * |
| * o-a->o-b->1 predict alt 1 |
| * | |
| * |-EOT->o predict alt 2 |
| * |
| * To generate code for EOT, treat it as the "default" path, which |
| * implies there is no way to mismatch a char for the state from |
| * which the EOT emanates. |
| */ |
| public static final int EOT = -2; |
| |
| public static final int EOF = -1; |
| |
| /** We have labels like EPSILON that are below 0; it's hard to |
| * store them in an array with negative index so use this |
| * constant as an index shift when accessing arrays based upon |
| * token type. If real token type is i, then array index would be |
| * NUM_FAUX_LABELS + i. |
| */ |
| public static final int NUM_FAUX_LABELS = -INVALID; |
| |
| /** Anything at this value or larger can be considered a simple atom int |
| * for easy comparison during analysis only; faux labels are not used |
| * during parse time for real token types or char values. |
| */ |
| public static final int MIN_ATOM_VALUE = EOT; |
| |
| // TODO: is 0 a valid unicode char? max is FFFF -1, right? |
| public static final int MIN_CHAR_VALUE = '\u0000'; |
| public static final int MAX_CHAR_VALUE = '\uFFFF'; |
| |
| /** End of rule token type; imaginary token type used only for |
| * local, partial FOLLOW sets to indicate that the local FOLLOW |
| * hit the end of rule. During error recovery, the local FOLLOW |
| * of a token reference may go beyond the end of the rule and have |
| * to use FOLLOW(rule). I have to just shift the token types to 2..n |
| * rather than 1..n to accommodate this imaginary token in my bitsets. |
| * If I didn't use a bitset implementation for runtime sets, I wouldn't |
| * need this. EOF is another candidate for a run time token type for |
| * parsers. Follow sets are not computed for lexers so we do not have |
| * this issue. |
| */ |
| public static final int EOR_TOKEN_TYPE = |
| org.antlr.runtime.Token.EOR_TOKEN_TYPE; |
| |
| public static final int DOWN = org.antlr.runtime.Token.DOWN; |
| public static final int UP = org.antlr.runtime.Token.UP; |
| |
| /** tokens and char range overlap; tokens are MIN_TOKEN_TYPE..n */ |
| public static final int MIN_TOKEN_TYPE = |
| org.antlr.runtime.Token.MIN_TOKEN_TYPE; |
| |
| /** The wildcard '.' char atom implies all valid characters==UNICODE */ |
| //public static final IntSet ALLCHAR = IntervalSet.of(MIN_CHAR_VALUE,MAX_CHAR_VALUE); |
| |
| /** The token type or character value; or, signifies special label. */ |
| protected int label; |
| |
| /** A set of token types or character codes if label==SET */ |
| // TODO: try IntervalSet for everything |
| protected IntSet labelSet; |
| |
| public Label(int label) { |
| this.label = label; |
| } |
| |
| /** Make a set label */ |
| public Label(IntSet labelSet) { |
| if ( labelSet==null ) { |
| this.label = SET; |
| this.labelSet = IntervalSet.of(INVALID); |
| return; |
| } |
| int singleAtom = labelSet.getSingleElement(); |
| if ( singleAtom!=INVALID ) { |
| // convert back to a single atomic element if |labelSet|==1 |
| label = singleAtom; |
| return; |
| } |
| this.label = SET; |
| this.labelSet = labelSet; |
| } |
| |
| public Object clone() { |
| Label l; |
| try { |
| l = (Label)super.clone(); |
| l.label = this.label; |
| l.labelSet = new IntervalSet(); |
| l.labelSet.addAll(this.labelSet); |
| } |
| catch (CloneNotSupportedException e) { |
| throw new InternalError(); |
| } |
| return l; |
| } |
| |
| public void add(Label a) { |
| if ( isAtom() ) { |
| labelSet = IntervalSet.of(label); |
| label=SET; |
| if ( a.isAtom() ) { |
| labelSet.add(a.getAtom()); |
| } |
| else if ( a.isSet() ) { |
| labelSet.addAll(a.getSet()); |
| } |
| else { |
| throw new IllegalStateException("can't add element to Label of type "+label); |
| } |
| return; |
| } |
| if ( isSet() ) { |
| if ( a.isAtom() ) { |
| labelSet.add(a.getAtom()); |
| } |
| else if ( a.isSet() ) { |
| labelSet.addAll(a.getSet()); |
| } |
| else { |
| throw new IllegalStateException("can't add element to Label of type "+label); |
| } |
| return; |
| } |
| throw new IllegalStateException("can't add element to Label of type "+label); |
| } |
| |
| public boolean isAtom() { |
| return label>=MIN_ATOM_VALUE; |
| } |
| |
| public boolean isEpsilon() { |
| return label==EPSILON; |
| } |
| |
| public boolean isSemanticPredicate() { |
| return false; |
| } |
| |
| public boolean isAction() { |
| return false; |
| } |
| |
| public boolean isSet() { |
| return label==SET; |
| } |
| |
| /** return the single atom label or INVALID if not a single atom */ |
| public int getAtom() { |
| if ( isAtom() ) { |
| return label; |
| } |
| return INVALID; |
| } |
| |
| public IntSet getSet() { |
| if ( label!=SET ) { |
| // convert single element to a set if they ask for it. |
| return IntervalSet.of(label); |
| } |
| return labelSet; |
| } |
| |
| public void setSet(IntSet set) { |
| label=SET; |
| labelSet = set; |
| } |
| |
| public SemanticContext getSemanticContext() { |
| return null; |
| } |
| |
| public boolean matches(int atom) { |
| if ( label==atom ) { |
| return true; // handle the single atom case efficiently |
| } |
| if ( isSet() ) { |
| return labelSet.member(atom); |
| } |
| return false; |
| } |
| |
| public boolean matches(IntSet set) { |
| if ( isAtom() ) { |
| return set.member(getAtom()); |
| } |
| if ( isSet() ) { |
| // matches if intersection non-nil |
| return !getSet().and(set).isNil(); |
| } |
| return false; |
| } |
| |
| |
| public boolean matches(Label other) { |
| if ( other.isSet() ) { |
| return matches(other.getSet()); |
| } |
| if ( other.isAtom() ) { |
| return matches(other.getAtom()); |
| } |
| return false; |
| } |
| |
| public int hashCode() { |
| if (label==SET) { |
| return labelSet.hashCode(); |
| } |
| else { |
| return label; |
| } |
| } |
| |
| // TODO: do we care about comparing set {A} with atom A? Doesn't now. |
| public boolean equals(Object o) { |
| if ( o==null ) { |
| return false; |
| } |
| if ( this == o ) { |
| return true; // equals if same object |
| } |
| // labels must be the same even if epsilon or set or sempred etc... |
| if ( label!=((Label)o).label ) { |
| return false; |
| } |
| if ( label==SET ) { |
| return this.labelSet.equals(((Label)o).labelSet); |
| } |
| return true; // label values are same, so true |
| } |
| |
| public int compareTo(Object o) { |
| return this.label-((Label)o).label; |
| } |
| |
| /** Predicates are lists of AST nodes from the NFA created from the |
| * grammar, but the same predicate could be cut/paste into multiple |
| * places in the grammar. I must compare the text of all the |
| * predicates to truly answer whether {p1,p2} .equals {p1,p2}. |
| * Unfortunately, I cannot rely on the AST.equals() to work properly |
| * so I must do a brute force O(n^2) nested traversal of the Set |
| * doing a String compare. |
| * |
| * At this point, Labels are not compared for equals when they are |
| * predicates, but here's the code for future use. |
| */ |
| /* |
| protected boolean predicatesEquals(Set others) { |
| Iterator iter = semanticContext.iterator(); |
| while (iter.hasNext()) { |
| AST predAST = (AST) iter.next(); |
| Iterator inner = semanticContext.iterator(); |
| while (inner.hasNext()) { |
| AST otherPredAST = (AST) inner.next(); |
| if ( !predAST.getText().equals(otherPredAST.getText()) ) { |
| return false; |
| } |
| } |
| } |
| return true; |
| } |
| */ |
| |
| public String toString() { |
| switch (label) { |
| case SET : |
| return labelSet.toString(); |
| default : |
| return String.valueOf(label); |
| } |
| } |
| |
| public String toString(Grammar g) { |
| switch (label) { |
| case SET : |
| return labelSet.toString(g); |
| default : |
| return g.getTokenDisplayName(label); |
| } |
| } |
| |
| /* |
| public String predicatesToString() { |
| if ( semanticContext==NFAConfiguration.DEFAULT_CLAUSE_SEMANTIC_CONTEXT ) { |
| return "!other preds"; |
| } |
| StringBuffer buf = new StringBuffer(); |
| Iterator iter = semanticContext.iterator(); |
| while (iter.hasNext()) { |
| AST predAST = (AST) iter.next(); |
| buf.append(predAST.getText()); |
| if ( iter.hasNext() ) { |
| buf.append("&"); |
| } |
| } |
| return buf.toString(); |
| } |
| */ |
| |
| public static boolean intersect(Label label, Label edgeLabel) { |
| boolean hasIntersection = false; |
| boolean labelIsSet = label.isSet(); |
| boolean edgeIsSet = edgeLabel.isSet(); |
| if ( !labelIsSet && !edgeIsSet && edgeLabel.label==label.label ) { |
| hasIntersection = true; |
| } |
| else if ( labelIsSet && edgeIsSet && |
| !edgeLabel.getSet().and(label.getSet()).isNil() ) { |
| hasIntersection = true; |
| } |
| else if ( labelIsSet && !edgeIsSet && |
| label.getSet().member(edgeLabel.label) ) { |
| hasIntersection = true; |
| } |
| else if ( !labelIsSet && edgeIsSet && |
| edgeLabel.getSet().member(label.label) ) { |
| hasIntersection = true; |
| } |
| return hasIntersection; |
| } |
| } |
