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