JSON_checker.c
Go to the documentation of this file.
00001 /* JSON_checker.c */
00002 
00003 
00004 /* 2005-12-30 */
00005 
00006 /*
00007 Copyright (c) 2005 JSON.org
00008 
00009 Permission is hereby granted, free of charge, to any person obtaining a copy
00010 of this software and associated documentation files (the "Software"), to deal
00011 in the Software without restriction, including without limitation the rights
00012 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
00013 copies of the Software, and to permit persons to whom the Software is
00014 furnished to do so, subject to the following conditions:
00015 
00016 The above copyright notice and this permission notice shall be included in all
00017 copies or substantial portions of the Software.
00018 
00019 The Software shall be used for Good, not Evil.
00020 
00021 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00022 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00023 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
00024 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00025 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00026 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
00027 SOFTWARE.
00028 */
00029 
00030 
00031 #include "JSON_checker.h"
00032 
00033 #define true  1
00034 #define false 0
00035 
00036 /*
00037     Characters are mapped into these 32 symbol classes. This allows for
00038     significant reductions in the size of the state transition table.
00039 */
00040 
00041 /* error */
00042 #define S_ERR -1
00043 
00044 /* space */
00045 #define S_SPA 0
00046 
00047 /* other whitespace */
00048 #define S_WSP 1
00049 
00050 /* {  */
00051 #define S_LBE 2
00052 
00053 /* } */
00054 #define S_RBE 3
00055 
00056 /* [ */
00057 #define S_LBT 4
00058 
00059 /* ] */
00060 #define S_RBT 5
00061 
00062 /* : */
00063 #define S_COL 6
00064 
00065 /* , */
00066 #define S_COM 7
00067 
00068 /* " */
00069 #define S_QUO 8
00070 
00071 /* \ */
00072 #define S_BAC 9
00073 
00074 /* / */
00075 #define S_SLA 10
00076 
00077 /* + */
00078 #define S_PLU 11
00079 
00080 /* - */
00081 #define S_MIN 12
00082 
00083 /* . */
00084 #define S_DOT 13
00085 
00086 /* 0 */
00087 #define S_ZER 14
00088 
00089 /* 123456789 */
00090 #define S_DIG 15
00091 
00092 /* a */
00093 #define S__A_ 16
00094 
00095 /* b */
00096 #define S__B_ 17
00097 
00098 /* c */
00099 #define S__C_ 18
00100 
00101 /* d */
00102 #define S__D_ 19
00103 
00104 /* e */
00105 #define S__E_ 20
00106 
00107 /* f */
00108 #define S__F_ 21
00109 
00110 /* l */
00111 #define S__L_ 22
00112 
00113 /* n */
00114 #define S__N_ 23
00115 
00116 /* r */
00117 #define S__R_ 24
00118 
00119 /* s */
00120 #define S__S_ 25
00121 
00122 /* t */
00123 #define S__T_ 26
00124 
00125 /* u */
00126 #define S__U_ 27
00127 
00128 /* ABCDF */
00129 #define S_A_F 28
00130 
00131 /* E */
00132 #define S_E   29
00133 
00134 /* everything else */
00135 #define S_ETC 30
00136 
00137 
00138 /*
00139     This table maps the 128 ASCII characters into the 32 character classes.
00140     The remaining Unicode characters should be mapped to S_ETC.
00141 */
00142 static int ascii_class[128] = {
00143     S_ERR, S_ERR, S_ERR, S_ERR, S_ERR, S_ERR, S_ERR, S_ERR,
00144     S_ERR, S_WSP, S_WSP, S_ERR, S_ERR, S_WSP, S_ERR, S_ERR,
00145     S_ERR, S_ERR, S_ERR, S_ERR, S_ERR, S_ERR, S_ERR, S_ERR,
00146     S_ERR, S_ERR, S_ERR, S_ERR, S_ERR, S_ERR, S_ERR, S_ERR,
00147 
00148     S_SPA, S_ETC, S_QUO, S_ETC, S_ETC, S_ETC, S_ETC, S_ETC,
00149     S_ETC, S_ETC, S_ETC, S_PLU, S_COM, S_MIN, S_DOT, S_SLA,
00150     S_ZER, S_DIG, S_DIG, S_DIG, S_DIG, S_DIG, S_DIG, S_DIG,
00151     S_DIG, S_DIG, S_COL, S_ETC, S_ETC, S_ETC, S_ETC, S_ETC,
00152 
00153     S_ETC, S_A_F, S_A_F, S_A_F, S_A_F, S_E  , S_A_F, S_ETC,
00154     S_ETC, S_ETC, S_ETC, S_ETC, S_ETC, S_ETC, S_ETC, S_ETC,
00155     S_ETC, S_ETC, S_ETC, S_ETC, S_ETC, S_ETC, S_ETC, S_ETC,
00156     S_ETC, S_ETC, S_ETC, S_LBT, S_BAC, S_RBT, S_ETC, S_ETC,
00157 
00158     S_ETC, S__A_, S__B_, S__C_, S__D_, S__E_, S__F_, S_ETC,
00159     S_ETC, S_ETC, S_ETC, S_ETC, S__L_, S_ETC, S__N_, S_ETC,
00160     S_ETC, S_ETC, S__R_, S__S_, S__T_, S__U_, S_ETC, S_ETC,
00161     S_ETC, S_ETC, S_ETC, S_LBE, S_ETC, S_RBE, S_ETC, S_ETC
00162 };
00163 
00164 
00165 /*
00166     The state transition table takes the current state and the current symbol,
00167     and returns either a new state or an action. A new state is a number between
00168     0 and 29. An action is a negative number between -1 and -9. A JSON text is
00169     accepted if the end of the text is in state 9 and mode is MODE_DONE.
00170 */
00171 static int state_transition_table[30][31] = {
00172 /* 0*/ { 0, 0,-8,-1,-6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00173 /* 1*/ { 1, 1,-1,-9,-1,-1,-1,-1, 3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00174 /* 2*/ { 2, 2,-8,-1,-6,-5,-1,-1, 3,-1,-1,-1,20,-1,21,22,-1,-1,-1,-1,-1,13,-1,17,-1,-1,10,-1,-1,-1,-1},
00175 /* 3*/ { 3,-1, 3, 3, 3, 3, 3, 3,-4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3},
00176 /* 4*/ {-1,-1,-1,-1,-1,-1,-1,-1, 3, 3, 3,-1,-1,-1,-1,-1,-1, 3,-1,-1,-1, 3,-1, 3, 3,-1, 3, 5,-1,-1,-1},
00177 /* 5*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 6, 6, 6, 6, 6, 6, 6, 6,-1,-1,-1,-1,-1,-1, 6, 6,-1},
00178 /* 6*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 7, 7, 7, 7, 7, 7, 7, 7,-1,-1,-1,-1,-1,-1, 7, 7,-1},
00179 /* 7*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 8, 8, 8, 8, 8, 8, 8, 8,-1,-1,-1,-1,-1,-1, 8, 8,-1},
00180 /* 8*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 3, 3, 3, 3, 3, 3, 3, 3,-1,-1,-1,-1,-1,-1, 3, 3,-1},
00181 /* 9*/ { 9, 9,-1,-7,-1,-5,-1,-3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00182 /*10*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1},
00183 /*11*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,12,-1,-1,-1},
00184 /*12*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 9,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00185 /*13*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,14,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00186 /*14*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,15,-1,-1,-1,-1,-1,-1,-1,-1},
00187 /*15*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,16,-1,-1,-1,-1,-1},
00188 /*16*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 9,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00189 /*17*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,18,-1,-1,-1},
00190 /*18*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,19,-1,-1,-1,-1,-1,-1,-1,-1},
00191 /*19*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 9,-1,-1,-1,-1,-1,-1,-1,-1},
00192 /*20*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,21,22,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00193 /*21*/ { 9, 9,-1,-7,-1,-5,-1,-3,-1,-1,-1,-1,-1,23,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00194 /*22*/ { 9, 9,-1,-7,-1,-5,-1,-3,-1,-1,-1,-1,-1,23,22,22,-1,-1,-1,-1,24,-1,-1,-1,-1,-1,-1,-1,-1,24,-1},
00195 /*23*/ { 9, 9,-1,-7,-1,-5,-1,-3,-1,-1,-1,-1,-1,-1,23,23,-1,-1,-1,-1,24,-1,-1,-1,-1,-1,-1,-1,-1,24,-1},
00196 /*24*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,25,25,-1,26,26,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00197 /*25*/ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,26,26,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00198 /*26*/ { 9, 9,-1,-7,-1,-5,-1,-3,-1,-1,-1,-1,-1,-1,26,26,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00199 /*27*/ {27,27,-1,-1,-1,-1,-2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
00200 /*28*/ {28,28,-8,-1,-6,-1,-1,-1, 3,-1,-1,-1,20,-1,21,22,-1,-1,-1,-1,-1,13,-1,17,-1,-1,10,-1,-1,-1,-1},
00201 /*29*/ {29,29,-1,-1,-1,-1,-1,-1, 3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
00202 };
00203 
00204 
00205 
00206 /*
00207     These modes can be pushed on the PDA stack.
00208 */
00209 #define MODE_DONE   1
00210 #define MODE_KEY    2
00211 #define MODE_OBJECT 3
00212 #define MODE_ARRAY  4
00213 
00214 /*
00215     A stack maintains the states of nested structures.
00216 */
00217 #define MAX_DEPTH   20
00218 
00219 static int the_state;
00220 static int the_stack[MAX_DEPTH];
00221 static int the_top;
00222 
00223 static int the_index = 0;
00224 
00225 /*
00226     Push a mode onto the stack. Return false if there is overflow.
00227 */
00228 static int 
00229 push(int mode)
00230 {
00231     the_top += 1;
00232     if (the_top >= MAX_DEPTH) {
00233         return false;
00234     }
00235     the_stack[the_top] = mode;
00236     return true;
00237 }
00238 
00239 
00240 /*
00241     Pop the stack, assuring that the current mode matches the expectation.
00242     Return false if there is underflow or if the modes mismatch.
00243 */
00244 static int
00245 pop(int mode)
00246 {
00247     if (the_top < 0 || the_stack[the_top] != mode) {
00248         return false;
00249     }
00250     the_stack[the_top] = 0;
00251     the_top -= 1;
00252     return true;
00253 }
00254 
00255 int JSON_checker_push(int b);
00256 
00257 void JSON_checker_init() {
00258         the_state = 0;
00259    the_top = -1;
00260    push(MODE_DONE);
00261 }
00262 
00263 int JSON_checker_finished() {
00264          return the_state == 9 && pop(MODE_DONE);
00265 }
00266 
00267 /*
00268     The JSON_checker takes a UTF-16 encoded string and determines if it is a
00269     syntactically correct JSON text.
00270 
00271     It is implemented as a Pushdown Automaton; that means it is a finite state
00272     machine with a stack.
00273 */
00274 int 
00275 JSON_checker(unsigned short p[], int length)
00276 {
00277         JSON_checker_init();
00278 
00279         for (the_index = 0; the_index < length; the_index += 1) {
00280                 if(!(JSON_checker_push(p[the_index]))) return false;
00281         }
00282    
00283         return JSON_checker_finished() ;
00284 }
00285 
00286 
00287 int JSON_checker_push(int b) {
00288    int c;  /* the next character class */
00289    int s;  /* the next state */
00290         if ((b & 127) == b) {
00291             c = ascii_class[b];
00292             if (c <= S_ERR) {
00293                 return false;
00294             }
00295         } else {
00296             c = S_ETC;
00297         }
00298 /*
00299     Get the next state from the transition table.
00300 */
00301         s = state_transition_table[the_state][c];
00302         if (s < 0) {
00303 /*
00304     Perform one of the predefined actions.
00305 */
00306             switch (s) {
00307 /*
00308     empty }
00309 */
00310             case -9:
00311                 if (!pop(MODE_KEY)) {
00312                     return false;
00313                 }
00314                 the_state = 9;
00315                 break;
00316 /*
00317     {
00318 */
00319             case -8:
00320                 if (!push(MODE_KEY)) {
00321                     return false;
00322                 }
00323                 the_state = 1;
00324                 break;
00325 /*
00326     }
00327 */
00328             case -7:
00329                 if (!pop(MODE_OBJECT)) {
00330                     return false;
00331                 }
00332                 the_state = 9;
00333                 break;
00334 /*
00335     [
00336 */
00337             case -6:
00338                 if (!push(MODE_ARRAY)) {
00339                     return false;
00340                 }
00341                 the_state = 2;
00342                 break;
00343 /*
00344     ]
00345 */
00346             case -5:
00347                 if (!pop(MODE_ARRAY)) {
00348                     return false;
00349                 }
00350                 the_state = 9;
00351                 break;
00352 /*
00353     "
00354 */
00355             case -4:
00356                 switch (the_stack[the_top]) {
00357                 case MODE_KEY:
00358                     the_state = 27;
00359                     break;
00360                 case MODE_ARRAY:
00361                 case MODE_OBJECT:
00362                     the_state = 9;
00363                     break;
00364                 default:
00365                     return false;
00366                 }
00367                 break;
00368 /*
00369     ,
00370 */
00371             case -3:
00372                 switch (the_stack[the_top]) {
00373                 case MODE_OBJECT:
00374                     if (pop(MODE_OBJECT) && push(MODE_KEY)) {
00375                         the_state = 29;
00376                     }
00377                     break;
00378                 case MODE_ARRAY:
00379                     the_state = 28;
00380                     break;
00381                 default:
00382                     return false;
00383                 }
00384                 break;
00385 /*
00386     :
00387 */
00388             case -2:
00389                 if (pop(MODE_KEY) && push(MODE_OBJECT)) {
00390                     the_state = 28;
00391                     break;
00392                 }
00393 /*
00394     syntax error
00395 */
00396             case -1:
00397                 return false;
00398             }
00399         } else {
00400 /*
00401     Change the state and iterate.
00402 */
00403             the_state = s;
00404         }
00405                 return true;
00406 }
00407 /*
00408     Get the current character number.
00409 */
00410 int 
00411 JSON_checker_at_character()
00412 {
00413     return the_index;
00414 }


csm
Author(s): Andrea Censi
autogenerated on Mon Jan 16 2017 03:48:29