diff options
Diffstat (limited to 'runtime/CSharp3/Sources/Antlr3.Runtime/DFA.cs')
-rw-r--r-- | runtime/CSharp3/Sources/Antlr3.Runtime/DFA.cs | 318 |
1 files changed, 0 insertions, 318 deletions
diff --git a/runtime/CSharp3/Sources/Antlr3.Runtime/DFA.cs b/runtime/CSharp3/Sources/Antlr3.Runtime/DFA.cs deleted file mode 100644 index 76c4083..0000000 --- a/runtime/CSharp3/Sources/Antlr3.Runtime/DFA.cs +++ /dev/null @@ -1,318 +0,0 @@ -/* - * [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 ArgumentNullException = System.ArgumentNullException; - 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 bool debug = false; - - public DFA() - : this(SpecialStateTransitionDefault) - { - } - - public DFA( SpecialStateTransitionHandler specialStateTransition ) - { - this.SpecialStateTransition = specialStateTransition ?? 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 (input == null) - throw new ArgumentNullException("input"); - - DfaDebugMessage("Enter DFA.Predict for decision {0}", decisionNumber); - - int mark = input.Mark(); // remember where decision started in input - int s = 0; // we always start at s0 - try - { - while (true) - { - DfaDebugMessage("DFA {0} state {1} LA(1)={2}({3}), index={4}", decisionNumber, s, (char)input.LA(1), input.LA(1), input.Index); - - int specialState = special[s]; - if ( specialState >= 0 ) - { - DfaDebugMessage("DFA {0} state {1} is special state {2}", decisionNumber, s, specialState); - - s = SpecialStateTransition( this, specialState, input ); - - DfaDebugMessage("DFA {0} returns from special state {1} to {2}", decisionNumber, specialState, s); - - if ( s == -1 ) - { - NoViableAlt( s, input ); - return 0; - } - - input.Consume(); - continue; - } - - if ( accept[s] >= 1 ) - { - DfaDebugMessage("accept; predict {0} from state {1}", accept[s], 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? - DfaDebugMessage("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? - DfaDebugMessage("EOT transition"); - s = eot[s]; - input.Consume(); - continue; - } - - if ( c == unchecked( (char)TokenTypes.EndOfFile ) && eof[s] >= 0 ) - { - // EOF Transition to accept state? - DfaDebugMessage("accept via EOF; predict {0} from {1}", accept[eof[s]], eof[s]); - return accept[eof[s]]; - } - - // not in range and not EOF/EOT, must be invalid symbol - DfaDebugInvalidSymbol(s); - - NoViableAlt( s, input ); - return 0; - } - } - finally - { - input.Rewind( mark ); - } - } - - [Conditional("DEBUG_DFA")] - private void DfaDebugMessage(string format, params object[] args) - { - Console.Error.WriteLine(format, args); - } - - [Conditional("DEBUG_DFA")] - private void DfaDebugInvalidSymbol(int s) - { - Console.Error.WriteLine("min[{0}]={1}", s, min[s]); - Console.Error.WriteLine("max[{0}]={1}", s, max[s]); - Console.Error.WriteLine("eot[{0}]={1}", s, eot[s]); - Console.Error.WriteLine("eof[{0}]={1}", s, eof[s]); - - for (int p = 0; p < transition[s].Length; p++) - Console.Error.Write(transition[s][p] + " "); - - Console.Error.WriteLine(); - } - - 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); - } - } -} |