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