/*
* [The "BSD licence"]
* Copyright (c) 2005-2008 Terence Parr
* All rights reserved.
*
* Conversion to C#:
* Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc.
* 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.
*/
namespace Antlr.Runtime {
using ConditionalAttribute = System.Diagnostics.ConditionalAttribute;
using Console = System.Console;
using IDebugEventListener = Antlr.Runtime.Debug.IDebugEventListener;
public delegate int SpecialStateTransitionHandler(DFA dfa, int s, IIntStream input);
/** <summary>A DFA implemented as a set of transition tables.</summary>
*
* <remarks>
* Any state that has a semantic predicate edge is special; those states
* are generated with if-then-else structures in a specialStateTransition()
* which is generated by cyclicDFA template.
*
* There are at most 32767 states (16-bit signed short).
* Could get away with byte sometimes but would have to generate different
* types and the simulation code too. For a point of reference, the Java
* lexer's Tokens rule DFA has 326 states roughly.
* </remarks>
*/
public class DFA {
public DFA()
: this(new SpecialStateTransitionHandler(SpecialStateTransitionDefault)) {
}
public DFA(SpecialStateTransitionHandler specialStateTransition) {
this.SpecialStateTransition = specialStateTransition ?? new SpecialStateTransitionHandler(SpecialStateTransitionDefault);
}
protected short[] eot;
protected short[] eof;
protected char[] min;
protected char[] max;
protected short[] accept;
protected short[] special;
protected short[][] transition;
protected int decisionNumber;
/** <summary>Which recognizer encloses this DFA? Needed to check backtracking</summary> */
protected BaseRecognizer recognizer;
public readonly bool debug = false;
/** <summary>
* From the input stream, predict what alternative will succeed
* using this DFA (representing the covering regular approximation
* to the underlying CFL). Return an alternative number 1..n. Throw
* an exception upon error.
* </summary>
*/
public virtual int Predict(IIntStream input) {
if (debug) {
Console.Error.WriteLine("Enter DFA.predict for decision " + decisionNumber);
}
int mark = input.Mark(); // remember where decision started in input
int s = 0; // we always start at s0
try {
for (; ; ) {
if (debug)
Console.Error.WriteLine("DFA " + decisionNumber + " state " + s + " LA(1)=" + (char)input.LA(1) + "(" + input.LA(1) +
"), index=" + input.Index);
int specialState = special[s];
if (specialState >= 0) {
if (debug) {
Console.Error.WriteLine("DFA " + decisionNumber +
" state " + s + " is special state " + specialState);
}
s = SpecialStateTransition(this, specialState, input);
if (debug) {
Console.Error.WriteLine("DFA " + decisionNumber +
" returns from special state " + specialState + " to " + s);
}
if (s == -1) {
NoViableAlt(s, input);
return 0;
}
input.Consume();
continue;
}
if (accept[s] >= 1) {
if (debug)
Console.Error.WriteLine("accept; predict " + accept[s] + " from state " + s);
return accept[s];
}
// look for a normal char transition
char c = (char)input.LA(1); // -1 == \uFFFF, all tokens fit in 65000 space
if (c >= min[s] && c <= max[s]) {
int snext = transition[s][c - min[s]]; // move to next state
if (snext < 0) {
// was in range but not a normal transition
// must check EOT, which is like the else clause.
// eot[s]>=0 indicates that an EOT edge goes to another
// state.
if (eot[s] >= 0) { // EOT Transition to accept state?
if (debug)
Console.Error.WriteLine("EOT transition");
s = eot[s];
input.Consume();
// TODO: I had this as return accept[eot[s]]
// which assumed here that the EOT edge always
// went to an accept...faster to do this, but
// what about predicated edges coming from EOT
// target?
continue;
}
NoViableAlt(s, input);
return 0;
}
s = snext;
input.Consume();
continue;
}
if (eot[s] >= 0) { // EOT Transition?
if (debug)
Console.Error.WriteLine("EOT transition");
s = eot[s];
input.Consume();
continue;
}
if (c == unchecked((char)TokenTypes.EndOfFile) && eof[s] >= 0) { // EOF Transition to accept state?
if (debug)
Console.Error.WriteLine("accept via EOF; predict " + accept[eof[s]] + " from " + eof[s]);
return accept[eof[s]];
}
// not in range and not EOF/EOT, must be invalid symbol
if (debug) {
Console.Error.WriteLine("min[" + s + "]=" + min[s]);
Console.Error.WriteLine("max[" + s + "]=" + max[s]);
Console.Error.WriteLine("eot[" + s + "]=" + eot[s]);
Console.Error.WriteLine("eof[" + s + "]=" + eof[s]);
for (int p = 0; p < transition[s].Length; p++) {
Console.Error.Write(transition[s][p] + " ");
}
Console.Error.WriteLine();
}
NoViableAlt(s, input);
return 0;
}
} finally {
input.Rewind(mark);
}
}
protected virtual void NoViableAlt(int s, IIntStream input) {
if (recognizer.state.backtracking > 0) {
recognizer.state.failed = true;
return;
}
NoViableAltException nvae =
new NoViableAltException(Description,
decisionNumber,
s,
input);
Error(nvae);
throw nvae;
}
/** <summary>A hook for debugging interface</summary> */
public virtual void Error(NoViableAltException nvae) {
}
public SpecialStateTransitionHandler SpecialStateTransition {
get;
private set;
}
//public virtual int specialStateTransition( int s, IntStream input )
//{
// return -1;
//}
static int SpecialStateTransitionDefault(DFA dfa, int s, IIntStream input) {
return -1;
}
public virtual string Description {
get {
return "n/a";
}
}
/** <summary>
* Given a String that has a run-length-encoding of some unsigned shorts
* like "\1\2\3\9", convert to short[] {2,9,9,9}. We do this to avoid
* static short[] which generates so much init code that the class won't
* compile. :(
* </summary>
*/
public static short[] UnpackEncodedString(string encodedString) {
// walk first to find how big it is.
int size = 0;
for (int i = 0; i < encodedString.Length; i += 2) {
size += encodedString[i];
}
short[] data = new short[size];
int di = 0;
for (int i = 0; i < encodedString.Length; i += 2) {
char n = encodedString[i];
char v = encodedString[i + 1];
// add v n times to data
for (int j = 1; j <= n; j++) {
data[di++] = (short)v;
}
}
return data;
}
/** <summary>Hideous duplication of code, but I need different typed arrays out :(</summary> */
public static char[] UnpackEncodedStringToUnsignedChars(string encodedString) {
// walk first to find how big it is.
int size = 0;
for (int i = 0; i < encodedString.Length; i += 2) {
size += encodedString[i];
}
char[] data = new char[size];
int di = 0;
for (int i = 0; i < encodedString.Length; i += 2) {
char n = encodedString[i];
char v = encodedString[i + 1];
// add v n times to data
for (int j = 1; j <= n; j++) {
data[di++] = v;
}
}
return data;
}
[Conditional("ANTLR_DEBUG")]
protected virtual void DebugRecognitionException(RecognitionException ex) {
IDebugEventListener dbg = recognizer.DebugListener;
if (dbg != null)
dbg.RecognitionException(ex);
}
}
}