thirdparty/libantlr3c-3.2/src/antlr3cyclicdfa.c

   1 /** Support functions for traversing cyclic DFA states as laid
   2  *  out in static initialized structures by the code generator.
   3  *
   4  * A DFA implemented as a set of transition tables.
   5  *
   6  *  Any state that has a semantic predicate edge is special; those states
   7  *  are generated with if-then-else structures in a ->specialStateTransition()
   8  *  which is generated by cyclicDFA template.
   9  *
  10  *  There are at most 32767 states (16-bit signed short).
  11  *  Could get away with byte sometimes but would have to generate different
  12  *  types and the simulation code too.  For a point of reference, the Java
  13  *  lexer's Tokens rule DFA has 326 states roughly.
  14  */
  15
  16 // [The "BSD licence"]
  17 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
  18 // http://www.temporal-wave.com
  19 // http://www.linkedin.com/in/jimidle
  20 //
  21 // All rights reserved.
  22 //
  23 // Redistribution and use in source and binary forms, with or without
  24 // modification, are permitted provided that the following conditions
  25 // are met:
  26 // 1. Redistributions of source code must retain the above copyright
  27 //    notice, this list of conditions and the following disclaimer.
  28 // 2. Redistributions in binary form must reproduce the above copyright
  29 //    notice, this list of conditions and the following disclaimer in the
  30 //    documentation and/or other materials provided with the distribution.
  31 // 3. The name of the author may not be used to endorse or promote products
  32 //    derived from this software without specific prior written permission.
  33 //
  34 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  35 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  36 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  37 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  38 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  39 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  40 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  41 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  42 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  43 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  44
  45 #include    <antlr3defs.h>
  46 #include    <antlr3cyclicdfa.h>
  47
  48 #ifdef  ANTLR3_WINDOWS
  49 #pragma warning( disable : 4100 )
  50 #endif
  51
  52 static void
  53 noViableAlt(pANTLR3_BASE_RECOGNIZER rec, pANTLR3_CYCLIC_DFA cdfa, ANTLR3_UINT32 s)
  54 {
  55         // In backtracking mode, we just set the failed flag so that the
  56         // alt can just exit right now. If we are parsing though, then
  57         // we want the exception to be raised.
  58         //
  59     if  (rec->state->backtracking > 0)
  60     {
  61                 rec->state->failed = ANTLR3_TRUE;
  62     }
  63         else
  64         {
  65                 rec->exConstruct(rec);
  66                 rec->state->exception->type         = ANTLR3_NO_VIABLE_ALT_EXCEPTION;
  67                 rec->state->exception->message      = cdfa->description;
  68                 rec->state->exception->decisionNum  = cdfa->decisionNumber;
  69                 rec->state->exception->state        = s;
  70         }
  71 }
  72
  73 /** From the input stream, predict what alternative will succeed
  74  *  using this DFA (representing the covering regular approximation
  75  *  to the underlying CFL).  Return an alternative number 1..n.  Throw
  76  *  an exception upon error.
  77  */
  78 ANTLR3_API ANTLR3_INT32
  79 antlr3dfapredict (void * ctx, pANTLR3_BASE_RECOGNIZER rec, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA cdfa)
  80 {
  81     ANTLR3_MARKER       mark;
  82     ANTLR3_INT32        s;
  83     ANTLR3_INT32        specialState;
  84     ANTLR3_INT32        c;
  85
  86     mark        = is->mark(is);     /* Store where we are right now     */
  87     s           = 0;                /* Always start with state 0        */
  88
  89         for (;;)
  90         {
  91                 /* Pick out any special state entry for this state
  92                  */
  93                 specialState    = cdfa->special[s];
  94
  95                 /* Transition the special state and consume an input token
  96                  */
  97                 if  (specialState >= 0)
  98                 {
  99                         s = cdfa->specialStateTransition(ctx, rec, is, cdfa, specialState);
 100
 101                         // Error?
 102                         //
 103                         if      (s<0)
 104                         {
 105                                 // If the predicate/rule raised an exception then we leave it
 106                                 // in tact, else we have an NVA.
 107                                 //
 108                                 if      (rec->state->error != ANTLR3_TRUE)
 109                                 {
 110                                         noViableAlt(rec,cdfa, s);
 111                                 }
 112                                 is->rewind(is, mark);
 113                                 return  0;
 114                         }
 115                         is->consume(is);
 116                         continue;
 117                 }
 118
 119                 /* Accept state?
 120                  */
 121                 if  (cdfa->accept[s] >= 1)
 122                 {
 123                         is->rewind(is, mark);
 124                         return  cdfa->accept[s];
 125                 }
 126
 127                 /* Look for a normal transition state based upon the input token element
 128                  */
 129                 c = is->_LA(is, 1);
 130
 131                 /* Check against min and max for this state
 132                  */
 133                 if  (c>= cdfa->min[s] && c <= cdfa->max[s])
 134                 {
 135                         ANTLR3_INT32   snext;
 136
 137                         /* What is the next state?
 138                          */
 139                         snext = cdfa->transition[s][c - cdfa->min[s]];
 140
 141                         if      (snext < 0)
 142                         {
 143                                 /* Was in range but not a normal transition
 144                                  * must check EOT, which is like the else clause.
 145                                  * eot[s]>=0 indicates that an EOT edge goes to another
 146                                  * state.
 147                                  */
 148                                 if  (cdfa->eot[s] >= 0)
 149                                 {
 150                                         s = cdfa->eot[s];
 151                                         is->consume(is);
 152                                         continue;
 153                                 }
 154                                 noViableAlt(rec,cdfa, s);
 155                                 is->rewind(is, mark);
 156                                 return  0;
 157                         }
 158
 159                         /* New current state - move to it
 160                          */
 161                         s       = snext;
 162                         is->consume(is);
 163                         continue;
 164                 }
 165                 /* EOT Transition?
 166                  */
 167                 if  (cdfa->eot[s] >= 0)
 168                 {
 169                         s       = cdfa->eot[s];
 170                         is->consume(is);
 171                         continue;
 172                 }
 173                 /* EOF transition to accept state?
 174                  */
 175                 if  ( c == ANTLR3_TOKEN_EOF && cdfa->eof[s] >= 0)
 176                 {
 177                         is->rewind(is, mark);
 178                         return  cdfa->accept[cdfa->eof[s]];
 179                 }
 180
 181                 /* No alt, so bomb
 182                  */
 183                 noViableAlt(rec, cdfa, s);
 184                 is->rewind(is, mark);
 185                 return 0;
 186         }
 187
 188 }
 189
 190 /** Default special state implementation
 191  */
 192 ANTLR3_API ANTLR3_INT32
 193 antlr3dfaspecialStateTransition   (void * ctx, pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA dfa, ANTLR3_INT32 s)
 194 {
 195     return -1;
 196 }
 197
 198 /* Default special transition implementation
 199  */
 200 ANTLR3_API ANTLR3_INT32
 201 antlr3dfaspecialTransition    (void * ctx, pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA dfa, ANTLR3_INT32 s)
 202 {
 203     return 0;
 204 }