Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch parser-enhancements Excluding Merge-Ins
This is equivalent to a diff from 0557a179f9 to 09752e51a1
2015-11-10
| ||
12:41 | Change all parsers to use the standard "lempar.c" template in the tool/ folder and remove the customized lempar.c from src/, plus other compiler performance and space enhancements. (check-in: 0e7fb24ad3 user: drh tags: trunk) | |
12:31 | Fix harmless compiler warnings in FTS5. (Closed-Leaf check-in: 09752e51a1 user: drh tags: parser-enhancements) | |
03:30 | Performance enhancement to the tokenizer. (check-in: 6ea2df86c9 user: drh tags: parser-enhancements) | |
2015-11-09
| ||
19:33 | Change the parser to use the standard "lempar.c" template over in the tool/ folder rather than the customized "lempar.c" found in src/. (check-in: 0a72991f4e user: drh tags: parser-enhancements) | |
15:06 | Avoid recursion in the yy_find_shift_action() routine of the Lemon-generated parser, so that routine can be inlined, for a size reduction and performance increase. (check-in: 0557a179f9 user: drh tags: trunk) | |
14:11 | Size reduction and performance improvement in the stack-popping logic of the Lemon-generated parser. (check-in: 9748c48a4f user: drh tags: trunk) | |
Changes to Makefile.in.
641 641 # Rule to build the amalgamation 642 642 # 643 643 sqlite3.lo: sqlite3.c 644 644 $(LTCOMPILE) $(TEMP_STORE) -c sqlite3.c 645 645 646 646 # Rules to build the LEMON compiler generator 647 647 # 648 -lemon$(BEXE): $(TOP)/tool/lemon.c $(TOP)/src/lempar.c 648 +lemon$(BEXE): $(TOP)/tool/lemon.c $(TOP)/tool/lempar.c 649 649 $(BCC) -o $@ $(TOP)/tool/lemon.c 650 - cp $(TOP)/src/lempar.c . 650 + cp $(TOP)/tool/lempar.c . 651 651 652 652 # Rules to build individual *.o files from generated *.c files. This 653 653 # applies to: 654 654 # 655 655 # parse.o 656 656 # opcodes.o 657 657 #
Changes to Makefile.msc.
1306 1306 # Rule to build the amalgamation 1307 1307 # 1308 1308 sqlite3.lo: $(SQLITE3C) 1309 1309 $(LTCOMPILE) $(CORE_COMPILE_OPTS) -c $(SQLITE3C) 1310 1310 1311 1311 # Rules to build the LEMON compiler generator 1312 1312 # 1313 -lempar.c: $(TOP)\src\lempar.c 1314 - copy $(TOP)\src\lempar.c . 1313 +lempar.c: $(TOP)\tool\lempar.c 1314 + copy $(TOP)\tool\lempar.c . 1315 1315 1316 1316 lemon.exe: $(TOP)\tool\lemon.c lempar.c 1317 1317 $(BCC) $(NO_WARN) -Daccess=_access \ 1318 1318 -Fe$@ $(TOP)\tool\lemon.c /link $(LDFLAGS) $(NLTLINKOPTS) $(NLTLIBPATHS) 1319 1319 1320 1320 # Rules to build individual *.lo files from generated *.c files. This 1321 1321 # applies to:
Changes to ext/fts5/fts5_main.c.
870 870 871 871 static int fts5CursorFirstSorted(Fts5Table *pTab, Fts5Cursor *pCsr, int bDesc){ 872 872 Fts5Config *pConfig = pTab->pConfig; 873 873 Fts5Sorter *pSorter; 874 874 int nPhrase; 875 875 int nByte; 876 876 int rc = SQLITE_OK; 877 - char *zSql; 878 877 const char *zRank = pCsr->zRank; 879 878 const char *zRankArgs = pCsr->zRankArgs; 880 879 881 880 nPhrase = sqlite3Fts5ExprPhraseCount(pCsr->pExpr); 882 881 nByte = sizeof(Fts5Sorter) + sizeof(int) * (nPhrase-1); 883 882 pSorter = (Fts5Sorter*)sqlite3_malloc(nByte); 884 883 if( pSorter==0 ) return SQLITE_NOMEM;
Changes to ext/fts5/fts5parse.y.
54 54 #define YYNOERRORRECOVERY 1 55 55 56 56 /* 57 57 ** Make yytestcase() the same as testcase() 58 58 */ 59 59 #define yytestcase(X) testcase(X) 60 60 61 +/* 62 +** Indicate that sqlite3ParserFree() will never be called with a null 63 +** pointer. 64 +*/ 65 +#define YYPARSEFREENOTNULL 1 66 + 67 +/* 68 +** Alternative datatype for the argument to the malloc() routine passed 69 +** into sqlite3ParserAlloc(). The default is size_t. 70 +*/ 71 +#define YYMALLOCARGTYPE u64 72 + 61 73 } // end %include 62 74 63 75 %left OR. 64 76 %left AND. 65 77 %left NOT. 66 78 %left TERM. 67 79 %left COLON. ................................................................................ 164 176 /* 165 177 ** Optional "*" character. 166 178 */ 167 179 %type star_opt {int} 168 180 169 181 star_opt(A) ::= STAR. { A = 1; } 170 182 star_opt(A) ::= . { A = 0; } 171 - 172 - 173 - 174 -
Changes to main.mk.
550 550 tclsh $(TOP)/ext/fts2/mkfts2amal.tcl 551 551 552 552 fts3amal.c: target_source $(TOP)/ext/fts3/mkfts3amal.tcl 553 553 tclsh $(TOP)/ext/fts3/mkfts3amal.tcl 554 554 555 555 # Rules to build the LEMON compiler generator 556 556 # 557 -lemon: $(TOP)/tool/lemon.c $(TOP)/src/lempar.c 557 +lemon: $(TOP)/tool/lemon.c $(TOP)/tool/lempar.c 558 558 $(BCC) -o lemon $(TOP)/tool/lemon.c 559 - cp $(TOP)/src/lempar.c . 559 + cp $(TOP)/tool/lempar.c . 560 560 561 561 # Rules to build individual *.o files from generated *.c files. This 562 562 # applies to: 563 563 # 564 564 # parse.o 565 565 # opcodes.o 566 566 #
Deleted src/lempar.c.
1 -/* Driver template for the LEMON parser generator. 2 -** The author disclaims copyright to this source code. 3 -** 4 -** This version of "lempar.c" is modified, slightly, for use by SQLite. 5 -** The only modifications are the addition of a couple of NEVER() 6 -** macros to disable tests that are needed in the case of a general 7 -** LALR(1) grammar but which are always false in the 8 -** specific grammar used by SQLite. 9 -*/ 10 -/* First off, code is included that follows the "include" declaration 11 -** in the input grammar file. */ 12 -#include <stdio.h> 13 -%% 14 -/* Next is all token values, in a form suitable for use by makeheaders. 15 -** This section will be null unless lemon is run with the -m switch. 16 -*/ 17 -/* 18 -** These constants (all generated automatically by the parser generator) 19 -** specify the various kinds of tokens (terminals) that the parser 20 -** understands. 21 -** 22 -** Each symbol here is a terminal symbol in the grammar. 23 -*/ 24 -%% 25 -/* Make sure the INTERFACE macro is defined. 26 -*/ 27 -#ifndef INTERFACE 28 -# define INTERFACE 1 29 -#endif 30 -/* The next thing included is series of defines which control 31 -** various aspects of the generated parser. 32 -** YYCODETYPE is the data type used for storing terminal 33 -** and nonterminal numbers. "unsigned char" is 34 -** used if there are fewer than 250 terminals 35 -** and nonterminals. "int" is used otherwise. 36 -** YYNOCODE is a number of type YYCODETYPE which corresponds 37 -** to no legal terminal or nonterminal number. This 38 -** number is used to fill in empty slots of the hash 39 -** table. 40 -** YYFALLBACK If defined, this indicates that one or more tokens 41 -** have fall-back values which should be used if the 42 -** original value of the token will not parse. 43 -** YYACTIONTYPE is the data type used for storing terminal 44 -** and nonterminal numbers. "unsigned char" is 45 -** used if there are fewer than 250 rules and 46 -** states combined. "int" is used otherwise. 47 -** ParseTOKENTYPE is the data type used for minor tokens given 48 -** directly to the parser from the tokenizer. 49 -** YYMINORTYPE is the data type used for all minor tokens. 50 -** This is typically a union of many types, one of 51 -** which is ParseTOKENTYPE. The entry in the union 52 -** for base tokens is called "yy0". 53 -** YYSTACKDEPTH is the maximum depth of the parser's stack. If 54 -** zero the stack is dynamically sized using realloc() 55 -** ParseARG_SDECL A static variable declaration for the %extra_argument 56 -** ParseARG_PDECL A parameter declaration for the %extra_argument 57 -** ParseARG_STORE Code to store %extra_argument into yypParser 58 -** ParseARG_FETCH Code to extract %extra_argument from yypParser 59 -** YYERRORSYMBOL is the code number of the error symbol. If not 60 -** defined, then do no error processing. 61 -** YYNSTATE the combined number of states. 62 -** YYNRULE the number of rules in the grammar 63 -** YY_MAX_SHIFT Maximum value for shift actions 64 -** YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions 65 -** YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions 66 -** YY_MIN_REDUCE Maximum value for reduce actions 67 -** YY_ERROR_ACTION The yy_action[] code for syntax error 68 -** YY_ACCEPT_ACTION The yy_action[] code for accept 69 -** YY_NO_ACTION The yy_action[] code for no-op 70 -*/ 71 -%% 72 - 73 -/* The yyzerominor constant is used to initialize instances of 74 -** YYMINORTYPE objects to zero. */ 75 -static const YYMINORTYPE yyzerominor = { 0 }; 76 - 77 -/* Define the yytestcase() macro to be a no-op if is not already defined 78 -** otherwise. 79 -** 80 -** Applications can choose to define yytestcase() in the %include section 81 -** to a macro that can assist in verifying code coverage. For production 82 -** code the yytestcase() macro should be turned off. But it is useful 83 -** for testing. 84 -*/ 85 -#ifndef yytestcase 86 -# define yytestcase(X) 87 -#endif 88 - 89 - 90 -/* Next are the tables used to determine what action to take based on the 91 -** current state and lookahead token. These tables are used to implement 92 -** functions that take a state number and lookahead value and return an 93 -** action integer. 94 -** 95 -** Suppose the action integer is N. Then the action is determined as 96 -** follows 97 -** 98 -** 0 <= N <= YY_MAX_SHIFT Shift N. That is, push the lookahead 99 -** token onto the stack and goto state N. 100 -** 101 -** N between YY_MIN_SHIFTREDUCE Shift to an arbitrary state then 102 -** and YY_MAX_SHIFTREDUCE reduce by rule N-YY_MIN_SHIFTREDUCE. 103 -** 104 -** N between YY_MIN_REDUCE Reduce by rule N-YY_MIN_REDUCE 105 -** and YY_MAX_REDUCE 106 - 107 -** N == YY_ERROR_ACTION A syntax error has occurred. 108 -** 109 -** N == YY_ACCEPT_ACTION The parser accepts its input. 110 -** 111 -** N == YY_NO_ACTION No such action. Denotes unused 112 -** slots in the yy_action[] table. 113 -** 114 -** The action table is constructed as a single large table named yy_action[]. 115 -** Given state S and lookahead X, the action is computed as 116 -** 117 -** yy_action[ yy_shift_ofst[S] + X ] 118 -** 119 -** If the index value yy_shift_ofst[S]+X is out of range or if the value 120 -** yy_lookahead[yy_shift_ofst[S]+X] is not equal to X or if yy_shift_ofst[S] 121 -** is equal to YY_SHIFT_USE_DFLT, it means that the action is not in the table 122 -** and that yy_default[S] should be used instead. 123 -** 124 -** The formula above is for computing the action when the lookahead is 125 -** a terminal symbol. If the lookahead is a non-terminal (as occurs after 126 -** a reduce action) then the yy_reduce_ofst[] array is used in place of 127 -** the yy_shift_ofst[] array and YY_REDUCE_USE_DFLT is used in place of 128 -** YY_SHIFT_USE_DFLT. 129 -** 130 -** The following are the tables generated in this section: 131 -** 132 -** yy_action[] A single table containing all actions. 133 -** yy_lookahead[] A table containing the lookahead for each entry in 134 -** yy_action. Used to detect hash collisions. 135 -** yy_shift_ofst[] For each state, the offset into yy_action for 136 -** shifting terminals. 137 -** yy_reduce_ofst[] For each state, the offset into yy_action for 138 -** shifting non-terminals after a reduce. 139 -** yy_default[] Default action for each state. 140 -*/ 141 -%% 142 - 143 -/* The next table maps tokens into fallback tokens. If a construct 144 -** like the following: 145 -** 146 -** %fallback ID X Y Z. 147 -** 148 -** appears in the grammar, then ID becomes a fallback token for X, Y, 149 -** and Z. Whenever one of the tokens X, Y, or Z is input to the parser 150 -** but it does not parse, the type of the token is changed to ID and 151 -** the parse is retried before an error is thrown. 152 -*/ 153 -#ifdef YYFALLBACK 154 -static const YYCODETYPE yyFallback[] = { 155 -%% 156 -}; 157 -#endif /* YYFALLBACK */ 158 - 159 -/* The following structure represents a single element of the 160 -** parser's stack. Information stored includes: 161 -** 162 -** + The state number for the parser at this level of the stack. 163 -** 164 -** + The value of the token stored at this level of the stack. 165 -** (In other words, the "major" token.) 166 -** 167 -** + The semantic value stored at this level of the stack. This is 168 -** the information used by the action routines in the grammar. 169 -** It is sometimes called the "minor" token. 170 -** 171 -** After the "shift" half of a SHIFTREDUCE action, the stateno field 172 -** actually contains the reduce action for the second half of the 173 -** SHIFTREDUCE. 174 -*/ 175 -struct yyStackEntry { 176 - YYACTIONTYPE stateno; /* The state-number, or reduce action in SHIFTREDUCE */ 177 - YYCODETYPE major; /* The major token value. This is the code 178 - ** number for the token at this stack level */ 179 - YYMINORTYPE minor; /* The user-supplied minor token value. This 180 - ** is the value of the token */ 181 -}; 182 -typedef struct yyStackEntry yyStackEntry; 183 - 184 -/* The state of the parser is completely contained in an instance of 185 -** the following structure */ 186 -struct yyParser { 187 - int yyidx; /* Index of top element in stack */ 188 -#ifdef YYTRACKMAXSTACKDEPTH 189 - int yyidxMax; /* Maximum value of yyidx */ 190 -#endif 191 - int yyerrcnt; /* Shifts left before out of the error */ 192 - ParseARG_SDECL /* A place to hold %extra_argument */ 193 -#if YYSTACKDEPTH<=0 194 - int yystksz; /* Current side of the stack */ 195 - yyStackEntry *yystack; /* The parser's stack */ 196 -#else 197 - yyStackEntry yystack[YYSTACKDEPTH]; /* The parser's stack */ 198 -#endif 199 -}; 200 -typedef struct yyParser yyParser; 201 - 202 -#ifndef NDEBUG 203 -#include <stdio.h> 204 -static FILE *yyTraceFILE = 0; 205 -static char *yyTracePrompt = 0; 206 -#endif /* NDEBUG */ 207 - 208 -#ifndef NDEBUG 209 -/* 210 -** Turn parser tracing on by giving a stream to which to write the trace 211 -** and a prompt to preface each trace message. Tracing is turned off 212 -** by making either argument NULL 213 -** 214 -** Inputs: 215 -** <ul> 216 -** <li> A FILE* to which trace output should be written. 217 -** If NULL, then tracing is turned off. 218 -** <li> A prefix string written at the beginning of every 219 -** line of trace output. If NULL, then tracing is 220 -** turned off. 221 -** </ul> 222 -** 223 -** Outputs: 224 -** None. 225 -*/ 226 -void ParseTrace(FILE *TraceFILE, char *zTracePrompt){ 227 - yyTraceFILE = TraceFILE; 228 - yyTracePrompt = zTracePrompt; 229 - if( yyTraceFILE==0 ) yyTracePrompt = 0; 230 - else if( yyTracePrompt==0 ) yyTraceFILE = 0; 231 -} 232 -#endif /* NDEBUG */ 233 - 234 -#ifndef NDEBUG 235 -/* For tracing shifts, the names of all terminals and nonterminals 236 -** are required. The following table supplies these names */ 237 -static const char *const yyTokenName[] = { 238 -%% 239 -}; 240 -#endif /* NDEBUG */ 241 - 242 -#ifndef NDEBUG 243 -/* For tracing reduce actions, the names of all rules are required. 244 -*/ 245 -static const char *const yyRuleName[] = { 246 -%% 247 -}; 248 -#endif /* NDEBUG */ 249 - 250 - 251 -#if YYSTACKDEPTH<=0 252 -/* 253 -** Try to increase the size of the parser stack. 254 -*/ 255 -static void yyGrowStack(yyParser *p){ 256 - int newSize; 257 - yyStackEntry *pNew; 258 - 259 - newSize = p->yystksz*2 + 100; 260 - pNew = realloc(p->yystack, newSize*sizeof(pNew[0])); 261 - if( pNew ){ 262 - p->yystack = pNew; 263 - p->yystksz = newSize; 264 -#ifndef NDEBUG 265 - if( yyTraceFILE ){ 266 - fprintf(yyTraceFILE,"%sStack grows to %d entries!\n", 267 - yyTracePrompt, p->yystksz); 268 - } 269 -#endif 270 - } 271 -} 272 -#endif 273 - 274 -/* 275 -** This function allocates a new parser. 276 -** The only argument is a pointer to a function which works like 277 -** malloc. 278 -** 279 -** Inputs: 280 -** A pointer to the function used to allocate memory. 281 -** 282 -** Outputs: 283 -** A pointer to a parser. This pointer is used in subsequent calls 284 -** to Parse and ParseFree. 285 -*/ 286 -void *ParseAlloc(void *(*mallocProc)(u64)){ 287 - yyParser *pParser; 288 - pParser = (yyParser*)(*mallocProc)( (u64)sizeof(yyParser) ); 289 - if( pParser ){ 290 - pParser->yyidx = -1; 291 -#ifdef YYTRACKMAXSTACKDEPTH 292 - pParser->yyidxMax = 0; 293 -#endif 294 -#if YYSTACKDEPTH<=0 295 - pParser->yystack = NULL; 296 - pParser->yystksz = 0; 297 - yyGrowStack(pParser); 298 -#endif 299 - } 300 - return pParser; 301 -} 302 - 303 -/* The following function deletes the value associated with a 304 -** symbol. The symbol can be either a terminal or nonterminal. 305 -** "yymajor" is the symbol code, and "yypminor" is a pointer to 306 -** the value. 307 -*/ 308 -static void yy_destructor( 309 - yyParser *yypParser, /* The parser */ 310 - YYCODETYPE yymajor, /* Type code for object to destroy */ 311 - YYMINORTYPE *yypminor /* The object to be destroyed */ 312 -){ 313 - ParseARG_FETCH; 314 - switch( yymajor ){ 315 - /* Here is inserted the actions which take place when a 316 - ** terminal or non-terminal is destroyed. This can happen 317 - ** when the symbol is popped from the stack during a 318 - ** reduce or during error processing or when a parser is 319 - ** being destroyed before it is finished parsing. 320 - ** 321 - ** Note: during a reduce, the only symbols destroyed are those 322 - ** which appear on the RHS of the rule, but which are not used 323 - ** inside the C code. 324 - */ 325 -%% 326 - default: break; /* If no destructor action specified: do nothing */ 327 - } 328 -} 329 - 330 -/* 331 -** Pop the parser's stack once. 332 -** 333 -** If there is a destructor routine associated with the token which 334 -** is popped from the stack, then call it. 335 -*/ 336 -static void yy_pop_parser_stack(yyParser *pParser){ 337 - yyStackEntry *yytos; 338 - assert( pParser->yyidx>=0 ); 339 - yytos = &pParser->yystack[pParser->yyidx--]; 340 -#ifndef NDEBUG 341 - if( yyTraceFILE ){ 342 - fprintf(yyTraceFILE,"%sPopping %s\n", 343 - yyTracePrompt, 344 - yyTokenName[yytos->major]); 345 - } 346 -#endif 347 - yy_destructor(pParser, yytos->major, &yytos->minor); 348 -} 349 - 350 -/* 351 -** Deallocate and destroy a parser. Destructors are all called for 352 -** all stack elements before shutting the parser down. 353 -** 354 -** Inputs: 355 -** <ul> 356 -** <li> A pointer to the parser. This should be a pointer 357 -** obtained from ParseAlloc. 358 -** <li> A pointer to a function used to reclaim memory obtained 359 -** from malloc. 360 -** </ul> 361 -*/ 362 -void ParseFree( 363 - void *p, /* The parser to be deleted */ 364 - void (*freeProc)(void*) /* Function used to reclaim memory */ 365 -){ 366 - yyParser *pParser = (yyParser*)p; 367 - /* In SQLite, we never try to destroy a parser that was not successfully 368 - ** created in the first place. */ 369 - if( NEVER(pParser==0) ) return; 370 - while( pParser->yyidx>=0 ) yy_pop_parser_stack(pParser); 371 -#if YYSTACKDEPTH<=0 372 - free(pParser->yystack); 373 -#endif 374 - (*freeProc)((void*)pParser); 375 -} 376 - 377 -/* 378 -** Return the peak depth of the stack for a parser. 379 -*/ 380 -#ifdef YYTRACKMAXSTACKDEPTH 381 -int ParseStackPeak(void *p){ 382 - yyParser *pParser = (yyParser*)p; 383 - return pParser->yyidxMax; 384 -} 385 -#endif 386 - 387 -/* 388 -** Find the appropriate action for a parser given the terminal 389 -** look-ahead token iLookAhead. 390 -** 391 -** If the look-ahead token is YYNOCODE, then check to see if the action is 392 -** independent of the look-ahead. If it is, return the action, otherwise 393 -** return YY_NO_ACTION. 394 -*/ 395 -static int yy_find_shift_action( 396 - yyParser *pParser, /* The parser */ 397 - YYCODETYPE iLookAhead /* The look-ahead token */ 398 -){ 399 - int i; 400 - int stateno = pParser->yystack[pParser->yyidx].stateno; 401 - 402 - if( stateno>=YY_MIN_REDUCE ) return stateno; 403 - assert( stateno <= YY_SHIFT_COUNT ); 404 - do{ 405 - i = yy_shift_ofst[stateno]; 406 - if( i==YY_SHIFT_USE_DFLT ) return yy_default[stateno]; 407 - assert( iLookAhead!=YYNOCODE ); 408 - i += iLookAhead; 409 - if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ 410 - if( iLookAhead>0 ){ 411 -#ifdef YYFALLBACK 412 - YYCODETYPE iFallback; /* Fallback token */ 413 - if( iLookAhead<sizeof(yyFallback)/sizeof(yyFallback[0]) 414 - && (iFallback = yyFallback[iLookAhead])!=0 ){ 415 -#ifndef NDEBUG 416 - if( yyTraceFILE ){ 417 - fprintf(yyTraceFILE, "%sFALLBACK %s => %s\n", 418 - yyTracePrompt, yyTokenName[iLookAhead], yyTokenName[iFallback]); 419 - } 420 -#endif 421 - assert( yyFallback[iFallback]==0 ); /* Fallback loop must terminate */ 422 - iLookAhead = iFallback; 423 - continue; 424 - } 425 -#endif 426 -#ifdef YYWILDCARD 427 - { 428 - int j = i - iLookAhead + YYWILDCARD; 429 - if( 430 -#if YY_SHIFT_MIN+YYWILDCARD<0 431 - j>=0 && 432 -#endif 433 -#if YY_SHIFT_MAX+YYWILDCARD>=YY_ACTTAB_COUNT 434 - j<YY_ACTTAB_COUNT && 435 -#endif 436 - yy_lookahead[j]==YYWILDCARD 437 - ){ 438 -#ifndef NDEBUG 439 - if( yyTraceFILE ){ 440 - fprintf(yyTraceFILE, "%sWILDCARD %s => %s\n", 441 - yyTracePrompt, yyTokenName[iLookAhead], 442 - yyTokenName[YYWILDCARD]); 443 - } 444 -#endif /* NDEBUG */ 445 - return yy_action[j]; 446 - } 447 - } 448 -#endif /* YYWILDCARD */ 449 - } 450 - return yy_default[stateno]; 451 - }else{ 452 - return yy_action[i]; 453 - } 454 - }while(1); 455 -} 456 - 457 -/* 458 -** Find the appropriate action for a parser given the non-terminal 459 -** look-ahead token iLookAhead. 460 -** 461 -** If the look-ahead token is YYNOCODE, then check to see if the action is 462 -** independent of the look-ahead. If it is, return the action, otherwise 463 -** return YY_NO_ACTION. 464 -*/ 465 -static int yy_find_reduce_action( 466 - int stateno, /* Current state number */ 467 - YYCODETYPE iLookAhead /* The look-ahead token */ 468 -){ 469 - int i; 470 -#ifdef YYERRORSYMBOL 471 - if( stateno>YY_REDUCE_COUNT ){ 472 - return yy_default[stateno]; 473 - } 474 -#else 475 - assert( stateno<=YY_REDUCE_COUNT ); 476 -#endif 477 - i = yy_reduce_ofst[stateno]; 478 - assert( i!=YY_REDUCE_USE_DFLT ); 479 - assert( iLookAhead!=YYNOCODE ); 480 - i += iLookAhead; 481 -#ifdef YYERRORSYMBOL 482 - if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){ 483 - return yy_default[stateno]; 484 - } 485 -#else 486 - assert( i>=0 && i<YY_ACTTAB_COUNT ); 487 - assert( yy_lookahead[i]==iLookAhead ); 488 -#endif 489 - return yy_action[i]; 490 -} 491 - 492 -/* 493 -** The following routine is called if the stack overflows. 494 -*/ 495 -static void yyStackOverflow(yyParser *yypParser, YYMINORTYPE *yypMinor){ 496 - ParseARG_FETCH; 497 - yypParser->yyidx--; 498 -#ifndef NDEBUG 499 - if( yyTraceFILE ){ 500 - fprintf(yyTraceFILE,"%sStack Overflow!\n",yyTracePrompt); 501 - } 502 -#endif 503 - while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); 504 - /* Here code is inserted which will execute if the parser 505 - ** stack every overflows */ 506 -%% 507 - ParseARG_STORE; /* Suppress warning about unused %extra_argument var */ 508 -} 509 - 510 -/* 511 -** Print tracing information for a SHIFT action 512 -*/ 513 -#ifndef NDEBUG 514 -static void yyTraceShift(yyParser *yypParser, int yyNewState){ 515 - if( yyTraceFILE ){ 516 - int i; 517 - if( yyNewState<YYNSTATE ){ 518 - fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState); 519 - fprintf(yyTraceFILE,"%sStack:",yyTracePrompt); 520 - for(i=1; i<=yypParser->yyidx; i++) 521 - fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]); 522 - fprintf(yyTraceFILE,"\n"); 523 - }else{ 524 - fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt); 525 - } 526 - } 527 -} 528 -#else 529 -# define yyTraceShift(X,Y) 530 -#endif 531 - 532 -/* 533 -** Perform a shift action. Return the number of errors. 534 -*/ 535 -static void yy_shift( 536 - yyParser *yypParser, /* The parser to be shifted */ 537 - int yyNewState, /* The new state to shift in */ 538 - int yyMajor, /* The major token to shift in */ 539 - YYMINORTYPE *yypMinor /* Pointer to the minor token to shift in */ 540 -){ 541 - yyStackEntry *yytos; 542 - yypParser->yyidx++; 543 -#ifdef YYTRACKMAXSTACKDEPTH 544 - if( yypParser->yyidx>yypParser->yyidxMax ){ 545 - yypParser->yyidxMax = yypParser->yyidx; 546 - } 547 -#endif 548 -#if YYSTACKDEPTH>0 549 - if( yypParser->yyidx>=YYSTACKDEPTH ){ 550 - yyStackOverflow(yypParser, yypMinor); 551 - return; 552 - } 553 -#else 554 - if( yypParser->yyidx>=yypParser->yystksz ){ 555 - yyGrowStack(yypParser); 556 - if( yypParser->yyidx>=yypParser->yystksz ){ 557 - yyStackOverflow(yypParser, yypMinor); 558 - return; 559 - } 560 - } 561 -#endif 562 - yytos = &yypParser->yystack[yypParser->yyidx]; 563 - yytos->stateno = (YYACTIONTYPE)yyNewState; 564 - yytos->major = (YYCODETYPE)yyMajor; 565 - yytos->minor = *yypMinor; 566 - yyTraceShift(yypParser, yyNewState); 567 -} 568 - 569 -/* The following table contains information about every rule that 570 -** is used during the reduce. 571 -*/ 572 -static const struct { 573 - YYCODETYPE lhs; /* Symbol on the left-hand side of the rule */ 574 - unsigned char nrhs; /* Number of right-hand side symbols in the rule */ 575 -} yyRuleInfo[] = { 576 -%% 577 -}; 578 - 579 -static void yy_accept(yyParser*); /* Forward Declaration */ 580 - 581 -/* 582 -** Perform a reduce action and the shift that must immediately 583 -** follow the reduce. 584 -*/ 585 -static void yy_reduce( 586 - yyParser *yypParser, /* The parser */ 587 - int yyruleno /* Number of the rule by which to reduce */ 588 -){ 589 - int yygoto; /* The next state */ 590 - int yyact; /* The next action */ 591 - YYMINORTYPE yygotominor; /* The LHS of the rule reduced */ 592 - yyStackEntry *yymsp; /* The top of the parser's stack */ 593 - int yysize; /* Amount to pop the stack */ 594 - ParseARG_FETCH; 595 - yymsp = &yypParser->yystack[yypParser->yyidx]; 596 -#ifndef NDEBUG 597 - if( yyTraceFILE && yyruleno>=0 598 - && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){ 599 - yysize = yyRuleInfo[yyruleno].nrhs; 600 - fprintf(yyTraceFILE, "%sReduce [%s] -> state %d.\n", yyTracePrompt, 601 - yyRuleName[yyruleno], yymsp[-yysize].stateno); 602 - } 603 -#endif /* NDEBUG */ 604 - 605 - /* Silence complaints from purify about yygotominor being uninitialized 606 - ** in some cases when it is copied into the stack after the following 607 - ** switch. yygotominor is uninitialized when a rule reduces that does 608 - ** not set the value of its left-hand side nonterminal. Leaving the 609 - ** value of the nonterminal uninitialized is utterly harmless as long 610 - ** as the value is never used. So really the only thing this code 611 - ** accomplishes is to quieten purify. 612 - ** 613 - ** 2007-01-16: The wireshark project (www.wireshark.org) reports that 614 - ** without this code, their parser segfaults. I'm not sure what there 615 - ** parser is doing to make this happen. This is the second bug report 616 - ** from wireshark this week. Clearly they are stressing Lemon in ways 617 - ** that it has not been previously stressed... (SQLite ticket #2172) 618 - */ 619 - /*memset(&yygotominor, 0, sizeof(yygotominor));*/ 620 - yygotominor = yyzerominor; 621 - 622 - 623 - switch( yyruleno ){ 624 - /* Beginning here are the reduction cases. A typical example 625 - ** follows: 626 - ** case 0: 627 - ** #line <lineno> <grammarfile> 628 - ** { ... } // User supplied code 629 - ** #line <lineno> <thisfile> 630 - ** break; 631 - */ 632 -%% 633 - }; 634 - assert( yyruleno>=0 && yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) ); 635 - yygoto = yyRuleInfo[yyruleno].lhs; 636 - yysize = yyRuleInfo[yyruleno].nrhs; 637 - yypParser->yyidx -= yysize; 638 - yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto); 639 - if( yyact <= YY_MAX_SHIFTREDUCE ){ 640 - if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 641 - /* If the reduce action popped at least 642 - ** one element off the stack, then we can push the new element back 643 - ** onto the stack here, and skip the stack overflow test in yy_shift(). 644 - ** That gives a significant speed improvement. */ 645 - if( yysize ){ 646 - yypParser->yyidx++; 647 - yymsp -= yysize-1; 648 - yymsp->stateno = (YYACTIONTYPE)yyact; 649 - yymsp->major = (YYCODETYPE)yygoto; 650 - yymsp->minor = yygotominor; 651 - yyTraceShift(yypParser, yyact); 652 - }else{ 653 - yy_shift(yypParser,yyact,yygoto,&yygotominor); 654 - } 655 - }else{ 656 - assert( yyact == YY_ACCEPT_ACTION ); 657 - yy_accept(yypParser); 658 - } 659 -} 660 - 661 -/* 662 -** The following code executes when the parse fails 663 -*/ 664 -#ifndef YYNOERRORRECOVERY 665 -static void yy_parse_failed( 666 - yyParser *yypParser /* The parser */ 667 -){ 668 - ParseARG_FETCH; 669 -#ifndef NDEBUG 670 - if( yyTraceFILE ){ 671 - fprintf(yyTraceFILE,"%sFail!\n",yyTracePrompt); 672 - } 673 -#endif 674 - while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); 675 - /* Here code is inserted which will be executed whenever the 676 - ** parser fails */ 677 -%% 678 - ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ 679 -} 680 -#endif /* YYNOERRORRECOVERY */ 681 - 682 -/* 683 -** The following code executes when a syntax error first occurs. 684 -*/ 685 -static void yy_syntax_error( 686 - yyParser *yypParser, /* The parser */ 687 - int yymajor, /* The major type of the error token */ 688 - YYMINORTYPE yyminor /* The minor type of the error token */ 689 -){ 690 - ParseARG_FETCH; 691 -#define TOKEN (yyminor.yy0) 692 -%% 693 - ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ 694 -} 695 - 696 -/* 697 -** The following is executed when the parser accepts 698 -*/ 699 -static void yy_accept( 700 - yyParser *yypParser /* The parser */ 701 -){ 702 - ParseARG_FETCH; 703 -#ifndef NDEBUG 704 - if( yyTraceFILE ){ 705 - fprintf(yyTraceFILE,"%sAccept!\n",yyTracePrompt); 706 - } 707 -#endif 708 - while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); 709 - /* Here code is inserted which will be executed whenever the 710 - ** parser accepts */ 711 -%% 712 - ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ 713 -} 714 - 715 -/* The main parser program. 716 -** The first argument is a pointer to a structure obtained from 717 -** "ParseAlloc" which describes the current state of the parser. 718 -** The second argument is the major token number. The third is 719 -** the minor token. The fourth optional argument is whatever the 720 -** user wants (and specified in the grammar) and is available for 721 -** use by the action routines. 722 -** 723 -** Inputs: 724 -** <ul> 725 -** <li> A pointer to the parser (an opaque structure.) 726 -** <li> The major token number. 727 -** <li> The minor token number. 728 -** <li> An option argument of a grammar-specified type. 729 -** </ul> 730 -** 731 -** Outputs: 732 -** None. 733 -*/ 734 -void Parse( 735 - void *yyp, /* The parser */ 736 - int yymajor, /* The major token code number */ 737 - ParseTOKENTYPE yyminor /* The value for the token */ 738 - ParseARG_PDECL /* Optional %extra_argument parameter */ 739 -){ 740 - YYMINORTYPE yyminorunion; 741 - int yyact; /* The parser action. */ 742 -#if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY) 743 - int yyendofinput; /* True if we are at the end of input */ 744 -#endif 745 -#ifdef YYERRORSYMBOL 746 - int yyerrorhit = 0; /* True if yymajor has invoked an error */ 747 -#endif 748 - yyParser *yypParser; /* The parser */ 749 - 750 - /* (re)initialize the parser, if necessary */ 751 - yypParser = (yyParser*)yyp; 752 - if( yypParser->yyidx<0 ){ 753 -#if YYSTACKDEPTH<=0 754 - if( yypParser->yystksz <=0 ){ 755 - /*memset(&yyminorunion, 0, sizeof(yyminorunion));*/ 756 - yyminorunion = yyzerominor; 757 - yyStackOverflow(yypParser, &yyminorunion); 758 - return; 759 - } 760 -#endif 761 - yypParser->yyidx = 0; 762 - yypParser->yyerrcnt = -1; 763 - yypParser->yystack[0].stateno = 0; 764 - yypParser->yystack[0].major = 0; 765 - } 766 - yyminorunion.yy0 = yyminor; 767 -#if !defined(YYERRORSYMBOL) && !defined(YYNOERRORRECOVERY) 768 - yyendofinput = (yymajor==0); 769 -#endif 770 - ParseARG_STORE; 771 - 772 -#ifndef NDEBUG 773 - if( yyTraceFILE ){ 774 - fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]); 775 - } 776 -#endif 777 - 778 - do{ 779 - yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor); 780 - if( yyact <= YY_MAX_SHIFTREDUCE ){ 781 - if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE; 782 - yy_shift(yypParser,yyact,yymajor,&yyminorunion); 783 - yypParser->yyerrcnt--; 784 - yymajor = YYNOCODE; 785 - }else if( yyact <= YY_MAX_REDUCE ){ 786 - yy_reduce(yypParser,yyact-YY_MIN_REDUCE); 787 - }else{ 788 - assert( yyact == YY_ERROR_ACTION ); 789 -#ifdef YYERRORSYMBOL 790 - int yymx; 791 -#endif 792 -#ifndef NDEBUG 793 - if( yyTraceFILE ){ 794 - fprintf(yyTraceFILE,"%sSyntax Error!\n",yyTracePrompt); 795 - } 796 -#endif 797 -#ifdef YYERRORSYMBOL 798 - /* A syntax error has occurred. 799 - ** The response to an error depends upon whether or not the 800 - ** grammar defines an error token "ERROR". 801 - ** 802 - ** This is what we do if the grammar does define ERROR: 803 - ** 804 - ** * Call the %syntax_error function. 805 - ** 806 - ** * Begin popping the stack until we enter a state where 807 - ** it is legal to shift the error symbol, then shift 808 - ** the error symbol. 809 - ** 810 - ** * Set the error count to three. 811 - ** 812 - ** * Begin accepting and shifting new tokens. No new error 813 - ** processing will occur until three tokens have been 814 - ** shifted successfully. 815 - ** 816 - */ 817 - if( yypParser->yyerrcnt<0 ){ 818 - yy_syntax_error(yypParser,yymajor,yyminorunion); 819 - } 820 - yymx = yypParser->yystack[yypParser->yyidx].major; 821 - if( yymx==YYERRORSYMBOL || yyerrorhit ){ 822 -#ifndef NDEBUG 823 - if( yyTraceFILE ){ 824 - fprintf(yyTraceFILE,"%sDiscard input token %s\n", 825 - yyTracePrompt,yyTokenName[yymajor]); 826 - } 827 -#endif 828 - yy_destructor(yypParser, (YYCODETYPE)yymajor,&yyminorunion); 829 - yymajor = YYNOCODE; 830 - }else{ 831 - while( 832 - yypParser->yyidx >= 0 && 833 - yymx != YYERRORSYMBOL && 834 - (yyact = yy_find_reduce_action( 835 - yypParser->yystack[yypParser->yyidx].stateno, 836 - YYERRORSYMBOL)) >= YY_MIN_REDUCE 837 - ){ 838 - yy_pop_parser_stack(yypParser); 839 - } 840 - if( yypParser->yyidx < 0 || yymajor==0 ){ 841 - yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); 842 - yy_parse_failed(yypParser); 843 - yymajor = YYNOCODE; 844 - }else if( yymx!=YYERRORSYMBOL ){ 845 - YYMINORTYPE u2; 846 - u2.YYERRSYMDT = 0; 847 - yy_shift(yypParser,yyact,YYERRORSYMBOL,&u2); 848 - } 849 - } 850 - yypParser->yyerrcnt = 3; 851 - yyerrorhit = 1; 852 -#elif defined(YYNOERRORRECOVERY) 853 - /* If the YYNOERRORRECOVERY macro is defined, then do not attempt to 854 - ** do any kind of error recovery. Instead, simply invoke the syntax 855 - ** error routine and continue going as if nothing had happened. 856 - ** 857 - ** Applications can set this macro (for example inside %include) if 858 - ** they intend to abandon the parse upon the first syntax error seen. 859 - */ 860 - yy_syntax_error(yypParser,yymajor,yyminorunion); 861 - yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); 862 - yymajor = YYNOCODE; 863 - 864 -#else /* YYERRORSYMBOL is not defined */ 865 - /* This is what we do if the grammar does not define ERROR: 866 - ** 867 - ** * Report an error message, and throw away the input token. 868 - ** 869 - ** * If the input token is $, then fail the parse. 870 - ** 871 - ** As before, subsequent error messages are suppressed until 872 - ** three input tokens have been successfully shifted. 873 - */ 874 - if( yypParser->yyerrcnt<=0 ){ 875 - yy_syntax_error(yypParser,yymajor,yyminorunion); 876 - } 877 - yypParser->yyerrcnt = 3; 878 - yy_destructor(yypParser,(YYCODETYPE)yymajor,&yyminorunion); 879 - if( yyendofinput ){ 880 - yy_parse_failed(yypParser); 881 - } 882 - yymajor = YYNOCODE; 883 -#endif 884 - } 885 - }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 ); 886 -#ifndef NDEBUG 887 - if( yyTraceFILE ){ 888 - fprintf(yyTraceFILE,"%sReturn\n",yyTracePrompt); 889 - } 890 -#endif 891 - return; 892 -}
Changes to src/parse.y.
56 56 #define YYNOERRORRECOVERY 1 57 57 58 58 /* 59 59 ** Make yytestcase() the same as testcase() 60 60 */ 61 61 #define yytestcase(X) testcase(X) 62 62 63 +/* 64 +** Indicate that sqlite3ParserFree() will never be called with a null 65 +** pointer. 66 +*/ 67 +#define YYPARSEFREENOTNULL 1 68 + 69 +/* 70 +** Alternative datatype for the argument to the malloc() routine passed 71 +** into sqlite3ParserAlloc(). The default is size_t. 72 +*/ 73 +#define YYMALLOCARGTYPE u64 74 + 63 75 /* 64 76 ** An instance of this structure holds information about the 65 77 ** LIMIT clause of a SELECT statement. 66 78 */ 67 79 struct LimitVal { 68 80 Expr *pLimit; /* The LIMIT expression. NULL if there is no limit */ 69 81 Expr *pOffset; /* The OFFSET expression. NULL if there is none */ ................................................................................ 635 647 dbnm(A) ::= DOT nm(X). {A = X;} 636 648 637 649 %type fullname {SrcList*} 638 650 %destructor fullname {sqlite3SrcListDelete(pParse->db, $$);} 639 651 fullname(A) ::= nm(X) dbnm(Y). {A = sqlite3SrcListAppend(pParse->db,0,&X,&Y);} 640 652 641 653 %type joinop {int} 642 -%type joinop2 {int} 643 654 joinop(X) ::= COMMA|JOIN. { X = JT_INNER; } 644 655 joinop(X) ::= JOIN_KW(A) JOIN. { X = sqlite3JoinType(pParse,&A,0,0); } 645 656 joinop(X) ::= JOIN_KW(A) nm(B) JOIN. { X = sqlite3JoinType(pParse,&A,&B,0); } 646 657 joinop(X) ::= JOIN_KW(A) nm(B) nm(C) JOIN. 647 658 { X = sqlite3JoinType(pParse,&A,&B,&C); } 648 659 649 660 %type on_opt {Expr*}
Changes to src/tokenize.c.
365 365 } 366 366 #endif 367 367 default: { 368 368 if( !IdChar(*z) ){ 369 369 break; 370 370 } 371 371 for(i=1; IdChar(z[i]); i++){} 372 - *tokenType = keywordCode((char*)z, i); 373 - return i; 372 + *tokenType = TK_ID; 373 + return keywordCode((char*)z, i, tokenType); 374 374 } 375 375 } 376 376 *tokenType = TK_ILLEGAL; 377 377 return 1; 378 378 } 379 379 380 380 /*
Changes to tool/lempar.c.
1 -/* Driver template for the LEMON parser generator. 2 -** The author disclaims copyright to this source code. 1 +/* 2 +** 2000-05-29 3 +** 4 +** The author disclaims copyright to this source code. In place of 5 +** a legal notice, here is a blessing: 6 +** 7 +** May you do good and not evil. 8 +** May you find forgiveness for yourself and forgive others. 9 +** May you share freely, never taking more than you give. 10 +** 11 +************************************************************************* 12 +** Driver template for the LEMON parser generator. 13 +** 14 +** The "lemon" program processes an LALR(1) input grammar file, then uses 15 +** this template to construct a parser. The "lemon" program inserts text 16 +** at each "%%" line. Also, any "P-a-r-s-e" identifer prefix (without the 17 +** interstitial "-" characters) contained in this template is changed into 18 +** the value of the %name directive from the grammar. Otherwise, the content 19 +** of this template is copied straight through into the generate parser 20 +** source file. 21 +** 22 +** The following is the concatenation of all %include directives from the 23 +** input grammar file: 3 24 */ 4 -/* First off, code is included that follows the "include" declaration 5 -** in the input grammar file. */ 6 25 #include <stdio.h> 26 +/************ Begin %include sections from the grammar ************************/ 7 27 %% 8 -/* Next is all token values, in a form suitable for use by makeheaders. 9 -** This section will be null unless lemon is run with the -m switch. 10 -*/ 11 -/* 12 -** These constants (all generated automatically by the parser generator) 13 -** specify the various kinds of tokens (terminals) that the parser 14 -** understands. 15 -** 16 -** Each symbol here is a terminal symbol in the grammar. 17 -*/ 28 +/**************** End of %include directives **********************************/ 29 +/* These constants specify the various numeric values for terminal symbols 30 +** in a format understandable to "makeheaders". This section is blank unless 31 +** "lemon" is run with the "-m" command-line option. 32 +***************** Begin makeheaders token definitions *************************/ 18 33 %% 19 -/* Make sure the INTERFACE macro is defined. 20 -*/ 21 -#ifndef INTERFACE 22 -# define INTERFACE 1 23 -#endif 24 -/* The next thing included is series of defines which control 34 +/**************** End makeheaders token definitions ***************************/ 35 + 36 +/* The next sections is a series of control #defines. 25 37 ** various aspects of the generated parser. 26 -** YYCODETYPE is the data type used for storing terminal 27 -** and nonterminal numbers. "unsigned char" is 28 -** used if there are fewer than 250 terminals 29 -** and nonterminals. "int" is used otherwise. 30 -** YYNOCODE is a number of type YYCODETYPE which corresponds 31 -** to no legal terminal or nonterminal number. This 32 -** number is used to fill in empty slots of the hash 33 -** table. 38 +** YYCODETYPE is the data type used to store the integer codes 39 +** that represent terminal and non-terminal symbols. 40 +** "unsigned char" is used if there are fewer than 41 +** 256 symbols. Larger types otherwise. 42 +** YYNOCODE is a number of type YYCODETYPE that is not used for 43 +** any terminal or nonterminal symbol. 34 44 ** YYFALLBACK If defined, this indicates that one or more tokens 35 -** have fall-back values which should be used if the 36 -** original value of the token will not parse. 37 -** YYACTIONTYPE is the data type used for storing terminal 38 -** and nonterminal numbers. "unsigned char" is 39 -** used if there are fewer than 250 rules and 40 -** states combined. "int" is used otherwise. 41 -** ParseTOKENTYPE is the data type used for minor tokens given 42 -** directly to the parser from the tokenizer. 43 -** YYMINORTYPE is the data type used for all minor tokens. 45 +** (also known as: "terminal symbols") have fall-back 46 +** values which should be used if the original symbol 47 +** would not parse. This permits keywords to sometimes 48 +** be used as identifiers, for example. 49 +** YYACTIONTYPE is the data type used for "action codes" - numbers 50 +** that indicate what to do in response to the next 51 +** token. 52 +** ParseTOKENTYPE is the data type used for minor type for terminal 53 +** symbols. Background: A "minor type" is a semantic 54 +** value associated with a terminal or non-terminal 55 +** symbols. For example, for an "ID" terminal symbol, 56 +** the minor type might be the name of the identifier. 57 +** Each non-terminal can have a different minor type. 58 +** Terminal symbols all have the same minor type, though. 59 +** This macros defines the minor type for terminal 60 +** symbols. 61 +** YYMINORTYPE is the data type used for all minor types. 44 62 ** This is typically a union of many types, one of 45 63 ** which is ParseTOKENTYPE. The entry in the union 46 -** for base tokens is called "yy0". 64 +** for terminal symbols is called "yy0". 47 65 ** YYSTACKDEPTH is the maximum depth of the parser's stack. If 48 66 ** zero the stack is dynamically sized using realloc() 49 67 ** ParseARG_SDECL A static variable declaration for the %extra_argument 50 68 ** ParseARG_PDECL A parameter declaration for the %extra_argument 51 69 ** ParseARG_STORE Code to store %extra_argument into yypParser 52 70 ** ParseARG_FETCH Code to extract %extra_argument from yypParser 53 71 ** YYERRORSYMBOL is the code number of the error symbol. If not ................................................................................ 58 76 ** YY_MIN_SHIFTREDUCE Minimum value for shift-reduce actions 59 77 ** YY_MAX_SHIFTREDUCE Maximum value for shift-reduce actions 60 78 ** YY_MIN_REDUCE Maximum value for reduce actions 61 79 ** YY_ERROR_ACTION The yy_action[] code for syntax error 62 80 ** YY_ACCEPT_ACTION The yy_action[] code for accept 63 81 ** YY_NO_ACTION The yy_action[] code for no-op 64 82 */ 83 +#ifndef INTERFACE 84 +# define INTERFACE 1 85 +#endif 86 +/************* Begin control #defines *****************************************/ 65 87 %% 88 +/************* End control #defines *******************************************/ 66 89 67 90 /* The yyzerominor constant is used to initialize instances of 68 91 ** YYMINORTYPE objects to zero. */ 69 92 static const YYMINORTYPE yyzerominor = { 0 }; 70 93 71 94 /* Define the yytestcase() macro to be a no-op if is not already defined 72 95 ** otherwise. ................................................................................ 127 150 ** yy_lookahead[] A table containing the lookahead for each entry in 128 151 ** yy_action. Used to detect hash collisions. 129 152 ** yy_shift_ofst[] For each state, the offset into yy_action for 130 153 ** shifting terminals. 131 154 ** yy_reduce_ofst[] For each state, the offset into yy_action for 132 155 ** shifting non-terminals after a reduce. 133 156 ** yy_default[] Default action for each state. 134 -*/ 157 +** 158 +*********** Begin parsing tables **********************************************/ 135 159 %% 160 +/********** End of lemon-generated parsing tables *****************************/ 136 161 137 -/* The next table maps tokens into fallback tokens. If a construct 138 -** like the following: 162 +/* The next table maps tokens (terminal symbols) into fallback tokens. 163 +** If a construct like the following: 139 164 ** 140 165 ** %fallback ID X Y Z. 141 166 ** 142 167 ** appears in the grammar, then ID becomes a fallback token for X, Y, 143 168 ** and Z. Whenever one of the tokens X, Y, or Z is input to the parser 144 169 ** but it does not parse, the type of the token is changed to ID and 145 170 ** the parse is retried before an error is thrown. 171 +** 172 +** This feature can be used, for example, to cause some keywords in a language 173 +** to revert to identifiers if they keyword does not apply in the context where 174 +** it appears. 146 175 */ 147 176 #ifdef YYFALLBACK 148 177 static const YYCODETYPE yyFallback[] = { 149 178 %% 150 179 }; 151 180 #endif /* YYFALLBACK */ 152 181 ................................................................................ 261 290 yyTracePrompt, p->yystksz); 262 291 } 263 292 #endif 264 293 } 265 294 } 266 295 #endif 267 296 297 +/* Datatype of the argument to the memory allocated passed as the 298 +** second argument to ParseAlloc() below. This can be changed by 299 +** putting an appropriate #define in the %include section of the input 300 +** grammar. 301 +*/ 302 +#ifndef YYMALLOCARGTYPE 303 +# define YYMALLOCARGTYPE size_t 304 +#endif 305 + 268 306 /* 269 307 ** This function allocates a new parser. 270 308 ** The only argument is a pointer to a function which works like 271 309 ** malloc. 272 310 ** 273 311 ** Inputs: 274 312 ** A pointer to the function used to allocate memory. 275 313 ** 276 314 ** Outputs: 277 315 ** A pointer to a parser. This pointer is used in subsequent calls 278 316 ** to Parse and ParseFree. 279 317 */ 280 -void *ParseAlloc(void *(*mallocProc)(size_t)){ 318 +void *ParseAlloc(void *(*mallocProc)(YYMALLOCARGTYPE)){ 281 319 yyParser *pParser; 282 - pParser = (yyParser*)(*mallocProc)( (size_t)sizeof(yyParser) ); 320 + pParser = (yyParser*)(*mallocProc)( (YYMALLOCARGTYPE)sizeof(yyParser) ); 283 321 if( pParser ){ 284 322 pParser->yyidx = -1; 285 323 #ifdef YYTRACKMAXSTACKDEPTH 286 324 pParser->yyidxMax = 0; 287 325 #endif 288 326 #if YYSTACKDEPTH<=0 289 327 pParser->yystack = NULL; ................................................................................ 290 328 pParser->yystksz = 0; 291 329 yyGrowStack(pParser); 292 330 #endif 293 331 } 294 332 return pParser; 295 333 } 296 334 297 -/* The following function deletes the value associated with a 298 -** symbol. The symbol can be either a terminal or nonterminal. 299 -** "yymajor" is the symbol code, and "yypminor" is a pointer to 300 -** the value. 335 +/* The following function deletes the "minor type" or semantic value 336 +** associated with a symbol. The symbol can be either a terminal 337 +** or nonterminal. "yymajor" is the symbol code, and "yypminor" is 338 +** a pointer to the value to be deleted. The code used to do the 339 +** deletions is derived from the %destructor and/or %token_destructor 340 +** directives of the input grammar. 301 341 */ 302 342 static void yy_destructor( 303 343 yyParser *yypParser, /* The parser */ 304 344 YYCODETYPE yymajor, /* Type code for object to destroy */ 305 345 YYMINORTYPE *yypminor /* The object to be destroyed */ 306 346 ){ 307 347 ParseARG_FETCH; ................................................................................ 309 349 /* Here is inserted the actions which take place when a 310 350 ** terminal or non-terminal is destroyed. This can happen 311 351 ** when the symbol is popped from the stack during a 312 352 ** reduce or during error processing or when a parser is 313 353 ** being destroyed before it is finished parsing. 314 354 ** 315 355 ** Note: during a reduce, the only symbols destroyed are those 316 - ** which appear on the RHS of the rule, but which are not used 356 + ** which appear on the RHS of the rule, but which are *not* used 317 357 ** inside the C code. 318 358 */ 359 +/********* Begin destructor definitions ***************************************/ 319 360 %% 361 +/********* End destructor definitions *****************************************/ 320 362 default: break; /* If no destructor action specified: do nothing */ 321 363 } 322 364 } 323 365 324 366 /* 325 367 ** Pop the parser's stack once. 326 368 ** ................................................................................ 338 380 yyTokenName[yytos->major]); 339 381 } 340 382 #endif 341 383 yy_destructor(pParser, yytos->major, &yytos->minor); 342 384 } 343 385 344 386 /* 345 -** Deallocate and destroy a parser. Destructors are all called for 387 +** Deallocate and destroy a parser. Destructors are called for 346 388 ** all stack elements before shutting the parser down. 347 389 ** 348 -** Inputs: 349 -** <ul> 350 -** <li> A pointer to the parser. This should be a pointer 351 -** obtained from ParseAlloc. 352 -** <li> A pointer to a function used to reclaim memory obtained 353 -** from malloc. 354 -** </ul> 390 +** If the YYPARSEFREENEVERNULL macro exists (for example because it 391 +** is defined in a %include section of the input grammar) then it is 392 +** assumed that the input pointer is never NULL. 355 393 */ 356 394 void ParseFree( 357 395 void *p, /* The parser to be deleted */ 358 396 void (*freeProc)(void*) /* Function used to reclaim memory */ 359 397 ){ 360 398 yyParser *pParser = (yyParser*)p; 399 +#ifndef YYPARSEFREENEVERNULL 361 400 if( pParser==0 ) return; 401 +#endif 362 402 while( pParser->yyidx>=0 ) yy_pop_parser_stack(pParser); 363 403 #if YYSTACKDEPTH<=0 364 404 free(pParser->yystack); 365 405 #endif 366 406 (*freeProc)((void*)pParser); 367 407 } 368 408 ................................................................................ 375 415 return pParser->yyidxMax; 376 416 } 377 417 #endif 378 418 379 419 /* 380 420 ** Find the appropriate action for a parser given the terminal 381 421 ** look-ahead token iLookAhead. 382 -** 383 -** If the look-ahead token is YYNOCODE, then check to see if the action is 384 -** independent of the look-ahead. If it is, return the action, otherwise 385 -** return YY_NO_ACTION. 386 422 */ 387 423 static int yy_find_shift_action( 388 424 yyParser *pParser, /* The parser */ 389 425 YYCODETYPE iLookAhead /* The look-ahead token */ 390 426 ){ 391 427 int i; 392 428 int stateno = pParser->yystack[pParser->yyidx].stateno; ................................................................................ 445 481 } 446 482 }while(1); 447 483 } 448 484 449 485 /* 450 486 ** Find the appropriate action for a parser given the non-terminal 451 487 ** look-ahead token iLookAhead. 452 -** 453 -** If the look-ahead token is YYNOCODE, then check to see if the action is 454 -** independent of the look-ahead. If it is, return the action, otherwise 455 -** return YY_NO_ACTION. 456 488 */ 457 489 static int yy_find_reduce_action( 458 490 int stateno, /* Current state number */ 459 491 YYCODETYPE iLookAhead /* The look-ahead token */ 460 492 ){ 461 493 int i; 462 494 #ifdef YYERRORSYMBOL ................................................................................ 491 523 if( yyTraceFILE ){ 492 524 fprintf(yyTraceFILE,"%sStack Overflow!\n",yyTracePrompt); 493 525 } 494 526 #endif 495 527 while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); 496 528 /* Here code is inserted which will execute if the parser 497 529 ** stack every overflows */ 530 +/******** Begin %stack_overflow code ******************************************/ 498 531 %% 532 +/******** End %stack_overflow code ********************************************/ 499 533 ParseARG_STORE; /* Suppress warning about unused %extra_argument var */ 500 534 } 501 535 502 536 /* 503 537 ** Print tracing information for a SHIFT action 504 538 */ 505 539 #ifndef NDEBUG ................................................................................ 518 552 } 519 553 } 520 554 #else 521 555 # define yyTraceShift(X,Y) 522 556 #endif 523 557 524 558 /* 525 -** Perform a shift action. Return the number of errors. 559 +** Perform a shift action. 526 560 */ 527 561 static void yy_shift( 528 562 yyParser *yypParser, /* The parser to be shifted */ 529 563 int yyNewState, /* The new state to shift in */ 530 564 int yyMajor, /* The major token to shift in */ 531 565 YYMINORTYPE *yypMinor /* Pointer to the minor token to shift in */ 532 566 ){ ................................................................................ 589 623 if( yyTraceFILE && yyruleno>=0 590 624 && yyruleno<(int)(sizeof(yyRuleName)/sizeof(yyRuleName[0])) ){ 591 625 yysize = yyRuleInfo[yyruleno].nrhs; 592 626 fprintf(yyTraceFILE, "%sReduce [%s] -> state %d.\n", yyTracePrompt, 593 627 yyRuleName[yyruleno], yymsp[-yysize].stateno); 594 628 } 595 629 #endif /* NDEBUG */ 596 - 597 - /* Silence complaints from purify about yygotominor being uninitialized 598 - ** in some cases when it is copied into the stack after the following 599 - ** switch. yygotominor is uninitialized when a rule reduces that does 600 - ** not set the value of its left-hand side nonterminal. Leaving the 601 - ** value of the nonterminal uninitialized is utterly harmless as long 602 - ** as the value is never used. So really the only thing this code 603 - ** accomplishes is to quieten purify. 604 - ** 605 - ** 2007-01-16: The wireshark project (www.wireshark.org) reports that 606 - ** without this code, their parser segfaults. I'm not sure what there 607 - ** parser is doing to make this happen. This is the second bug report 608 - ** from wireshark this week. Clearly they are stressing Lemon in ways 609 - ** that it has not been previously stressed... (SQLite ticket #2172) 610 - */ 611 - /*memset(&yygotominor, 0, sizeof(yygotominor));*/ 612 630 yygotominor = yyzerominor; 613 - 614 631 615 632 switch( yyruleno ){ 616 633 /* Beginning here are the reduction cases. A typical example 617 634 ** follows: 618 635 ** case 0: 619 636 ** #line <lineno> <grammarfile> 620 637 ** { ... } // User supplied code 621 638 ** #line <lineno> <thisfile> 622 639 ** break; 623 640 */ 641 +/********** Begin reduce actions **********************************************/ 624 642 %% 643 +/********** End reduce actions ************************************************/ 625 644 }; 626 645 assert( yyruleno>=0 && yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) ); 627 646 yygoto = yyRuleInfo[yyruleno].lhs; 628 647 yysize = yyRuleInfo[yyruleno].nrhs; 629 648 yypParser->yyidx -= yysize; 630 649 yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto); 631 650 if( yyact <= YY_MAX_SHIFTREDUCE ){ ................................................................................ 662 681 if( yyTraceFILE ){ 663 682 fprintf(yyTraceFILE,"%sFail!\n",yyTracePrompt); 664 683 } 665 684 #endif 666 685 while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); 667 686 /* Here code is inserted which will be executed whenever the 668 687 ** parser fails */ 688 +/************ Begin %parse_failure code ***************************************/ 669 689 %% 690 +/************ End %parse_failure code *****************************************/ 670 691 ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ 671 692 } 672 693 #endif /* YYNOERRORRECOVERY */ 673 694 674 695 /* 675 696 ** The following code executes when a syntax error first occurs. 676 697 */ ................................................................................ 677 698 static void yy_syntax_error( 678 699 yyParser *yypParser, /* The parser */ 679 700 int yymajor, /* The major type of the error token */ 680 701 YYMINORTYPE yyminor /* The minor type of the error token */ 681 702 ){ 682 703 ParseARG_FETCH; 683 704 #define TOKEN (yyminor.yy0) 705 +/************ Begin %syntax_error code ****************************************/ 684 706 %% 707 +/************ End %syntax_error code ******************************************/ 685 708 ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ 686 709 } 687 710 688 711 /* 689 712 ** The following is executed when the parser accepts 690 713 */ 691 714 static void yy_accept( ................................................................................ 696 719 if( yyTraceFILE ){ 697 720 fprintf(yyTraceFILE,"%sAccept!\n",yyTracePrompt); 698 721 } 699 722 #endif 700 723 while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser); 701 724 /* Here code is inserted which will be executed whenever the 702 725 ** parser accepts */ 726 +/*********** Begin %parse_accept code *****************************************/ 703 727 %% 728 +/*********** End %parse_accept code *******************************************/ 704 729 ParseARG_STORE; /* Suppress warning about unused %extra_argument variable */ 705 730 } 706 731 707 732 /* The main parser program. 708 733 ** The first argument is a pointer to a structure obtained from 709 734 ** "ParseAlloc" which describes the current state of the parser. 710 735 ** The second argument is the major token number. The third is
Changes to tool/mkkeywordhash.c.
273 273 { "WHEN", "TK_WHEN", ALWAYS }, 274 274 { "WHERE", "TK_WHERE", ALWAYS }, 275 275 }; 276 276 277 277 /* Number of keywords */ 278 278 static int nKeyword = (sizeof(aKeywordTable)/sizeof(aKeywordTable[0])); 279 279 280 -/* An array to map all upper-case characters into their corresponding 281 -** lower-case character. 282 -*/ 283 -const unsigned char sqlite3UpperToLower[] = { 284 - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 285 - 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 286 - 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 287 - 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 97, 98, 99,100,101,102,103, 288 - 104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121, 289 - 122, 91, 92, 93, 94, 95, 96, 97, 98, 99,100,101,102,103,104,105,106,107, 290 - 108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125, 291 - 126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143, 292 - 144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161, 293 - 162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179, 294 - 180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197, 295 - 198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215, 296 - 216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233, 297 - 234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251, 298 - 252,253,254,255 299 -}; 300 -#define UpperToLower sqlite3UpperToLower 280 +/* Map all alphabetic characters into the same case */ 281 +#define charMap(X) (0x20|(X)) 301 282 302 283 /* 303 284 ** Comparision function for two Keyword records 304 285 */ 305 286 static int keywordCompare1(const void *a, const void *b){ 306 287 const Keyword *pA = (Keyword*)a; 307 288 const Keyword *pB = (Keyword*)b; ................................................................................ 343 324 } 344 325 345 326 /* 346 327 ** This routine does the work. The generated code is printed on standard 347 328 ** output. 348 329 */ 349 330 int main(int argc, char **argv){ 350 - int i, j, k, h; 331 + int i, j, k, h, m; 351 332 int bestSize, bestCount; 352 333 int count; 353 334 int nChar; 354 335 int totalLen = 0; 355 336 int aHash[1000]; /* 1000 is much bigger than nKeyword */ 356 337 char zText[2000]; 357 338 ................................................................................ 368 349 /* Fill in the lengths of strings and hashes for all entries. */ 369 350 for(i=0; i<nKeyword; i++){ 370 351 Keyword *p = &aKeywordTable[i]; 371 352 p->len = (int)strlen(p->zName); 372 353 assert( p->len<sizeof(p->zOrigName) ); 373 354 memcpy(p->zOrigName, p->zName, p->len+1); 374 355 totalLen += p->len; 375 - p->hash = (UpperToLower[(int)p->zName[0]]*4) ^ 376 - (UpperToLower[(int)p->zName[p->len-1]]*3) ^ p->len; 356 + p->hash = (charMap(p->zName[0])*4) ^ 357 + (charMap(p->zName[p->len-1])*3) ^ (p->len*1); 377 358 p->id = i+1; 378 359 } 379 360 380 361 /* Sort the table from shortest to longest keyword */ 381 362 qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare1); 382 363 383 364 /* Look for short keywords embedded in longer keywords */ ................................................................................ 477 458 aKeywordTable[i].iNext = aHash[h]; 478 459 aHash[h] = i+1; 479 460 } 480 461 481 462 /* Begin generating code */ 482 463 printf("%s", zHdr); 483 464 printf("/* Hash score: %d */\n", bestCount); 484 - printf("static int keywordCode(const char *z, int n){\n"); 465 + printf("static int keywordCode(const char *z, int n, int *pType){\n"); 485 466 printf(" /* zText[] encodes %d bytes of keywords in %d bytes */\n", 486 467 totalLen + nKeyword, nChar+1 ); 487 468 for(i=j=k=0; i<nKeyword; i++){ 488 469 Keyword *p = &aKeywordTable[i]; 489 470 if( p->substrId ) continue; 490 471 memcpy(&zText[k], p->zName, p->len); 491 472 k += p->len; ................................................................................ 581 562 printf("\n"); 582 563 j = 0; 583 564 } 584 565 } 585 566 printf("%s };\n", j==0 ? "" : "\n"); 586 567 587 568 printf(" int h, i;\n"); 588 - printf(" if( n<2 ) return TK_ID;\n"); 589 - printf(" h = ((charMap(z[0])*4) ^\n" 590 - " (charMap(z[n-1])*3) ^\n" 591 - " n) %% %d;\n", bestSize); 592 - printf(" for(i=((int)aHash[h])-1; i>=0; i=((int)aNext[i])-1){\n"); 593 - printf(" if( aLen[i]==n &&" 594 - " sqlite3StrNICmp(&zText[aOffset[i]],z,n)==0 ){\n"); 569 + printf(" if( n>=2 ){\n"); 570 + printf(" h = ((charMap(z[0])*4) ^ (charMap(z[n-1])*3) ^ n) %% %d;\n", 571 + bestSize); 572 + printf(" for(i=((int)aHash[h])-1; i>=0; i=((int)aNext[i])-1){\n"); 573 + printf(" if( aLen[i]==n &&" 574 + " sqlite3StrNICmp(&zText[aOffset[i]],z,n)==0 ){\n"); 595 575 for(i=0; i<nKeyword; i++){ 596 - printf(" testcase( i==%d ); /* %s */\n", 576 + printf(" testcase( i==%d ); /* %s */\n", 597 577 i, aKeywordTable[i].zOrigName); 598 578 } 599 - printf(" return aCode[i];\n"); 579 + printf(" *pType = aCode[i];\n"); 580 + printf(" break;\n"); 581 + printf(" }\n"); 600 582 printf(" }\n"); 601 583 printf(" }\n"); 602 - printf(" return TK_ID;\n"); 584 + printf(" return n;\n"); 603 585 printf("}\n"); 604 586 printf("int sqlite3KeywordCode(const unsigned char *z, int n){\n"); 605 - printf(" return keywordCode((char*)z, n);\n"); 587 + printf(" int id = TK_ID;\n"); 588 + printf(" keywordCode((char*)z, n, &id);\n"); 589 + printf(" return id;\n"); 606 590 printf("}\n"); 607 591 printf("#define SQLITE_N_KEYWORD %d\n", nKeyword); 608 592 609 593 return 0; 610 594 }