175897234Sdrh<html> 275897234Sdrh<head> 375897234Sdrh<title>The Lemon Parser Generator</title> 475897234Sdrh</head> 59a243e69Sdrh<body bgcolor='white'> 69a243e69Sdrh<h1 align='center'>The Lemon Parser Generator</h1> 775897234Sdrh 89bccde3dSdrh<p>Lemon is an LALR(1) parser generator for C. 99bccde3dSdrhIt does the same job as "bison" and "yacc". 109a243e69SdrhBut Lemon is not a bison or yacc clone. Lemon 1175897234Sdrhuses a different grammar syntax which is designed to 129bccde3dSdrhreduce the number of coding errors. Lemon also uses a 139bccde3dSdrhparsing engine that is faster than yacc and 149bccde3dSdrhbison and which is both reentrant and threadsafe. 159bccde3dSdrh(Update: Since the previous sentence was written, bison 169bccde3dSdrhhas also been updated so that it too can generate a 179bccde3dSdrhreentrant and threadsafe parser.) 189bccde3dSdrhLemon also implements features that can be used 199a243e69Sdrhto eliminate resource leaks, making it suitable for use 2075897234Sdrhin long-running programs such as graphical user interfaces 2175897234Sdrhor embedded controllers.</p> 2275897234Sdrh 2375897234Sdrh<p>This document is an introduction to the Lemon 2475897234Sdrhparser generator.</p> 2575897234Sdrh 26c5e56b34Sdrh<h2>Security Note</h2> 27c5e56b34Sdrh 28c5e56b34Sdrh<p>The language parser code created by Lemon is very robust and 29c5e56b34Sdrhis well-suited for use in internet-facing applications that need to 30c5e56b34Sdrhsafely process maliciously crafted inputs. 31c5e56b34Sdrh 32c5e56b34Sdrh<p>The "lemon.exe" command-line tool itself works great when given a valid 33c5e56b34Sdrhinput grammar file and almost always gives helpful 34c5e56b34Sdrherror messages for malformed inputs. However, it is possible for 35c5e56b34Sdrha malicious user to craft a grammar file that will cause 36c5e56b34Sdrhlemon.exe to crash. 37c5e56b34SdrhWe do not see this as a problem, as lemon.exe is not intended to be used 38c5e56b34Sdrhwith hostile inputs. 39c5e56b34SdrhTo summarize:</p> 40c5e56b34Sdrh 41c5e56b34Sdrh<ul> 42c5e56b34Sdrh<li>Parser code generated by lemon → Robust and secure 43c5e56b34Sdrh<li>The "lemon.exe" command line tool itself → Not so much 44c5e56b34Sdrh</ul> 45c5e56b34Sdrh 4675897234Sdrh<h2>Theory of Operation</h2> 4775897234Sdrh 4875897234Sdrh<p>The main goal of Lemon is to translate a context free grammar (CFG) 4975897234Sdrhfor a particular language into C code that implements a parser for 5075897234Sdrhthat language. 5175897234SdrhThe program has two inputs: 5275897234Sdrh<ul> 5375897234Sdrh<li>The grammar specification. 5475897234Sdrh<li>A parser template file. 5575897234Sdrh</ul> 5675897234SdrhTypically, only the grammar specification is supplied by the programmer. 5775897234SdrhLemon comes with a default parser template which works fine for most 5875897234Sdrhapplications. But the user is free to substitute a different parser 5975897234Sdrhtemplate if desired.</p> 6075897234Sdrh 619a243e69Sdrh<p>Depending on command-line options, Lemon will generate up to 629a243e69Sdrhthree output files. 6375897234Sdrh<ul> 6475897234Sdrh<li>C code to implement the parser. 6575897234Sdrh<li>A header file defining an integer ID for each terminal symbol. 6675897234Sdrh<li>An information file that describes the states of the generated parser 6775897234Sdrh automaton. 6875897234Sdrh</ul> 6975897234SdrhBy default, all three of these output files are generated. 709bccde3dSdrhThe header file is suppressed if the "-m" command-line option is 719bccde3dSdrhused and the report file is omitted when "-q" is selected.</p> 7275897234Sdrh 739bccde3dSdrh<p>The grammar specification file uses a ".y" suffix, by convention. 7475897234SdrhIn the examples used in this document, we'll assume the name of the 759bccde3dSdrhgrammar file is "gram.y". A typical use of Lemon would be the 7675897234Sdrhfollowing command: 7775897234Sdrh<pre> 7875897234Sdrh lemon gram.y 7975897234Sdrh</pre> 809bccde3dSdrhThis command will generate three output files named "gram.c", 819bccde3dSdrh"gram.h" and "gram.out". 8275897234SdrhThe first is C code to implement the parser. The second 8375897234Sdrhis the header file that defines numerical values for all 8475897234Sdrhterminal symbols, and the last is the report that explains 8575897234Sdrhthe states used by the parser automaton.</p> 8675897234Sdrh 8775897234Sdrh<h3>Command Line Options</h3> 8875897234Sdrh 8975897234Sdrh<p>The behavior of Lemon can be modified using command-line options. 9075897234SdrhYou can obtain a list of the available command-line options together 9175897234Sdrhwith a brief explanation of what each does by typing 9275897234Sdrh<pre> 939a243e69Sdrh lemon "-?" 9475897234Sdrh</pre> 9575897234SdrhAs of this writing, the following command-line options are supported: 9675897234Sdrh<ul> 979bccde3dSdrh<li><b>-b</b> 989bccde3dSdrhShow only the basis for each parser state in the report file. 999bccde3dSdrh<li><b>-c</b> 1009a243e69SdrhDo not compress the generated action tables. The parser will be a 1019a243e69Sdrhlittle larger and slower, but it will detect syntax errors sooner. 102fb32c44eSdrh<li><b>-d</b><i>directory</i> 103fb32c44eSdrhWrite all output files into <i>directory</i>. Normally, output files 104fb32c44eSdrhare written into the directory that contains the input grammar file. 1059bccde3dSdrh<li><b>-D<i>name</i></b> 1069a243e69SdrhDefine C preprocessor macro <i>name</i>. This macro is usable by 107*5f0d37b5Sdrh"<tt><a href='#pifdef'>%ifdef</a></tt>", 108*5f0d37b5Sdrh"<tt><a href='#pifdef'>%ifndef</a></tt>", and 109*5f0d37b5Sdrh"<tt><a href="#pifdef">%if</a></tt> lines 1109a243e69Sdrhin the grammar file. 111*5f0d37b5Sdrh<li><b>-E</b> 112*5f0d37b5SdrhRun the "%if" preprocessor step only and print the revised grammar 113*5f0d37b5Sdrhfile. 1149bccde3dSdrh<li><b>-g</b> 1159bccde3dSdrhDo not generate a parser. Instead write the input grammar to standard 1169bccde3dSdrhoutput with all comments, actions, and other extraneous text removed. 1179bccde3dSdrh<li><b>-l</b> 118dfe4e6bbSdrhOmit "#line" directives in the generated parser C code. 1199bccde3dSdrh<li><b>-m</b> 1209bccde3dSdrhCause the output C source code to be compatible with the "makeheaders" 1219bccde3dSdrhprogram. 1229bccde3dSdrh<li><b>-p</b> 1239bccde3dSdrhDisplay all conflicts that are resolved by 1249bccde3dSdrh<a href='#precrules'>precedence rules</a>. 1259bccde3dSdrh<li><b>-q</b> 1269bccde3dSdrhSuppress generation of the report file. 1279bccde3dSdrh<li><b>-r</b> 1289bccde3dSdrhDo not sort or renumber the parser states as part of optimization. 1299bccde3dSdrh<li><b>-s</b> 130ed5e6688SdrhShow parser statistics before exiting. 1319bccde3dSdrh<li><b>-T<i>file</i></b> 1329bccde3dSdrhUse <i>file</i> as the template for the generated C-code parser implementation. 1339bccde3dSdrh<li><b>-x</b> 1349bccde3dSdrhPrint the Lemon version number. 13575897234Sdrh</ul> 13675897234Sdrh 13775897234Sdrh<h3>The Parser Interface</h3> 13875897234Sdrh 13975897234Sdrh<p>Lemon doesn't generate a complete, working program. It only generates 14075897234Sdrha few subroutines that implement a parser. This section describes 14175897234Sdrhthe interface to those subroutines. It is up to the programmer to 14275897234Sdrhcall these subroutines in an appropriate way in order to produce a 14375897234Sdrhcomplete system.</p> 14475897234Sdrh 14575897234Sdrh<p>Before a program begins using a Lemon-generated parser, the program 14675897234Sdrhmust first create the parser. 14775897234SdrhA new parser is created as follows: 14875897234Sdrh<pre> 14975897234Sdrh void *pParser = ParseAlloc( malloc ); 15075897234Sdrh</pre> 15175897234SdrhThe ParseAlloc() routine allocates and initializes a new parser and 15275897234Sdrhreturns a pointer to it. 1539bccde3dSdrhThe actual data structure used to represent a parser is opaque — 15475897234Sdrhits internal structure is not visible or usable by the calling routine. 15575897234SdrhFor this reason, the ParseAlloc() routine returns a pointer to void 15675897234Sdrhrather than a pointer to some particular structure. 15775897234SdrhThe sole argument to the ParseAlloc() routine is a pointer to the 1589bccde3dSdrhsubroutine used to allocate memory. Typically this means malloc().</p> 15975897234Sdrh 16075897234Sdrh<p>After a program is finished using a parser, it can reclaim all 16175897234Sdrhmemory allocated by that parser by calling 16275897234Sdrh<pre> 16375897234Sdrh ParseFree(pParser, free); 16475897234Sdrh</pre> 16575897234SdrhThe first argument is the same pointer returned by ParseAlloc(). The 16675897234Sdrhsecond argument is a pointer to the function used to release bulk 16775897234Sdrhmemory back to the system.</p> 16875897234Sdrh 16975897234Sdrh<p>After a parser has been allocated using ParseAlloc(), the programmer 17075897234Sdrhmust supply the parser with a sequence of tokens (terminal symbols) to 17175897234Sdrhbe parsed. This is accomplished by calling the following function 17275897234Sdrhonce for each token: 17375897234Sdrh<pre> 17475897234Sdrh Parse(pParser, hTokenID, sTokenData, pArg); 17575897234Sdrh</pre> 17675897234SdrhThe first argument to the Parse() routine is the pointer returned by 17775897234SdrhParseAlloc(). 1789a243e69SdrhThe second argument is a small positive integer that tells the parser the 17975897234Sdrhtype of the next token in the data stream. 18075897234SdrhThere is one token type for each terminal symbol in the grammar. 18175897234SdrhThe gram.h file generated by Lemon contains #define statements that 18275897234Sdrhmap symbolic terminal symbol names into appropriate integer values. 1839bccde3dSdrhA value of 0 for the second argument is a special flag to the 1849bccde3dSdrhparser to indicate that the end of input has been reached. 18575897234SdrhThe third argument is the value of the given token. By default, 1869a243e69Sdrhthe type of the third argument is "void*", but the grammar will 18775897234Sdrhusually redefine this type to be some kind of structure. 18875897234SdrhTypically the second argument will be a broad category of tokens 1899bccde3dSdrhsuch as "identifier" or "number" and the third argument will 19075897234Sdrhbe the name of the identifier or the value of the number.</p> 19175897234Sdrh 19275897234Sdrh<p>The Parse() function may have either three or four arguments, 19345f31be8Sdrhdepending on the grammar. If the grammar specification file requests 1949a243e69Sdrhit (via the <tt><a href='#extraarg'>%extra_argument</a></tt> directive), 19545f31be8Sdrhthe Parse() function will have a fourth parameter that can be 19675897234Sdrhof any type chosen by the programmer. The parser doesn't do anything 19775897234Sdrhwith this argument except to pass it through to action routines. 19875897234SdrhThis is a convenient mechanism for passing state information down 19975897234Sdrhto the action routines without having to use global variables.</p> 20075897234Sdrh 20175897234Sdrh<p>A typical use of a Lemon parser might look something like the 20275897234Sdrhfollowing: 20375897234Sdrh<pre> 2049a243e69Sdrh 1 ParseTree *ParseFile(const char *zFilename){ 2059a243e69Sdrh 2 Tokenizer *pTokenizer; 2069a243e69Sdrh 3 void *pParser; 2079a243e69Sdrh 4 Token sToken; 2089a243e69Sdrh 5 int hTokenId; 2099a243e69Sdrh 6 ParserState sState; 2109a243e69Sdrh 7 2119a243e69Sdrh 8 pTokenizer = TokenizerCreate(zFilename); 2129a243e69Sdrh 9 pParser = ParseAlloc( malloc ); 2139a243e69Sdrh 10 InitParserState(&sState); 2149a243e69Sdrh 11 while( GetNextToken(pTokenizer, &hTokenId, &sToken) ){ 2159a243e69Sdrh 12 Parse(pParser, hTokenId, sToken, &sState); 21675897234Sdrh 13 } 2179a243e69Sdrh 14 Parse(pParser, 0, sToken, &sState); 21875897234Sdrh 15 ParseFree(pParser, free ); 21975897234Sdrh 16 TokenizerFree(pTokenizer); 22075897234Sdrh 17 return sState.treeRoot; 22175897234Sdrh 18 } 22275897234Sdrh</pre> 22375897234SdrhThis example shows a user-written routine that parses a file of 22475897234Sdrhtext and returns a pointer to the parse tree. 2259bccde3dSdrh(All error-handling code is omitted from this example to keep it 22675897234Sdrhsimple.) 22775897234SdrhWe assume the existence of some kind of tokenizer which is created 22875897234Sdrhusing TokenizerCreate() on line 8 and deleted by TokenizerFree() 22975897234Sdrhon line 16. The GetNextToken() function on line 11 retrieves the 23075897234Sdrhnext token from the input file and puts its type in the 23175897234Sdrhinteger variable hTokenId. The sToken variable is assumed to be 23275897234Sdrhsome kind of structure that contains details about each token, 23375897234Sdrhsuch as its complete text, what line it occurs on, etc.</p> 23475897234Sdrh 23575897234Sdrh<p>This example also assumes the existence of structure of type 23675897234SdrhParserState that holds state information about a particular parse. 23775897234SdrhAn instance of such a structure is created on line 6 and initialized 23875897234Sdrhon line 10. A pointer to this structure is passed into the Parse() 23975897234Sdrhroutine as the optional 4th argument. 24075897234SdrhThe action routine specified by the grammar for the parser can use 24175897234Sdrhthe ParserState structure to hold whatever information is useful and 24275897234Sdrhappropriate. In the example, we note that the treeRoot field of 24375897234Sdrhthe ParserState structure is left pointing to the root of the parse 24475897234Sdrhtree.</p> 24575897234Sdrh 24675897234Sdrh<p>The core of this example as it relates to Lemon is as follows: 24775897234Sdrh<pre> 24875897234Sdrh ParseFile(){ 24975897234Sdrh pParser = ParseAlloc( malloc ); 2509a243e69Sdrh while( GetNextToken(pTokenizer,&hTokenId, &sToken) ){ 25175897234Sdrh Parse(pParser, hTokenId, sToken); 25275897234Sdrh } 25375897234Sdrh Parse(pParser, 0, sToken); 25475897234Sdrh ParseFree(pParser, free ); 25575897234Sdrh } 25675897234Sdrh</pre> 25775897234SdrhBasically, what a program has to do to use a Lemon-generated parser 25875897234Sdrhis first create the parser, then send it lots of tokens obtained by 25975897234Sdrhtokenizing an input source. When the end of input is reached, the 26075897234SdrhParse() routine should be called one last time with a token type 26175897234Sdrhof 0. This step is necessary to inform the parser that the end of 26275897234Sdrhinput has been reached. Finally, we reclaim memory used by the 26375897234Sdrhparser by calling ParseFree().</p> 26475897234Sdrh 26575897234Sdrh<p>There is one other interface routine that should be mentioned 26675897234Sdrhbefore we move on. 26775897234SdrhThe ParseTrace() function can be used to generate debugging output 26875897234Sdrhfrom the parser. A prototype for this routine is as follows: 26975897234Sdrh<pre> 27075897234Sdrh ParseTrace(FILE *stream, char *zPrefix); 27175897234Sdrh</pre> 27275897234SdrhAfter this routine is called, a short (one-line) message is written 27375897234Sdrhto the designated output stream every time the parser changes states 27475897234Sdrhor calls an action routine. Each such message is prefaced using 27575897234Sdrhthe text given by zPrefix. This debugging output can be turned off 27675897234Sdrhby calling ParseTrace() again with a first argument of NULL (0).</p> 27775897234Sdrh 27875897234Sdrh<h3>Differences With YACC and BISON</h3> 27975897234Sdrh 28075897234Sdrh<p>Programmers who have previously used the yacc or bison parser 28175897234Sdrhgenerator will notice several important differences between yacc and/or 28275897234Sdrhbison and Lemon. 28375897234Sdrh<ul> 28475897234Sdrh<li>In yacc and bison, the parser calls the tokenizer. In Lemon, 28575897234Sdrh the tokenizer calls the parser. 28675897234Sdrh<li>Lemon uses no global variables. Yacc and bison use global variables 28775897234Sdrh to pass information between the tokenizer and parser. 28875897234Sdrh<li>Lemon allows multiple parsers to be running simultaneously. Yacc 28975897234Sdrh and bison do not. 29075897234Sdrh</ul> 29175897234SdrhThese differences may cause some initial confusion for programmers 29275897234Sdrhwith prior yacc and bison experience. 29375897234SdrhBut after years of experience using Lemon, I firmly 29475897234Sdrhbelieve that the Lemon way of doing things is better.</p> 29575897234Sdrh 29645f31be8Sdrh<p><i>Updated as of 2016-02-16:</i> 29745f31be8SdrhThe text above was written in the 1990s. 29845f31be8SdrhWe are told that Bison has lately been enhanced to support the 29945f31be8Sdrhtokenizer-calls-parser paradigm used by Lemon, and to obviate the 30045f31be8Sdrhneed for global variables.</p> 30145f31be8Sdrh 30275897234Sdrh<h2>Input File Syntax</h2> 30375897234Sdrh 30475897234Sdrh<p>The main purpose of the grammar specification file for Lemon is 30575897234Sdrhto define the grammar for the parser. But the input file also 30675897234Sdrhspecifies additional information Lemon requires to do its job. 30775897234SdrhMost of the work in using Lemon is in writing an appropriate 30875897234Sdrhgrammar file.</p> 30975897234Sdrh 3109a243e69Sdrh<p>The grammar file for Lemon is, for the most part, free format. 31175897234SdrhIt does not have sections or divisions like yacc or bison. Any 31275897234Sdrhdeclaration can occur at any point in the file. 31375897234SdrhLemon ignores whitespace (except where it is needed to separate 3149a243e69Sdrhtokens), and it honors the same commenting conventions as C and C++.</p> 31575897234Sdrh 31675897234Sdrh<h3>Terminals and Nonterminals</h3> 31775897234Sdrh 31875897234Sdrh<p>A terminal symbol (token) is any string of alphanumeric 3199bccde3dSdrhand/or underscore characters 32075897234Sdrhthat begins with an uppercase letter. 321c8eee5e5SdrhA terminal can contain lowercase letters after the first character, 32275897234Sdrhbut the usual convention is to make terminals all uppercase. 32375897234SdrhA nonterminal, on the other hand, is any string of alphanumeric 32475897234Sdrhand underscore characters than begins with a lowercase letter. 3259a243e69SdrhAgain, the usual convention is to make nonterminals use all lowercase 3269a243e69Sdrhletters.</p> 32775897234Sdrh 32875897234Sdrh<p>In Lemon, terminal and nonterminal symbols do not need to 32975897234Sdrhbe declared or identified in a separate section of the grammar file. 33075897234SdrhLemon is able to generate a list of all terminals and nonterminals 33175897234Sdrhby examining the grammar rules, and it can always distinguish a 33275897234Sdrhterminal from a nonterminal by checking the case of the first 33375897234Sdrhcharacter of the name.</p> 33475897234Sdrh 33575897234Sdrh<p>Yacc and bison allow terminal symbols to have either alphanumeric 33675897234Sdrhnames or to be individual characters included in single quotes, like 33775897234Sdrhthis: ')' or '$'. Lemon does not allow this alternative form for 33875897234Sdrhterminal symbols. With Lemon, all symbols, terminals and nonterminals, 33975897234Sdrhmust have alphanumeric names.</p> 34075897234Sdrh 34175897234Sdrh<h3>Grammar Rules</h3> 34275897234Sdrh 34375897234Sdrh<p>The main component of a Lemon grammar file is a sequence of grammar 34475897234Sdrhrules. 34575897234SdrhEach grammar rule consists of a nonterminal symbol followed by 3469bccde3dSdrhthe special symbol "::=" and then a list of terminals and/or nonterminals. 34775897234SdrhThe rule is terminated by a period. 34875897234SdrhThe list of terminals and nonterminals on the right-hand side of the 34975897234Sdrhrule can be empty. 35075897234SdrhRules can occur in any order, except that the left-hand side of the 35175897234Sdrhfirst rule is assumed to be the start symbol for the grammar (unless 3529a243e69Sdrhspecified otherwise using the <tt><a href='#start_symbol'>%start_symbol</a></tt> 3539a243e69Sdrhdirective described below.) 35475897234SdrhA typical sequence of grammar rules might look something like this: 35575897234Sdrh<pre> 35675897234Sdrh expr ::= expr PLUS expr. 35775897234Sdrh expr ::= expr TIMES expr. 35875897234Sdrh expr ::= LPAREN expr RPAREN. 35975897234Sdrh expr ::= VALUE. 36075897234Sdrh</pre> 36175897234Sdrh</p> 36275897234Sdrh 3639bccde3dSdrh<p>There is one non-terminal in this example, "expr", and five 3649bccde3dSdrhterminal symbols or tokens: "PLUS", "TIMES", "LPAREN", 3659bccde3dSdrh"RPAREN" and "VALUE".</p> 36675897234Sdrh 36775897234Sdrh<p>Like yacc and bison, Lemon allows the grammar to specify a block 36875897234Sdrhof C code that will be executed whenever a grammar rule is reduced 36975897234Sdrhby the parser. 37075897234SdrhIn Lemon, this action is specified by putting the C code (contained 37175897234Sdrhwithin curly braces <tt>{...}</tt>) immediately after the 37275897234Sdrhperiod that closes the rule. 37375897234SdrhFor example: 37475897234Sdrh<pre> 37575897234Sdrh expr ::= expr PLUS expr. { printf("Doing an addition...\n"); } 37675897234Sdrh</pre> 37775897234Sdrh</p> 37875897234Sdrh 37975897234Sdrh<p>In order to be useful, grammar actions must normally be linked to 38075897234Sdrhtheir associated grammar rules. 3819bccde3dSdrhIn yacc and bison, this is accomplished by embedding a "$$" in the 38275897234Sdrhaction to stand for the value of the left-hand side of the rule and 3839bccde3dSdrhsymbols "$1", "$2", and so forth to stand for the value of 38475897234Sdrhthe terminal or nonterminal at position 1, 2 and so forth on the 38575897234Sdrhright-hand side of the rule. 38675897234SdrhThis idea is very powerful, but it is also very error-prone. The 38775897234Sdrhsingle most common source of errors in a yacc or bison grammar is 38875897234Sdrhto miscount the number of symbols on the right-hand side of a grammar 3899bccde3dSdrhrule and say "$7" when you really mean "$8".</p> 39075897234Sdrh 39175897234Sdrh<p>Lemon avoids the need to count grammar symbols by assigning symbolic 39275897234Sdrhnames to each symbol in a grammar rule and then using those symbolic 39375897234Sdrhnames in the action. 39475897234SdrhIn yacc or bison, one would write this: 39575897234Sdrh<pre> 3969a243e69Sdrh expr -> expr PLUS expr { $$ = $1 + $3; }; 39775897234Sdrh</pre> 39875897234SdrhBut in Lemon, the same rule becomes the following: 39975897234Sdrh<pre> 40075897234Sdrh expr(A) ::= expr(B) PLUS expr(C). { A = B+C; } 40175897234Sdrh</pre> 40275897234SdrhIn the Lemon rule, any symbol in parentheses after a grammar rule 40375897234Sdrhsymbol becomes a place holder for that symbol in the grammar rule. 40475897234SdrhThis place holder can then be used in the associated C action to 40575897234Sdrhstand for the value of that symbol.<p> 40675897234Sdrh 40775897234Sdrh<p>The Lemon notation for linking a grammar rule with its reduce 40875897234Sdrhaction is superior to yacc/bison on several counts. 40975897234SdrhFirst, as mentioned above, the Lemon method avoids the need to 41075897234Sdrhcount grammar symbols. 41175897234SdrhSecondly, if a terminal or nonterminal in a Lemon grammar rule 41275897234Sdrhincludes a linking symbol in parentheses but that linking symbol 41375897234Sdrhis not actually used in the reduce action, then an error message 41475897234Sdrhis generated. 41575897234SdrhFor example, the rule 41675897234Sdrh<pre> 41775897234Sdrh expr(A) ::= expr(B) PLUS expr(C). { A = B; } 41875897234Sdrh</pre> 4199bccde3dSdrhwill generate an error because the linking symbol "C" is used 42075897234Sdrhin the grammar rule but not in the reduce action.</p> 42175897234Sdrh 42275897234Sdrh<p>The Lemon notation for linking grammar rules to reduce actions 42375897234Sdrhalso facilitates the use of destructors for reclaiming memory 42475897234Sdrhallocated by the values of terminals and nonterminals on the 42575897234Sdrhright-hand side of a rule.</p> 42675897234Sdrh 4279bccde3dSdrh<a name='precrules'></a> 42875897234Sdrh<h3>Precedence Rules</h3> 42975897234Sdrh 43075897234Sdrh<p>Lemon resolves parsing ambiguities in exactly the same way as 43175897234Sdrhyacc and bison. A shift-reduce conflict is resolved in favor 43275897234Sdrhof the shift, and a reduce-reduce conflict is resolved by reducing 43375897234Sdrhwhichever rule comes first in the grammar file.</p> 43475897234Sdrh 43575897234Sdrh<p>Just like in 43675897234Sdrhyacc and bison, Lemon allows a measure of control 4379a243e69Sdrhover the resolution of parsing conflicts using precedence rules. 43875897234SdrhA precedence value can be assigned to any terminal symbol 4399bccde3dSdrhusing the 4409a243e69Sdrh<tt><a href='#pleft'>%left</a></tt>, 4419a243e69Sdrh<tt><a href='#pright'>%right</a></tt> or 4429a243e69Sdrh<tt><a href='#pnonassoc'>%nonassoc</a></tt> directives. Terminal symbols 4439a243e69Sdrhmentioned in earlier directives have a lower precedence than 44475897234Sdrhterminal symbols mentioned in later directives. For example:</p> 44575897234Sdrh 44675897234Sdrh<p><pre> 44775897234Sdrh %left AND. 44875897234Sdrh %left OR. 44975897234Sdrh %nonassoc EQ NE GT GE LT LE. 45075897234Sdrh %left PLUS MINUS. 45175897234Sdrh %left TIMES DIVIDE MOD. 45275897234Sdrh %right EXP NOT. 45375897234Sdrh</pre></p> 45475897234Sdrh 45575897234Sdrh<p>In the preceding sequence of directives, the AND operator is 45675897234Sdrhdefined to have the lowest precedence. The OR operator is one 45775897234Sdrhprecedence level higher. And so forth. Hence, the grammar would 45875897234Sdrhattempt to group the ambiguous expression 45975897234Sdrh<pre> 46075897234Sdrh a AND b OR c 46175897234Sdrh</pre> 46275897234Sdrhlike this 46375897234Sdrh<pre> 46475897234Sdrh a AND (b OR c). 46575897234Sdrh</pre> 46675897234SdrhThe associativity (left, right or nonassoc) is used to determine 46775897234Sdrhthe grouping when the precedence is the same. AND is left-associative 46875897234Sdrhin our example, so 46975897234Sdrh<pre> 47075897234Sdrh a AND b AND c 47175897234Sdrh</pre> 47275897234Sdrhis parsed like this 47375897234Sdrh<pre> 47475897234Sdrh (a AND b) AND c. 47575897234Sdrh</pre> 47675897234SdrhThe EXP operator is right-associative, though, so 47775897234Sdrh<pre> 47875897234Sdrh a EXP b EXP c 47975897234Sdrh</pre> 48075897234Sdrhis parsed like this 48175897234Sdrh<pre> 48275897234Sdrh a EXP (b EXP c). 48375897234Sdrh</pre> 48475897234SdrhThe nonassoc precedence is used for non-associative operators. 48575897234SdrhSo 48675897234Sdrh<pre> 48775897234Sdrh a EQ b EQ c 48875897234Sdrh</pre> 48975897234Sdrhis an error.</p> 49075897234Sdrh 49175897234Sdrh<p>The precedence of non-terminals is transferred to rules as follows: 49275897234SdrhThe precedence of a grammar rule is equal to the precedence of the 49375897234Sdrhleft-most terminal symbol in the rule for which a precedence is 49475897234Sdrhdefined. This is normally what you want, but in those cases where 495ed5e6688Sdrhyou want the precedence of a grammar rule to be something different, 49675897234Sdrhyou can specify an alternative precedence symbol by putting the 49775897234Sdrhsymbol in square braces after the period at the end of the rule and 49875897234Sdrhbefore any C-code. For example:</p> 49975897234Sdrh 50075897234Sdrh<p><pre> 50175897234Sdrh expr = MINUS expr. [NOT] 50275897234Sdrh</pre></p> 50375897234Sdrh 50475897234Sdrh<p>This rule has a precedence equal to that of the NOT symbol, not the 50575897234SdrhMINUS symbol as would have been the case by default.</p> 50675897234Sdrh 50775897234Sdrh<p>With the knowledge of how precedence is assigned to terminal 50875897234Sdrhsymbols and individual 50975897234Sdrhgrammar rules, we can now explain precisely how parsing conflicts 51075897234Sdrhare resolved in Lemon. Shift-reduce conflicts are resolved 51175897234Sdrhas follows: 51275897234Sdrh<ul> 51375897234Sdrh<li> If either the token to be shifted or the rule to be reduced 51475897234Sdrh lacks precedence information, then resolve in favor of the 51575897234Sdrh shift, but report a parsing conflict. 51675897234Sdrh<li> If the precedence of the token to be shifted is greater than 51775897234Sdrh the precedence of the rule to reduce, then resolve in favor 51875897234Sdrh of the shift. No parsing conflict is reported. 5199a243e69Sdrh<li> If the precedence of the token to be shifted is less than the 52075897234Sdrh precedence of the rule to reduce, then resolve in favor of the 52175897234Sdrh reduce action. No parsing conflict is reported. 52275897234Sdrh<li> If the precedences are the same and the shift token is 52375897234Sdrh right-associative, then resolve in favor of the shift. 52475897234Sdrh No parsing conflict is reported. 5259a243e69Sdrh<li> If the precedences are the same and the shift token is 52675897234Sdrh left-associative, then resolve in favor of the reduce. 52775897234Sdrh No parsing conflict is reported. 5289a243e69Sdrh<li> Otherwise, resolve the conflict by doing the shift, and 5299a243e69Sdrh report a parsing conflict. 53075897234Sdrh</ul> 53175897234SdrhReduce-reduce conflicts are resolved this way: 53275897234Sdrh<ul> 53375897234Sdrh<li> If either reduce rule 53475897234Sdrh lacks precedence information, then resolve in favor of the 5359a243e69Sdrh rule that appears first in the grammar, and report a parsing 53675897234Sdrh conflict. 5379a243e69Sdrh<li> If both rules have precedence and the precedence is different, 53875897234Sdrh then resolve the dispute in favor of the rule with the highest 5399a243e69Sdrh precedence, and do not report a conflict. 54075897234Sdrh<li> Otherwise, resolve the conflict by reducing by the rule that 5419a243e69Sdrh appears first in the grammar, and report a parsing conflict. 54275897234Sdrh</ul> 54375897234Sdrh 54475897234Sdrh<h3>Special Directives</h3> 54575897234Sdrh 54675897234Sdrh<p>The input grammar to Lemon consists of grammar rules and special 54775897234Sdrhdirectives. We've described all the grammar rules, so now we'll 54875897234Sdrhtalk about the special directives.</p> 54975897234Sdrh 5509a243e69Sdrh<p>Directives in Lemon can occur in any order. You can put them before 5519a243e69Sdrhthe grammar rules, or after the grammar rules, or in the midst of the 55275897234Sdrhgrammar rules. It doesn't matter. The relative order of 55375897234Sdrhdirectives used to assign precedence to terminals is important, but 55475897234Sdrhother than that, the order of directives in Lemon is arbitrary.</p> 55575897234Sdrh 55675897234Sdrh<p>Lemon supports the following special directives: 55775897234Sdrh<ul> 5589a243e69Sdrh<li><tt><a href='#pcode'>%code</a></tt> 5599a243e69Sdrh<li><tt><a href='#default_destructor'>%default_destructor</a></tt> 5609a243e69Sdrh<li><tt><a href='#default_type'>%default_type</a></tt> 5619a243e69Sdrh<li><tt><a href='#destructor'>%destructor</a></tt> 562*5f0d37b5Sdrh<li><tt><a href='#pifdef'>%else</a></tt> 5639a243e69Sdrh<li><tt><a href='#pifdef'>%endif</a></tt> 5649a243e69Sdrh<li><tt><a href='#extraarg'>%extra_argument</a></tt> 5659a243e69Sdrh<li><tt><a href='#pfallback'>%fallback</a></tt> 566*5f0d37b5Sdrh<li><tt><a href='#pifdef'>%if</a></tt> 5679a243e69Sdrh<li><tt><a href='#pifdef'>%ifdef</a></tt> 5689a243e69Sdrh<li><tt><a href='#pifdef'>%ifndef</a></tt> 5699a243e69Sdrh<li><tt><a href='#pinclude'>%include</a></tt> 5709a243e69Sdrh<li><tt><a href='#pleft'>%left</a></tt> 5719a243e69Sdrh<li><tt><a href='#pname'>%name</a></tt> 5729a243e69Sdrh<li><tt><a href='#pnonassoc'>%nonassoc</a></tt> 5739a243e69Sdrh<li><tt><a href='#parse_accept'>%parse_accept</a></tt> 5749a243e69Sdrh<li><tt><a href='#parse_failure'>%parse_failure</a></tt> 5759a243e69Sdrh<li><tt><a href='#pright'>%right</a></tt> 5769a243e69Sdrh<li><tt><a href='#stack_overflow'>%stack_overflow</a></tt> 5779a243e69Sdrh<li><tt><a href='#stack_size'>%stack_size</a></tt> 5789a243e69Sdrh<li><tt><a href='#start_symbol'>%start_symbol</a></tt> 5799a243e69Sdrh<li><tt><a href='#syntax_error'>%syntax_error</a></tt> 5809a243e69Sdrh<li><tt><a href='#token_class'>%token_class</a></tt> 5819a243e69Sdrh<li><tt><a href='#token_destructor'>%token_destructor</a></tt> 5829a243e69Sdrh<li><tt><a href='#token_prefix'>%token_prefix</a></tt> 5839a243e69Sdrh<li><tt><a href='#token_type'>%token_type</a></tt> 5849a243e69Sdrh<li><tt><a href='#ptype'>%type</a></tt> 5859a243e69Sdrh<li><tt><a href='#pwildcard'>%wildcard</a></tt> 58675897234Sdrh</ul> 58775897234SdrhEach of these directives will be described separately in the 58875897234Sdrhfollowing sections:</p> 58975897234Sdrh 5909bccde3dSdrh<a name='pcode'></a> 591f2340fc7Sdrh<h4>The <tt>%code</tt> directive</h4> 592f2340fc7Sdrh 5939a243e69Sdrh<p>The <tt>%code</tt> directive is used to specify additional C code that 594f2340fc7Sdrhis added to the end of the main output file. This is similar to 5959a243e69Sdrhthe <tt><a href='#pinclude'>%include</a></tt> directive except that 5969a243e69Sdrh<tt>%include</tt> is inserted at the beginning of the main output file.</p> 597f2340fc7Sdrh 5989a243e69Sdrh<p><tt>%code</tt> is typically used to include some action routines or perhaps 5999bccde3dSdrha tokenizer or even the "main()" function 6009bccde3dSdrhas part of the output file.</p> 601f2340fc7Sdrh 6029bccde3dSdrh<a name='default_destructor'></a> 603f2340fc7Sdrh<h4>The <tt>%default_destructor</tt> directive</h4> 604f2340fc7Sdrh 6059a243e69Sdrh<p>The <tt>%default_destructor</tt> directive specifies a destructor to 606f2340fc7Sdrhuse for non-terminals that do not have their own destructor 6079a243e69Sdrhspecified by a separate <tt>%destructor</tt> directive. See the documentation 6089a243e69Sdrhon the <tt><a name='#destructor'>%destructor</a></tt> directive below for 6099bccde3dSdrhadditional information.</p> 610f2340fc7Sdrh 6119a243e69Sdrh<p>In some grammars, many different non-terminal symbols have the 612f2340fc7Sdrhsame data type and hence the same destructor. This directive is 6139a243e69Sdrha convenient way to specify the same destructor for all those 614f2340fc7Sdrhnon-terminals using a single statement.</p> 615f2340fc7Sdrh 6169bccde3dSdrh<a name='default_type'></a> 617f2340fc7Sdrh<h4>The <tt>%default_type</tt> directive</h4> 618f2340fc7Sdrh 6199a243e69Sdrh<p>The <tt>%default_type</tt> directive specifies the data type of non-terminal 6209a243e69Sdrhsymbols that do not have their own data type defined using a separate 6219a243e69Sdrh<tt><a href='#ptype'>%type</a></tt> directive.</p> 622f2340fc7Sdrh 6239bccde3dSdrh<a name='destructor'></a> 62475897234Sdrh<h4>The <tt>%destructor</tt> directive</h4> 62575897234Sdrh 6269a243e69Sdrh<p>The <tt>%destructor</tt> directive is used to specify a destructor for 62775897234Sdrha non-terminal symbol. 6289a243e69Sdrh(See also the <tt><a href='#token_destructor'>%token_destructor</a></tt> 6299bccde3dSdrhdirective which is used to specify a destructor for terminal symbols.)</p> 63075897234Sdrh 63175897234Sdrh<p>A non-terminal's destructor is called to dispose of the 63275897234Sdrhnon-terminal's value whenever the non-terminal is popped from 63375897234Sdrhthe stack. This includes all of the following circumstances: 63475897234Sdrh<ul> 63575897234Sdrh<li> When a rule reduces and the value of a non-terminal on 63675897234Sdrh the right-hand side is not linked to C code. 63775897234Sdrh<li> When the stack is popped during error processing. 63875897234Sdrh<li> When the ParseFree() function runs. 63975897234Sdrh</ul> 64075897234SdrhThe destructor can do whatever it wants with the value of 64175897234Sdrhthe non-terminal, but its design is to deallocate memory 64275897234Sdrhor other resources held by that non-terminal.</p> 64375897234Sdrh 64475897234Sdrh<p>Consider an example: 64575897234Sdrh<pre> 64675897234Sdrh %type nt {void*} 64775897234Sdrh %destructor nt { free($$); } 64875897234Sdrh nt(A) ::= ID NUM. { A = malloc( 100 ); } 64975897234Sdrh</pre> 6509a243e69SdrhThis example is a bit contrived, but it serves to illustrate how 65175897234Sdrhdestructors work. The example shows a non-terminal named 6529bccde3dSdrh"nt" that holds values of type "void*". When the rule for 6539bccde3dSdrhan "nt" reduces, it sets the value of the non-terminal to 65475897234Sdrhspace obtained from malloc(). Later, when the nt non-terminal 65575897234Sdrhis popped from the stack, the destructor will fire and call 65675897234Sdrhfree() on this malloced space, thus avoiding a memory leak. 6579bccde3dSdrh(Note that the symbol "$$" in the destructor code is replaced 65875897234Sdrhby the value of the non-terminal.)</p> 65975897234Sdrh 66075897234Sdrh<p>It is important to note that the value of a non-terminal is passed 66175897234Sdrhto the destructor whenever the non-terminal is removed from the 66275897234Sdrhstack, unless the non-terminal is used in a C-code action. If 66375897234Sdrhthe non-terminal is used by C-code, then it is assumed that the 6649bccde3dSdrhC-code will take care of destroying it. 6659bccde3dSdrhMore commonly, the value is used to build some 6669a243e69Sdrhlarger structure, and we don't want to destroy it, which is why 66775897234Sdrhthe destructor is not called in this circumstance.</p> 66875897234Sdrh 6699bccde3dSdrh<p>Destructors help avoid memory leaks by automatically freeing 6709bccde3dSdrhallocated objects when they go out of scope. 67175897234SdrhTo do the same using yacc or bison is much more difficult.</p> 67275897234Sdrh 6739a243e69Sdrh<a name='extraarg'></a> 67475897234Sdrh<h4>The <tt>%extra_argument</tt> directive</h4> 67575897234Sdrh 6769a243e69SdrhThe <tt>%extra_argument</tt> directive instructs Lemon to add a 4th parameter 67775897234Sdrhto the parameter list of the Parse() function it generates. Lemon 67875897234Sdrhdoesn't do anything itself with this extra argument, but it does 67975897234Sdrhmake the argument available to C-code action routines, destructors, 68075897234Sdrhand so forth. For example, if the grammar file contains:</p> 68175897234Sdrh 68275897234Sdrh<p><pre> 68375897234Sdrh %extra_argument { MyStruct *pAbc } 68475897234Sdrh</pre></p> 68575897234Sdrh 68675897234Sdrh<p>Then the Parse() function generated will have an 4th parameter 6879bccde3dSdrhof type "MyStruct*" and all action routines will have access to 6889bccde3dSdrha variable named "pAbc" that is the value of the 4th parameter 68975897234Sdrhin the most recent call to Parse().</p> 69075897234Sdrh 691fb32c44eSdrh<p>The <tt>%extra_context</tt> directive works the same except that it 692fb32c44eSdrhis passed in on the ParseAlloc() or ParseInit() routines instead of 693fb32c44eSdrhon Parse(). 694fb32c44eSdrh 695fb32c44eSdrh<a name='extractx'></a> 696fb32c44eSdrh<h4>The <tt>%extra_context</tt> directive</h4> 697fb32c44eSdrh 698ed5e6688SdrhThe <tt>%extra_context</tt> directive instructs Lemon to add a 2nd parameter 699fb32c44eSdrhto the parameter list of the ParseAlloc() and ParseInif() functions. Lemon 700fb32c44eSdrhdoesn't do anything itself with these extra argument, but it does 701fb32c44eSdrhstore the value make it available to C-code action routines, destructors, 702fb32c44eSdrhand so forth. For example, if the grammar file contains:</p> 703fb32c44eSdrh 704fb32c44eSdrh<p><pre> 705fb32c44eSdrh %extra_context { MyStruct *pAbc } 706fb32c44eSdrh</pre></p> 707fb32c44eSdrh 708ed5e6688Sdrh<p>Then the ParseAlloc() and ParseInit() functions will have an 2nd parameter 709fb32c44eSdrhof type "MyStruct*" and all action routines will have access to 710ed5e6688Sdrha variable named "pAbc" that is the value of that 2nd parameter.</p> 711fb32c44eSdrh 712fb32c44eSdrh<p>The <tt>%extra_argument</tt> directive works the same except that it 713fb32c44eSdrhis passed in on the Parse() routine instead of on ParseAlloc()/ParseInit(). 714fb32c44eSdrh 7159bccde3dSdrh<a name='pfallback'></a> 7169bccde3dSdrh<h4>The <tt>%fallback</tt> directive</h4> 7179bccde3dSdrh 7189a243e69Sdrh<p>The <tt>%fallback</tt> directive specifies an alternative meaning for one 7199bccde3dSdrhor more tokens. The alternative meaning is tried if the original token 7209a243e69Sdrhwould have generated a syntax error.</p> 7219bccde3dSdrh 7229a243e69Sdrh<p>The <tt>%fallback</tt> directive was added to support robust parsing of SQL 7239a243e69Sdrhsyntax in <a href='https://www.sqlite.org/'>SQLite</a>. 7249bccde3dSdrhThe SQL language contains a large assortment of keywords, each of which 7259bccde3dSdrhappears as a different token to the language parser. SQL contains so 7269a243e69Sdrhmany keywords that it can be difficult for programmers to keep up with 7279bccde3dSdrhthem all. Programmers will, therefore, sometimes mistakenly use an 7289a243e69Sdrhobscure language keyword for an identifier. The <tt>%fallback</tt> directive 7299bccde3dSdrhprovides a mechanism to tell the parser: "If you are unable to parse 7309a243e69Sdrhthis keyword, try treating it as an identifier instead."</p> 7319bccde3dSdrh 7329a243e69Sdrh<p>The syntax of <tt>%fallback</tt> is as follows: 7339bccde3dSdrh 7349bccde3dSdrh<blockquote> 7359bccde3dSdrh<tt>%fallback</tt> <i>ID</i> <i>TOKEN...</i> <b>.</b> 7369a243e69Sdrh</blockquote></p> 7379bccde3dSdrh 7389a243e69Sdrh<p>In words, the <tt>%fallback</tt> directive is followed by a list of token 7399a243e69Sdrhnames terminated by a period. 7409a243e69SdrhThe first token name is the fallback token — the 7419bccde3dSdrhtoken to which all the other tokens fall back to. The second and subsequent 7429bccde3dSdrharguments are tokens which fall back to the token identified by the first 7439a243e69Sdrhargument.</p> 7449bccde3dSdrh 7459bccde3dSdrh<a name='pifdef'></a> 746*5f0d37b5Sdrh<h4>The <tt>%if</tt> directive and its friends</h4> 7479bccde3dSdrh 748*5f0d37b5Sdrh<p>The <tt>%if</tt>, <tt>%ifdef</tt>, <tt>%ifndef</tt>, <tt>%else</tt>, 749*5f0d37b5Sdrhand <tt>%endif</tt> directives 750*5f0d37b5Sdrhare similar to #if, #ifdef, #ifndef, #else, and #endif in the C-preprocessor, 7519a243e69Sdrhjust not as general. 7529bccde3dSdrhEach of these directives must begin at the left margin. No whitespace 7539a243e69Sdrhis allowed between the "%" and the directive name.</p> 7549bccde3dSdrh 7559a243e69Sdrh<p>Grammar text in between "<tt>%ifdef MACRO</tt>" and the next nested 7569a243e69Sdrh"<tt>%endif</tt>" is 7579bccde3dSdrhignored unless the "-DMACRO" command-line option is used. Grammar text 7589a243e69Sdrhbetwen "<tt>%ifndef MACRO</tt>" and the next nested "<tt>%endif</tt>" is 759*5f0d37b5Sdrhincluded except when the "-DMACRO" command-line option is used.<p> 7609bccde3dSdrh 761*5f0d37b5Sdrh<p>The text in between "<tt>%if</tt> <i>CONDITIONAL</i>" and its 762*5f0d37b5Sdrhcorresponding <tt>%endif</tt> is included only if <i>CONDITIONAL</i> 763*5f0d37b5Sdrhis true. The CONDITION is one or more macro names, optionally connected 764*5f0d37b5Sdrhusing the "||" and "&&" binary operators, the "!" unary operator, 765*5f0d37b5Sdrhand grouped using balanced parentheses. Each term is true if the 766*5f0d37b5Sdrhcorresponding macro exists, and false if it does not exist.</p> 7679bccde3dSdrh 768*5f0d37b5Sdrh<p>An optional "<tt>%else</tt>" directive can occur anywhere in between a 769*5f0d37b5Sdrh<tt>%ifdef</tt>, <tt>%ifndef</tt>, or <tt>%if</tt> directive and 770*5f0d37b5Sdrhits corresponding <tt>%endif</tt>.</p> 771*5f0d37b5Sdrh 772*5f0d37b5Sdrh<p>Note that the argument to <tt>%ifdef</tt> and <tt>%ifndef</tt> is 773*5f0d37b5Sdrhintended to be a single preprocessor symbol name, not a general expression. 774*5f0d37b5SdrhUse the "<tt>%if</tt>" directive for general expressions.</p> 7759bccde3dSdrh 7769bccde3dSdrh<a name='pinclude'></a> 77775897234Sdrh<h4>The <tt>%include</tt> directive</h4> 77875897234Sdrh 7799a243e69Sdrh<p>The <tt>%include</tt> directive specifies C code that is included at the 7809a243e69Sdrhtop of the generated parser. You can include any text you want — 781f2340fc7Sdrhthe Lemon parser generator copies it blindly. If you have multiple 7829a243e69Sdrh<tt>%include</tt> directives in your grammar file, their values are concatenated 7839a243e69Sdrhso that all <tt>%include</tt> code ultimately appears near the top of the 7849a243e69Sdrhgenerated parser, in the same order as it appeared in the grammar.</p> 78575897234Sdrh 7869a243e69Sdrh<p>The <tt>%include</tt> directive is very handy for getting some extra #include 78775897234Sdrhpreprocessor statements at the beginning of the generated parser. 78875897234SdrhFor example:</p> 78975897234Sdrh 79075897234Sdrh<p><pre> 79175897234Sdrh %include {#include <unistd.h>} 79275897234Sdrh</pre></p> 79375897234Sdrh 79475897234Sdrh<p>This might be needed, for example, if some of the C actions in the 7959a243e69Sdrhgrammar call functions that are prototyped in unistd.h.</p> 79675897234Sdrh 79760ce5d31Sdrh<p>Use the <tt><a href="#pcode">%code</a></tt> directive to add code to 79860ce5d31Sdrhthe end of the generated parser.</p> 79960ce5d31Sdrh 8009bccde3dSdrh<a name='pleft'></a> 80175897234Sdrh<h4>The <tt>%left</tt> directive</h4> 80275897234Sdrh 8039a243e69SdrhThe <tt>%left</tt> directive is used (along with the 8049a243e69Sdrh<tt><a href='#pright'>%right</a></tt> and 8059a243e69Sdrh<tt><a href='#pnonassoc'>%nonassoc</a></tt> directives) to declare 8069a243e69Sdrhprecedences of terminal symbols. 8079a243e69SdrhEvery terminal symbol whose name appears after 8089a243e69Sdrha <tt>%left</tt> directive but before the next period (".") is 80975897234Sdrhgiven the same left-associative precedence value. Subsequent 8109a243e69Sdrh<tt>%left</tt> directives have higher precedence. For example:</p> 81175897234Sdrh 81275897234Sdrh<p><pre> 81375897234Sdrh %left AND. 81475897234Sdrh %left OR. 81575897234Sdrh %nonassoc EQ NE GT GE LT LE. 81675897234Sdrh %left PLUS MINUS. 81775897234Sdrh %left TIMES DIVIDE MOD. 81875897234Sdrh %right EXP NOT. 81975897234Sdrh</pre></p> 82075897234Sdrh 8219a243e69Sdrh<p>Note the period that terminates each <tt>%left</tt>, 8229a243e69Sdrh<tt>%right</tt> or <tt>%nonassoc</tt> 82375897234Sdrhdirective.</p> 82475897234Sdrh 82575897234Sdrh<p>LALR(1) grammars can get into a situation where they require 82675897234Sdrha large amount of stack space if you make heavy use or right-associative 8279a243e69Sdrhoperators. For this reason, it is recommended that you use <tt>%left</tt> 8289a243e69Sdrhrather than <tt>%right</tt> whenever possible.</p> 82975897234Sdrh 8309bccde3dSdrh<a name='pname'></a> 83175897234Sdrh<h4>The <tt>%name</tt> directive</h4> 83275897234Sdrh 83375897234Sdrh<p>By default, the functions generated by Lemon all begin with the 8349bccde3dSdrhfive-character string "Parse". You can change this string to something 8359a243e69Sdrhdifferent using the <tt>%name</tt> directive. For instance:</p> 83675897234Sdrh 83775897234Sdrh<p><pre> 83875897234Sdrh %name Abcde 83975897234Sdrh</pre></p> 84075897234Sdrh 84175897234Sdrh<p>Putting this directive in the grammar file will cause Lemon to generate 84275897234Sdrhfunctions named 84375897234Sdrh<ul> 84475897234Sdrh<li> AbcdeAlloc(), 84575897234Sdrh<li> AbcdeFree(), 84675897234Sdrh<li> AbcdeTrace(), and 84775897234Sdrh<li> Abcde(). 84875897234Sdrh</ul> 8499a243e69SdrhThe <tt>%name</tt> directive allows you to generate two or more different 8509a243e69Sdrhparsers and link them all into the same executable.</p> 85175897234Sdrh 8529bccde3dSdrh<a name='pnonassoc'></a> 85375897234Sdrh<h4>The <tt>%nonassoc</tt> directive</h4> 85475897234Sdrh 85575897234Sdrh<p>This directive is used to assign non-associative precedence to 8569bccde3dSdrhone or more terminal symbols. See the section on 8579bccde3dSdrh<a href='#precrules'>precedence rules</a> 8589a243e69Sdrhor on the <tt><a href='#pleft'>%left</a></tt> directive 8599a243e69Sdrhfor additional information.</p> 86075897234Sdrh 8619bccde3dSdrh<a name='parse_accept'></a> 86275897234Sdrh<h4>The <tt>%parse_accept</tt> directive</h4> 86375897234Sdrh 8649a243e69Sdrh<p>The <tt>%parse_accept</tt> directive specifies a block of C code that is 8659bccde3dSdrhexecuted whenever the parser accepts its input string. To "accept" 86675897234Sdrhan input string means that the parser was able to process all tokens 86775897234Sdrhwithout error.</p> 86875897234Sdrh 86975897234Sdrh<p>For example:</p> 87075897234Sdrh 87175897234Sdrh<p><pre> 87275897234Sdrh %parse_accept { 87375897234Sdrh printf("parsing complete!\n"); 87475897234Sdrh } 87575897234Sdrh</pre></p> 87675897234Sdrh 8779bccde3dSdrh<a name='parse_failure'></a> 87875897234Sdrh<h4>The <tt>%parse_failure</tt> directive</h4> 87975897234Sdrh 8809a243e69Sdrh<p>The <tt>%parse_failure</tt> directive specifies a block of C code that 88175897234Sdrhis executed whenever the parser fails complete. This code is not 88275897234Sdrhexecuted until the parser has tried and failed to resolve an input 88375897234Sdrherror using is usual error recovery strategy. The routine is 88475897234Sdrhonly invoked when parsing is unable to continue.</p> 88575897234Sdrh 88675897234Sdrh<p><pre> 88775897234Sdrh %parse_failure { 88875897234Sdrh fprintf(stderr,"Giving up. Parser is hopelessly lost...\n"); 88975897234Sdrh } 89075897234Sdrh</pre></p> 89175897234Sdrh 8929bccde3dSdrh<a name='pright'></a> 89375897234Sdrh<h4>The <tt>%right</tt> directive</h4> 89475897234Sdrh 89575897234Sdrh<p>This directive is used to assign right-associative precedence to 8969bccde3dSdrhone or more terminal symbols. See the section on 8979bccde3dSdrh<a href='#precrules'>precedence rules</a> 8989bccde3dSdrhor on the <a href='#pleft'>%left</a> directive for additional information.</p> 89975897234Sdrh 9009bccde3dSdrh<a name='stack_overflow'></a> 90175897234Sdrh<h4>The <tt>%stack_overflow</tt> directive</h4> 90275897234Sdrh 9039a243e69Sdrh<p>The <tt>%stack_overflow</tt> directive specifies a block of C code that 90475897234Sdrhis executed if the parser's internal stack ever overflows. Typically 90575897234Sdrhthis just prints an error message. After a stack overflow, the parser 90675897234Sdrhwill be unable to continue and must be reset.</p> 90775897234Sdrh 90875897234Sdrh<p><pre> 90975897234Sdrh %stack_overflow { 91075897234Sdrh fprintf(stderr,"Giving up. Parser stack overflow\n"); 91175897234Sdrh } 91275897234Sdrh</pre></p> 91375897234Sdrh 91475897234Sdrh<p>You can help prevent parser stack overflows by avoiding the use 91575897234Sdrhof right recursion and right-precedence operators in your grammar. 9169a243e69SdrhUse left recursion and and left-precedence operators instead to 91775897234Sdrhencourage rules to reduce sooner and keep the stack size down. 91875897234SdrhFor example, do rules like this: 91975897234Sdrh<pre> 92075897234Sdrh list ::= list element. // left-recursion. Good! 92175897234Sdrh list ::= . 92275897234Sdrh</pre> 92375897234SdrhNot like this: 92475897234Sdrh<pre> 92575897234Sdrh list ::= element list. // right-recursion. Bad! 92675897234Sdrh list ::= . 9279a243e69Sdrh</pre></p> 92875897234Sdrh 9299bccde3dSdrh<a name='stack_size'></a> 93075897234Sdrh<h4>The <tt>%stack_size</tt> directive</h4> 93175897234Sdrh 93275897234Sdrh<p>If stack overflow is a problem and you can't resolve the trouble 93375897234Sdrhby using left-recursion, then you might want to increase the size 93475897234Sdrhof the parser's stack using this directive. Put an positive integer 9359a243e69Sdrhafter the <tt>%stack_size</tt> directive and Lemon will generate a parse 93675897234Sdrhwith a stack of the requested size. The default value is 100.</p> 93775897234Sdrh 93875897234Sdrh<p><pre> 93975897234Sdrh %stack_size 2000 94075897234Sdrh</pre></p> 94175897234Sdrh 9429bccde3dSdrh<a name='start_symbol'></a> 94375897234Sdrh<h4>The <tt>%start_symbol</tt> directive</h4> 94475897234Sdrh 9459a243e69Sdrh<p>By default, the start symbol for the grammar that Lemon generates 94675897234Sdrhis the first non-terminal that appears in the grammar file. But you 9479a243e69Sdrhcan choose a different start symbol using the 9489a243e69Sdrh<tt>%start_symbol</tt> directive.</p> 94975897234Sdrh 95075897234Sdrh<p><pre> 95175897234Sdrh %start_symbol prog 95275897234Sdrh</pre></p> 95375897234Sdrh 9549a243e69Sdrh<a name='syntax_error'></a> 9559a243e69Sdrh<h4>The <tt>%syntax_error</tt> directive</h4> 9569a243e69Sdrh 9579a243e69Sdrh<p>See <a href='#error_processing'>Error Processing</a>.</p> 9589a243e69Sdrh 9599a243e69Sdrh<a name='token_class'></a> 9609a243e69Sdrh<h4>The <tt>%token_class</tt> directive</h4> 9619a243e69Sdrh 9629a243e69Sdrh<p>Undocumented. Appears to be related to the MULTITERMINAL concept. 9639a243e69Sdrh<a href='http://sqlite.org/src/fdiff?v1=796930d5fc2036c7&v2=624b24c5dc048e09&sbs=0'>Implementation</a>.</p> 9649a243e69Sdrh 9659bccde3dSdrh<a name='token_destructor'></a> 96675897234Sdrh<h4>The <tt>%token_destructor</tt> directive</h4> 96775897234Sdrh 9689a243e69Sdrh<p>The <tt>%destructor</tt> directive assigns a destructor to a non-terminal 9699a243e69Sdrhsymbol. (See the description of the 9709a243e69Sdrh<tt><a href='%destructor'>%destructor</a></tt> directive above.) 9719a243e69SdrhThe <tt>%token_destructor</tt> directive does the same thing 9729a243e69Sdrhfor all terminal symbols.</p> 97375897234Sdrh 97475897234Sdrh<p>Unlike non-terminal symbols which may each have a different data type 97575897234Sdrhfor their values, terminals all use the same data type (defined by 9769a243e69Sdrhthe <tt><a href='#token_type'>%token_type</a></tt> directive) 9779a243e69Sdrhand so they use a common destructor. 9789a243e69SdrhOther than that, the token destructor works just like the non-terminal 97975897234Sdrhdestructors.</p> 98075897234Sdrh 9819bccde3dSdrh<a name='token_prefix'></a> 98275897234Sdrh<h4>The <tt>%token_prefix</tt> directive</h4> 98375897234Sdrh 98475897234Sdrh<p>Lemon generates #defines that assign small integer constants 98575897234Sdrhto each terminal symbol in the grammar. If desired, Lemon will 98675897234Sdrhadd a prefix specified by this directive 9879a243e69Sdrhto each of the #defines it generates.</p> 9889a243e69Sdrh 9899a243e69Sdrh<p>So if the default output of Lemon looked like this: 99075897234Sdrh<pre> 99175897234Sdrh #define AND 1 99275897234Sdrh #define MINUS 2 99375897234Sdrh #define OR 3 99475897234Sdrh #define PLUS 4 99575897234Sdrh</pre> 99675897234SdrhYou can insert a statement into the grammar like this: 99775897234Sdrh<pre> 99875897234Sdrh %token_prefix TOKEN_ 99975897234Sdrh</pre> 100075897234Sdrhto cause Lemon to produce these symbols instead: 100175897234Sdrh<pre> 100275897234Sdrh #define TOKEN_AND 1 100375897234Sdrh #define TOKEN_MINUS 2 100475897234Sdrh #define TOKEN_OR 3 100575897234Sdrh #define TOKEN_PLUS 4 10069a243e69Sdrh</pre></p> 100775897234Sdrh 10089bccde3dSdrh<a name='token_type'></a><a name='ptype'></a> 100975897234Sdrh<h4>The <tt>%token_type</tt> and <tt>%type</tt> directives</h4> 101075897234Sdrh 101175897234Sdrh<p>These directives are used to specify the data types for values 101275897234Sdrhon the parser's stack associated with terminal and non-terminal 101375897234Sdrhsymbols. The values of all terminal symbols must be of the same 101475897234Sdrhtype. This turns out to be the same data type as the 3rd parameter 101575897234Sdrhto the Parse() function generated by Lemon. Typically, you will 1016ed5e6688Sdrhmake the value of a terminal symbol be a pointer to some kind of 101775897234Sdrhtoken structure. Like this:</p> 101875897234Sdrh 101975897234Sdrh<p><pre> 102075897234Sdrh %token_type {Token*} 102175897234Sdrh</pre></p> 102275897234Sdrh 102375897234Sdrh<p>If the data type of terminals is not specified, the default value 1024dfe4e6bbSdrhis "void*".</p> 102575897234Sdrh 102675897234Sdrh<p>Non-terminal symbols can each have their own data types. Typically 10279a243e69Sdrhthe data type of a non-terminal is a pointer to the root of a parse tree 102875897234Sdrhstructure that contains all information about that non-terminal. 102975897234SdrhFor example:</p> 103075897234Sdrh 103175897234Sdrh<p><pre> 103275897234Sdrh %type expr {Expr*} 103375897234Sdrh</pre></p> 103475897234Sdrh 103575897234Sdrh<p>Each entry on the parser's stack is actually a union containing 103675897234Sdrhinstances of all data types for every non-terminal and terminal symbol. 103775897234SdrhLemon will automatically use the correct element of this union depending 103875897234Sdrhon what the corresponding non-terminal or terminal symbol is. But 103975897234Sdrhthe grammar designer should keep in mind that the size of the union 104075897234Sdrhwill be the size of its largest element. So if you have a single 104175897234Sdrhnon-terminal whose data type requires 1K of storage, then your 100 104275897234Sdrhentry parser stack will require 100K of heap space. If you are willing 104375897234Sdrhand able to pay that price, fine. You just need to know.</p> 104475897234Sdrh 10459bccde3dSdrh<a name='pwildcard'></a> 10469bccde3dSdrh<h4>The <tt>%wildcard</tt> directive</h4> 10479bccde3dSdrh 10489a243e69Sdrh<p>The <tt>%wildcard</tt> directive is followed by a single token name and a 10499bccde3dSdrhperiod. This directive specifies that the identified token should 10509a243e69Sdrhmatch any input token.</p> 10519bccde3dSdrh 10529bccde3dSdrh<p>When the generated parser has the choice of matching an input against 10539bccde3dSdrhthe wildcard token and some other token, the other token is always used. 10549a243e69SdrhThe wildcard token is only matched if there are no alternatives.</p> 10559bccde3dSdrh 10569a243e69Sdrh<a name='error_processing'></a> 105775897234Sdrh<h3>Error Processing</h3> 105875897234Sdrh 105975897234Sdrh<p>After extensive experimentation over several years, it has been 106075897234Sdrhdiscovered that the error recovery strategy used by yacc is about 106175897234Sdrhas good as it gets. And so that is what Lemon uses.</p> 106275897234Sdrh 106375897234Sdrh<p>When a Lemon-generated parser encounters a syntax error, it 10649a243e69Sdrhfirst invokes the code specified by the <tt>%syntax_error</tt> directive, if 106575897234Sdrhany. It then enters its error recovery strategy. The error recovery 106675897234Sdrhstrategy is to begin popping the parsers stack until it enters a 106775897234Sdrhstate where it is permitted to shift a special non-terminal symbol 10689bccde3dSdrhnamed "error". It then shifts this non-terminal and continues 10699a243e69Sdrhparsing. The <tt>%syntax_error</tt> routine will not be called again 107075897234Sdrhuntil at least three new tokens have been successfully shifted.</p> 107175897234Sdrh 107275897234Sdrh<p>If the parser pops its stack until the stack is empty, and it still 10739a243e69Sdrhis unable to shift the error symbol, then the 10749a243e69Sdrh<tt><a href='#parse_failure'>%parse_failure</a></tt> routine 107575897234Sdrhis invoked and the parser resets itself to its start state, ready 107675897234Sdrhto begin parsing a new file. This is what will happen at the very 107775897234Sdrhfirst syntax error, of course, if there are no instances of the 10789bccde3dSdrh"error" non-terminal in your grammar.</p> 107975897234Sdrh 108075897234Sdrh</body> 108175897234Sdrh</html> 1082