doc/lemon.html

   1 <html>
   2 <head>
   3 <title>The Lemon Parser Generator</title>
   4 </head>
   5 <body bgcolor=white>
   6 <h1 align=center>The Lemon Parser Generator</h1>
   7
   8 <p>Lemon is an LALR(1) parser generator for C.
   9 It does the same job as "bison" and "yacc".
  10 But lemon is not a bison or yacc clone.  Lemon
  11 uses a different grammar syntax which is designed to
  12 reduce the number of coding errors.  Lemon also uses a
  13 parsing engine that is faster than yacc and
  14 bison and which is both reentrant and threadsafe.
  15 (Update: Since the previous sentence was written, bison
  16 has also been updated so that it too can generate a
  17 reentrant and threadsafe parser.)
  18 Lemon also implements features that can be used
  19 to eliminate resource leaks, making is suitable for use
  20 in long-running programs such as graphical user interfaces
  21 or embedded controllers.</p>
  22
  23 <p>This document is an introduction to the Lemon
  24 parser generator.</p>
  25
  26 <h2>Theory of Operation</h2>
  27
  28 <p>The main goal of Lemon is to translate a context free grammar (CFG)
  29 for a particular language into C code that implements a parser for
  30 that language.
  31 The program has two inputs:
  32 <ul>
  33 <li>The grammar specification.
  34 <li>A parser template file.
  35 </ul>
  36 Typically, only the grammar specification is supplied by the programmer.
  37 Lemon comes with a default parser template which works fine for most
  38 applications.  But the user is free to substitute a different parser
  39 template if desired.</p>
  40
  41 <p>Depending on command-line options, Lemon will generate between
  42 one and three files of outputs.
  43 <ul>
  44 <li>C code to implement the parser.
  45 <li>A header file defining an integer ID for each terminal symbol.
  46 <li>An information file that describes the states of the generated parser
  47     automaton.
  48 </ul>
  49 By default, all three of these output files are generated.
  50 The header file is suppressed if the "-m" command-line option is
  51 used and the report file is omitted when "-q" is selected.</p>
  52
  53 <p>The grammar specification file uses a ".y" suffix, by convention.
  54 In the examples used in this document, we'll assume the name of the
  55 grammar file is "gram.y".  A typical use of Lemon would be the
  56 following command:
  57 <pre>
  58    lemon gram.y
  59 </pre>
  60 This command will generate three output files named "gram.c",
  61 "gram.h" and "gram.out".
  62 The first is C code to implement the parser.  The second
  63 is the header file that defines numerical values for all
  64 terminal symbols, and the last is the report that explains
  65 the states used by the parser automaton.</p>
  66
  67 <h3>Command Line Options</h3>
  68
  69 <p>The behavior of Lemon can be modified using command-line options.
  70 You can obtain a list of the available command-line options together
  71 with a brief explanation of what each does by typing
  72 <pre>
  73    lemon -?
  74 </pre>
  75 As of this writing, the following command-line options are supported:
  76 <ul>
  77 <li><b>-b</b>
  78 Show only the basis for each parser state in the report file.
  79 <li><b>-c</b>
  80 Do not compress the generated action tables.
  81 <li><b>-D<i>name</i></b>
  82 Define C preprocessor macro <i>name</i>.  This macro is useable by
  83 "%ifdef" lines in the grammar file.
  84 <li><b>-g</b>
  85 Do not generate a parser.  Instead write the input grammar to standard
  86 output with all comments, actions, and other extraneous text removed.
  87 <li><b>-l</b>
  88 Omit "#line" directives in the generated parser C code.
  89 <li><b>-m</b>
  90 Cause the output C source code to be compatible with the "makeheaders"
  91 program.
  92 <li><b>-p</b>
  93 Display all conflicts that are resolved by
  94 <a href='#precrules'>precedence rules</a>.
  95 <li><b>-q</b>
  96 Suppress generation of the report file.
  97 <li><b>-r</b>
  98 Do not sort or renumber the parser states as part of optimization.
  99 <li><b>-s</b>
 100 Show parser statistics before existing.
 101 <li><b>-T<i>file</i></b>
 102 Use <i>file</i> as the template for the generated C-code parser implementation.
 103 <li><b>-x</b>
 104 Print the Lemon version number.
 105 </ul>
 106
 107 <h3>The Parser Interface</h3>
 108
 109 <p>Lemon doesn't generate a complete, working program.  It only generates
 110 a few subroutines that implement a parser.  This section describes
 111 the interface to those subroutines.  It is up to the programmer to
 112 call these subroutines in an appropriate way in order to produce a
 113 complete system.</p>
 114
 115 <p>Before a program begins using a Lemon-generated parser, the program
 116 must first create the parser.
 117 A new parser is created as follows:
 118 <pre>
 119    void *pParser = ParseAlloc( malloc );
 120 </pre>
 121 The ParseAlloc() routine allocates and initializes a new parser and
 122 returns a pointer to it.
 123 The actual data structure used to represent a parser is opaque &mdash;
 124 its internal structure is not visible or usable by the calling routine.
 125 For this reason, the ParseAlloc() routine returns a pointer to void
 126 rather than a pointer to some particular structure.
 127 The sole argument to the ParseAlloc() routine is a pointer to the
 128 subroutine used to allocate memory.  Typically this means malloc().</p>
 129
 130 <p>After a program is finished using a parser, it can reclaim all
 131 memory allocated by that parser by calling
 132 <pre>
 133    ParseFree(pParser, free);
 134 </pre>
 135 The first argument is the same pointer returned by ParseAlloc().  The
 136 second argument is a pointer to the function used to release bulk
 137 memory back to the system.</p>
 138
 139 <p>After a parser has been allocated using ParseAlloc(), the programmer
 140 must supply the parser with a sequence of tokens (terminal symbols) to
 141 be parsed.  This is accomplished by calling the following function
 142 once for each token:
 143 <pre>
 144    Parse(pParser, hTokenID, sTokenData, pArg);
 145 </pre>
 146 The first argument to the Parse() routine is the pointer returned by
 147 ParseAlloc().
 148 The second argument is a small positive integer that tells the parse the
 149 type of the next token in the data stream.
 150 There is one token type for each terminal symbol in the grammar.
 151 The gram.h file generated by Lemon contains #define statements that
 152 map symbolic terminal symbol names into appropriate integer values.
 153 A value of 0 for the second argument is a special flag to the
 154 parser to indicate that the end of input has been reached.
 155 The third argument is the value of the given token.  By default,
 156 the type of the third argument is integer, but the grammar will
 157 usually redefine this type to be some kind of structure.
 158 Typically the second argument will be a broad category of tokens
 159 such as "identifier" or "number" and the third argument will
 160 be the name of the identifier or the value of the number.</p>
 161
 162 <p>The Parse() function may have either three or four arguments,
 163 depending on the grammar.  If the grammar specification file requests
 164 it (via the <a href='#extraarg'><tt>extra_argument</tt> directive</a>),
 165 the Parse() function will have a fourth parameter that can be
 166 of any type chosen by the programmer.  The parser doesn't do anything
 167 with this argument except to pass it through to action routines.
 168 This is a convenient mechanism for passing state information down
 169 to the action routines without having to use global variables.</p>
 170
 171 <p>A typical use of a Lemon parser might look something like the
 172 following:
 173 <pre>
 174    01 ParseTree *ParseFile(const char *zFilename){
 175    02    Tokenizer *pTokenizer;
 176    03    void *pParser;
 177    04    Token sToken;
 178    05    int hTokenId;
 179    06    ParserState sState;
 180    07
 181    08    pTokenizer = TokenizerCreate(zFilename);
 182    09    pParser = ParseAlloc( malloc );
 183    10    InitParserState(&sState);
 184    11    while( GetNextToken(pTokenizer, &hTokenId, &sToken) ){
 185    12       Parse(pParser, hTokenId, sToken, &sState);
 186    13    }
 187    14    Parse(pParser, 0, sToken, &sState);
 188    15    ParseFree(pParser, free );
 189    16    TokenizerFree(pTokenizer);
 190    17    return sState.treeRoot;
 191    18 }
 192 </pre>
 193 This example shows a user-written routine that parses a file of
 194 text and returns a pointer to the parse tree.
 195 (All error-handling code is omitted from this example to keep it
 196 simple.)
 197 We assume the existence of some kind of tokenizer which is created
 198 using TokenizerCreate() on line 8 and deleted by TokenizerFree()
 199 on line 16.  The GetNextToken() function on line 11 retrieves the
 200 next token from the input file and puts its type in the
 201 integer variable hTokenId.  The sToken variable is assumed to be
 202 some kind of structure that contains details about each token,
 203 such as its complete text, what line it occurs on, etc. </p>
 204
 205 <p>This example also assumes the existence of structure of type
 206 ParserState that holds state information about a particular parse.
 207 An instance of such a structure is created on line 6 and initialized
 208 on line 10.  A pointer to this structure is passed into the Parse()
 209 routine as the optional 4th argument.
 210 The action routine specified by the grammar for the parser can use
 211 the ParserState structure to hold whatever information is useful and
 212 appropriate.  In the example, we note that the treeRoot field of
 213 the ParserState structure is left pointing to the root of the parse
 214 tree.</p>
 215
 216 <p>The core of this example as it relates to Lemon is as follows:
 217 <pre>
 218    ParseFile(){
 219       pParser = ParseAlloc( malloc );
 220       while( GetNextToken(pTokenizer,&hTokenId, &sToken) ){
 221          Parse(pParser, hTokenId, sToken);
 222       }
 223       Parse(pParser, 0, sToken);
 224       ParseFree(pParser, free );
 225    }
 226 </pre>
 227 Basically, what a program has to do to use a Lemon-generated parser
 228 is first create the parser, then send it lots of tokens obtained by
 229 tokenizing an input source.  When the end of input is reached, the
 230 Parse() routine should be called one last time with a token type
 231 of 0.  This step is necessary to inform the parser that the end of
 232 input has been reached.  Finally, we reclaim memory used by the
 233 parser by calling ParseFree().</p>
 234
 235 <p>There is one other interface routine that should be mentioned
 236 before we move on.
 237 The ParseTrace() function can be used to generate debugging output
 238 from the parser.  A prototype for this routine is as follows:
 239 <pre>
 240    ParseTrace(FILE *stream, char *zPrefix);
 241 </pre>
 242 After this routine is called, a short (one-line) message is written
 243 to the designated output stream every time the parser changes states
 244 or calls an action routine.  Each such message is prefaced using
 245 the text given by zPrefix.  This debugging output can be turned off
 246 by calling ParseTrace() again with a first argument of NULL (0).</p>
 247
 248 <h3>Differences With YACC and BISON</h3>
 249
 250 <p>Programmers who have previously used the yacc or bison parser
 251 generator will notice several important differences between yacc and/or
 252 bison and Lemon.
 253 <ul>
 254 <li>In yacc and bison, the parser calls the tokenizer.  In Lemon,
 255     the tokenizer calls the parser.
 256 <li>Lemon uses no global variables.  Yacc and bison use global variables
 257     to pass information between the tokenizer and parser.
 258 <li>Lemon allows multiple parsers to be running simultaneously.  Yacc
 259     and bison do not.
 260 </ul>
 261 These differences may cause some initial confusion for programmers
 262 with prior yacc and bison experience.
 263 But after years of experience using Lemon, I firmly
 264 believe that the Lemon way of doing things is better.</p>
 265
 266 <p><i>Updated as of 2016-02-16:</i>
 267 The text above was written in the 1990s.
 268 We are told that Bison has lately been enhanced to support the
 269 tokenizer-calls-parser paradigm used by Lemon, and to obviate the
 270 need for global variables.</p>
 271
 272 <h2>Input File Syntax</h2>
 273
 274 <p>The main purpose of the grammar specification file for Lemon is
 275 to define the grammar for the parser.  But the input file also
 276 specifies additional information Lemon requires to do its job.
 277 Most of the work in using Lemon is in writing an appropriate
 278 grammar file.</p>
 279
 280 <p>The grammar file for lemon is, for the most part, free format.
 281 It does not have sections or divisions like yacc or bison.  Any
 282 declaration can occur at any point in the file.
 283 Lemon ignores whitespace (except where it is needed to separate
 284 tokens) and it honors the same commenting conventions as C and C++.</p>
 285
 286 <h3>Terminals and Nonterminals</h3>
 287
 288 <p>A terminal symbol (token) is any string of alphanumeric
 289 and/or underscore characters
 290 that begins with an upper case letter.
 291 A terminal can contain lowercase letters after the first character,
 292 but the usual convention is to make terminals all upper case.
 293 A nonterminal, on the other hand, is any string of alphanumeric
 294 and underscore characters than begins with a lower case letter.
 295 Again, the usual convention is to make nonterminals use all lower
 296 case letters.</p>
 297
 298 <p>In Lemon, terminal and nonterminal symbols do not need to
 299 be declared or identified in a separate section of the grammar file.
 300 Lemon is able to generate a list of all terminals and nonterminals
 301 by examining the grammar rules, and it can always distinguish a
 302 terminal from a nonterminal by checking the case of the first
 303 character of the name.</p>
 304
 305 <p>Yacc and bison allow terminal symbols to have either alphanumeric
 306 names or to be individual characters included in single quotes, like
 307 this: ')' or '$'.  Lemon does not allow this alternative form for
 308 terminal symbols.  With Lemon, all symbols, terminals and nonterminals,
 309 must have alphanumeric names.</p>
 310
 311 <h3>Grammar Rules</h3>
 312
 313 <p>The main component of a Lemon grammar file is a sequence of grammar
 314 rules.
 315 Each grammar rule consists of a nonterminal symbol followed by
 316 the special symbol "::=" and then a list of terminals and/or nonterminals.
 317 The rule is terminated by a period.
 318 The list of terminals and nonterminals on the right-hand side of the
 319 rule can be empty.
 320 Rules can occur in any order, except that the left-hand side of the
 321 first rule is assumed to be the start symbol for the grammar (unless
 322 specified otherwise using the <tt>%start</tt> directive described below.)
 323 A typical sequence of grammar rules might look something like this:
 324 <pre>
 325   expr ::= expr PLUS expr.
 326   expr ::= expr TIMES expr.
 327   expr ::= LPAREN expr RPAREN.
 328   expr ::= VALUE.
 329 </pre>
 330 </p>
 331
 332 <p>There is one non-terminal in this example, "expr", and five
 333 terminal symbols or tokens: "PLUS", "TIMES", "LPAREN",
 334 "RPAREN" and "VALUE".</p>
 335
 336 <p>Like yacc and bison, Lemon allows the grammar to specify a block
 337 of C code that will be executed whenever a grammar rule is reduced
 338 by the parser.
 339 In Lemon, this action is specified by putting the C code (contained
 340 within curly braces <tt>{...}</tt>) immediately after the
 341 period that closes the rule.
 342 For example:
 343 <pre>
 344   expr ::= expr PLUS expr.   { printf("Doing an addition...\n"); }
 345 </pre>
 346 </p>
 347
 348 <p>In order to be useful, grammar actions must normally be linked to
 349 their associated grammar rules.
 350 In yacc and bison, this is accomplished by embedding a "$$" in the
 351 action to stand for the value of the left-hand side of the rule and
 352 symbols "$1", "$2", and so forth to stand for the value of
 353 the terminal or nonterminal at position 1, 2 and so forth on the
 354 right-hand side of the rule.
 355 This idea is very powerful, but it is also very error-prone.  The
 356 single most common source of errors in a yacc or bison grammar is
 357 to miscount the number of symbols on the right-hand side of a grammar
 358 rule and say "$7" when you really mean "$8".</p>
 359
 360 <p>Lemon avoids the need to count grammar symbols by assigning symbolic
 361 names to each symbol in a grammar rule and then using those symbolic
 362 names in the action.
 363 In yacc or bison, one would write this:
 364 <pre>
 365   expr -> expr PLUS expr  { $$ = $1 + $3; };
 366 </pre>
 367 But in Lemon, the same rule becomes the following:
 368 <pre>
 369   expr(A) ::= expr(B) PLUS expr(C).  { A = B+C; }
 370 </pre>
 371 In the Lemon rule, any symbol in parentheses after a grammar rule
 372 symbol becomes a place holder for that symbol in the grammar rule.
 373 This place holder can then be used in the associated C action to
 374 stand for the value of that symbol.<p>
 375
 376 <p>The Lemon notation for linking a grammar rule with its reduce
 377 action is superior to yacc/bison on several counts.
 378 First, as mentioned above, the Lemon method avoids the need to
 379 count grammar symbols.
 380 Secondly, if a terminal or nonterminal in a Lemon grammar rule
 381 includes a linking symbol in parentheses but that linking symbol
 382 is not actually used in the reduce action, then an error message
 383 is generated.
 384 For example, the rule
 385 <pre>
 386   expr(A) ::= expr(B) PLUS expr(C).  { A = B; }
 387 </pre>
 388 will generate an error because the linking symbol "C" is used
 389 in the grammar rule but not in the reduce action.</p>
 390
 391 <p>The Lemon notation for linking grammar rules to reduce actions
 392 also facilitates the use of destructors for reclaiming memory
 393 allocated by the values of terminals and nonterminals on the
 394 right-hand side of a rule.</p>
 395
 396 <a name='precrules'></a>
 397 <h3>Precedence Rules</h3>
 398
 399 <p>Lemon resolves parsing ambiguities in exactly the same way as
 400 yacc and bison.  A shift-reduce conflict is resolved in favor
 401 of the shift, and a reduce-reduce conflict is resolved by reducing
 402 whichever rule comes first in the grammar file.</p>
 403
 404 <p>Just like in
 405 yacc and bison, Lemon allows a measure of control
 406 over the resolution of paring conflicts using precedence rules.
 407 A precedence value can be assigned to any terminal symbol
 408 using the
 409 <a href='#pleft'>%left</a>,
 410 <a href='#pright'>%right</a> or
 411 <a href='#pnonassoc'>%nonassoc</a> directives.  Terminal symbols
 412 mentioned in earlier directives have a lower precedence that
 413 terminal symbols mentioned in later directives.  For example:</p>
 414
 415 <p><pre>
 416    %left AND.
 417    %left OR.
 418    %nonassoc EQ NE GT GE LT LE.
 419    %left PLUS MINUS.
 420    %left TIMES DIVIDE MOD.
 421    %right EXP NOT.
 422 </pre></p>
 423
 424 <p>In the preceding sequence of directives, the AND operator is
 425 defined to have the lowest precedence.  The OR operator is one
 426 precedence level higher.  And so forth.  Hence, the grammar would
 427 attempt to group the ambiguous expression
 428 <pre>
 429      a AND b OR c
 430 </pre>
 431 like this
 432 <pre>
 433      a AND (b OR c).
 434 </pre>
 435 The associativity (left, right or nonassoc) is used to determine
 436 the grouping when the precedence is the same.  AND is left-associative
 437 in our example, so
 438 <pre>
 439      a AND b AND c
 440 </pre>
 441 is parsed like this
 442 <pre>
 443      (a AND b) AND c.
 444 </pre>
 445 The EXP operator is right-associative, though, so
 446 <pre>
 447      a EXP b EXP c
 448 </pre>
 449 is parsed like this
 450 <pre>
 451      a EXP (b EXP c).
 452 </pre>
 453 The nonassoc precedence is used for non-associative operators.
 454 So
 455 <pre>
 456      a EQ b EQ c
 457 </pre>
 458 is an error.</p>
 459
 460 <p>The precedence of non-terminals is transferred to rules as follows:
 461 The precedence of a grammar rule is equal to the precedence of the
 462 left-most terminal symbol in the rule for which a precedence is
 463 defined.  This is normally what you want, but in those cases where
 464 you want to precedence of a grammar rule to be something different,
 465 you can specify an alternative precedence symbol by putting the
 466 symbol in square braces after the period at the end of the rule and
 467 before any C-code.  For example:</p>
 468
 469 <p><pre>
 470    expr = MINUS expr.  [NOT]
 471 </pre></p>
 472
 473 <p>This rule has a precedence equal to that of the NOT symbol, not the
 474 MINUS symbol as would have been the case by default.</p>
 475
 476 <p>With the knowledge of how precedence is assigned to terminal
 477 symbols and individual
 478 grammar rules, we can now explain precisely how parsing conflicts
 479 are resolved in Lemon.  Shift-reduce conflicts are resolved
 480 as follows:
 481 <ul>
 482 <li> If either the token to be shifted or the rule to be reduced
 483      lacks precedence information, then resolve in favor of the
 484      shift, but report a parsing conflict.
 485 <li> If the precedence of the token to be shifted is greater than
 486      the precedence of the rule to reduce, then resolve in favor
 487      of the shift.  No parsing conflict is reported.
 488 <li> If the precedence of the token it be shifted is less than the
 489      precedence of the rule to reduce, then resolve in favor of the
 490      reduce action.  No parsing conflict is reported.
 491 <li> If the precedences are the same and the shift token is
 492      right-associative, then resolve in favor of the shift.
 493      No parsing conflict is reported.
 494 <li> If the precedences are the same the shift token is
 495      left-associative, then resolve in favor of the reduce.
 496      No parsing conflict is reported.
 497 <li> Otherwise, resolve the conflict by doing the shift and
 498      report the parsing conflict.
 499 </ul>
 500 Reduce-reduce conflicts are resolved this way:
 501 <ul>
 502 <li> If either reduce rule
 503      lacks precedence information, then resolve in favor of the
 504      rule that appears first in the grammar and report a parsing
 505      conflict.
 506 <li> If both rules have precedence and the precedence is different
 507      then resolve the dispute in favor of the rule with the highest
 508      precedence and do not report a conflict.
 509 <li> Otherwise, resolve the conflict by reducing by the rule that
 510      appears first in the grammar and report a parsing conflict.
 511 </ul>
 512
 513 <h3>Special Directives</h3>
 514
 515 <p>The input grammar to Lemon consists of grammar rules and special
 516 directives.  We've described all the grammar rules, so now we'll
 517 talk about the special directives.</p>
 518
 519 <p>Directives in lemon can occur in any order.  You can put them before
 520 the grammar rules, or after the grammar rules, or in the mist of the
 521 grammar rules.  It doesn't matter.  The relative order of
 522 directives used to assign precedence to terminals is important, but
 523 other than that, the order of directives in Lemon is arbitrary.</p>
 524
 525 <p>Lemon supports the following special directives:
 526 <ul>
 527 <li><tt>%code</tt>
 528 <li><tt>%default_destructor</tt>
 529 <li><tt>%default_type</tt>
 530 <li><tt>%destructor</tt>
 531 <li><tt>%endif</tt>
 532 <li><tt>%extra_argument</tt>
 533 <li><tt>%fallback</tt>
 534 <li><tt>%ifdef</tt>
 535 <li><tt>%ifndef</tt>
 536 <li><tt>%include</tt>
 537 <li><tt>%left</tt>
 538 <li><tt>%name</tt>
 539 <li><tt>%nonassoc</tt>
 540 <li><tt>%parse_accept</tt>
 541 <li><tt>%parse_failure </tt>
 542 <li><tt>%right</tt>
 543 <li><tt>%stack_overflow</tt>
 544 <li><tt>%stack_size</tt>
 545 <li><tt>%start_symbol</tt>
 546 <li><tt>%syntax_error</tt>
 547 <li><tt>%token_class</tt>
 548 <li><tt>%token_destructor</tt>
 549 <li><tt>%token_prefix</tt>
 550 <li><tt>%token_type</tt>
 551 <li><tt>%type</tt>
 552 <li><tt>%wildcard</tt>
 553 </ul>
 554 Each of these directives will be described separately in the
 555 following sections:</p>
 556
 557 <a name='pcode'></a>
 558 <h4>The <tt>%code</tt> directive</h4>
 559
 560 <p>The %code directive is used to specify addition C code that
 561 is added to the end of the main output file.  This is similar to
 562 the <a href='#pinclude'>%include</a> directive except that %include
 563 is inserted at the beginning of the main output file.</p>
 564
 565 <p>%code is typically used to include some action routines or perhaps
 566 a tokenizer or even the "main()" function
 567 as part of the output file.</p>
 568
 569 <a name='default_destructor'></a>
 570 <h4>The <tt>%default_destructor</tt> directive</h4>
 571
 572 <p>The %default_destructor directive specifies a destructor to
 573 use for non-terminals that do not have their own destructor
 574 specified by a separate %destructor directive.  See the documentation
 575 on the <a name='#destructor'>%destructor</a> directive below for
 576 additional information.</p>
 577
 578 <p>In some grammers, many different non-terminal symbols have the
 579 same datatype and hence the same destructor.  This directive is
 580 a convenience way to specify the same destructor for all those
 581 non-terminals using a single statement.</p>
 582
 583 <a name='default_type'></a>
 584 <h4>The <tt>%default_type</tt> directive</h4>
 585
 586 <p>The %default_type directive specifies the datatype of non-terminal
 587 symbols that do no have their own datatype defined using a separate
 588 <a href='#ptype'>%type</a> directive.
 589 </p>
 590
 591 <a name='destructor'></a>
 592 <h4>The <tt>%destructor</tt> directive</h4>
 593
 594 <p>The %destructor directive is used to specify a destructor for
 595 a non-terminal symbol.
 596 (See also the <a href='#token_destructor'>%token_destructor</a>
 597 directive which is used to specify a destructor for terminal symbols.)</p>
 598
 599 <p>A non-terminal's destructor is called to dispose of the
 600 non-terminal's value whenever the non-terminal is popped from
 601 the stack.  This includes all of the following circumstances:
 602 <ul>
 603 <li> When a rule reduces and the value of a non-terminal on
 604      the right-hand side is not linked to C code.
 605 <li> When the stack is popped during error processing.
 606 <li> When the ParseFree() function runs.
 607 </ul>
 608 The destructor can do whatever it wants with the value of
 609 the non-terminal, but its design is to deallocate memory
 610 or other resources held by that non-terminal.</p>
 611
 612 <p>Consider an example:
 613 <pre>
 614    %type nt {void*}
 615    %destructor nt { free($$); }
 616    nt(A) ::= ID NUM.   { A = malloc( 100 ); }
 617 </pre>
 618 This example is a bit contrived but it serves to illustrate how
 619 destructors work.  The example shows a non-terminal named
 620 "nt" that holds values of type "void*".  When the rule for
 621 an "nt" reduces, it sets the value of the non-terminal to
 622 space obtained from malloc().  Later, when the nt non-terminal
 623 is popped from the stack, the destructor will fire and call
 624 free() on this malloced space, thus avoiding a memory leak.
 625 (Note that the symbol "$$" in the destructor code is replaced
 626 by the value of the non-terminal.)</p>
 627
 628 <p>It is important to note that the value of a non-terminal is passed
 629 to the destructor whenever the non-terminal is removed from the
 630 stack, unless the non-terminal is used in a C-code action.  If
 631 the non-terminal is used by C-code, then it is assumed that the
 632 C-code will take care of destroying it.
 633 More commonly, the value is used to build some
 634 larger structure and we don't want to destroy it, which is why
 635 the destructor is not called in this circumstance.</p>
 636
 637 <p>Destructors help avoid memory leaks by automatically freeing
 638 allocated objects when they go out of scope.
 639 To do the same using yacc or bison is much more difficult.</p>
 640
 641 <a name="extraarg"></a>
 642 <h4>The <tt>%extra_argument</tt> directive</h4>
 643
 644 The %extra_argument directive instructs Lemon to add a 4th parameter
 645 to the parameter list of the Parse() function it generates.  Lemon
 646 doesn't do anything itself with this extra argument, but it does
 647 make the argument available to C-code action routines, destructors,
 648 and so forth.  For example, if the grammar file contains:</p>
 649
 650 <p><pre>
 651     %extra_argument { MyStruct *pAbc }
 652 </pre></p>
 653
 654 <p>Then the Parse() function generated will have an 4th parameter
 655 of type "MyStruct*" and all action routines will have access to
 656 a variable named "pAbc" that is the value of the 4th parameter
 657 in the most recent call to Parse().</p>
 658
 659 <a name='pfallback'></a>
 660 <h4>The <tt>%fallback</tt> directive</h4>
 661
 662 <p>The %fallback directive specifies an alternative meaning for one
 663 or more tokens.  The alternative meaning is tried if the original token
 664 would have generated a syntax error.
 665
 666 <p>The %fallback directive was added to support robust parsing of SQL
 667 syntax in <a href="https://www.sqlite.org/">SQLite</a>.
 668 The SQL language contains a large assortment of keywords, each of which
 669 appears as a different token to the language parser.  SQL contains so
 670 many keywords, that it can be difficult for programmers to keep up with
 671 them all.  Programmers will, therefore, sometimes mistakenly use an
 672 obscure language keyword for an identifier.  The %fallback directive
 673 provides a mechanism to tell the parser:  "If you are unable to parse
 674 this keyword, try treating it as an identifier instead."
 675
 676 <p>The syntax of %fallback is as follows:
 677
 678 <blockquote>
 679 <tt>%fallback</tt>  <i>ID</i> <i>TOKEN...</i> <b>.</b>
 680 </blockquote>
 681
 682 <p>In words, the %fallback directive is followed by a list of token names
 683 terminated by a period.  The first token name is the fallback token - the
 684 token to which all the other tokens fall back to.  The second and subsequent
 685 arguments are tokens which fall back to the token identified by the first
 686 argument.
 687
 688 <a name='pifdef'></a>
 689 <h4>The <tt>%ifdef</tt>, <tt>%ifndef</tt>, and <tt>%endif</tt> directives.</h4>
 690
 691 <p>The %ifdef, %ifndef, and %endif directives are similar to
 692 #ifdef, #ifndef, and #endif in the C-preprocessor, just not as general.
 693 Each of these directives must begin at the left margin.  No whitespace
 694 is allowed between the "%" and the directive name.
 695
 696 <p>Grammar text in between "%ifdef MACRO" and the next nested "%endif" is
 697 ignored unless the "-DMACRO" command-line option is used.  Grammar text
 698 betwen "%ifndef MACRO" and the next nested "%endif" is included except when
 699 the "-DMACRO" command-line option is used.
 700
 701 <p>Note that the argument to %ifdef and %ifndef must be a single
 702 preprocessor symbol name, not a general expression.  There is no "%else"
 703 directive.
 704
 705
 706 <a name='pinclude'></a>
 707 <h4>The <tt>%include</tt> directive</h4>
 708
 709 <p>The %include directive specifies C code that is included at the
 710 top of the generated parser.  You can include any text you want --
 711 the Lemon parser generator copies it blindly.  If you have multiple
 712 %include directives in your grammar file, their values are concatenated
 713 so that all %include code ultimately appears near the top of the
 714 generated parser, in the same order as it appeared in the grammer.</p>
 715
 716 <p>The %include directive is very handy for getting some extra #include
 717 preprocessor statements at the beginning of the generated parser.
 718 For example:</p>
 719
 720 <p><pre>
 721    %include {#include &lt;unistd.h&gt;}
 722 </pre></p>
 723
 724 <p>This might be needed, for example, if some of the C actions in the
 725 grammar call functions that are prototyed in unistd.h.</p>
 726
 727 <a name='pleft'></a>
 728 <h4>The <tt>%left</tt> directive</h4>
 729
 730 The %left directive is used (along with the <a href='#pright'>%right</a> and
 731 <a href='#pnonassoc'>%nonassoc</a> directives) to declare precedences of
 732 terminal symbols.  Every terminal symbol whose name appears after
 733 a %left directive but before the next period (".") is
 734 given the same left-associative precedence value.  Subsequent
 735 %left directives have higher precedence.  For example:</p>
 736
 737 <p><pre>
 738    %left AND.
 739    %left OR.
 740    %nonassoc EQ NE GT GE LT LE.
 741    %left PLUS MINUS.
 742    %left TIMES DIVIDE MOD.
 743    %right EXP NOT.
 744 </pre></p>
 745
 746 <p>Note the period that terminates each %left, %right or %nonassoc
 747 directive.</p>
 748
 749 <p>LALR(1) grammars can get into a situation where they require
 750 a large amount of stack space if you make heavy use or right-associative
 751 operators.  For this reason, it is recommended that you use %left
 752 rather than %right whenever possible.</p>
 753
 754 <a name='pname'></a>
 755 <h4>The <tt>%name</tt> directive</h4>
 756
 757 <p>By default, the functions generated by Lemon all begin with the
 758 five-character string "Parse".  You can change this string to something
 759 different using the %name directive.  For instance:</p>
 760
 761 <p><pre>
 762    %name Abcde
 763 </pre></p>
 764
 765 <p>Putting this directive in the grammar file will cause Lemon to generate
 766 functions named
 767 <ul>
 768 <li> AbcdeAlloc(),
 769 <li> AbcdeFree(),
 770 <li> AbcdeTrace(), and
 771 <li> Abcde().
 772 </ul>
 773 The %name directive allows you to generator two or more different
 774 parsers and link them all into the same executable.
 775 </p>
 776
 777 <a name='pnonassoc'></a>
 778 <h4>The <tt>%nonassoc</tt> directive</h4>
 779
 780 <p>This directive is used to assign non-associative precedence to
 781 one or more terminal symbols.  See the section on
 782 <a href='#precrules'>precedence rules</a>
 783 or on the <a href='#pleft'>%left</a> directive for additional information.</p>
 784
 785 <a name='parse_accept'></a>
 786 <h4>The <tt>%parse_accept</tt> directive</h4>
 787
 788 <p>The %parse_accept directive specifies a block of C code that is
 789 executed whenever the parser accepts its input string.  To "accept"
 790 an input string means that the parser was able to process all tokens
 791 without error.</p>
 792
 793 <p>For example:</p>
 794
 795 <p><pre>
 796    %parse_accept {
 797       printf("parsing complete!\n");
 798    }
 799 </pre></p>
 800
 801 <a name='parse_failure'></a>
 802 <h4>The <tt>%parse_failure</tt> directive</h4>
 803
 804 <p>The %parse_failure directive specifies a block of C code that
 805 is executed whenever the parser fails complete.  This code is not
 806 executed until the parser has tried and failed to resolve an input
 807 error using is usual error recovery strategy.  The routine is
 808 only invoked when parsing is unable to continue.</p>
 809
 810 <p><pre>
 811    %parse_failure {
 812      fprintf(stderr,"Giving up.  Parser is hopelessly lost...\n");
 813    }
 814 </pre></p>
 815
 816 <a name='pright'></a>
 817 <h4>The <tt>%right</tt> directive</h4>
 818
 819 <p>This directive is used to assign right-associative precedence to
 820 one or more terminal symbols.  See the section on
 821 <a href='#precrules'>precedence rules</a>
 822 or on the <a href='#pleft'>%left</a> directive for additional information.</p>
 823
 824 <a name='stack_overflow'></a>
 825 <h4>The <tt>%stack_overflow</tt> directive</h4>
 826
 827 <p>The %stack_overflow directive specifies a block of C code that
 828 is executed if the parser's internal stack ever overflows.  Typically
 829 this just prints an error message.  After a stack overflow, the parser
 830 will be unable to continue and must be reset.</p>
 831
 832 <p><pre>
 833    %stack_overflow {
 834      fprintf(stderr,"Giving up.  Parser stack overflow\n");
 835    }
 836 </pre></p>
 837
 838 <p>You can help prevent parser stack overflows by avoiding the use
 839 of right recursion and right-precedence operators in your grammar.
 840 Use left recursion and and left-precedence operators instead, to
 841 encourage rules to reduce sooner and keep the stack size down.
 842 For example, do rules like this:
 843 <pre>
 844    list ::= list element.      // left-recursion.  Good!
 845    list ::= .
 846 </pre>
 847 Not like this:
 848 <pre>
 849    list ::= element list.      // right-recursion.  Bad!
 850    list ::= .
 851 </pre>
 852
 853 <a name='stack_size'></a>
 854 <h4>The <tt>%stack_size</tt> directive</h4>
 855
 856 <p>If stack overflow is a problem and you can't resolve the trouble
 857 by using left-recursion, then you might want to increase the size
 858 of the parser's stack using this directive.  Put an positive integer
 859 after the %stack_size directive and Lemon will generate a parse
 860 with a stack of the requested size.  The default value is 100.</p>
 861
 862 <p><pre>
 863    %stack_size 2000
 864 </pre></p>
 865
 866 <a name='start_symbol'></a>
 867 <h4>The <tt>%start_symbol</tt> directive</h4>
 868
 869 <p>By default, the start-symbol for the grammar that Lemon generates
 870 is the first non-terminal that appears in the grammar file.  But you
 871 can choose a different start-symbol using the %start_symbol directive.</p>
 872
 873 <p><pre>
 874    %start_symbol  prog
 875 </pre></p>
 876
 877 <a name='token_destructor'></a>
 878 <h4>The <tt>%token_destructor</tt> directive</h4>
 879
 880 <p>The %destructor directive assigns a destructor to a non-terminal
 881 symbol.  (See the description of the %destructor directive above.)
 882 This directive does the same thing for all terminal symbols.</p>
 883
 884 <p>Unlike non-terminal symbols which may each have a different data type
 885 for their values, terminals all use the same data type (defined by
 886 the %token_type directive) and so they use a common destructor.  Other
 887 than that, the token destructor works just like the non-terminal
 888 destructors.</p>
 889
 890 <a name='token_prefix'></a>
 891 <h4>The <tt>%token_prefix</tt> directive</h4>
 892
 893 <p>Lemon generates #defines that assign small integer constants
 894 to each terminal symbol in the grammar.  If desired, Lemon will
 895 add a prefix specified by this directive
 896 to each of the #defines it generates.
 897 So if the default output of Lemon looked like this:
 898 <pre>
 899     #define AND              1
 900     #define MINUS            2
 901     #define OR               3
 902     #define PLUS             4
 903 </pre>
 904 You can insert a statement into the grammar like this:
 905 <pre>
 906     %token_prefix    TOKEN_
 907 </pre>
 908 to cause Lemon to produce these symbols instead:
 909 <pre>
 910     #define TOKEN_AND        1
 911     #define TOKEN_MINUS      2
 912     #define TOKEN_OR         3
 913     #define TOKEN_PLUS       4
 914 </pre>
 915
 916 <a name='token_type'></a><a name='ptype'></a>
 917 <h4>The <tt>%token_type</tt> and <tt>%type</tt> directives</h4>
 918
 919 <p>These directives are used to specify the data types for values
 920 on the parser's stack associated with terminal and non-terminal
 921 symbols.  The values of all terminal symbols must be of the same
 922 type.  This turns out to be the same data type as the 3rd parameter
 923 to the Parse() function generated by Lemon.  Typically, you will
 924 make the value of a terminal symbol by a pointer to some kind of
 925 token structure.  Like this:</p>
 926
 927 <p><pre>
 928    %token_type    {Token*}
 929 </pre></p>
 930
 931 <p>If the data type of terminals is not specified, the default value
 932 is "void*".</p>
 933
 934 <p>Non-terminal symbols can each have their own data types.  Typically
 935 the data type  of a non-terminal is a pointer to the root of a parse-tree
 936 structure that contains all information about that non-terminal.
 937 For example:</p>
 938
 939 <p><pre>
 940    %type   expr  {Expr*}
 941 </pre></p>
 942
 943 <p>Each entry on the parser's stack is actually a union containing
 944 instances of all data types for every non-terminal and terminal symbol.
 945 Lemon will automatically use the correct element of this union depending
 946 on what the corresponding non-terminal or terminal symbol is.  But
 947 the grammar designer should keep in mind that the size of the union
 948 will be the size of its largest element.  So if you have a single
 949 non-terminal whose data type requires 1K of storage, then your 100
 950 entry parser stack will require 100K of heap space.  If you are willing
 951 and able to pay that price, fine.  You just need to know.</p>
 952
 953 <a name='pwildcard'></a>
 954 <h4>The <tt>%wildcard</tt> directive</h4>
 955
 956 <p>The %wildcard directive is followed by a single token name and a
 957 period.  This directive specifies that the identified token should
 958 match any input token.
 959
 960 <p>When the generated parser has the choice of matching an input against
 961 the wildcard token and some other token, the other token is always used.
 962 The wildcard token is only matched if there are no other alternatives.
 963
 964 <h3>Error Processing</h3>
 965
 966 <p>After extensive experimentation over several years, it has been
 967 discovered that the error recovery strategy used by yacc is about
 968 as good as it gets.  And so that is what Lemon uses.</p>
 969
 970 <p>When a Lemon-generated parser encounters a syntax error, it
 971 first invokes the code specified by the %syntax_error directive, if
 972 any.  It then enters its error recovery strategy.  The error recovery
 973 strategy is to begin popping the parsers stack until it enters a
 974 state where it is permitted to shift a special non-terminal symbol
 975 named "error".  It then shifts this non-terminal and continues
 976 parsing.  But the %syntax_error routine will not be called again
 977 until at least three new tokens have been successfully shifted.</p>
 978
 979 <p>If the parser pops its stack until the stack is empty, and it still
 980 is unable to shift the error symbol, then the %parse_failed routine
 981 is invoked and the parser resets itself to its start state, ready
 982 to begin parsing a new file.  This is what will happen at the very
 983 first syntax error, of course, if there are no instances of the
 984 "error" non-terminal in your grammar.</p>
 985
 986 </body>
 987 </html>