1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD license"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2010 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Redistribution and use in source and binary forms, with or without 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modification, are permitted provided that the following conditions 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are met: 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Redistributions of source code must retain the above copyright 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer. 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Redistributions in binary form must reproduce the above copyright 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer in the 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * documentation and/or other materials provided with the distribution. 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. The name of the author may not be used to endorse or promote products 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this software without specific prior written permission. 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.analysis; 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.misc.IntSet; 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.misc.IntervalSet; 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.tool.Grammar; 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** A state machine transition label. A label can be either a simple 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * label such as a token or character. A label can be a set of char or 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * tokens. It can be an epsilon transition. It can be a semantic predicate 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (which assumes an epsilon transition) or a tree of predicates (in a DFA). 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Special label types have to be < 0 to avoid conflict with char. 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class Label implements Comparable, Cloneable { 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int INVALID = -7; 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int ACTION = -6; 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int EPSILON = -5; 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final String EPSILON_STR = "<EPSILON>"; 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** label is a semantic predicate; implies label is epsilon also */ 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int SEMPRED = -4; 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** label is a set of tokens or char */ 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int SET = -3; 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** End of Token is like EOF for lexer rules. It implies that no more 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * characters are available and that NFA conversion should terminate 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * for this path. For example 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A : 'a' 'b' | 'a' ; 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * yields a DFA predictor: 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * o-a->o-b->1 predict alt 1 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * |-EOT->o predict alt 2 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * To generate code for EOT, treat it as the "default" path, which 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * implies there is no way to mismatch a char for the state from 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * which the EOT emanates. 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int EOT = -2; 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int EOF = -1; 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** We have labels like EPSILON that are below 0; it's hard to 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * store them in an array with negative index so use this 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * constant as an index shift when accessing arrays based upon 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * token type. If real token type is i, then array index would be 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NUM_FAUX_LABELS + i. 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int NUM_FAUX_LABELS = -INVALID; 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Anything at this value or larger can be considered a simple atom int 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * for easy comparison during analysis only; faux labels are not used 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * during parse time for real token types or char values. 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int MIN_ATOM_VALUE = EOT; 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: is 0 a valid unicode char? max is FFFF -1, right? 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int MIN_CHAR_VALUE = '\u0000'; 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int MAX_CHAR_VALUE = '\uFFFF'; 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** End of rule token type; imaginary token type used only for 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * local, partial FOLLOW sets to indicate that the local FOLLOW 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * hit the end of rule. During error recovery, the local FOLLOW 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of a token reference may go beyond the end of the rule and have 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to use FOLLOW(rule). I have to just shift the token types to 2..n 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * rather than 1..n to accommodate this imaginary token in my bitsets. 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If I didn't use a bitset implementation for runtime sets, I wouldn't 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * need this. EOF is another candidate for a run time token type for 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * parsers. Follow sets are not computed for lexers so we do not have 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * this issue. 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int EOR_TOKEN_TYPE = 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver org.antlr.runtime.Token.EOR_TOKEN_TYPE; 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int DOWN = org.antlr.runtime.Token.DOWN; 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int UP = org.antlr.runtime.Token.UP; 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** tokens and char range overlap; tokens are MIN_TOKEN_TYPE..n */ 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final int MIN_TOKEN_TYPE = 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver org.antlr.runtime.Token.MIN_TOKEN_TYPE; 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** The wildcard '.' char atom implies all valid characters==UNICODE */ 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //public static final IntSet ALLCHAR = IntervalSet.of(MIN_CHAR_VALUE,MAX_CHAR_VALUE); 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** The token type or character value; or, signifies special label. */ 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int label; 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** A set of token types or character codes if label==SET */ 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: try IntervalSet for everything 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected IntSet labelSet; 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Label(int label) { 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.label = label; 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Make a set label */ 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Label(IntSet labelSet) { 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( labelSet==null ) { 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.label = SET; 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.labelSet = IntervalSet.of(INVALID); 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int singleAtom = labelSet.getSingleElement(); 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( singleAtom!=INVALID ) { 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // convert back to a single atomic element if |labelSet|==1 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label = singleAtom; 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.label = SET; 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.labelSet = labelSet; 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Object clone() { 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label l; 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver try { 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver l = (Label)super.clone(); 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver l.label = this.label; 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver l.labelSet = new IntervalSet(); 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver l.labelSet.addAll(this.labelSet); 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver catch (CloneNotSupportedException e) { 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new InternalError(); 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return l; 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void add(Label a) { 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( isAtom() ) { 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labelSet = IntervalSet.of(label); 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label=SET; 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( a.isAtom() ) { 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labelSet.add(a.getAtom()); 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( a.isSet() ) { 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labelSet.addAll(a.getSet()); 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new IllegalStateException("can't add element to Label of type "+label); 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( isSet() ) { 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( a.isAtom() ) { 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labelSet.add(a.getAtom()); 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( a.isSet() ) { 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labelSet.addAll(a.getSet()); 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new IllegalStateException("can't add element to Label of type "+label); 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new IllegalStateException("can't add element to Label of type "+label); 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isAtom() { 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return label>=MIN_ATOM_VALUE; 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isEpsilon() { 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return label==EPSILON; 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isSemanticPredicate() { 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isAction() { 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isSet() { 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return label==SET; 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** return the single atom label or INVALID if not a single atom */ 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int getAtom() { 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( isAtom() ) { 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return label; 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return INVALID; 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public IntSet getSet() { 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( label!=SET ) { 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // convert single element to a set if they ask for it. 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return IntervalSet.of(label); 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return labelSet; 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void setSet(IntSet set) { 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label=SET; 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labelSet = set; 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public SemanticContext getSemanticContext() { 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean matches(int atom) { 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( label==atom ) { 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; // handle the single atom case efficiently 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( isSet() ) { 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return labelSet.member(atom); 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean matches(IntSet set) { 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( isAtom() ) { 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return set.member(getAtom()); 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( isSet() ) { 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // matches if intersection non-nil 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return !getSet().and(set).isNil(); 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean matches(Label other) { 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( other.isSet() ) { 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return matches(other.getSet()); 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( other.isAtom() ) { 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return matches(other.getAtom()); 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int hashCode() { 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (label==SET) { 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return labelSet.hashCode(); 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return label; 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: do we care about comparing set {A} with atom A? Doesn't now. 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean equals(Object o) { 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( o==null ) { 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( this == o ) { 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; // equals if same object 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // labels must be the same even if epsilon or set or sempred etc... 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( label!=((Label)o).label ) { 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( label==SET ) { 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this.labelSet.equals(((Label)o).labelSet); 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; // label values are same, so true 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int compareTo(Object o) { 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this.label-((Label)o).label; 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Predicates are lists of AST nodes from the NFA created from the 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * grammar, but the same predicate could be cut/paste into multiple 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * places in the grammar. I must compare the text of all the 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * predicates to truly answer whether {p1,p2} .equals {p1,p2}. 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Unfortunately, I cannot rely on the AST.equals() to work properly 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * so I must do a brute force O(n^2) nested traversal of the Set 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * doing a String compare. 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * At this point, Labels are not compared for equals when they are 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * predicates, but here's the code for future use. 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected boolean predicatesEquals(Set others) { 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Iterator iter = semanticContext.iterator(); 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (iter.hasNext()) { 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver AST predAST = (AST) iter.next(); 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Iterator inner = semanticContext.iterator(); 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (inner.hasNext()) { 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver AST otherPredAST = (AST) inner.next(); 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !predAST.getText().equals(otherPredAST.getText()) ) { 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toString() { 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver switch (label) { 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver case SET : 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return labelSet.toString(); 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver default : 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return String.valueOf(label); 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toString(Grammar g) { 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver switch (label) { 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver case SET : 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return labelSet.toString(g); 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver default : 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return g.getTokenDisplayName(label); 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String predicatesToString() { 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( semanticContext==NFAConfiguration.DEFAULT_CLAUSE_SEMANTIC_CONTEXT ) { 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return "!other preds"; 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuffer buf = new StringBuffer(); 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Iterator iter = semanticContext.iterator(); 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (iter.hasNext()) { 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver AST predAST = (AST) iter.next(); 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(predAST.getText()); 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( iter.hasNext() ) { 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append("&"); 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf.toString(); 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static boolean intersect(Label label, Label edgeLabel) { 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean hasIntersection = false; 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean labelIsSet = label.isSet(); 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean edgeIsSet = edgeLabel.isSet(); 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !labelIsSet && !edgeIsSet && edgeLabel.label==label.label ) { 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver hasIntersection = true; 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( labelIsSet && edgeIsSet && 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver !edgeLabel.getSet().and(label.getSet()).isNil() ) { 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver hasIntersection = true; 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( labelIsSet && !edgeIsSet && 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label.getSet().member(edgeLabel.label) ) { 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver hasIntersection = true; 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( !labelIsSet && edgeIsSet && 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver edgeLabel.getSet().member(label.label) ) { 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver hasIntersection = true; 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return hasIntersection; 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 383