DFA.js revision 324c4644fee44b9898524c09511bd33c3f12e2df 
1/** A DFA implemented as a set of transition tables.
2 *
3 *  Any state that has a semantic predicate edge is special; those states
4 *  are generated with if-then-else structures in a specialStateTransition()
5 *  which is generated by cyclicDFA template.
6 *
7 *  There are at most 32767 states (16-bit signed short).
8 *  Could get away with byte sometimes but would have to generate different
9 *  types and the simulation code too.  For a point of reference, the Java
10 *  lexer's Tokens rule DFA has 326 states roughly.
11 */
12org.antlr.runtime.DFA = function() {};
13
14org.antlr.runtime.DFA.prototype = {
15    /** From the input stream, predict what alternative will succeed
16     *  using this DFA (representing the covering regular approximation
17     *  to the underlying CFL).  Return an alternative number 1..n.  Throw
18     *  an exception upon error.
19     */
20    predict: function(input) {
21        var mark = input.mark(), // remember where decision started in input
22            s = 0, // we always start at s0
23            specialState,
24            c,
25            snext;
26
27        try {
28            while ( true ) {
29                specialState = this.special[s];
30                if ( specialState>=0 ) {
31                    s = this.specialStateTransition(specialState,input);
32                    if (s===-1) {
33                        this.noViableAlt(s, input);
34                        return 0;
35                    }
36                    input.consume();
37                    continue;
38                }
39                if ( this.accept[s] >= 1 ) {
40                    return this.accept[s];
41                }
42                // look for a normal char transition
43                c = input.LA(1); // -1 == \uFFFF, all tokens fit in 65000 space
44
45                if (c===org.antlr.runtime.Token.EOF) {
46                    c = -1;
47                } else if (org.antlr.lang.isString(c)) {
48                    c = c.charCodeAt(0);
49                }
50
51                if (c>=this.min[s] && c<=this.max[s]) {
52                    snext = this.transition[s][c-this.min[s]]; // move to next state
53                    if ( snext < 0 ) {
54                        // was in range but not a normal transition
55                        // must check EOT, which is like the else clause.
56                        // eot[s]>=0 indicates that an EOT edge goes to another
57                        // state.
58                        if ( this.eot[s]>=0 ) {  // EOT Transition to accept state?
59                            s = this.eot[s];
60                            input.consume();
61                            // TODO: I had this as return accept[eot[s]]
62                            // which assumed here that the EOT edge always
63                            // went to an accept...faster to do this, but
64                            // what about predicated edges coming from EOT
65                            // target?
66                            continue;
67                        }
68                        this.noViableAlt(s,input);
69                        return 0;
70                    }
71                    s = snext;
72                    input.consume();
73                    continue;
74                }
75                if ( this.eot[s]>=0 ) {  // EOT Transition?
76                    s = this.eot[s];
77                    input.consume();
78                    continue;
79                }
80                if ( c==org.antlr.runtime.Token.EOF && this.eof[s]>=0 ) {  // EOF Transition to accept state?
81                    return this.accept[this.eof[s]];
82                }
83                // not in range and not EOF/EOT, must be invalid symbol
84                this.noViableAlt(s,input);
85                return 0;
86            }
87        }
88        finally {
89            input.rewind(mark);
90        }
91    },
92
93    noViableAlt: function(s, input) {
94        if (this.recognizer.state.backtracking>0) {
95            this.recognizer.state.failed=true;
96            return;
97        }
98        var nvae =
99            new org.antlr.runtime.NoViableAltException(this.getDescription(),
100                                     this.decisionNumber,
101                                     s,
102                                     input);
103        this.error(nvae);
104        throw nvae;
105    },
106
107    /** A hook for debugging interface */
108    error: function(nvae) { },
109
110    specialStateTransition: function(s, input) {
111        return -1;
112    },
113
114    getDescription: function() {
115        return "n/a";
116    }
117};
118
119org.antlr.lang.augmentObject(org.antlr.runtime.DFA, {
120    /** Given a String that has a run-length-encoding of some unsigned shorts
121     *  like "\1\2\3\9", convert to short[] {2,9,9,9}.
122     */
123    unpackEncodedString: function(encodedString) {
124        // walk first to find how big it is.
125        var i,
126            data = [],
127            di = 0,
128            n,
129            v,
130            j;
131        for (i=0; i<encodedString.length; i+=2) {
132            n = encodedString.charCodeAt(i);
133            v = encodedString.charCodeAt(i+1);
134            if (v===0xffff) {
135                v = -1; // overflow at 16 bits
136            }
137            // add v n times to data
138            for (j=1; j<=n; j++) {
139                data[di++] = v;
140            }
141        }
142        return data;
143    },
144
145    // alias
146    unpackEncodedStringToUnsignedChars: function(encodedString) {
147        return org.antlr.runtime.DFA.unpackEncodedString(encodedString);
148    }
149});
150