doc/lemon.html

   1 <html>
   2 <head>
   3 <title>The Lemon Parser Generator</title>
   4 </head>
   5 <body>
   6 <a id="main"></a>
   7 <h1 align='center'>The Lemon Parser Generator</h1>
   8
   9 <p>Lemon is an LALR(1) parser generator for C.
  10 It does the same job as "bison" and "yacc".
  11 But Lemon is not a bison or yacc clone.  Lemon
  12 uses a different grammar syntax which is designed to
  13 reduce the number of coding errors.  Lemon also uses a
  14 parsing engine that is faster than yacc and
  15 bison and which is both reentrant and threadsafe.
  16 (Update: Since the previous sentence was written, bison
  17 has also been updated so that it too can generate a
  18 reentrant and threadsafe parser.)
  19 Lemon also implements features that can be used
  20 to eliminate resource leaks, making it suitable for use
  21 in long-running programs such as graphical user interfaces
  22 or embedded controllers.</p>
  23
  24 <p>This document is an introduction to the Lemon
  25 parser generator.</p>
  26
  27 <a id="toc"></a>
  28 <h2>1.0 Table of Contents</h2>
  29 <ul>
  30 <li><a href="#main">Introduction</a>
  31 <li><a href="#toc">1.0 Table of Contents</a>
  32 <li><a href="#secnot">2.0 Security Notes</a><br>
  33 <li><a href="#optheory">3.0 Theory of Operation</a>
  34     <ul>
  35     <li><a href="#options">3.1 Command Line Options</a>
  36     <li><a href="#interface">3.2 The Parser Interface</a>
  37         <ul>
  38         <li><a href="#onstack">3.2.1 Allocating The Parse Object On Stack</a>
  39         <li><a href="#ifsum">3.2.2 Interface Summary</a>
  40         </ul>
  41     <li><a href="#yaccdiff">3.3 Differences With YACC and BISON</a>
  42     <li><a href="#build">3.4 Building The "lemon" Or "lemon.exe" Executable</a>
  43     </ul>
  44 <li><a href="#syntax">4.0 Input File Syntax</a>
  45     <ul>
  46     <li><a href="#tnt">4.1 Terminals and Nonterminals</a>
  47     <li><a href="#rules">4.2 Grammar Rules</a>
  48     <li><a href="#precrules">4.3 Precedence Rules</a>
  49     <li><a href="#special">4.4 Special Directives</a>
  50     </ul>
  51 <li><a href="#errors">5.0 Error Processing</a>
  52 <li><a href="#history">6.0 History of Lemon</a>
  53 <li><a href="#copyright">7.0 Copyright</a>
  54 </ul>
  55
  56 <a id="secnot"></a>
  57 <h2>2.0 Security Note</h2>
  58
  59 <p>The language parser code created by Lemon is very robust and
  60 is well-suited for use in internet-facing applications that need to
  61 safely process maliciously crafted inputs.</p>
  62
  63 <p>The "lemon.exe" command-line tool itself works great when given a valid
  64 input grammar file and almost always gives helpful
  65 error messages for malformed inputs.  However,  it is possible for
  66 a malicious user to craft a grammar file that will cause
  67 lemon.exe to crash.
  68 We do not see this as a problem, as lemon.exe is not intended to be used
  69 with hostile inputs.
  70 To summarize:</p>
  71
  72 <ul>
  73 <li>Parser code generated by lemon &rarr; Robust and secure
  74 <li>The "lemon.exe" command line tool itself &rarr; Not so much
  75 </ul>
  76
  77 <a id="optheory"></a>
  78 <h2>3.0 Theory of Operation</h2>
  79
  80 <p>Lemon is computer program that translates a context free grammar (CFG)
  81 for a particular language into C code that implements a parser for
  82 that language.
  83 The Lemon program has two inputs:</p>
  84 <ul>
  85 <li>The grammar specification.
  86 <li>A parser template file.
  87 </ul>
  88 <p>Typically, only the grammar specification is supplied by the programmer.
  89 Lemon comes with a default parser template
  90 ("<a href="https://sqlite.org/src/file/tool/lempar.c">lempar.c</a>")
  91 that works fine for most applications.  But the user is free to substitute
  92 a different parser template if desired.</p>
  93
  94 <p>Depending on command-line options, Lemon will generate up to
  95 three output files.</p>
  96 <ul>
  97 <li>C code to implement a parser for the input grammar.
  98 <li>A header file defining an integer ID for each terminal symbol
  99     (or "token").
 100 <li>An information file that describes the states of the generated parser
 101     automaton.
 102 </ul>
 103 <p>By default, all three of these output files are generated.
 104 The header file is suppressed if the "-m" command-line option is
 105 used and the report file is omitted when "-q" is selected.</p>
 106
 107 <p>The grammar specification file uses a ".y" suffix, by convention.
 108 In the examples used in this document, we'll assume the name of the
 109 grammar file is "gram.y".  A typical use of Lemon would be the
 110 following command:</p>
 111 <pre>
 112    lemon gram.y
 113 </pre>
 114 <p>This command will generate three output files named "gram.c",
 115 "gram.h" and "gram.out".
 116 The first is C code to implement the parser.  The second
 117 is the header file that defines numerical values for all
 118 terminal symbols, and the last is the report that explains
 119 the states used by the parser automaton.</p>
 120
 121 <a id="options"></a>
 122 <h3>3.1 Command Line Options</h3>
 123
 124 <p>The behavior of Lemon can be modified using command-line options.
 125 You can obtain a list of the available command-line options together
 126 with a brief explanation of what each does by typing</p>
 127 <pre>
 128    lemon "-?"
 129 </pre>
 130 <p>As of this writing, the following command-line options are supported:</p>
 131 <ul>
 132 <li><b>-b</b>
 133 Show only the basis for each parser state in the report file.
 134 <li><b>-c</b>
 135 Do not compress the generated action tables.  The parser will be a
 136 little larger and slower, but it will detect syntax errors sooner.
 137 <li><b>-d</b><i>directory</i>
 138 Write all output files into <i>directory</i>.  Normally, output files
 139 are written into the directory that contains the input grammar file.
 140 <li><b>-D<i>name</i></b>
 141 Define C preprocessor macro <i>name</i>.  This macro is usable by
 142 "<tt><a href='#pifdef'>%ifdef</a></tt>",
 143 "<tt><a href='#pifdef'>%ifndef</a></tt>", and
 144 "<tt><a href="#pifdef">%if</a></tt> lines
 145 in the grammar file.
 146 <li><b>-E</b>
 147 Run the "%if" preprocessor step only and print the revised grammar
 148 file.
 149 <li><b>-g</b>
 150 Do not generate a parser.  Instead write the input grammar to standard
 151 output with all comments, actions, and other extraneous text removed.
 152 <li><b>-l</b>
 153 Omit "#line" directives in the generated parser C code.
 154 <li><b>-m</b>
 155 Cause the output C source code to be compatible with the "makeheaders"
 156 program.
 157 <li><b>-p</b>
 158 Display all conflicts that are resolved by
 159 <a href='#precrules'>precedence rules</a>.
 160 <li><b>-q</b>
 161 Suppress generation of the report file.
 162 <li><b>-r</b>
 163 Do not sort or renumber the parser states as part of optimization.
 164 <li><b>-s</b>
 165 Show parser statistics before exiting.
 166 <li><b>-T<i>file</i></b>
 167 Use <i>file</i> as the template for the generated C-code parser implementation.
 168 <li><b>-x</b>
 169 Print the Lemon version number.
 170 </ul>
 171
 172 <a id="interface"></a>
 173 <h3>3.2 The Parser Interface</h3>
 174
 175 <p>Lemon doesn't generate a complete, working program.  It only generates
 176 a few subroutines that implement a parser.  This section describes
 177 the interface to those subroutines.  It is up to the programmer to
 178 call these subroutines in an appropriate way in order to produce a
 179 complete system.</p>
 180
 181 <p>Before a program begins using a Lemon-generated parser, the program
 182 must first create the parser.
 183 A new parser is created as follows:</p>
 184 <pre>
 185    void *pParser = ParseAlloc( malloc );
 186 </pre>
 187 <p>The ParseAlloc() routine allocates and initializes a new parser and
 188 returns a pointer to it.
 189 The actual data structure used to represent a parser is opaque &mdash;
 190 its internal structure is not visible or usable by the calling routine.
 191 For this reason, the ParseAlloc() routine returns a pointer to void
 192 rather than a pointer to some particular structure.
 193 The sole argument to the ParseAlloc() routine is a pointer to the
 194 subroutine used to allocate memory.  Typically this means malloc().</p>
 195
 196 <p>After a program is finished using a parser, it can reclaim all
 197 memory allocated by that parser by calling</p>
 198 <pre>
 199    ParseFree(pParser, free);
 200 </pre>
 201 <p>The first argument is the same pointer returned by ParseAlloc().  The
 202 second argument is a pointer to the function used to release bulk
 203 memory back to the system.</p>
 204
 205 <p>After a parser has been allocated using ParseAlloc(), the programmer
 206 must supply the parser with a sequence of tokens (terminal symbols) to
 207 be parsed.  This is accomplished by calling the following function
 208 once for each token:<p>
 209 <pre>
 210    Parse(pParser, hTokenID, sTokenData, pArg);
 211 </pre>
 212 <p>The first argument to the Parse() routine is the pointer returned by
 213 ParseAlloc().
 214 The second argument is a small positive integer that tells the parser the
 215 type of the next token in the data stream.
 216 There is one token type for each terminal symbol in the grammar.
 217 The gram.h file generated by Lemon contains #define statements that
 218 map symbolic terminal symbol names into appropriate integer values.
 219 A value of 0 for the second argument is a special flag to the
 220 parser to indicate that the end of input has been reached.
 221 The third argument is the value of the given token.  By default,
 222 the type of the third argument is "void*", but the grammar will
 223 usually redefine this type to be some kind of structure.
 224 Typically the second argument will be a broad category of tokens
 225 such as "identifier" or "number" and the third argument will
 226 be the name of the identifier or the value of the number.</p>
 227
 228 <p>The Parse() function may have either three or four arguments,
 229 depending on the grammar.  If the grammar specification file requests
 230 it (via the <tt><a href='#extraarg'>%extra_argument</a></tt> directive),
 231 the Parse() function will have a fourth parameter that can be
 232 of any type chosen by the programmer.  The parser doesn't do anything
 233 with this argument except to pass it through to action routines.
 234 This is a convenient mechanism for passing state information down
 235 to the action routines without having to use global variables.</p>
 236
 237 <p>A typical use of a Lemon parser might look something like the
 238 following:</p>
 239 <pre>
 240     1 ParseTree *ParseFile(const char *zFilename){
 241     2    Tokenizer *pTokenizer;
 242     3    void *pParser;
 243     4    Token sToken;
 244     5    int hTokenId;
 245     6    ParserState sState;
 246     7
 247     8    pTokenizer = TokenizerCreate(zFilename);
 248     9    pParser = ParseAlloc( malloc );
 249    10    InitParserState(&amp;sState);
 250    11    while( GetNextToken(pTokenizer, &amp;hTokenId, &amp;sToken) ){
 251    12       Parse(pParser, hTokenId, sToken, &amp;sState);
 252    13    }
 253    14    Parse(pParser, 0, sToken, &amp;sState);
 254    15    ParseFree(pParser, free );
 255    16    TokenizerFree(pTokenizer);
 256    17    return sState.treeRoot;
 257    18 }
 258 </pre>
 259 <p>This example shows a user-written routine that parses a file of
 260 text and returns a pointer to the parse tree.
 261 (All error-handling code is omitted from this example to keep it
 262 simple.)
 263 We assume the existence of some kind of tokenizer which is created
 264 using TokenizerCreate() on line 8 and deleted by TokenizerFree()
 265 on line 16.  The GetNextToken() function on line 11 retrieves the
 266 next token from the input file and puts its type in the
 267 integer variable hTokenId.  The sToken variable is assumed to be
 268 some kind of structure that contains details about each token,
 269 such as its complete text, what line it occurs on, etc.</p>
 270
 271 <p>This example also assumes the existence of a structure of type
 272 ParserState that holds state information about a particular parse.
 273 An instance of such a structure is created on line 6 and initialized
 274 on line 10.  A pointer to this structure is passed into the Parse()
 275 routine as the optional 4th argument.
 276 The action routine specified by the grammar for the parser can use
 277 the ParserState structure to hold whatever information is useful and
 278 appropriate.  In the example, we note that the treeRoot field of
 279 the ParserState structure is left pointing to the root of the parse
 280 tree.</p>
 281
 282 <p>The core of this example as it relates to Lemon is as follows:</p>
 283 <pre>
 284    ParseFile(){
 285       pParser = ParseAlloc( malloc );
 286       while( GetNextToken(pTokenizer,&amp;hTokenId, &amp;sToken) ){
 287          Parse(pParser, hTokenId, sToken);
 288       }
 289       Parse(pParser, 0, sToken);
 290       ParseFree(pParser, free );
 291    }
 292 </pre>
 293 <p>Basically, what a program has to do to use a Lemon-generated parser
 294 is first create the parser, then send it lots of tokens obtained by
 295 tokenizing an input source.  When the end of input is reached, the
 296 Parse() routine should be called one last time with a token type
 297 of 0.  This step is necessary to inform the parser that the end of
 298 input has been reached.  Finally, we reclaim memory used by the
 299 parser by calling ParseFree().</p>
 300
 301 <p>There is one other interface routine that should be mentioned
 302 before we move on.
 303 The ParseTrace() function can be used to generate debugging output
 304 from the parser.  A prototype for this routine is as follows:</p>
 305 <pre>
 306    ParseTrace(FILE *stream, char *zPrefix);
 307 </pre>
 308 <p>After this routine is called, a short (one-line) message is written
 309 to the designated output stream every time the parser changes states
 310 or calls an action routine.  Each such message is prefaced using
 311 the text given by zPrefix.  This debugging output can be turned off
 312 by calling ParseTrace() again with a first argument of NULL (0).</p>
 313
 314 <a id="onstack"></a>
 315 <h4>3.2.1 Allocating The Parse Object On Stack</h4>
 316
 317 <p>If all calls to the Parse() interface are made from within
 318 <a href="#pcode"><tt>%code</tt> directives</a>, then the parse
 319 object can be allocated from the stack rather than from the heap.
 320 These are the steps:
 321
 322 <ul>
 323 <li> Declare a local variable of type "yyParser"
 324 <li> Initialize the variable using ParseInit()
 325 <li> Pass a pointer to the variable in calls to Parse()
 326 <li> Deallocate substructure in the parse variable using ParseFinalize().
 327 </ul>
 328
 329 <p>The following code illustrates how this is done:
 330
 331 <pre>
 332    ParseFile(){
 333       yyParser x;
 334       ParseInit( &x );
 335       while( GetNextToken(pTokenizer,&amp;hTokenId, &amp;sToken) ){
 336          Parse(&x, hTokenId, sToken);
 337       }
 338       Parse(&x, 0, sToken);
 339       ParseFinalize( &x );
 340    }
 341 </pre>
 342
 343 <a id="ifsum"></a>
 344 <h4>3.2.2 Interface Summary</h4>
 345
 346 <p>Here is a quick overview of the C-language interface to a
 347 Lemon-generated parser:</p>
 348
 349 <blockquote><pre>
 350 void *ParseAlloc( (void*(*malloc)(size_t) );
 351 void ParseFree(void *pParser, (void(*free)(void*) );
 352 void Parse(void *pParser, int tokenCode, ParseTOKENTYPE token, ...);
 353 void ParseTrace(FILE *stream, char *zPrefix);
 354 </pre></blockquote>
 355
 356 <p>Notes:</p>
 357 <ul>
 358 <li> Use the <a href="#pname"><tt>%name</tt> directive</a> to change
 359 the "Parse" prefix names of the procedures in the interface.
 360 <li> Use the <a href="#token_type"><tt>%token_type</tt> directive</a>
 361 to define the "ParseTOKENTYPE" type.
 362 <li> Use the <a href="#extraarg"><tt>%extra_argument</tt> directive</a>
 363 to specify the type and name of the 4th parameter to the
 364 Parse() function.
 365 </ul>
 366
 367 <a id="yaccdiff"></a>
 368 <h3>3.3 Differences With YACC and BISON</h3>
 369
 370 <p>Programmers who have previously used the yacc or bison parser
 371 generator will notice several important differences between yacc and/or
 372 bison and Lemon.</p>
 373 <ul>
 374 <li>In yacc and bison, the parser calls the tokenizer.  In Lemon,
 375     the tokenizer calls the parser.
 376 <li>Lemon uses no global variables.  Yacc and bison use global variables
 377     to pass information between the tokenizer and parser.
 378 <li>Lemon allows multiple parsers to be running simultaneously.  Yacc
 379     and bison do not.
 380 </ul>
 381 <p>These differences may cause some initial confusion for programmers
 382 with prior yacc and bison experience.
 383 But after years of experience using Lemon, I firmly
 384 believe that the Lemon way of doing things is better.</p>
 385
 386 <p><i>Updated as of 2016-02-16:</i>
 387 The text above was written in the 1990s.
 388 We are told that Bison has lately been enhanced to support the
 389 tokenizer-calls-parser paradigm used by Lemon, eliminating the
 390 need for global variables.</p>
 391
 392 <a id="build"><a>
 393 <h3>3.4 Building The "lemon" or "lemon.exe" Executable</h3>
 394
 395 <p>The "lemon" or "lemon.exe" program is built from a single file
 396 of C-code named
 397 "<a href="https://sqlite.org/src/tool/lemon.c">lemon.c</a>".
 398 The Lemon source code is generic C89 code that uses
 399 no unusual or non-standard libraries.  Any
 400 reasonable C compiler should suffice to compile the lemon program.
 401 A command-line like the following will usually work:</p>
 402
 403 <blockquote><pre>
 404 cc -o lemon lemon.c
 405 </pre></blockquote
 406
 407 <p>On Windows machines with Visual C++ installed, bring up a
 408 "VS20<i>NN</i> x64 Native Tools Command Prompt" window and enter:
 409
 410 <blockquote><pre>
 411 cl lemon.c
 412 </pre></blockquote>
 413
 414 <p>Compiling Lemon really is that simple.
 415 Additional compiler options such as
 416 "-O2" or "-g" or "-Wall" can be added if desired, but they are not
 417 necessary.</p>
 418
 419
 420 <a id="syntax"></a>
 421 <h2>4.0 Input File Syntax</h2>
 422
 423 <p>The main purpose of the grammar specification file for Lemon is
 424 to define the grammar for the parser.  But the input file also
 425 specifies additional information Lemon requires to do its job.
 426 Most of the work in using Lemon is in writing an appropriate
 427 grammar file.</p>
 428
 429 <p>The grammar file for Lemon is, for the most part, a free format.
 430 It does not have sections or divisions like yacc or bison.  Any
 431 declaration can occur at any point in the file.  Lemon ignores
 432 whitespace (except where it is needed to separate tokens), and it
 433 honors the same commenting conventions as C and C++.</p>
 434
 435 <a id="tnt"></a>
 436 <h3>4.1 Terminals and Nonterminals</h3>
 437
 438 <p>A terminal symbol (token) is any string of alphanumeric
 439 and/or underscore characters
 440 that begins with an uppercase letter.
 441 A terminal can contain lowercase letters after the first character,
 442 but the usual convention is to make terminals all uppercase.
 443 A nonterminal, on the other hand, is any string of alphanumeric
 444 and underscore characters than begins with a lowercase letter.
 445 Again, the usual convention is to make nonterminals use all lowercase
 446 letters.</p>
 447
 448 <p>In Lemon, terminal and nonterminal symbols do not need to
 449 be declared or identified in a separate section of the grammar file.
 450 Lemon is able to generate a list of all terminals and nonterminals
 451 by examining the grammar rules, and it can always distinguish a
 452 terminal from a nonterminal by checking the case of the first
 453 character of the name.</p>
 454
 455 <p>Yacc and bison allow terminal symbols to have either alphanumeric
 456 names or to be individual characters included in single quotes, like
 457 this: ')' or '$'.  Lemon does not allow this alternative form for
 458 terminal symbols.  With Lemon, all symbols, terminals and nonterminals,
 459 must have alphanumeric names.</p>
 460
 461 <a id="rules"></a>
 462 <h3>4.2 Grammar Rules</h3>
 463
 464 <p>The main component of a Lemon grammar file is a sequence of grammar
 465 rules.
 466 Each grammar rule consists of a nonterminal symbol followed by
 467 the special symbol "::=" and then a list of terminals and/or nonterminals.
 468 The rule is terminated by a period.
 469 The list of terminals and nonterminals on the right-hand side of the
 470 rule can be empty.
 471 Rules can occur in any order, except that the left-hand side of the
 472 first rule is assumed to be the start symbol for the grammar (unless
 473 specified otherwise using the <tt><a href='#start_symbol'>%start_symbol</a></tt>
 474 directive described below.)
 475 A typical sequence of grammar rules might look something like this:</p>
 476 <pre>
 477   expr ::= expr PLUS expr.
 478   expr ::= expr TIMES expr.
 479   expr ::= LPAREN expr RPAREN.
 480   expr ::= VALUE.
 481 </pre>
 482
 483 <p>There is one non-terminal in this example, "expr", and five
 484 terminal symbols or tokens: "PLUS", "TIMES", "LPAREN",
 485 "RPAREN" and "VALUE".</p>
 486
 487 <p>Like yacc and bison, Lemon allows the grammar to specify a block
 488 of C code that will be executed whenever a grammar rule is reduced
 489 by the parser.
 490 In Lemon, this action is specified by putting the C code (contained
 491 within curly braces <tt>{...}</tt>) immediately after the
 492 period that closes the rule.
 493 For example:</p>
 494 <pre>
 495   expr ::= expr PLUS expr.   { printf("Doing an addition...\n"); }
 496 </pre>
 497
 498 <p>In order to be useful, grammar actions must normally be linked to
 499 their associated grammar rules.
 500 In yacc and bison, this is accomplished by embedding a "$$" in the
 501 action to stand for the value of the left-hand side of the rule and
 502 symbols "$1", "$2", and so forth to stand for the value of
 503 the terminal or nonterminal at position 1, 2 and so forth on the
 504 right-hand side of the rule.
 505 This idea is very powerful, but it is also very error-prone.  The
 506 single most common source of errors in a yacc or bison grammar is
 507 to miscount the number of symbols on the right-hand side of a grammar
 508 rule and say "$7" when you really mean "$8".</p>
 509
 510 <p>Lemon avoids the need to count grammar symbols by assigning symbolic
 511 names to each symbol in a grammar rule and then using those symbolic
 512 names in the action.
 513 In yacc or bison, one would write this:</p>
 514 <pre>
 515   expr -&gt; expr PLUS expr  { $$ = $1 + $3; };
 516 </pre>
 517 <p>But in Lemon, the same rule becomes the following:</p>
 518 <pre>
 519   expr(A) ::= expr(B) PLUS expr(C).  { A = B+C; }
 520 </pre>
 521 <p>In the Lemon rule, any symbol in parentheses after a grammar rule
 522 symbol becomes a place holder for that symbol in the grammar rule.
 523 This place holder can then be used in the associated C action to
 524 stand for the value of that symbol.</p>
 525
 526 <p>The Lemon notation for linking a grammar rule with its reduce
 527 action is superior to yacc/bison on several counts.
 528 First, as mentioned above, the Lemon method avoids the need to
 529 count grammar symbols.
 530 Secondly, if a terminal or nonterminal in a Lemon grammar rule
 531 includes a linking symbol in parentheses but that linking symbol
 532 is not actually used in the reduce action, then an error message
 533 is generated.
 534 For example, the rule</p>
 535 <pre>
 536   expr(A) ::= expr(B) PLUS expr(C).  { A = B; }
 537 </pre>
 538 <p>will generate an error because the linking symbol "C" is used
 539 in the grammar rule but not in the reduce action.</p>
 540
 541 <p>The Lemon notation for linking grammar rules to reduce actions
 542 also facilitates the use of destructors for reclaiming memory
 543 allocated by the values of terminals and nonterminals on the
 544 right-hand side of a rule.</p>
 545
 546 <a id='precrules'></a>
 547 <h3>4.3 Precedence Rules</h3>
 548
 549 <p>Lemon resolves parsing ambiguities in exactly the same way as
 550 yacc and bison.  A shift-reduce conflict is resolved in favor
 551 of the shift, and a reduce-reduce conflict is resolved by reducing
 552 whichever rule comes first in the grammar file.</p>
 553
 554 <p>Just like in
 555 yacc and bison, Lemon allows a measure of control
 556 over the resolution of parsing conflicts using precedence rules.
 557 A precedence value can be assigned to any terminal symbol
 558 using the
 559 <tt><a href='#pleft'>%left</a></tt>,
 560 <tt><a href='#pright'>%right</a></tt> or
 561 <tt><a href='#pnonassoc'>%nonassoc</a></tt> directives.  Terminal symbols
 562 mentioned in earlier directives have a lower precedence than
 563 terminal symbols mentioned in later directives.  For example:</p>
 564
 565 <pre>
 566    %left AND.
 567    %left OR.
 568    %nonassoc EQ NE GT GE LT LE.
 569    %left PLUS MINUS.
 570    %left TIMES DIVIDE MOD.
 571    %right EXP NOT.
 572 </pre>
 573
 574 <p>In the preceding sequence of directives, the AND operator is
 575 defined to have the lowest precedence.  The OR operator is one
 576 precedence level higher.  And so forth.  Hence, the grammar would
 577 attempt to group the ambiguous expression</p>
 578 <pre>
 579      a AND b OR c
 580 </pre>
 581 <p>like this</p>
 582 <pre>
 583      a AND (b OR c).
 584 </pre>
 585 <p>The associativity (left, right or nonassoc) is used to determine
 586 the grouping when the precedence is the same.  AND is left-associative
 587 in our example, so</p>
 588 <pre>
 589      a AND b AND c
 590 </pre>
 591 <p>is parsed like this</p>
 592 <pre>
 593      (a AND b) AND c.
 594 </pre>
 595 <p>The EXP operator is right-associative, though, so</p>
 596 <pre>
 597      a EXP b EXP c
 598 </pre>
 599 <p>is parsed like this</p>
 600 <pre>
 601      a EXP (b EXP c).
 602 </pre>
 603 <p>The nonassoc precedence is used for non-associative operators.
 604 So</p>
 605 <pre>
 606      a EQ b EQ c
 607 </pre>
 608 <p>is an error.</p>
 609
 610 <p>The precedence of non-terminals is transferred to rules as follows:
 611 The precedence of a grammar rule is equal to the precedence of the
 612 left-most terminal symbol in the rule for which a precedence is
 613 defined.  This is normally what you want, but in those cases where
 614 you want the precedence of a grammar rule to be something different,
 615 you can specify an alternative precedence symbol by putting the
 616 symbol in square braces after the period at the end of the rule and
 617 before any C-code.  For example:</p>
 618
 619 <pre>
 620    expr = MINUS expr.  [NOT]
 621 </pre>
 622
 623 <p>This rule has a precedence equal to that of the NOT symbol, not the
 624 MINUS symbol as would have been the case by default.</p>
 625
 626 <p>With the knowledge of how precedence is assigned to terminal
 627 symbols and individual
 628 grammar rules, we can now explain precisely how parsing conflicts
 629 are resolved in Lemon.  Shift-reduce conflicts are resolved
 630 as follows:</p>
 631 <ul>
 632 <li> If either the token to be shifted or the rule to be reduced
 633      lacks precedence information, then resolve in favor of the
 634      shift, but report a parsing conflict.
 635 <li> If the precedence of the token to be shifted is greater than
 636      the precedence of the rule to reduce, then resolve in favor
 637      of the shift.  No parsing conflict is reported.
 638 <li> If the precedence of the token to be shifted is less than the
 639      precedence of the rule to reduce, then resolve in favor of the
 640      reduce action.  No parsing conflict is reported.
 641 <li> If the precedences are the same and the shift token is
 642      right-associative, then resolve in favor of the shift.
 643      No parsing conflict is reported.
 644 <li> If the precedences are the same and the shift token is
 645      left-associative, then resolve in favor of the reduce.
 646      No parsing conflict is reported.
 647 <li> Otherwise, resolve the conflict by doing the shift, and
 648      report a parsing conflict.
 649 </ul>
 650 <p>Reduce-reduce conflicts are resolved this way:</p>
 651 <ul>
 652 <li> If either reduce rule
 653      lacks precedence information, then resolve in favor of the
 654      rule that appears first in the grammar, and report a parsing
 655      conflict.
 656 <li> If both rules have precedence and the precedence is different,
 657      then resolve the dispute in favor of the rule with the highest
 658      precedence, and do not report a conflict.
 659 <li> Otherwise, resolve the conflict by reducing by the rule that
 660      appears first in the grammar, and report a parsing conflict.
 661 </ul>
 662
 663 <a id="special"></a>
 664 <h3>4.4 Special Directives</h3>
 665
 666 <p>The input grammar to Lemon consists of grammar rules and special
 667 directives.  We've described all the grammar rules, so now we'll
 668 talk about the special directives.</p>
 669
 670 <p>Directives in Lemon can occur in any order.  You can put them before
 671 the grammar rules, or after the grammar rules, or in the midst of the
 672 grammar rules.  It doesn't matter.  The relative order of
 673 directives used to assign precedence to terminals is important, but
 674 other than that, the order of directives in Lemon is arbitrary.</p>
 675
 676 <p>Lemon supports the following special directives:</p>
 677 <ul>
 678 <li><tt><a href='#pcode'>%code</a></tt>
 679 <li><tt><a href='#default_destructor'>%default_destructor</a></tt>
 680 <li><tt><a href='#default_type'>%default_type</a></tt>
 681 <li><tt><a href='#destructor'>%destructor</a></tt>
 682 <li><tt><a href='#pifdef'>%else</a></tt>
 683 <li><tt><a href='#pifdef'>%endif</a></tt>
 684 <li><tt><a href='#extraarg'>%extra_argument</a></tt>
 685 <li><tt><a href='#pfallback'>%fallback</a></tt>
 686 <li><tt><a href='#reallc'>%free</a></tt>
 687 <li><tt><a href='#pifdef'>%if</a></tt>
 688 <li><tt><a href='#pifdef'>%ifdef</a></tt>
 689 <li><tt><a href='#pifdef'>%ifndef</a></tt>
 690 <li><tt><a href='#pinclude'>%include</a></tt>
 691 <li><tt><a href='#pleft'>%left</a></tt>
 692 <li><tt><a href='#pname'>%name</a></tt>
 693 <li><tt><a href='#pnonassoc'>%nonassoc</a></tt>
 694 <li><tt><a href='#parse_accept'>%parse_accept</a></tt>
 695 <li><tt><a href='#parse_failure'>%parse_failure</a></tt>
 696 <li><tt><a href='#pright'>%right</a></tt>
 697 <li><tt><a href='#reallc'>%realloc</a></tt>
 698 <li><tt><a href='#stack_overflow'>%stack_overflow</a></tt>
 699 <li><tt><a href='#stack_size'>%stack_size</a></tt>
 700 <li><tt><a href='#start_symbol'>%start_symbol</a></tt>
 701 <li><tt><a href='#syntax_error'>%syntax_error</a></tt>
 702 <li><tt><a href='#token'>%token</a></tt>
 703 <li><tt><a href='#token_class'>%token_class</a></tt>
 704 <li><tt><a href='#token_destructor'>%token_destructor</a></tt>
 705 <li><tt><a href='#token_prefix'>%token_prefix</a></tt>
 706 <li><tt><a href='#token_type'>%token_type</a></tt>
 707 <li><tt><a href='#ptype'>%type</a></tt>
 708 <li><tt><a href='#pwildcard'>%wildcard</a></tt>
 709 </ul>
 710 <p>Each of these directives will be described separately in the
 711 following sections:</p>
 712
 713 <a id='pcode'></a>
 714 <h4>4.4.1 The <tt>%code</tt> directive</h4>
 715
 716 <p>The <tt>%code</tt> directive is used to specify additional C code that
 717 is added to the end of the main output file.  This is similar to
 718 the <tt><a href='#pinclude'>%include</a></tt> directive except that
 719 <tt>%include</tt> is inserted at the beginning of the main output file.</p>
 720
 721 <p><tt>%code</tt> is typically used to include some action routines or perhaps
 722 a tokenizer or even the "main()" function
 723 as part of the output file.</p>
 724
 725 <p>There can be multiple <tt>%code</tt> directives.  The arguments of
 726 all <tt>%code</tt> directives are concatenated.</p>
 727
 728 <a id='default_destructor'></a>
 729 <h4>4.4.2 The <tt>%default_destructor</tt> directive</h4>
 730
 731 <p>The <tt>%default_destructor</tt> directive specifies a destructor to
 732 use for non-terminals that do not have their own destructor
 733 specified by a separate <tt>%destructor</tt> directive.  See the documentation
 734 on the <tt><a href='#destructor'>%destructor</a></tt> directive below for
 735 additional information.</p>
 736
 737 <p>In some grammars, many different non-terminal symbols have the
 738 same data type and hence the same destructor.  This directive is
 739 a convenient way to specify the same destructor for all those
 740 non-terminals using a single statement.</p>
 741
 742 <a id='default_type'></a>
 743 <h4>4.4.3 The <tt>%default_type</tt> directive</h4>
 744
 745 <p>The <tt>%default_type</tt> directive specifies the data type of non-terminal
 746 symbols that do not have their own data type defined using a separate
 747 <tt><a href='#ptype'>%type</a></tt> directive.</p>
 748
 749 <a id='destructor'></a>
 750 <h4>4.4.4 The <tt>%destructor</tt> directive</h4>
 751
 752 <p>The <tt>%destructor</tt> directive is used to specify a destructor for
 753 a non-terminal symbol.
 754 (See also the <tt><a href='#token_destructor'>%token_destructor</a></tt>
 755 directive which is used to specify a destructor for terminal symbols.)</p>
 756
 757 <p>A non-terminal's destructor is called to dispose of the
 758 non-terminal's value whenever the non-terminal is popped from
 759 the stack.  This includes all of the following circumstances:</p>
 760 <ul>
 761 <li> When a rule reduces and the value of a non-terminal on
 762      the right-hand side is not linked to C code.
 763 <li> When the stack is popped during error processing.
 764 <li> When the ParseFree() function runs.
 765 </ul>
 766 <p>The destructor can do whatever it wants with the value of
 767 the non-terminal, but its design is to deallocate memory
 768 or other resources held by that non-terminal.</p>
 769
 770 <p>Consider an example:</p>
 771 <pre>
 772    %type nt {void*}
 773    %destructor nt { free($$); }
 774    nt(A) ::= ID NUM.   { A = malloc( 100 ); }
 775 </pre>
 776 <p>This example is a bit contrived, but it serves to illustrate how
 777 destructors work.  The example shows a non-terminal named
 778 "nt" that holds values of type "void*".  When the rule for
 779 an "nt" reduces, it sets the value of the non-terminal to
 780 space obtained from malloc().  Later, when the nt non-terminal
 781 is popped from the stack, the destructor will fire and call
 782 free() on this malloced space, thus avoiding a memory leak.
 783 (Note that the symbol "$$" in the destructor code is replaced
 784 by the value of the non-terminal.)</p>
 785
 786 <p>It is important to note that the value of a non-terminal is passed
 787 to the destructor whenever the non-terminal is removed from the
 788 stack, unless the non-terminal is used in a C-code action.  If
 789 the non-terminal is used by C-code, then it is assumed that the
 790 C-code will take care of destroying it.
 791 More commonly, the value is used to build some
 792 larger structure, and we don't want to destroy it, which is why
 793 the destructor is not called in this circumstance.</p>
 794
 795 <p>Destructors help avoid memory leaks by automatically freeing
 796 allocated objects when they go out of scope.
 797 To do the same using yacc or bison is much more difficult.</p>
 798
 799 <a id='extraarg'></a>
 800 <h4>4.4.5 The <tt>%extra_argument</tt> directive</h4>
 801
 802 <p>The <tt>%extra_argument</tt> directive instructs Lemon to add a 4th parameter
 803 to the parameter list of the Parse() function it generates.  Lemon
 804 doesn't do anything itself with this extra argument, but it does
 805 make the argument available to C-code action routines, destructors,
 806 and so forth.  For example, if the grammar file contains:</p>
 807
 808 <pre>
 809     %extra_argument { MyStruct *pAbc }
 810 </pre>
 811
 812 <p>Then the Parse() function generated will have an 4th parameter
 813 of type "MyStruct*" and all action routines will have access to
 814 a variable named "pAbc" that is the value of the 4th parameter
 815 in the most recent call to Parse().</p>
 816
 817 <p>The <tt>%extra_context</tt> directive works the same except that it
 818 is passed in on the ParseAlloc() or ParseInit() routines instead of
 819 on Parse().</p>
 820
 821 <a id='extractx'></a>
 822 <h4>4.4.6 The <tt>%extra_context</tt> directive</h4>
 823
 824 <p>The <tt>%extra_context</tt> directive instructs Lemon to add a 2nd parameter
 825 to the parameter list of the ParseAlloc() and ParseInit() functions.  Lemon
 826 doesn't do anything itself with these extra argument, but it does
 827 store the value make it available to C-code action routines, destructors,
 828 and so forth.  For example, if the grammar file contains:</p>
 829
 830 <pre>
 831     %extra_context { MyStruct *pAbc }
 832 </pre>
 833
 834 <p>Then the ParseAlloc() and ParseInit() functions will have an 2nd parameter
 835 of type "MyStruct*" and all action routines will have access to
 836 a variable named "pAbc" that is the value of that 2nd parameter.</p>
 837
 838 <p>The <tt>%extra_argument</tt> directive works the same except that it
 839 is passed in on the Parse() routine instead of on ParseAlloc()/ParseInit().</p>
 840
 841 <a id='pfallback'></a>
 842 <h4>4.4.7 The <tt>%fallback</tt> directive</h4>
 843
 844 <p>The <tt>%fallback</tt> directive specifies an alternative meaning for one
 845 or more tokens.  The alternative meaning is tried if the original token
 846 would have generated a syntax error.</p>
 847
 848 <p>The <tt>%fallback</tt> directive was added to support robust parsing of SQL
 849 syntax in <a href='https://www.sqlite.org/'>SQLite</a>.
 850 The SQL language contains a large assortment of keywords, each of which
 851 appears as a different token to the language parser.  SQL contains so
 852 many keywords that it can be difficult for programmers to keep up with
 853 them all.  Programmers will, therefore, sometimes mistakenly use an
 854 obscure language keyword for an identifier.  The <tt>%fallback</tt> directive
 855 provides a mechanism to tell the parser:  "If you are unable to parse
 856 this keyword, try treating it as an identifier instead."</p>
 857
 858 <p>The syntax of <tt>%fallback</tt> is as follows:</p>
 859
 860 <blockquote>
 861 <tt>%fallback</tt> <i>ID</i> <i>TOKEN...</i> <b>.</b>
 862 </blockquote></p>
 863
 864 <p>In words, the <tt>%fallback</tt> directive is followed by a list of token
 865 names terminated by a period.
 866 The first token name is the fallback token &mdash; the
 867 token to which all the other tokens fall back to.  The second and subsequent
 868 arguments are tokens which fall back to the token identified by the first
 869 argument.</p>
 870
 871 <a id='pifdef'></a>
 872 <h4>4.4.8 The <tt>%if</tt> directive and its friends</h4>
 873
 874 <p>The <tt>%if</tt>, <tt>%ifdef</tt>, <tt>%ifndef</tt>, <tt>%else</tt>,
 875 and <tt>%endif</tt> directives
 876 are similar to #if, #ifdef, #ifndef, #else, and #endif in the C-preprocessor,
 877 just not as general.
 878 Each of these directives must begin at the left margin.  No whitespace
 879 is allowed between the "%" and the directive name.</p>
 880
 881 <p>Grammar text in between "<tt>%ifdef MACRO</tt>" and the next nested
 882 "<tt>%endif</tt>" is
 883 ignored unless the "-DMACRO" command-line option is used.  Grammar text
 884 betwen "<tt>%ifndef MACRO</tt>" and the next nested "<tt>%endif</tt>" is
 885 included except when the "-DMACRO" command-line option is used.<p>
 886
 887 <p>The text in between "<tt>%if</tt> <i>CONDITIONAL</i>" and its
 888 corresponding <tt>%endif</tt> is included only if <i>CONDITIONAL</i>
 889 is true.  The CONDITION is one or more macro names, optionally connected
 890 using the "||" and "&amp;&amp;" binary operators, the "!" unary operator,
 891 and grouped using balanced parentheses.  Each term is true if the
 892 corresponding macro exists, and false if it does not exist.</p>
 893
 894 <p>An optional "<tt>%else</tt>" directive can occur anywhere in between a
 895 <tt>%ifdef</tt>, <tt>%ifndef</tt>, or <tt>%if</tt> directive and
 896 its corresponding <tt>%endif</tt>.</p>
 897
 898 <p>Note that the argument to <tt>%ifdef</tt> and <tt>%ifndef</tt> is
 899 intended to be a single preprocessor symbol name, not a general expression.
 900 Use the "<tt>%if</tt>" directive for general expressions.</p>
 901
 902 <a id='pinclude'></a>
 903 <h4>4.4.9 The <tt>%include</tt> directive</h4>
 904
 905 <p>The <tt>%include</tt> directive specifies C code that is included at the
 906 top of the generated parser.  You can include any text you want &mdash;
 907 the Lemon parser generator copies it blindly.  If you have multiple
 908 <tt>%include</tt> directives in your grammar file, their values are concatenated
 909 so that all <tt>%include</tt> code ultimately appears near the top of the
 910 generated parser, in the same order as it appeared in the grammar.</p>
 911
 912 <p>The <tt>%include</tt> directive is very handy for getting some extra #include
 913 preprocessor statements at the beginning of the generated parser.
 914 For example:</p>
 915
 916 <pre>
 917    %include {#include &lt;unistd.h&gt;}
 918 </pre>
 919
 920 <p>This might be needed, for example, if some of the C actions in the
 921 grammar call functions that are prototyped in unistd.h.</p>
 922
 923 <p>Use the <tt><a href="#pcode">%code</a></tt> directive to add code to
 924 the end of the generated parser.</p>
 925
 926 <a id='pleft'></a>
 927 <h4>4.4.10 The <tt>%left</tt> directive</h4>
 928
 929 The <tt>%left</tt> directive is used (along with the
 930 <tt><a href='#pright'>%right</a></tt> and
 931 <tt><a href='#pnonassoc'>%nonassoc</a></tt> directives) to declare
 932 precedences of terminal symbols.
 933 Every terminal symbol whose name appears after
 934 a <tt>%left</tt> directive but before the next period (".") is
 935 given the same left-associative precedence value.  Subsequent
 936 <tt>%left</tt> directives have higher precedence.  For example:</p>
 937
 938 <pre>
 939    %left AND.
 940    %left OR.
 941    %nonassoc EQ NE GT GE LT LE.
 942    %left PLUS MINUS.
 943    %left TIMES DIVIDE MOD.
 944    %right EXP NOT.
 945 </pre>
 946
 947 <p>Note the period that terminates each <tt>%left</tt>,
 948 <tt>%right</tt> or <tt>%nonassoc</tt>
 949 directive.</p>
 950
 951 <p>LALR(1) grammars can get into a situation where they require
 952 a large amount of stack space if you make heavy use or right-associative
 953 operators.  For this reason, it is recommended that you use <tt>%left</tt>
 954 rather than <tt>%right</tt> whenever possible.</p>
 955
 956 <a id='pname'></a>
 957 <h4>4.4.11 The <tt>%name</tt> directive</h4>
 958
 959 <p>By default, the functions generated by Lemon all begin with the
 960 five-character string "Parse".  You can change this string to something
 961 different using the <tt>%name</tt> directive.  For instance:</p>
 962
 963 <pre>
 964    %name Abcde
 965 </pre>
 966
 967 <p>Putting this directive in the grammar file will cause Lemon to generate
 968 functions named</p>
 969 <ul>
 970 <li> AbcdeAlloc(),
 971 <li> AbcdeFree(),
 972 <li> AbcdeTrace(), and
 973 <li> Abcde().
 974 </ul>
 975 </p>The <tt>%name</tt> directive allows you to generate two or more different
 976 parsers and link them all into the same executable.</p>
 977
 978 <a id='pnonassoc'></a>
 979 <h4>4.4.12 The <tt>%nonassoc</tt> directive</h4>
 980
 981 <p>This directive is used to assign non-associative precedence to
 982 one or more terminal symbols.  See the section on
 983 <a href='#precrules'>precedence rules</a>
 984 or on the <tt><a href='#pleft'>%left</a></tt> directive
 985 for additional information.</p>
 986
 987 <a id='parse_accept'></a>
 988 <h4>4.4.13 The <tt>%parse_accept</tt> directive</h4>
 989
 990 <p>The <tt>%parse_accept</tt> directive specifies a block of C code that is
 991 executed whenever the parser accepts its input string.  To "accept"
 992 an input string means that the parser was able to process all tokens
 993 without error.</p>
 994
 995 <p>For example:</p>
 996
 997 <pre>
 998    %parse_accept {
 999       printf("parsing complete!\n");
1000    }
1001 </pre>
1002
1003 <a id='parse_failure'></a>
1004 <h4>4.4.14 The <tt>%parse_failure</tt> directive</h4>
1005
1006 <p>The <tt>%parse_failure</tt> directive specifies a block of C code that
1007 is executed whenever the parser fails complete.  This code is not
1008 executed until the parser has tried and failed to resolve an input
1009 error using is usual error recovery strategy.  The routine is
1010 only invoked when parsing is unable to continue.</p>
1011
1012 <pre>
1013    %parse_failure {
1014      fprintf(stderr,"Giving up.  Parser is hopelessly lost...\n");
1015    }
1016 </pre>
1017
1018 <a id='pright'></a>
1019 <h4>4.4.15 The <tt>%right</tt> directive</h4>
1020
1021 <p>This directive is used to assign right-associative precedence to
1022 one or more terminal symbols.  See the section on
1023 <a href='#precrules'>precedence rules</a>
1024 or on the <a href='#pleft'>%left</a> directive for additional information.</p>
1025
1026 <a id='stack_overflow'></a>
1027 <h4>4.4.16 The <tt>%stack_overflow</tt> directive</h4>
1028
1029 <p>The <tt>%stack_overflow</tt> directive specifies a block of C code that
1030 is executed if the parser's internal stack ever overflows.  Typically
1031 this just prints an error message.  After a stack overflow, the parser
1032 will be unable to continue and must be reset.</p>
1033
1034 <pre>
1035    %stack_overflow {
1036      fprintf(stderr,"Giving up.  Parser stack overflow\n");
1037    }
1038 </pre>
1039
1040 <p>You can help prevent parser stack overflows by avoiding the use
1041 of right recursion and right-precedence operators in your grammar.
1042 Use left recursion and and left-precedence operators instead to
1043 encourage rules to reduce sooner and keep the stack size down.
1044 For example, do rules like this:</p>
1045 <pre>
1046    list ::= list element.      // left-recursion.  Good!
1047    list ::= .
1048 </pre>
1049 <p>Not like this:</p>
1050 <pre>
1051    list ::= element list.      // right-recursion.  Bad!
1052    list ::= .
1053 </pre>
1054
1055 <a id='stack_size'></a>
1056 <h4>4.4.17 The <tt>%stack_size</tt> directive</h4>
1057
1058 <p>If stack overflow is a problem and you can't resolve the trouble
1059 by using left-recursion, then you might want to increase the size
1060 of the parser's stack using this directive.  Put an positive integer
1061 after the <tt>%stack_size</tt> directive and Lemon will generate a parse
1062 with a stack of the requested size.  The default value is 100.</p>
1063
1064 <pre>
1065    %stack_size 2000
1066 </pre>
1067
1068 <a id='start_symbol'></a>
1069 <h4>4.4.18 The <tt>%start_symbol</tt> directive</h4>
1070
1071 <p>By default, the start symbol for the grammar that Lemon generates
1072 is the first non-terminal that appears in the grammar file.  But you
1073 can choose a different start symbol using the
1074 <tt>%start_symbol</tt> directive.</p>
1075
1076 <pre>
1077    %start_symbol  prog
1078 </pre>
1079
1080 <a id='syntax_error'></a>
1081 <h4>4.4.19 The <tt>%syntax_error</tt> directive</h4>
1082
1083 <p>See <a href='#errors'>Error Processing</a>.</p>
1084
1085 <a id='token'></a>
1086 <h4>4.4.20 The <tt>%token</tt> directive</h4>
1087
1088 <p>Tokens are normally created automatically, the first time they are used.
1089 Any identifier that begins with an upper-case letter is a token.
1090
1091 <p>Sometimes it is useful to declare tokens in advance, however.  The
1092 integer values assigned to each token determined by the order in which
1093 the tokens are seen.  So by declaring tokens in advance, it is possible to
1094 cause some tokens to have low-numbered values, which might be desirable in
1095 some grammers, or to have sequential values assigned to a sequence of
1096 related tokens.  For this reason, the %token directive is provided to
1097 declare tokens in advance.  The syntax is as follows:
1098
1099 <blockquote>
1100 <tt>%token</tt> <i>TOKEN</i> <i>TOKEN...</i> <b>.</b>
1101 </blockquote></p>
1102
1103 <p>The %token directive is followed by zero or more token symbols and
1104 terminated by a single ".".  Each token named is created if it does not
1105 already exist.  Tokens are created in order.
1106
1107
1108 <a id='token_class'></a>
1109 <h4>4.4.21 The <tt>%token_class</tt> directive</h4>
1110
1111 <p>Undocumented.  Appears to be related to the MULTITERMINAL concept.
1112 <a href='http://sqlite.org/src/fdiff?v1=796930d5fc2036c7&v2=624b24c5dc048e09&sbs=0'>Implementation</a>.</p>
1113
1114 <a id='token_destructor'></a>
1115 <h4>4.4.22 The <tt>%token_destructor</tt> directive</h4>
1116
1117 <p>The <tt>%destructor</tt> directive assigns a destructor to a non-terminal
1118 symbol.  (See the description of the
1119 <tt><a href='%destructor'>%destructor</a></tt> directive above.)
1120 The <tt>%token_destructor</tt> directive does the same thing
1121 for all terminal symbols.</p>
1122
1123 <p>Unlike non-terminal symbols, which may each have a different data type
1124 for their values, terminals all use the same data type (defined by
1125 the <tt><a href='#token_type'>%token_type</a></tt> directive)
1126 and so they use a common destructor.
1127 Other than that, the token destructor works just like the non-terminal
1128 destructors.</p>
1129
1130 <a id='token_prefix'></a>
1131 <h4>4.4.23 The <tt>%token_prefix</tt> directive</h4>
1132
1133 <p>Lemon generates #defines that assign small integer constants
1134 to each terminal symbol in the grammar.  If desired, Lemon will
1135 add a prefix specified by this directive
1136 to each of the #defines it generates.</p>
1137
1138 <p>So if the default output of Lemon looked like this:</p>
1139 <pre>
1140     #define AND              1
1141     #define MINUS            2
1142     #define OR               3
1143     #define PLUS             4
1144 </pre>
1145 <p>You can insert a statement into the grammar like this:</p>
1146 <pre>
1147     %token_prefix    TOKEN_
1148 </pre>
1149 <p>to cause Lemon to produce these symbols instead:</p>
1150 <pre>
1151     #define TOKEN_AND        1
1152     #define TOKEN_MINUS      2
1153     #define TOKEN_OR         3
1154     #define TOKEN_PLUS       4
1155 </pre>
1156
1157 <a id='token_type'></a><a id='ptype'></a>
1158 <h4>4.4.24 The <tt>%token_type</tt> and <tt>%type</tt> directives</h4>
1159
1160 <p>These directives are used to specify the data types for values
1161 on the parser's stack associated with terminal and non-terminal
1162 symbols.  The values of all terminal symbols must be of the same
1163 type.  This turns out to be the same data type as the 3rd parameter
1164 to the Parse() function generated by Lemon.  Typically, you will
1165 make the value of a terminal symbol be a pointer to some kind of
1166 token structure.  Like this:</p>
1167
1168 <pre>
1169    %token_type    {Token*}
1170 </pre>
1171
1172 <p>If the data type of terminals is not specified, the default value
1173 is "void*".</p>
1174
1175 <p>Non-terminal symbols can each have their own data types.  Typically
1176 the data type of a non-terminal is a pointer to the root of a parse tree
1177 structure that contains all information about that non-terminal.
1178 For example:</p>
1179
1180 <pre>
1181    %type   expr  {Expr*}
1182 </pre>
1183
1184 <p>Each entry on the parser's stack is actually a union containing
1185 instances of all data types for every non-terminal and terminal symbol.
1186 Lemon will automatically use the correct element of this union depending
1187 on what the corresponding non-terminal or terminal symbol is.  But
1188 the grammar designer should keep in mind that the size of the union
1189 will be the size of its largest element.  So if you have a single
1190 non-terminal whose data type requires 1K of storage, then your 100
1191 entry parser stack will require 100K of heap space.  If you are willing
1192 and able to pay that price, fine.  You just need to know.</p>
1193
1194 <a id='pwildcard'></a>
1195 <h4>4.4.25 The <tt>%wildcard</tt> directive</h4>
1196
1197 <p>The <tt>%wildcard</tt> directive is followed by a single token name and a
1198 period.  This directive specifies that the identified token should
1199 match any input token.</p>
1200
1201 <p>When the generated parser has the choice of matching an input against
1202 the wildcard token and some other token, the other token is always used.
1203 The wildcard token is only matched if there are no alternatives.</p>
1204
1205 <a id='reallc'></a>
1206 <h4>4.4.26 The <tt>%realloc</tt> and <tt>%free</tt> directives</h4>
1207
1208 <p>The <tt>%realloc</tt> and <tt>%free</tt> directives defines function
1209 that allocate and free heap memory.  The signatures of these functions
1210 should be the same as the realloc() and free() functions from the standard
1211 C library.
1212
1213 <p>If both of these functions are defined
1214 then these functions are used to allocate and free
1215 memory for supplemental parser stack space, if the initial
1216 parse stack space is exceeded.  The initial parser stack size
1217 is specified by either <tt>%stack_size</tt> or the
1218 -DYYSTACKDEPTH compile-time flag.
1219
1220 <a id='errors'></a>
1221 <h2>5.0 Error Processing</h2>
1222
1223 <p>After extensive experimentation over several years, it has been
1224 discovered that the error recovery strategy used by yacc is about
1225 as good as it gets.  And so that is what Lemon uses.</p>
1226
1227 <p>When a Lemon-generated parser encounters a syntax error, it
1228 first invokes the code specified by the <tt>%syntax_error</tt> directive, if
1229 any.  It then enters its error recovery strategy.  The error recovery
1230 strategy is to begin popping the parsers stack until it enters a
1231 state where it is permitted to shift a special non-terminal symbol
1232 named "error".  It then shifts this non-terminal and continues
1233 parsing.  The <tt>%syntax_error</tt> routine will not be called again
1234 until at least three new tokens have been successfully shifted.</p>
1235
1236 <p>If the parser pops its stack until the stack is empty, and it still
1237 is unable to shift the error symbol, then the
1238 <tt><a href='#parse_failure'>%parse_failure</a></tt> routine
1239 is invoked and the parser resets itself to its start state, ready
1240 to begin parsing a new file.  This is what will happen at the very
1241 first syntax error, of course, if there are no instances of the
1242 "error" non-terminal in your grammar.</p>
1243
1244
1245 <a id='history'></a>
1246 <h2>6.0 History of Lemon</h2>
1247
1248 <p>Lemon was originally written by Richard Hipp sometime in the late
1249 1980s on a Sun4 Workstation using K&amp;R C.
1250 There was a companion LL(1) parser generator program named "Lime".
1251 The Lime source code has been lost.</p>
1252
1253 <p>The lemon.c source file was originally many separate files that were
1254 compiled together to generate the "lemon" executable.  Sometime in the
1255 1990s, the individual source code files were combined together into
1256 the current single large "lemon.c" source file.  You can still see traces
1257 of original filenames in the code.</p>
1258
1259 <p>Since 2001, Lemon has been part of the
1260 <a href="https://sqlite.org/">SQLite project</a> and the source code
1261 to Lemon has been managed as a part of the
1262 <a href="https://sqlite.org/src">SQLite source tree</a> in the following
1263 files:</p>
1264
1265 <ul>
1266 <li> <a href="https://sqlite.org/src/file/tool/lemon.c">tool/lemon.c</a>
1267 <li> <a href="https://sqlite.org/src/file/tool/lempar.c">tool/lempar.c</a>
1268 <li> <a href="https://sqlite.org/src/file/doc/lemon.html">doc/lemon.html</a>
1269 </ul>
1270
1271 <a id="copyright"></a>
1272 <h2>7.0 Copyright</h2>
1273
1274 <p>All of the source code to Lemon, including the template parser file
1275 "lempar.c" and this documentation file ("lemon.html") are in the public
1276 domain.  You can use the code for any purpose and without attribution.</p>
1277
1278 <p>The code comes with no warranty.  If it breaks, you get to keep both
1279 pieces.</p>
1280
1281 </body>
1282 </html>