/*
* [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
{
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;
public DFA()
: this( new SpecialStateTransitionHandler( SpecialStateTransitionDefault ) )
{
}
public DFA( SpecialStateTransitionHandler specialStateTransition )
{
this.SpecialStateTransition = specialStateTransition ?? new SpecialStateTransitionHandler( SpecialStateTransitionDefault );
}
public virtual string Description
{
get
{
return "n/a";
}
}
/** <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;
}
/** <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);
}
}
}