bundles/org.simantics.databoard/cpp/DataBoardTest/libantlr3c-3.2/src/antlr3cyclicdfa.c

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