001: package org.antlr.runtime;
002:
003: /** A DFA implemented as a set of transition tables.
004: *
005: * Any state that has a semantic predicate edge is special; those states
006: * are generated with if-then-else structures in a specialStateTransition()
007: * which is generated by cyclicDFA template.
008: *
009: * There are at most 32767 states (16-bit signed short).
010: * Could get away with byte sometimes but would have to generate different
011: * types and the simulation code too. For a point of reference, the Java
012: * lexer's Tokens rule DFA has 326 states roughly.
013: */
014: public class DFA {
015: protected short[] eot;
016: protected short[] eof;
017: protected char[] min;
018: protected char[] max;
019: protected short[] accept;
020: protected short[] special;
021: protected short[][] transition;
022:
023: protected int decisionNumber;
024:
025: /** Which recognizer encloses this DFA? Needed to check backtracking */
026: protected BaseRecognizer recognizer;
027:
028: public static final boolean debug = false;
029:
030: /** From the input stream, predict what alternative will succeed
031: * using this DFA (representing the covering regular approximation
032: * to the underlying CFL). Return an alternative number 1..n. Throw
033: * an exception upon error.
034: */
035: public int predict(IntStream input) throws RecognitionException {
036: int mark = input.mark(); // remember where decision started in input
037: int s = 0; // we always start at s0
038: try {
039: while (true) {
040: if (debug)
041: System.err.println("DFA " + decisionNumber
042: + " state " + s + " LA(1)="
043: + (char) input.LA(1) + "(" + input.LA(1)
044: + "), index=" + input.index());
045: int specialState = special[s];
046: if (specialState >= 0) {
047: if (debug)
048: System.err.println("DFA " + decisionNumber
049: + " state " + s + " is special state "
050: + specialState);
051: s = specialStateTransition(specialState, input);
052: input.consume();
053: continue;
054: }
055: if (accept[s] >= 1) {
056: if (debug)
057: System.err.println("accept; predict "
058: + accept[s] + " from state " + s);
059: return accept[s];
060: }
061: // look for a normal char transition
062: char c = (char) input.LA(1); // -1 == \uFFFF, all tokens fit in 65000 space
063: if (c >= min[s] && c <= max[s]) {
064: int snext = transition[s][c - min[s]]; // move to next state
065: if (snext < 0) {
066: // was in range but not a normal transition
067: // must check EOT, which is like the else clause.
068: // eot[s]>=0 indicates that an EOT edge goes to another
069: // state.
070: if (eot[s] >= 0) { // EOT Transition to accept state?
071: if (debug)
072: System.err.println("EOT transition");
073: s = eot[s];
074: input.consume();
075: // TODO: I had this as return accept[eot[s]]
076: // which assumed here that the EOT edge always
077: // went to an accept...faster to do this, but
078: // what about predicated edges coming from EOT
079: // target?
080: continue;
081: }
082: noViableAlt(s, input);
083: return 0;
084: }
085: s = snext;
086: input.consume();
087: continue;
088: }
089: if (eot[s] >= 0) { // EOT Transition?
090: if (debug)
091: System.err.println("EOT transition");
092: s = eot[s];
093: input.consume();
094: continue;
095: }
096: if (c == (char) Token.EOF && eof[s] >= 0) { // EOF Transition to accept state?
097: if (debug)
098: System.err.println("accept via EOF; predict "
099: + accept[eof[s]] + " from " + eof[s]);
100: return accept[eof[s]];
101: }
102: // not in range and not EOF/EOT, must be invalid symbol
103: if (debug) {
104: System.err.println("min[" + s + "]=" + min[s]);
105: System.err.println("max[" + s + "]=" + max[s]);
106: System.err.println("eot[" + s + "]=" + eot[s]);
107: System.err.println("eof[" + s + "]=" + eof[s]);
108: for (int p = 0; p < transition[s].length; p++) {
109: System.err.print(transition[s][p] + " ");
110: }
111: System.err.println();
112: }
113: noViableAlt(s, input);
114: return 0;
115: }
116: } finally {
117: input.rewind(mark);
118: }
119: }
120:
121: protected void noViableAlt(int s, IntStream input)
122: throws NoViableAltException {
123: if (recognizer.backtracking > 0) {
124: recognizer.failed = true;
125: return;
126: }
127: NoViableAltException nvae = new NoViableAltException(
128: getDescription(), decisionNumber, s, input);
129: error(nvae);
130: throw nvae;
131: }
132:
133: /** A hook for debugging interface */
134: protected void error(NoViableAltException nvae) {
135: ;
136: }
137:
138: public int specialStateTransition(int s, IntStream input)
139: throws NoViableAltException {
140: return -1;
141: }
142:
143: public String getDescription() {
144: return "n/a";
145: }
146:
147: /** Given a String that has a run-length-encoding of some unsigned shorts
148: * like "\1\2\3\9", convert to short[] {2,9,9,9}. We do this to avoid
149: * static short[] which generates so much init code that the class won't
150: * compile. :(
151: */
152: public static short[] unpackEncodedString(String encodedString) {
153: // walk first to find how big it is.
154: int size = 0;
155: for (int i = 0; i < encodedString.length(); i += 2) {
156: size += encodedString.charAt(i);
157: }
158: short[] data = new short[size];
159: int di = 0;
160: for (int i = 0; i < encodedString.length(); i += 2) {
161: char n = encodedString.charAt(i);
162: char v = encodedString.charAt(i + 1);
163: // add v n times to data
164: for (int j = 1; j <= n; j++) {
165: data[di++] = (short) v;
166: }
167: }
168: return data;
169: }
170:
171: /** Hideous duplication of code, but I need different typed arrays out :( */
172: public static char[] unpackEncodedStringToUnsignedChars(
173: String encodedString) {
174: // walk first to find how big it is.
175: int size = 0;
176: for (int i = 0; i < encodedString.length(); i += 2) {
177: size += encodedString.charAt(i);
178: }
179: char[] data = new char[size];
180: int di = 0;
181: for (int i = 0; i < encodedString.length(); i += 2) {
182: char n = encodedString.charAt(i);
183: char v = encodedString.charAt(i + 1);
184: // add v n times to data
185: for (int j = 1; j <= n; j++) {
186: data[di++] = v;
187: }
188: }
189: return data;
190: }
191:
192: public int specialTransition(int state, int symbol) {
193: return 0;
194: }
195: }
|