2011-05-06 02:37:34 +00:00
|
|
|
<html>
|
|
|
|
|
<head>
|
|
|
|
|
<title>The Lemon Parser Generator</title>
|
|
|
|
|
</head>
|
2021-02-10 16:31:51 +00:00
|
|
|
<body>
|
|
|
|
|
<a id="main"></a>
|
2018-09-18 16:31:37 +00:00
|
|
|
<h1 align='center'>The Lemon Parser Generator</h1>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2016-12-05 20:29:15 +00:00
|
|
|
<p>Lemon is an LALR(1) parser generator for C.
|
|
|
|
|
It does the same job as "bison" and "yacc".
|
2018-09-18 16:31:37 +00:00
|
|
|
But Lemon is not a bison or yacc clone. Lemon
|
2011-05-06 02:37:34 +00:00
|
|
|
uses a different grammar syntax which is designed to
|
2016-12-05 20:29:15 +00:00
|
|
|
reduce the number of coding errors. Lemon also uses a
|
|
|
|
|
parsing engine that is faster than yacc and
|
|
|
|
|
bison and which is both reentrant and threadsafe.
|
|
|
|
|
(Update: Since the previous sentence was written, bison
|
|
|
|
|
has also been updated so that it too can generate a
|
|
|
|
|
reentrant and threadsafe parser.)
|
|
|
|
|
Lemon also implements features that can be used
|
2018-09-18 16:31:37 +00:00
|
|
|
to eliminate resource leaks, making it suitable for use
|
2011-05-06 02:37:34 +00:00
|
|
|
in long-running programs such as graphical user interfaces
|
|
|
|
|
or embedded controllers.</p>
|
|
|
|
|
|
|
|
|
|
<p>This document is an introduction to the Lemon
|
|
|
|
|
parser generator.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id="toc"></a>
|
|
|
|
|
<h2>1.0 Table of Contents</h2>
|
|
|
|
|
<ul>
|
|
|
|
|
<li><a href="#main">Introduction</a>
|
|
|
|
|
<li><a href="#toc">1.0 Table of Contents</a>
|
|
|
|
|
<li><a href="#secnot">2.0 Security Notes</a><br>
|
|
|
|
|
<li><a href="#optheory">3.0 Theory of Operation</a>
|
|
|
|
|
<ul>
|
|
|
|
|
<li><a href="#options">3.1 Command Line Options</a>
|
|
|
|
|
<li><a href="#interface">3.2 The Parser Interface</a>
|
|
|
|
|
<ul>
|
|
|
|
|
<li><a href="#onstack">3.2.1 Allocating The Parse Object On Stack</a>
|
|
|
|
|
<li><a href="#ifsum">3.2.2 Interface Summary</a>
|
|
|
|
|
</ul>
|
|
|
|
|
<li><a href="#yaccdiff">3.3 Differences With YACC and BISON</a>
|
|
|
|
|
<li><a href="#build">3.4 Building The "lemon" Or "lemon.exe" Executable</a>
|
|
|
|
|
</ul>
|
|
|
|
|
<li><a href="#syntax">4.0 Input File Syntax</a>
|
|
|
|
|
<ul>
|
|
|
|
|
<li><a href="#tnt">4.1 Terminals and Nonterminals</a>
|
|
|
|
|
<li><a href="#rules">4.2 Grammar Rules</a>
|
|
|
|
|
<li><a href="#precrules">4.3 Precedence Rules</a>
|
|
|
|
|
<li><a href="#special">4.4 Special Directives</a>
|
|
|
|
|
</ul>
|
|
|
|
|
<li><a href="#errors">5.0 Error Processing</a>
|
|
|
|
|
<li><a href="#history">6.0 History of Lemon</a>
|
|
|
|
|
<li><a href="#copyright">7.0 Copyright</a>
|
|
|
|
|
</ul>
|
|
|
|
|
|
|
|
|
|
<a id="secnot"></a>
|
|
|
|
|
<h2>2.0 Security Note</h2>
|
2017-09-27 21:07:03 +00:00
|
|
|
|
|
|
|
|
<p>The language parser code created by Lemon is very robust and
|
|
|
|
|
is well-suited for use in internet-facing applications that need to
|
2021-02-10 16:31:51 +00:00
|
|
|
safely process maliciously crafted inputs.</p>
|
2017-09-27 21:07:03 +00:00
|
|
|
|
|
|
|
|
<p>The "lemon.exe" command-line tool itself works great when given a valid
|
|
|
|
|
input grammar file and almost always gives helpful
|
|
|
|
|
error messages for malformed inputs. However, it is possible for
|
|
|
|
|
a malicious user to craft a grammar file that will cause
|
|
|
|
|
lemon.exe to crash.
|
|
|
|
|
We do not see this as a problem, as lemon.exe is not intended to be used
|
|
|
|
|
with hostile inputs.
|
|
|
|
|
To summarize:</p>
|
|
|
|
|
|
|
|
|
|
<ul>
|
|
|
|
|
<li>Parser code generated by lemon → Robust and secure
|
|
|
|
|
<li>The "lemon.exe" command line tool itself → Not so much
|
|
|
|
|
</ul>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id="optheory"></a>
|
|
|
|
|
<h2>3.0 Theory of Operation</h2>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>Lemon is computer program that translates a context free grammar (CFG)
|
2011-05-06 02:37:34 +00:00
|
|
|
for a particular language into C code that implements a parser for
|
|
|
|
|
that language.
|
2021-02-10 16:31:51 +00:00
|
|
|
The Lemon program has two inputs:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<ul>
|
|
|
|
|
<li>The grammar specification.
|
|
|
|
|
<li>A parser template file.
|
|
|
|
|
</ul>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>Typically, only the grammar specification is supplied by the programmer.
|
|
|
|
|
Lemon comes with a default parser template
|
|
|
|
|
("<a href="https://sqlite.org/src/file/tool/lempar.c">lempar.c</a>")
|
|
|
|
|
that works fine for most applications. But the user is free to substitute
|
|
|
|
|
a different parser template if desired.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>Depending on command-line options, Lemon will generate up to
|
2021-02-10 16:31:51 +00:00
|
|
|
three output files.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<ul>
|
2021-02-10 16:31:51 +00:00
|
|
|
<li>C code to implement a parser for the input grammar.
|
|
|
|
|
<li>A header file defining an integer ID for each terminal symbol
|
|
|
|
|
(or "token").
|
2011-05-06 02:37:34 +00:00
|
|
|
<li>An information file that describes the states of the generated parser
|
|
|
|
|
automaton.
|
|
|
|
|
</ul>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>By default, all three of these output files are generated.
|
2016-12-05 20:29:15 +00:00
|
|
|
The header file is suppressed if the "-m" command-line option is
|
|
|
|
|
used and the report file is omitted when "-q" is selected.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2016-12-05 20:29:15 +00:00
|
|
|
<p>The grammar specification file uses a ".y" suffix, by convention.
|
2011-05-06 02:37:34 +00:00
|
|
|
In the examples used in this document, we'll assume the name of the
|
2016-12-05 20:29:15 +00:00
|
|
|
grammar file is "gram.y". A typical use of Lemon would be the
|
2021-02-10 16:31:51 +00:00
|
|
|
following command:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
lemon gram.y
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>This command will generate three output files named "gram.c",
|
2016-12-05 20:29:15 +00:00
|
|
|
"gram.h" and "gram.out".
|
2011-05-06 02:37:34 +00:00
|
|
|
The first is C code to implement the parser. The second
|
|
|
|
|
is the header file that defines numerical values for all
|
|
|
|
|
terminal symbols, and the last is the report that explains
|
|
|
|
|
the states used by the parser automaton.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id="options"></a>
|
|
|
|
|
<h3>3.1 Command Line Options</h3>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>The behavior of Lemon can be modified using command-line options.
|
|
|
|
|
You can obtain a list of the available command-line options together
|
2021-02-10 16:31:51 +00:00
|
|
|
with a brief explanation of what each does by typing</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
2018-09-18 16:31:37 +00:00
|
|
|
lemon "-?"
|
2011-05-06 02:37:34 +00:00
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>As of this writing, the following command-line options are supported:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<ul>
|
2016-12-05 20:29:15 +00:00
|
|
|
<li><b>-b</b>
|
|
|
|
|
Show only the basis for each parser state in the report file.
|
|
|
|
|
<li><b>-c</b>
|
2018-09-18 16:31:37 +00:00
|
|
|
Do not compress the generated action tables. The parser will be a
|
|
|
|
|
little larger and slower, but it will detect syntax errors sooner.
|
|
|
|
|
<li><b>-d</b><i>directory</i>
|
|
|
|
|
Write all output files into <i>directory</i>. Normally, output files
|
|
|
|
|
are written into the directory that contains the input grammar file.
|
2016-12-05 20:29:15 +00:00
|
|
|
<li><b>-D<i>name</i></b>
|
2018-09-18 16:31:37 +00:00
|
|
|
Define C preprocessor macro <i>name</i>. This macro is usable by
|
2020-08-17 17:03:40 +00:00
|
|
|
"<tt><a href='#pifdef'>%ifdef</a></tt>",
|
|
|
|
|
"<tt><a href='#pifdef'>%ifndef</a></tt>", and
|
|
|
|
|
"<tt><a href="#pifdef">%if</a></tt> lines
|
2018-09-18 16:31:37 +00:00
|
|
|
in the grammar file.
|
2020-08-17 17:03:40 +00:00
|
|
|
<li><b>-E</b>
|
|
|
|
|
Run the "%if" preprocessor step only and print the revised grammar
|
|
|
|
|
file.
|
2016-12-05 20:29:15 +00:00
|
|
|
<li><b>-g</b>
|
|
|
|
|
Do not generate a parser. Instead write the input grammar to standard
|
|
|
|
|
output with all comments, actions, and other extraneous text removed.
|
|
|
|
|
<li><b>-l</b>
|
|
|
|
|
Omit "#line" directives in the generated parser C code.
|
|
|
|
|
<li><b>-m</b>
|
|
|
|
|
Cause the output C source code to be compatible with the "makeheaders"
|
2018-09-18 16:31:37 +00:00
|
|
|
program.
|
2016-12-05 20:29:15 +00:00
|
|
|
<li><b>-p</b>
|
2018-09-18 16:31:37 +00:00
|
|
|
Display all conflicts that are resolved by
|
2016-12-05 20:29:15 +00:00
|
|
|
<a href='#precrules'>precedence rules</a>.
|
|
|
|
|
<li><b>-q</b>
|
|
|
|
|
Suppress generation of the report file.
|
|
|
|
|
<li><b>-r</b>
|
|
|
|
|
Do not sort or renumber the parser states as part of optimization.
|
|
|
|
|
<li><b>-s</b>
|
2020-05-24 11:23:38 +00:00
|
|
|
Show parser statistics before exiting.
|
2016-12-05 20:29:15 +00:00
|
|
|
<li><b>-T<i>file</i></b>
|
|
|
|
|
Use <i>file</i> as the template for the generated C-code parser implementation.
|
|
|
|
|
<li><b>-x</b>
|
|
|
|
|
Print the Lemon version number.
|
2011-05-06 02:37:34 +00:00
|
|
|
</ul>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id="interface"></a>
|
|
|
|
|
<h3>3.2 The Parser Interface</h3>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>Lemon doesn't generate a complete, working program. It only generates
|
|
|
|
|
a few subroutines that implement a parser. This section describes
|
|
|
|
|
the interface to those subroutines. It is up to the programmer to
|
|
|
|
|
call these subroutines in an appropriate way in order to produce a
|
|
|
|
|
complete system.</p>
|
|
|
|
|
|
|
|
|
|
<p>Before a program begins using a Lemon-generated parser, the program
|
|
|
|
|
must first create the parser.
|
2021-02-10 16:31:51 +00:00
|
|
|
A new parser is created as follows:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
void *pParser = ParseAlloc( malloc );
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The ParseAlloc() routine allocates and initializes a new parser and
|
2011-05-06 02:37:34 +00:00
|
|
|
returns a pointer to it.
|
2016-12-05 20:29:15 +00:00
|
|
|
The actual data structure used to represent a parser is opaque —
|
2011-05-06 02:37:34 +00:00
|
|
|
its internal structure is not visible or usable by the calling routine.
|
|
|
|
|
For this reason, the ParseAlloc() routine returns a pointer to void
|
|
|
|
|
rather than a pointer to some particular structure.
|
|
|
|
|
The sole argument to the ParseAlloc() routine is a pointer to the
|
2016-12-05 20:29:15 +00:00
|
|
|
subroutine used to allocate memory. Typically this means malloc().</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>After a program is finished using a parser, it can reclaim all
|
2021-02-10 16:31:51 +00:00
|
|
|
memory allocated by that parser by calling</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
ParseFree(pParser, free);
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The first argument is the same pointer returned by ParseAlloc(). The
|
2011-05-06 02:37:34 +00:00
|
|
|
second argument is a pointer to the function used to release bulk
|
|
|
|
|
memory back to the system.</p>
|
|
|
|
|
|
|
|
|
|
<p>After a parser has been allocated using ParseAlloc(), the programmer
|
|
|
|
|
must supply the parser with a sequence of tokens (terminal symbols) to
|
|
|
|
|
be parsed. This is accomplished by calling the following function
|
2021-02-10 16:31:51 +00:00
|
|
|
once for each token:<p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
Parse(pParser, hTokenID, sTokenData, pArg);
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The first argument to the Parse() routine is the pointer returned by
|
2011-05-06 02:37:34 +00:00
|
|
|
ParseAlloc().
|
2018-09-18 16:31:37 +00:00
|
|
|
The second argument is a small positive integer that tells the parser the
|
2011-05-06 02:37:34 +00:00
|
|
|
type of the next token in the data stream.
|
|
|
|
|
There is one token type for each terminal symbol in the grammar.
|
|
|
|
|
The gram.h file generated by Lemon contains #define statements that
|
|
|
|
|
map symbolic terminal symbol names into appropriate integer values.
|
2016-12-05 20:29:15 +00:00
|
|
|
A value of 0 for the second argument is a special flag to the
|
|
|
|
|
parser to indicate that the end of input has been reached.
|
2011-05-06 02:37:34 +00:00
|
|
|
The third argument is the value of the given token. By default,
|
2018-09-18 16:31:37 +00:00
|
|
|
the type of the third argument is "void*", but the grammar will
|
2011-05-06 02:37:34 +00:00
|
|
|
usually redefine this type to be some kind of structure.
|
|
|
|
|
Typically the second argument will be a broad category of tokens
|
2016-12-05 20:29:15 +00:00
|
|
|
such as "identifier" or "number" and the third argument will
|
2011-05-06 02:37:34 +00:00
|
|
|
be the name of the identifier or the value of the number.</p>
|
|
|
|
|
|
|
|
|
|
<p>The Parse() function may have either three or four arguments,
|
2016-12-05 20:29:15 +00:00
|
|
|
depending on the grammar. If the grammar specification file requests
|
2018-09-18 16:31:37 +00:00
|
|
|
it (via the <tt><a href='#extraarg'>%extra_argument</a></tt> directive),
|
2016-12-05 20:29:15 +00:00
|
|
|
the Parse() function will have a fourth parameter that can be
|
2011-05-06 02:37:34 +00:00
|
|
|
of any type chosen by the programmer. The parser doesn't do anything
|
|
|
|
|
with this argument except to pass it through to action routines.
|
|
|
|
|
This is a convenient mechanism for passing state information down
|
|
|
|
|
to the action routines without having to use global variables.</p>
|
|
|
|
|
|
|
|
|
|
<p>A typical use of a Lemon parser might look something like the
|
2021-02-10 16:31:51 +00:00
|
|
|
following:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
2018-09-18 16:31:37 +00:00
|
|
|
1 ParseTree *ParseFile(const char *zFilename){
|
|
|
|
|
2 Tokenizer *pTokenizer;
|
|
|
|
|
3 void *pParser;
|
|
|
|
|
4 Token sToken;
|
|
|
|
|
5 int hTokenId;
|
|
|
|
|
6 ParserState sState;
|
|
|
|
|
7
|
|
|
|
|
8 pTokenizer = TokenizerCreate(zFilename);
|
|
|
|
|
9 pParser = ParseAlloc( malloc );
|
|
|
|
|
10 InitParserState(&sState);
|
|
|
|
|
11 while( GetNextToken(pTokenizer, &hTokenId, &sToken) ){
|
|
|
|
|
12 Parse(pParser, hTokenId, sToken, &sState);
|
2011-05-06 02:37:34 +00:00
|
|
|
13 }
|
2018-09-18 16:31:37 +00:00
|
|
|
14 Parse(pParser, 0, sToken, &sState);
|
2011-05-06 02:37:34 +00:00
|
|
|
15 ParseFree(pParser, free );
|
|
|
|
|
16 TokenizerFree(pTokenizer);
|
|
|
|
|
17 return sState.treeRoot;
|
|
|
|
|
18 }
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>This example shows a user-written routine that parses a file of
|
2011-05-06 02:37:34 +00:00
|
|
|
text and returns a pointer to the parse tree.
|
2016-12-05 20:29:15 +00:00
|
|
|
(All error-handling code is omitted from this example to keep it
|
2011-05-06 02:37:34 +00:00
|
|
|
simple.)
|
|
|
|
|
We assume the existence of some kind of tokenizer which is created
|
|
|
|
|
using TokenizerCreate() on line 8 and deleted by TokenizerFree()
|
|
|
|
|
on line 16. The GetNextToken() function on line 11 retrieves the
|
2018-09-18 16:31:37 +00:00
|
|
|
next token from the input file and puts its type in the
|
2011-05-06 02:37:34 +00:00
|
|
|
integer variable hTokenId. The sToken variable is assumed to be
|
|
|
|
|
some kind of structure that contains details about each token,
|
2018-09-18 16:31:37 +00:00
|
|
|
such as its complete text, what line it occurs on, etc.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>This example also assumes the existence of a structure of type
|
2011-05-06 02:37:34 +00:00
|
|
|
ParserState that holds state information about a particular parse.
|
|
|
|
|
An instance of such a structure is created on line 6 and initialized
|
|
|
|
|
on line 10. A pointer to this structure is passed into the Parse()
|
|
|
|
|
routine as the optional 4th argument.
|
|
|
|
|
The action routine specified by the grammar for the parser can use
|
|
|
|
|
the ParserState structure to hold whatever information is useful and
|
|
|
|
|
appropriate. In the example, we note that the treeRoot field of
|
|
|
|
|
the ParserState structure is left pointing to the root of the parse
|
|
|
|
|
tree.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The core of this example as it relates to Lemon is as follows:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
ParseFile(){
|
|
|
|
|
pParser = ParseAlloc( malloc );
|
2018-09-18 16:31:37 +00:00
|
|
|
while( GetNextToken(pTokenizer,&hTokenId, &sToken) ){
|
2011-05-06 02:37:34 +00:00
|
|
|
Parse(pParser, hTokenId, sToken);
|
|
|
|
|
}
|
|
|
|
|
Parse(pParser, 0, sToken);
|
|
|
|
|
ParseFree(pParser, free );
|
|
|
|
|
}
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>Basically, what a program has to do to use a Lemon-generated parser
|
2011-05-06 02:37:34 +00:00
|
|
|
is first create the parser, then send it lots of tokens obtained by
|
|
|
|
|
tokenizing an input source. When the end of input is reached, the
|
|
|
|
|
Parse() routine should be called one last time with a token type
|
|
|
|
|
of 0. This step is necessary to inform the parser that the end of
|
|
|
|
|
input has been reached. Finally, we reclaim memory used by the
|
|
|
|
|
parser by calling ParseFree().</p>
|
|
|
|
|
|
|
|
|
|
<p>There is one other interface routine that should be mentioned
|
|
|
|
|
before we move on.
|
|
|
|
|
The ParseTrace() function can be used to generate debugging output
|
2021-02-10 16:31:51 +00:00
|
|
|
from the parser. A prototype for this routine is as follows:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
ParseTrace(FILE *stream, char *zPrefix);
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>After this routine is called, a short (one-line) message is written
|
2011-05-06 02:37:34 +00:00
|
|
|
to the designated output stream every time the parser changes states
|
|
|
|
|
or calls an action routine. Each such message is prefaced using
|
|
|
|
|
the text given by zPrefix. This debugging output can be turned off
|
|
|
|
|
by calling ParseTrace() again with a first argument of NULL (0).</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id="onstack"></a>
|
|
|
|
|
<h4>3.2.1 Allocating The Parse Object On Stack</h4>
|
|
|
|
|
|
|
|
|
|
<p>If all calls to the Parse() interface are made from within
|
|
|
|
|
<a href="#pcode"><tt>%code</tt> directives</a>, then the parse
|
|
|
|
|
object can be allocated from the stack rather than from the heap.
|
|
|
|
|
These are the steps:
|
|
|
|
|
|
|
|
|
|
<ul>
|
|
|
|
|
<li> Declare a local variable of type "yyParser"
|
|
|
|
|
<li> Initialize the variable using ParseInit()
|
|
|
|
|
<li> Pass a pointer to the variable in calls ot Parse()
|
|
|
|
|
<li> Deallocate substructure in the parse variable using ParseFinalize().
|
|
|
|
|
</ul>
|
|
|
|
|
|
|
|
|
|
<p>The following code illustrates how this is done:
|
|
|
|
|
|
|
|
|
|
<pre>
|
|
|
|
|
ParseFile(){
|
|
|
|
|
yyParser x;
|
|
|
|
|
ParseInit( &x );
|
|
|
|
|
while( GetNextToken(pTokenizer,&hTokenId, &sToken) ){
|
|
|
|
|
Parse(&x, hTokenId, sToken);
|
|
|
|
|
}
|
|
|
|
|
Parse(&x, 0, sToken);
|
|
|
|
|
ParseFinalize( &x );
|
|
|
|
|
}
|
|
|
|
|
</pre>
|
|
|
|
|
|
|
|
|
|
<a id="ifsum"></a>
|
|
|
|
|
<h4>3.2.2 Interface Summary</h4>
|
|
|
|
|
|
|
|
|
|
<p>Here is a quick overview of the C-language interface to a
|
|
|
|
|
Lemon-generated parser:</p>
|
|
|
|
|
|
|
|
|
|
<blockquote><pre>
|
|
|
|
|
void *ParseAlloc( (void*(*malloc)(size_t) );
|
|
|
|
|
void ParseFree(void *pParser, (void(*free)(void*) );
|
|
|
|
|
void Parse(void *pParser, int tokenCode, ParseTOKENTYPE token, ...);
|
|
|
|
|
void ParseTrace(FILE *stream, char *zPrefix);
|
|
|
|
|
</pre></blockquote>
|
|
|
|
|
|
|
|
|
|
<p>Notes:</p>
|
|
|
|
|
<ul>
|
|
|
|
|
<li> Use the <a href="#pname"><tt>%name</tt> directive</a> to change
|
|
|
|
|
the "Parse" prefix names of the procedures in the interface.
|
|
|
|
|
<li> Use the <a href="#token_type"><tt>%token_type</tt> directive</a>
|
|
|
|
|
to define the "ParseTOKENTYPE" type.
|
|
|
|
|
<li> Use the <a href="#extraarg"><tt>%extra_argument</tt> directive</a>
|
|
|
|
|
to specify the type and name of the 4th parameter to the
|
|
|
|
|
Parse() function.
|
|
|
|
|
</ul>
|
|
|
|
|
|
|
|
|
|
<a id="yaccdiff"></a>
|
|
|
|
|
<h3>3.3 Differences With YACC and BISON</h3>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>Programmers who have previously used the yacc or bison parser
|
|
|
|
|
generator will notice several important differences between yacc and/or
|
2021-02-10 16:31:51 +00:00
|
|
|
bison and Lemon.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<ul>
|
|
|
|
|
<li>In yacc and bison, the parser calls the tokenizer. In Lemon,
|
|
|
|
|
the tokenizer calls the parser.
|
|
|
|
|
<li>Lemon uses no global variables. Yacc and bison use global variables
|
|
|
|
|
to pass information between the tokenizer and parser.
|
|
|
|
|
<li>Lemon allows multiple parsers to be running simultaneously. Yacc
|
|
|
|
|
and bison do not.
|
|
|
|
|
</ul>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>These differences may cause some initial confusion for programmers
|
2011-05-06 02:37:34 +00:00
|
|
|
with prior yacc and bison experience.
|
|
|
|
|
But after years of experience using Lemon, I firmly
|
|
|
|
|
believe that the Lemon way of doing things is better.</p>
|
|
|
|
|
|
2016-12-05 20:29:15 +00:00
|
|
|
<p><i>Updated as of 2016-02-16:</i>
|
|
|
|
|
The text above was written in the 1990s.
|
|
|
|
|
We are told that Bison has lately been enhanced to support the
|
2021-02-10 16:31:51 +00:00
|
|
|
tokenizer-calls-parser paradigm used by Lemon, eliminating the
|
2016-12-05 20:29:15 +00:00
|
|
|
need for global variables.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id="build"><a>
|
|
|
|
|
<h3>3.4 Building The "lemon" or "lemon.exe" Executable</h3>
|
|
|
|
|
|
|
|
|
|
<p>The "lemon" or "lemon.exe" program is built from a single file
|
|
|
|
|
of C-code named
|
|
|
|
|
"<a href="https://sqlite.org/src/tool/lemon.c">lemon.c</a>".
|
|
|
|
|
The Lemon source code is generic C89 code that uses
|
|
|
|
|
no unusual or non-standard libraries. Any
|
|
|
|
|
reasonable C compiler should suffice to compile the lemon program.
|
|
|
|
|
A command-line like the following will usually work:</p>
|
|
|
|
|
|
|
|
|
|
<blockquote><pre>
|
|
|
|
|
cc -o lemon lemon.c
|
|
|
|
|
</pre></blockquote
|
|
|
|
|
|
|
|
|
|
<p>On Windows machines with Visual C++ installed, bring up a
|
|
|
|
|
"VS20<i>NN</i> x64 Native Tools Command Prompt" window and enter:
|
|
|
|
|
|
|
|
|
|
<blockquote><pre>
|
|
|
|
|
cl lemon.c
|
|
|
|
|
</pre></blockquote>
|
|
|
|
|
|
|
|
|
|
<p>Compiling Lemon really is that simple.
|
|
|
|
|
Additional compiler options such as
|
|
|
|
|
"-O2" or "-g" or "-Wall" can be added if desired, but they are not
|
|
|
|
|
necessary.</p>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<a id="syntax"></a>
|
|
|
|
|
<h2>4.0 Input File Syntax</h2>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>The main purpose of the grammar specification file for Lemon is
|
|
|
|
|
to define the grammar for the parser. But the input file also
|
|
|
|
|
specifies additional information Lemon requires to do its job.
|
|
|
|
|
Most of the work in using Lemon is in writing an appropriate
|
|
|
|
|
grammar file.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The grammar file for Lemon is, for the most part, a free format.
|
2011-05-06 02:37:34 +00:00
|
|
|
It does not have sections or divisions like yacc or bison. Any
|
2021-02-10 16:31:51 +00:00
|
|
|
declaration can occur at any point in the file. Lemon ignores
|
|
|
|
|
whitespace (except where it is needed to separate tokens), and it
|
|
|
|
|
honors the same commenting conventions as C and C++.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id="tnt"></a>
|
|
|
|
|
<h3>4.1 Terminals and Nonterminals</h3>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>A terminal symbol (token) is any string of alphanumeric
|
2016-12-05 20:29:15 +00:00
|
|
|
and/or underscore characters
|
2018-09-18 16:31:37 +00:00
|
|
|
that begins with an uppercase letter.
|
2011-12-26 19:52:17 +00:00
|
|
|
A terminal can contain lowercase letters after the first character,
|
2018-09-18 16:31:37 +00:00
|
|
|
but the usual convention is to make terminals all uppercase.
|
2011-05-06 02:37:34 +00:00
|
|
|
A nonterminal, on the other hand, is any string of alphanumeric
|
2018-09-18 16:31:37 +00:00
|
|
|
and underscore characters than begins with a lowercase letter.
|
|
|
|
|
Again, the usual convention is to make nonterminals use all lowercase
|
|
|
|
|
letters.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>In Lemon, terminal and nonterminal symbols do not need to
|
2011-05-06 02:37:34 +00:00
|
|
|
be declared or identified in a separate section of the grammar file.
|
|
|
|
|
Lemon is able to generate a list of all terminals and nonterminals
|
|
|
|
|
by examining the grammar rules, and it can always distinguish a
|
|
|
|
|
terminal from a nonterminal by checking the case of the first
|
|
|
|
|
character of the name.</p>
|
|
|
|
|
|
|
|
|
|
<p>Yacc and bison allow terminal symbols to have either alphanumeric
|
|
|
|
|
names or to be individual characters included in single quotes, like
|
|
|
|
|
this: ')' or '$'. Lemon does not allow this alternative form for
|
|
|
|
|
terminal symbols. With Lemon, all symbols, terminals and nonterminals,
|
|
|
|
|
must have alphanumeric names.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id="rules"></a>
|
|
|
|
|
<h3>4.2 Grammar Rules</h3>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>The main component of a Lemon grammar file is a sequence of grammar
|
|
|
|
|
rules.
|
|
|
|
|
Each grammar rule consists of a nonterminal symbol followed by
|
2016-12-05 20:29:15 +00:00
|
|
|
the special symbol "::=" and then a list of terminals and/or nonterminals.
|
2011-05-06 02:37:34 +00:00
|
|
|
The rule is terminated by a period.
|
|
|
|
|
The list of terminals and nonterminals on the right-hand side of the
|
|
|
|
|
rule can be empty.
|
|
|
|
|
Rules can occur in any order, except that the left-hand side of the
|
|
|
|
|
first rule is assumed to be the start symbol for the grammar (unless
|
2018-09-18 16:31:37 +00:00
|
|
|
specified otherwise using the <tt><a href='#start_symbol'>%start_symbol</a></tt>
|
|
|
|
|
directive described below.)
|
2021-02-10 16:31:51 +00:00
|
|
|
A typical sequence of grammar rules might look something like this:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
expr ::= expr PLUS expr.
|
|
|
|
|
expr ::= expr TIMES expr.
|
|
|
|
|
expr ::= LPAREN expr RPAREN.
|
|
|
|
|
expr ::= VALUE.
|
|
|
|
|
</pre>
|
|
|
|
|
|
2016-12-05 20:29:15 +00:00
|
|
|
<p>There is one non-terminal in this example, "expr", and five
|
|
|
|
|
terminal symbols or tokens: "PLUS", "TIMES", "LPAREN",
|
|
|
|
|
"RPAREN" and "VALUE".</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>Like yacc and bison, Lemon allows the grammar to specify a block
|
|
|
|
|
of C code that will be executed whenever a grammar rule is reduced
|
|
|
|
|
by the parser.
|
|
|
|
|
In Lemon, this action is specified by putting the C code (contained
|
|
|
|
|
within curly braces <tt>{...}</tt>) immediately after the
|
|
|
|
|
period that closes the rule.
|
2021-02-10 16:31:51 +00:00
|
|
|
For example:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
expr ::= expr PLUS expr. { printf("Doing an addition...\n"); }
|
|
|
|
|
</pre>
|
|
|
|
|
|
|
|
|
|
<p>In order to be useful, grammar actions must normally be linked to
|
|
|
|
|
their associated grammar rules.
|
2016-12-05 20:29:15 +00:00
|
|
|
In yacc and bison, this is accomplished by embedding a "$$" in the
|
2011-05-06 02:37:34 +00:00
|
|
|
action to stand for the value of the left-hand side of the rule and
|
2016-12-05 20:29:15 +00:00
|
|
|
symbols "$1", "$2", and so forth to stand for the value of
|
2011-05-06 02:37:34 +00:00
|
|
|
the terminal or nonterminal at position 1, 2 and so forth on the
|
|
|
|
|
right-hand side of the rule.
|
|
|
|
|
This idea is very powerful, but it is also very error-prone. The
|
|
|
|
|
single most common source of errors in a yacc or bison grammar is
|
|
|
|
|
to miscount the number of symbols on the right-hand side of a grammar
|
2016-12-05 20:29:15 +00:00
|
|
|
rule and say "$7" when you really mean "$8".</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>Lemon avoids the need to count grammar symbols by assigning symbolic
|
|
|
|
|
names to each symbol in a grammar rule and then using those symbolic
|
|
|
|
|
names in the action.
|
2021-02-10 16:31:51 +00:00
|
|
|
In yacc or bison, one would write this:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
2018-09-18 16:31:37 +00:00
|
|
|
expr -> expr PLUS expr { $$ = $1 + $3; };
|
2011-05-06 02:37:34 +00:00
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>But in Lemon, the same rule becomes the following:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
expr(A) ::= expr(B) PLUS expr(C). { A = B+C; }
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>In the Lemon rule, any symbol in parentheses after a grammar rule
|
2011-05-06 02:37:34 +00:00
|
|
|
symbol becomes a place holder for that symbol in the grammar rule.
|
|
|
|
|
This place holder can then be used in the associated C action to
|
2021-02-10 16:31:51 +00:00
|
|
|
stand for the value of that symbol.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>The Lemon notation for linking a grammar rule with its reduce
|
|
|
|
|
action is superior to yacc/bison on several counts.
|
|
|
|
|
First, as mentioned above, the Lemon method avoids the need to
|
|
|
|
|
count grammar symbols.
|
|
|
|
|
Secondly, if a terminal or nonterminal in a Lemon grammar rule
|
|
|
|
|
includes a linking symbol in parentheses but that linking symbol
|
|
|
|
|
is not actually used in the reduce action, then an error message
|
|
|
|
|
is generated.
|
2021-02-10 16:31:51 +00:00
|
|
|
For example, the rule</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
expr(A) ::= expr(B) PLUS expr(C). { A = B; }
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>will generate an error because the linking symbol "C" is used
|
2011-05-06 02:37:34 +00:00
|
|
|
in the grammar rule but not in the reduce action.</p>
|
|
|
|
|
|
|
|
|
|
<p>The Lemon notation for linking grammar rules to reduce actions
|
|
|
|
|
also facilitates the use of destructors for reclaiming memory
|
|
|
|
|
allocated by the values of terminals and nonterminals on the
|
|
|
|
|
right-hand side of a rule.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='precrules'></a>
|
|
|
|
|
<h3>4.3 Precedence Rules</h3>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>Lemon resolves parsing ambiguities in exactly the same way as
|
|
|
|
|
yacc and bison. A shift-reduce conflict is resolved in favor
|
|
|
|
|
of the shift, and a reduce-reduce conflict is resolved by reducing
|
|
|
|
|
whichever rule comes first in the grammar file.</p>
|
|
|
|
|
|
|
|
|
|
<p>Just like in
|
2018-09-18 16:31:37 +00:00
|
|
|
yacc and bison, Lemon allows a measure of control
|
|
|
|
|
over the resolution of parsing conflicts using precedence rules.
|
2011-05-06 02:37:34 +00:00
|
|
|
A precedence value can be assigned to any terminal symbol
|
2018-09-18 16:31:37 +00:00
|
|
|
using the
|
|
|
|
|
<tt><a href='#pleft'>%left</a></tt>,
|
|
|
|
|
<tt><a href='#pright'>%right</a></tt> or
|
|
|
|
|
<tt><a href='#pnonassoc'>%nonassoc</a></tt> directives. Terminal symbols
|
|
|
|
|
mentioned in earlier directives have a lower precedence than
|
2011-05-06 02:37:34 +00:00
|
|
|
terminal symbols mentioned in later directives. For example:</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%left AND.
|
|
|
|
|
%left OR.
|
|
|
|
|
%nonassoc EQ NE GT GE LT LE.
|
|
|
|
|
%left PLUS MINUS.
|
|
|
|
|
%left TIMES DIVIDE MOD.
|
|
|
|
|
%right EXP NOT.
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>In the preceding sequence of directives, the AND operator is
|
|
|
|
|
defined to have the lowest precedence. The OR operator is one
|
|
|
|
|
precedence level higher. And so forth. Hence, the grammar would
|
2021-02-10 16:31:51 +00:00
|
|
|
attempt to group the ambiguous expression</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
a AND b OR c
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>like this</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
a AND (b OR c).
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The associativity (left, right or nonassoc) is used to determine
|
2011-05-06 02:37:34 +00:00
|
|
|
the grouping when the precedence is the same. AND is left-associative
|
2021-02-10 16:31:51 +00:00
|
|
|
in our example, so</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
a AND b AND c
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>is parsed like this</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
(a AND b) AND c.
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The EXP operator is right-associative, though, so</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
a EXP b EXP c
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>is parsed like this</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
a EXP (b EXP c).
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The nonassoc precedence is used for non-associative operators.
|
|
|
|
|
So</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
a EQ b EQ c
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>is an error.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>The precedence of non-terminals is transferred to rules as follows:
|
|
|
|
|
The precedence of a grammar rule is equal to the precedence of the
|
|
|
|
|
left-most terminal symbol in the rule for which a precedence is
|
|
|
|
|
defined. This is normally what you want, but in those cases where
|
2020-05-24 11:23:38 +00:00
|
|
|
you want the precedence of a grammar rule to be something different,
|
2011-05-06 02:37:34 +00:00
|
|
|
you can specify an alternative precedence symbol by putting the
|
|
|
|
|
symbol in square braces after the period at the end of the rule and
|
|
|
|
|
before any C-code. For example:</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
expr = MINUS expr. [NOT]
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>This rule has a precedence equal to that of the NOT symbol, not the
|
|
|
|
|
MINUS symbol as would have been the case by default.</p>
|
|
|
|
|
|
|
|
|
|
<p>With the knowledge of how precedence is assigned to terminal
|
|
|
|
|
symbols and individual
|
|
|
|
|
grammar rules, we can now explain precisely how parsing conflicts
|
|
|
|
|
are resolved in Lemon. Shift-reduce conflicts are resolved
|
2021-02-10 16:31:51 +00:00
|
|
|
as follows:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<ul>
|
|
|
|
|
<li> If either the token to be shifted or the rule to be reduced
|
|
|
|
|
lacks precedence information, then resolve in favor of the
|
|
|
|
|
shift, but report a parsing conflict.
|
|
|
|
|
<li> If the precedence of the token to be shifted is greater than
|
|
|
|
|
the precedence of the rule to reduce, then resolve in favor
|
|
|
|
|
of the shift. No parsing conflict is reported.
|
2018-09-18 16:31:37 +00:00
|
|
|
<li> If the precedence of the token to be shifted is less than the
|
2011-05-06 02:37:34 +00:00
|
|
|
precedence of the rule to reduce, then resolve in favor of the
|
|
|
|
|
reduce action. No parsing conflict is reported.
|
|
|
|
|
<li> If the precedences are the same and the shift token is
|
|
|
|
|
right-associative, then resolve in favor of the shift.
|
|
|
|
|
No parsing conflict is reported.
|
2018-09-18 16:31:37 +00:00
|
|
|
<li> If the precedences are the same and the shift token is
|
2011-05-06 02:37:34 +00:00
|
|
|
left-associative, then resolve in favor of the reduce.
|
|
|
|
|
No parsing conflict is reported.
|
2018-09-18 16:31:37 +00:00
|
|
|
<li> Otherwise, resolve the conflict by doing the shift, and
|
|
|
|
|
report a parsing conflict.
|
2011-05-06 02:37:34 +00:00
|
|
|
</ul>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>Reduce-reduce conflicts are resolved this way:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<ul>
|
2018-09-18 16:31:37 +00:00
|
|
|
<li> If either reduce rule
|
2011-05-06 02:37:34 +00:00
|
|
|
lacks precedence information, then resolve in favor of the
|
2018-09-18 16:31:37 +00:00
|
|
|
rule that appears first in the grammar, and report a parsing
|
2011-05-06 02:37:34 +00:00
|
|
|
conflict.
|
2018-09-18 16:31:37 +00:00
|
|
|
<li> If both rules have precedence and the precedence is different,
|
2011-05-06 02:37:34 +00:00
|
|
|
then resolve the dispute in favor of the rule with the highest
|
2018-09-18 16:31:37 +00:00
|
|
|
precedence, and do not report a conflict.
|
2011-05-06 02:37:34 +00:00
|
|
|
<li> Otherwise, resolve the conflict by reducing by the rule that
|
2018-09-18 16:31:37 +00:00
|
|
|
appears first in the grammar, and report a parsing conflict.
|
2011-05-06 02:37:34 +00:00
|
|
|
</ul>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id="special"></a>
|
|
|
|
|
<h3>4.4 Special Directives</h3>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>The input grammar to Lemon consists of grammar rules and special
|
|
|
|
|
directives. We've described all the grammar rules, so now we'll
|
|
|
|
|
talk about the special directives.</p>
|
|
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>Directives in Lemon can occur in any order. You can put them before
|
|
|
|
|
the grammar rules, or after the grammar rules, or in the midst of the
|
2011-05-06 02:37:34 +00:00
|
|
|
grammar rules. It doesn't matter. The relative order of
|
|
|
|
|
directives used to assign precedence to terminals is important, but
|
|
|
|
|
other than that, the order of directives in Lemon is arbitrary.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>Lemon supports the following special directives:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<ul>
|
2018-09-18 16:31:37 +00:00
|
|
|
<li><tt><a href='#pcode'>%code</a></tt>
|
|
|
|
|
<li><tt><a href='#default_destructor'>%default_destructor</a></tt>
|
|
|
|
|
<li><tt><a href='#default_type'>%default_type</a></tt>
|
|
|
|
|
<li><tt><a href='#destructor'>%destructor</a></tt>
|
2020-08-17 17:03:40 +00:00
|
|
|
<li><tt><a href='#pifdef'>%else</a></tt>
|
2018-09-18 16:31:37 +00:00
|
|
|
<li><tt><a href='#pifdef'>%endif</a></tt>
|
|
|
|
|
<li><tt><a href='#extraarg'>%extra_argument</a></tt>
|
|
|
|
|
<li><tt><a href='#pfallback'>%fallback</a></tt>
|
2020-08-17 17:03:40 +00:00
|
|
|
<li><tt><a href='#pifdef'>%if</a></tt>
|
2018-09-18 16:31:37 +00:00
|
|
|
<li><tt><a href='#pifdef'>%ifdef</a></tt>
|
|
|
|
|
<li><tt><a href='#pifdef'>%ifndef</a></tt>
|
|
|
|
|
<li><tt><a href='#pinclude'>%include</a></tt>
|
|
|
|
|
<li><tt><a href='#pleft'>%left</a></tt>
|
|
|
|
|
<li><tt><a href='#pname'>%name</a></tt>
|
|
|
|
|
<li><tt><a href='#pnonassoc'>%nonassoc</a></tt>
|
|
|
|
|
<li><tt><a href='#parse_accept'>%parse_accept</a></tt>
|
|
|
|
|
<li><tt><a href='#parse_failure'>%parse_failure</a></tt>
|
|
|
|
|
<li><tt><a href='#pright'>%right</a></tt>
|
|
|
|
|
<li><tt><a href='#stack_overflow'>%stack_overflow</a></tt>
|
|
|
|
|
<li><tt><a href='#stack_size'>%stack_size</a></tt>
|
|
|
|
|
<li><tt><a href='#start_symbol'>%start_symbol</a></tt>
|
|
|
|
|
<li><tt><a href='#syntax_error'>%syntax_error</a></tt>
|
2021-10-05 20:25:47 +00:00
|
|
|
<li><tt><a href='#token'>%token</a></tt>
|
2018-09-18 16:31:37 +00:00
|
|
|
<li><tt><a href='#token_class'>%token_class</a></tt>
|
|
|
|
|
<li><tt><a href='#token_destructor'>%token_destructor</a></tt>
|
|
|
|
|
<li><tt><a href='#token_prefix'>%token_prefix</a></tt>
|
|
|
|
|
<li><tt><a href='#token_type'>%token_type</a></tt>
|
|
|
|
|
<li><tt><a href='#ptype'>%type</a></tt>
|
|
|
|
|
<li><tt><a href='#pwildcard'>%wildcard</a></tt>
|
2011-05-06 02:37:34 +00:00
|
|
|
</ul>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>Each of these directives will be described separately in the
|
2011-05-06 02:37:34 +00:00
|
|
|
following sections:</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='pcode'></a>
|
|
|
|
|
<h4>4.4.1 The <tt>%code</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%code</tt> directive is used to specify additional C code that
|
2011-05-06 02:37:34 +00:00
|
|
|
is added to the end of the main output file. This is similar to
|
2018-09-18 16:31:37 +00:00
|
|
|
the <tt><a href='#pinclude'>%include</a></tt> directive except that
|
|
|
|
|
<tt>%include</tt> is inserted at the beginning of the main output file.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p><tt>%code</tt> is typically used to include some action routines or perhaps
|
|
|
|
|
a tokenizer or even the "main()" function
|
2016-12-05 20:29:15 +00:00
|
|
|
as part of the output file.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>There can be multiple <tt>%code</tt> directives. The arguments of
|
|
|
|
|
all <tt>%code</tt> directives are concatenated.</p>
|
|
|
|
|
|
|
|
|
|
<a id='default_destructor'></a>
|
|
|
|
|
<h4>4.4.2 The <tt>%default_destructor</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%default_destructor</tt> directive specifies a destructor to
|
2011-05-06 02:37:34 +00:00
|
|
|
use for non-terminals that do not have their own destructor
|
2018-09-18 16:31:37 +00:00
|
|
|
specified by a separate <tt>%destructor</tt> directive. See the documentation
|
2021-02-10 16:31:51 +00:00
|
|
|
on the <tt><a href='#destructor'>%destructor</a></tt> directive below for
|
2016-12-05 20:29:15 +00:00
|
|
|
additional information.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>In some grammars, many different non-terminal symbols have the
|
|
|
|
|
same data type and hence the same destructor. This directive is
|
|
|
|
|
a convenient way to specify the same destructor for all those
|
2011-05-06 02:37:34 +00:00
|
|
|
non-terminals using a single statement.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='default_type'></a>
|
|
|
|
|
<h4>4.4.3 The <tt>%default_type</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%default_type</tt> directive specifies the data type of non-terminal
|
|
|
|
|
symbols that do not have their own data type defined using a separate
|
|
|
|
|
<tt><a href='#ptype'>%type</a></tt> directive.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='destructor'></a>
|
|
|
|
|
<h4>4.4.4 The <tt>%destructor</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%destructor</tt> directive is used to specify a destructor for
|
2011-05-06 02:37:34 +00:00
|
|
|
a non-terminal symbol.
|
2018-09-18 16:31:37 +00:00
|
|
|
(See also the <tt><a href='#token_destructor'>%token_destructor</a></tt>
|
2016-12-05 20:29:15 +00:00
|
|
|
directive which is used to specify a destructor for terminal symbols.)</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>A non-terminal's destructor is called to dispose of the
|
|
|
|
|
non-terminal's value whenever the non-terminal is popped from
|
2021-02-10 16:31:51 +00:00
|
|
|
the stack. This includes all of the following circumstances:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<ul>
|
|
|
|
|
<li> When a rule reduces and the value of a non-terminal on
|
|
|
|
|
the right-hand side is not linked to C code.
|
|
|
|
|
<li> When the stack is popped during error processing.
|
|
|
|
|
<li> When the ParseFree() function runs.
|
|
|
|
|
</ul>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The destructor can do whatever it wants with the value of
|
2011-05-06 02:37:34 +00:00
|
|
|
the non-terminal, but its design is to deallocate memory
|
|
|
|
|
or other resources held by that non-terminal.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>Consider an example:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
%type nt {void*}
|
|
|
|
|
%destructor nt { free($$); }
|
|
|
|
|
nt(A) ::= ID NUM. { A = malloc( 100 ); }
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>This example is a bit contrived, but it serves to illustrate how
|
2011-05-06 02:37:34 +00:00
|
|
|
destructors work. The example shows a non-terminal named
|
2016-12-05 20:29:15 +00:00
|
|
|
"nt" that holds values of type "void*". When the rule for
|
|
|
|
|
an "nt" reduces, it sets the value of the non-terminal to
|
2011-05-06 02:37:34 +00:00
|
|
|
space obtained from malloc(). Later, when the nt non-terminal
|
|
|
|
|
is popped from the stack, the destructor will fire and call
|
|
|
|
|
free() on this malloced space, thus avoiding a memory leak.
|
2016-12-05 20:29:15 +00:00
|
|
|
(Note that the symbol "$$" in the destructor code is replaced
|
2011-05-06 02:37:34 +00:00
|
|
|
by the value of the non-terminal.)</p>
|
|
|
|
|
|
|
|
|
|
<p>It is important to note that the value of a non-terminal is passed
|
|
|
|
|
to the destructor whenever the non-terminal is removed from the
|
|
|
|
|
stack, unless the non-terminal is used in a C-code action. If
|
|
|
|
|
the non-terminal is used by C-code, then it is assumed that the
|
2016-12-05 20:29:15 +00:00
|
|
|
C-code will take care of destroying it.
|
|
|
|
|
More commonly, the value is used to build some
|
2018-09-18 16:31:37 +00:00
|
|
|
larger structure, and we don't want to destroy it, which is why
|
2011-05-06 02:37:34 +00:00
|
|
|
the destructor is not called in this circumstance.</p>
|
|
|
|
|
|
2016-12-05 20:29:15 +00:00
|
|
|
<p>Destructors help avoid memory leaks by automatically freeing
|
|
|
|
|
allocated objects when they go out of scope.
|
2011-05-06 02:37:34 +00:00
|
|
|
To do the same using yacc or bison is much more difficult.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='extraarg'></a>
|
|
|
|
|
<h4>4.4.5 The <tt>%extra_argument</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The <tt>%extra_argument</tt> directive instructs Lemon to add a 4th parameter
|
2011-05-06 02:37:34 +00:00
|
|
|
to the parameter list of the Parse() function it generates. Lemon
|
|
|
|
|
doesn't do anything itself with this extra argument, but it does
|
|
|
|
|
make the argument available to C-code action routines, destructors,
|
|
|
|
|
and so forth. For example, if the grammar file contains:</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%extra_argument { MyStruct *pAbc }
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>Then the Parse() function generated will have an 4th parameter
|
2016-12-05 20:29:15 +00:00
|
|
|
of type "MyStruct*" and all action routines will have access to
|
|
|
|
|
a variable named "pAbc" that is the value of the 4th parameter
|
2011-05-06 02:37:34 +00:00
|
|
|
in the most recent call to Parse().</p>
|
|
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%extra_context</tt> directive works the same except that it
|
|
|
|
|
is passed in on the ParseAlloc() or ParseInit() routines instead of
|
2021-02-10 16:31:51 +00:00
|
|
|
on Parse().</p>
|
2018-09-18 16:31:37 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='extractx'></a>
|
|
|
|
|
<h4>4.4.6 The <tt>%extra_context</tt> directive</h4>
|
2018-09-18 16:31:37 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The <tt>%extra_context</tt> directive instructs Lemon to add a 2nd parameter
|
|
|
|
|
to the parameter list of the ParseAlloc() and ParseInit() functions. Lemon
|
2018-09-18 16:31:37 +00:00
|
|
|
doesn't do anything itself with these extra argument, but it does
|
|
|
|
|
store the value make it available to C-code action routines, destructors,
|
|
|
|
|
and so forth. For example, if the grammar file contains:</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2018-09-18 16:31:37 +00:00
|
|
|
%extra_context { MyStruct *pAbc }
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2018-09-18 16:31:37 +00:00
|
|
|
|
2020-05-24 11:23:38 +00:00
|
|
|
<p>Then the ParseAlloc() and ParseInit() functions will have an 2nd parameter
|
2018-09-18 16:31:37 +00:00
|
|
|
of type "MyStruct*" and all action routines will have access to
|
2020-05-24 11:23:38 +00:00
|
|
|
a variable named "pAbc" that is the value of that 2nd parameter.</p>
|
2018-09-18 16:31:37 +00:00
|
|
|
|
|
|
|
|
<p>The <tt>%extra_argument</tt> directive works the same except that it
|
2021-02-10 16:31:51 +00:00
|
|
|
is passed in on the Parse() routine instead of on ParseAlloc()/ParseInit().</p>
|
2018-09-18 16:31:37 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='pfallback'></a>
|
|
|
|
|
<h4>4.4.7 The <tt>%fallback</tt> directive</h4>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%fallback</tt> directive specifies an alternative meaning for one
|
2016-12-05 20:29:15 +00:00
|
|
|
or more tokens. The alternative meaning is tried if the original token
|
2018-09-18 16:31:37 +00:00
|
|
|
would have generated a syntax error.</p>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%fallback</tt> directive was added to support robust parsing of SQL
|
|
|
|
|
syntax in <a href='https://www.sqlite.org/'>SQLite</a>.
|
2016-12-05 20:29:15 +00:00
|
|
|
The SQL language contains a large assortment of keywords, each of which
|
|
|
|
|
appears as a different token to the language parser. SQL contains so
|
2018-09-18 16:31:37 +00:00
|
|
|
many keywords that it can be difficult for programmers to keep up with
|
2016-12-05 20:29:15 +00:00
|
|
|
them all. Programmers will, therefore, sometimes mistakenly use an
|
2018-09-18 16:31:37 +00:00
|
|
|
obscure language keyword for an identifier. The <tt>%fallback</tt> directive
|
2016-12-05 20:29:15 +00:00
|
|
|
provides a mechanism to tell the parser: "If you are unable to parse
|
2018-09-18 16:31:37 +00:00
|
|
|
this keyword, try treating it as an identifier instead."</p>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>The syntax of <tt>%fallback</tt> is as follows:</p>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
|
|
|
|
<blockquote>
|
2018-09-18 16:31:37 +00:00
|
|
|
<tt>%fallback</tt> <i>ID</i> <i>TOKEN...</i> <b>.</b>
|
|
|
|
|
</blockquote></p>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>In words, the <tt>%fallback</tt> directive is followed by a list of token
|
|
|
|
|
names terminated by a period.
|
|
|
|
|
The first token name is the fallback token — the
|
2016-12-05 20:29:15 +00:00
|
|
|
token to which all the other tokens fall back to. The second and subsequent
|
|
|
|
|
arguments are tokens which fall back to the token identified by the first
|
2018-09-18 16:31:37 +00:00
|
|
|
argument.</p>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='pifdef'></a>
|
|
|
|
|
<h4>4.4.8 The <tt>%if</tt> directive and its friends</h4>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
2020-08-17 17:03:40 +00:00
|
|
|
<p>The <tt>%if</tt>, <tt>%ifdef</tt>, <tt>%ifndef</tt>, <tt>%else</tt>,
|
|
|
|
|
and <tt>%endif</tt> directives
|
|
|
|
|
are similar to #if, #ifdef, #ifndef, #else, and #endif in the C-preprocessor,
|
2018-09-18 16:31:37 +00:00
|
|
|
just not as general.
|
2016-12-05 20:29:15 +00:00
|
|
|
Each of these directives must begin at the left margin. No whitespace
|
2018-09-18 16:31:37 +00:00
|
|
|
is allowed between the "%" and the directive name.</p>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>Grammar text in between "<tt>%ifdef MACRO</tt>" and the next nested
|
|
|
|
|
"<tt>%endif</tt>" is
|
2016-12-05 20:29:15 +00:00
|
|
|
ignored unless the "-DMACRO" command-line option is used. Grammar text
|
2018-09-18 16:31:37 +00:00
|
|
|
betwen "<tt>%ifndef MACRO</tt>" and the next nested "<tt>%endif</tt>" is
|
2020-08-17 17:03:40 +00:00
|
|
|
included except when the "-DMACRO" command-line option is used.<p>
|
|
|
|
|
|
|
|
|
|
<p>The text in between "<tt>%if</tt> <i>CONDITIONAL</i>" and its
|
|
|
|
|
corresponding <tt>%endif</tt> is included only if <i>CONDITIONAL</i>
|
|
|
|
|
is true. The CONDITION is one or more macro names, optionally connected
|
|
|
|
|
using the "||" and "&&" binary operators, the "!" unary operator,
|
|
|
|
|
and grouped using balanced parentheses. Each term is true if the
|
|
|
|
|
corresponding macro exists, and false if it does not exist.</p>
|
|
|
|
|
|
|
|
|
|
<p>An optional "<tt>%else</tt>" directive can occur anywhere in between a
|
|
|
|
|
<tt>%ifdef</tt>, <tt>%ifndef</tt>, or <tt>%if</tt> directive and
|
|
|
|
|
its corresponding <tt>%endif</tt>.</p>
|
|
|
|
|
|
|
|
|
|
<p>Note that the argument to <tt>%ifdef</tt> and <tt>%ifndef</tt> is
|
|
|
|
|
intended to be a single preprocessor symbol name, not a general expression.
|
|
|
|
|
Use the "<tt>%if</tt>" directive for general expressions.</p>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='pinclude'></a>
|
|
|
|
|
<h4>4.4.9 The <tt>%include</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%include</tt> directive specifies C code that is included at the
|
|
|
|
|
top of the generated parser. You can include any text you want —
|
2011-05-06 02:37:34 +00:00
|
|
|
the Lemon parser generator copies it blindly. If you have multiple
|
2018-09-18 16:31:37 +00:00
|
|
|
<tt>%include</tt> directives in your grammar file, their values are concatenated
|
|
|
|
|
so that all <tt>%include</tt> code ultimately appears near the top of the
|
|
|
|
|
generated parser, in the same order as it appeared in the grammar.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%include</tt> directive is very handy for getting some extra #include
|
2011-05-06 02:37:34 +00:00
|
|
|
preprocessor statements at the beginning of the generated parser.
|
|
|
|
|
For example:</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%include {#include <unistd.h>}
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>This might be needed, for example, if some of the C actions in the
|
2018-09-18 16:31:37 +00:00
|
|
|
grammar call functions that are prototyped in unistd.h.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-12-13 00:43:10 +00:00
|
|
|
<p>Use the <tt><a href="#pcode">%code</a></tt> directive to add code to
|
|
|
|
|
the end of the generated parser.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='pleft'></a>
|
|
|
|
|
<h4>4.4.10 The <tt>%left</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
The <tt>%left</tt> directive is used (along with the
|
|
|
|
|
<tt><a href='#pright'>%right</a></tt> and
|
|
|
|
|
<tt><a href='#pnonassoc'>%nonassoc</a></tt> directives) to declare
|
|
|
|
|
precedences of terminal symbols.
|
|
|
|
|
Every terminal symbol whose name appears after
|
|
|
|
|
a <tt>%left</tt> directive but before the next period (".") is
|
2011-05-06 02:37:34 +00:00
|
|
|
given the same left-associative precedence value. Subsequent
|
2018-09-18 16:31:37 +00:00
|
|
|
<tt>%left</tt> directives have higher precedence. For example:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%left AND.
|
|
|
|
|
%left OR.
|
|
|
|
|
%nonassoc EQ NE GT GE LT LE.
|
|
|
|
|
%left PLUS MINUS.
|
|
|
|
|
%left TIMES DIVIDE MOD.
|
|
|
|
|
%right EXP NOT.
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>Note the period that terminates each <tt>%left</tt>,
|
|
|
|
|
<tt>%right</tt> or <tt>%nonassoc</tt>
|
2011-05-06 02:37:34 +00:00
|
|
|
directive.</p>
|
|
|
|
|
|
|
|
|
|
<p>LALR(1) grammars can get into a situation where they require
|
|
|
|
|
a large amount of stack space if you make heavy use or right-associative
|
2018-09-18 16:31:37 +00:00
|
|
|
operators. For this reason, it is recommended that you use <tt>%left</tt>
|
|
|
|
|
rather than <tt>%right</tt> whenever possible.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='pname'></a>
|
|
|
|
|
<h4>4.4.11 The <tt>%name</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>By default, the functions generated by Lemon all begin with the
|
2016-12-05 20:29:15 +00:00
|
|
|
five-character string "Parse". You can change this string to something
|
2018-09-18 16:31:37 +00:00
|
|
|
different using the <tt>%name</tt> directive. For instance:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%name Abcde
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>Putting this directive in the grammar file will cause Lemon to generate
|
2021-02-10 16:31:51 +00:00
|
|
|
functions named</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<ul>
|
|
|
|
|
<li> AbcdeAlloc(),
|
|
|
|
|
<li> AbcdeFree(),
|
|
|
|
|
<li> AbcdeTrace(), and
|
|
|
|
|
<li> Abcde().
|
|
|
|
|
</ul>
|
2021-02-10 16:31:51 +00:00
|
|
|
</p>The <tt>%name</tt> directive allows you to generate two or more different
|
2018-09-18 16:31:37 +00:00
|
|
|
parsers and link them all into the same executable.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='pnonassoc'></a>
|
|
|
|
|
<h4>4.4.12 The <tt>%nonassoc</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>This directive is used to assign non-associative precedence to
|
2018-09-18 16:31:37 +00:00
|
|
|
one or more terminal symbols. See the section on
|
2016-12-05 20:29:15 +00:00
|
|
|
<a href='#precrules'>precedence rules</a>
|
2018-09-18 16:31:37 +00:00
|
|
|
or on the <tt><a href='#pleft'>%left</a></tt> directive
|
|
|
|
|
for additional information.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='parse_accept'></a>
|
|
|
|
|
<h4>4.4.13 The <tt>%parse_accept</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%parse_accept</tt> directive specifies a block of C code that is
|
2016-12-05 20:29:15 +00:00
|
|
|
executed whenever the parser accepts its input string. To "accept"
|
2011-05-06 02:37:34 +00:00
|
|
|
an input string means that the parser was able to process all tokens
|
|
|
|
|
without error.</p>
|
|
|
|
|
|
|
|
|
|
<p>For example:</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%parse_accept {
|
|
|
|
|
printf("parsing complete!\n");
|
|
|
|
|
}
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='parse_failure'></a>
|
|
|
|
|
<h4>4.4.14 The <tt>%parse_failure</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%parse_failure</tt> directive specifies a block of C code that
|
2011-05-06 02:37:34 +00:00
|
|
|
is executed whenever the parser fails complete. This code is not
|
|
|
|
|
executed until the parser has tried and failed to resolve an input
|
|
|
|
|
error using is usual error recovery strategy. The routine is
|
|
|
|
|
only invoked when parsing is unable to continue.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%parse_failure {
|
|
|
|
|
fprintf(stderr,"Giving up. Parser is hopelessly lost...\n");
|
|
|
|
|
}
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='pright'></a>
|
|
|
|
|
<h4>4.4.15 The <tt>%right</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>This directive is used to assign right-associative precedence to
|
2018-09-18 16:31:37 +00:00
|
|
|
one or more terminal symbols. See the section on
|
2016-12-05 20:29:15 +00:00
|
|
|
<a href='#precrules'>precedence rules</a>
|
|
|
|
|
or on the <a href='#pleft'>%left</a> directive for additional information.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='stack_overflow'></a>
|
|
|
|
|
<h4>4.4.16 The <tt>%stack_overflow</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%stack_overflow</tt> directive specifies a block of C code that
|
2011-05-06 02:37:34 +00:00
|
|
|
is executed if the parser's internal stack ever overflows. Typically
|
|
|
|
|
this just prints an error message. After a stack overflow, the parser
|
|
|
|
|
will be unable to continue and must be reset.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%stack_overflow {
|
|
|
|
|
fprintf(stderr,"Giving up. Parser stack overflow\n");
|
|
|
|
|
}
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>You can help prevent parser stack overflows by avoiding the use
|
|
|
|
|
of right recursion and right-precedence operators in your grammar.
|
2018-09-18 16:31:37 +00:00
|
|
|
Use left recursion and and left-precedence operators instead to
|
2011-05-06 02:37:34 +00:00
|
|
|
encourage rules to reduce sooner and keep the stack size down.
|
2021-02-10 16:31:51 +00:00
|
|
|
For example, do rules like this:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
list ::= list element. // left-recursion. Good!
|
|
|
|
|
list ::= .
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>Not like this:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
list ::= element list. // right-recursion. Bad!
|
|
|
|
|
list ::= .
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='stack_size'></a>
|
|
|
|
|
<h4>4.4.17 The <tt>%stack_size</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>If stack overflow is a problem and you can't resolve the trouble
|
|
|
|
|
by using left-recursion, then you might want to increase the size
|
|
|
|
|
of the parser's stack using this directive. Put an positive integer
|
2018-09-18 16:31:37 +00:00
|
|
|
after the <tt>%stack_size</tt> directive and Lemon will generate a parse
|
2011-05-06 02:37:34 +00:00
|
|
|
with a stack of the requested size. The default value is 100.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%stack_size 2000
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='start_symbol'></a>
|
|
|
|
|
<h4>4.4.18 The <tt>%start_symbol</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>By default, the start symbol for the grammar that Lemon generates
|
2011-05-06 02:37:34 +00:00
|
|
|
is the first non-terminal that appears in the grammar file. But you
|
2018-09-18 16:31:37 +00:00
|
|
|
can choose a different start symbol using the
|
|
|
|
|
<tt>%start_symbol</tt> directive.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%start_symbol prog
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='syntax_error'></a>
|
|
|
|
|
<h4>4.4.19 The <tt>%syntax_error</tt> directive</h4>
|
2018-09-18 16:31:37 +00:00
|
|
|
|
2021-10-05 20:25:47 +00:00
|
|
|
<p>See <a href='#errors'>Error Processing</a>.</p>
|
|
|
|
|
|
|
|
|
|
<a id='token'></a>
|
|
|
|
|
<h4>4.4.20 The <tt>%token</tt> directive</h4>
|
|
|
|
|
|
|
|
|
|
<p>Tokens are normally created automatically, the first time they are used.
|
|
|
|
|
Any identifier that begins with an upper-case letter is a token.
|
|
|
|
|
|
|
|
|
|
<p>Sometimes it is useful to declare tokens in advance, however. The
|
|
|
|
|
integer values assigned to each token determined by the order in which
|
|
|
|
|
the tokens are seen. So by declaring tokens in advance, it is possible to
|
|
|
|
|
cause some tokens to have low-numbered values, which might be desirable in
|
|
|
|
|
some grammers, or to have sequential values assigned to a sequence of
|
|
|
|
|
related tokens. For this reason, the %token directive is provided to
|
|
|
|
|
declare tokens in advance. The syntax is as follows:
|
|
|
|
|
|
|
|
|
|
<blockquote>
|
|
|
|
|
<tt>%token</tt> <i>TOKEN</i> <i>TOKEN...</i> <b>.</b>
|
|
|
|
|
</blockquote></p>
|
|
|
|
|
|
|
|
|
|
<p>The %token directive is followed by zero or more token symbols and
|
|
|
|
|
terminated by a single ".". Each token named is created if it does not
|
|
|
|
|
already exist. Tokens are created in order.
|
|
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='token_class'></a>
|
2021-10-05 20:25:47 +00:00
|
|
|
<h4>4.4.21 The <tt>%token_class</tt> directive</h4>
|
2018-09-18 16:31:37 +00:00
|
|
|
|
|
|
|
|
<p>Undocumented. Appears to be related to the MULTITERMINAL concept.
|
|
|
|
|
<a href='http://sqlite.org/src/fdiff?v1=796930d5fc2036c7&v2=624b24c5dc048e09&sbs=0'>Implementation</a>.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='token_destructor'></a>
|
2021-10-05 20:25:47 +00:00
|
|
|
<h4>4.4.22 The <tt>%token_destructor</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%destructor</tt> directive assigns a destructor to a non-terminal
|
|
|
|
|
symbol. (See the description of the
|
|
|
|
|
<tt><a href='%destructor'>%destructor</a></tt> directive above.)
|
|
|
|
|
The <tt>%token_destructor</tt> directive does the same thing
|
|
|
|
|
for all terminal symbols.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>Unlike non-terminal symbols, which may each have a different data type
|
2011-05-06 02:37:34 +00:00
|
|
|
for their values, terminals all use the same data type (defined by
|
2018-09-18 16:31:37 +00:00
|
|
|
the <tt><a href='#token_type'>%token_type</a></tt> directive)
|
|
|
|
|
and so they use a common destructor.
|
|
|
|
|
Other than that, the token destructor works just like the non-terminal
|
2011-05-06 02:37:34 +00:00
|
|
|
destructors.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='token_prefix'></a>
|
2021-10-05 20:25:47 +00:00
|
|
|
<h4>4.4.23 The <tt>%token_prefix</tt> directive</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>Lemon generates #defines that assign small integer constants
|
|
|
|
|
to each terminal symbol in the grammar. If desired, Lemon will
|
|
|
|
|
add a prefix specified by this directive
|
2018-09-18 16:31:37 +00:00
|
|
|
to each of the #defines it generates.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>So if the default output of Lemon looked like this:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
#define AND 1
|
|
|
|
|
#define MINUS 2
|
|
|
|
|
#define OR 3
|
|
|
|
|
#define PLUS 4
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>You can insert a statement into the grammar like this:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
%token_prefix TOKEN_
|
|
|
|
|
</pre>
|
2021-02-10 16:31:51 +00:00
|
|
|
<p>to cause Lemon to produce these symbols instead:</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
<pre>
|
|
|
|
|
#define TOKEN_AND 1
|
|
|
|
|
#define TOKEN_MINUS 2
|
|
|
|
|
#define TOKEN_OR 3
|
|
|
|
|
#define TOKEN_PLUS 4
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='token_type'></a><a id='ptype'></a>
|
2021-10-05 20:25:47 +00:00
|
|
|
<h4>4.4.24 The <tt>%token_type</tt> and <tt>%type</tt> directives</h4>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>These directives are used to specify the data types for values
|
|
|
|
|
on the parser's stack associated with terminal and non-terminal
|
|
|
|
|
symbols. The values of all terminal symbols must be of the same
|
|
|
|
|
type. This turns out to be the same data type as the 3rd parameter
|
|
|
|
|
to the Parse() function generated by Lemon. Typically, you will
|
2020-05-24 11:23:38 +00:00
|
|
|
make the value of a terminal symbol be a pointer to some kind of
|
2011-05-06 02:37:34 +00:00
|
|
|
token structure. Like this:</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%token_type {Token*}
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>If the data type of terminals is not specified, the default value
|
2016-12-05 20:29:15 +00:00
|
|
|
is "void*".</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>Non-terminal symbols can each have their own data types. Typically
|
2018-09-18 16:31:37 +00:00
|
|
|
the data type of a non-terminal is a pointer to the root of a parse tree
|
2011-05-06 02:37:34 +00:00
|
|
|
structure that contains all information about that non-terminal.
|
|
|
|
|
For example:</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
%type expr {Expr*}
|
2021-02-10 16:31:51 +00:00
|
|
|
</pre>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>Each entry on the parser's stack is actually a union containing
|
|
|
|
|
instances of all data types for every non-terminal and terminal symbol.
|
|
|
|
|
Lemon will automatically use the correct element of this union depending
|
|
|
|
|
on what the corresponding non-terminal or terminal symbol is. But
|
|
|
|
|
the grammar designer should keep in mind that the size of the union
|
|
|
|
|
will be the size of its largest element. So if you have a single
|
|
|
|
|
non-terminal whose data type requires 1K of storage, then your 100
|
|
|
|
|
entry parser stack will require 100K of heap space. If you are willing
|
|
|
|
|
and able to pay that price, fine. You just need to know.</p>
|
|
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='pwildcard'></a>
|
2021-10-05 20:25:47 +00:00
|
|
|
<h4>4.4.25 The <tt>%wildcard</tt> directive</h4>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
2018-09-18 16:31:37 +00:00
|
|
|
<p>The <tt>%wildcard</tt> directive is followed by a single token name and a
|
|
|
|
|
period. This directive specifies that the identified token should
|
|
|
|
|
match any input token.</p>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
|
|
|
|
<p>When the generated parser has the choice of matching an input against
|
|
|
|
|
the wildcard token and some other token, the other token is always used.
|
2018-09-18 16:31:37 +00:00
|
|
|
The wildcard token is only matched if there are no alternatives.</p>
|
2016-12-05 20:29:15 +00:00
|
|
|
|
2021-10-05 20:25:47 +00:00
|
|
|
<a id='errors'></a>
|
2021-02-10 16:31:51 +00:00
|
|
|
<h2>5.0 Error Processing</h2>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
|
|
|
|
<p>After extensive experimentation over several years, it has been
|
|
|
|
|
discovered that the error recovery strategy used by yacc is about
|
|
|
|
|
as good as it gets. And so that is what Lemon uses.</p>
|
|
|
|
|
|
|
|
|
|
<p>When a Lemon-generated parser encounters a syntax error, it
|
2018-09-18 16:31:37 +00:00
|
|
|
first invokes the code specified by the <tt>%syntax_error</tt> directive, if
|
2011-05-06 02:37:34 +00:00
|
|
|
any. It then enters its error recovery strategy. The error recovery
|
|
|
|
|
strategy is to begin popping the parsers stack until it enters a
|
|
|
|
|
state where it is permitted to shift a special non-terminal symbol
|
2016-12-05 20:29:15 +00:00
|
|
|
named "error". It then shifts this non-terminal and continues
|
2018-09-18 16:31:37 +00:00
|
|
|
parsing. The <tt>%syntax_error</tt> routine will not be called again
|
2011-05-06 02:37:34 +00:00
|
|
|
until at least three new tokens have been successfully shifted.</p>
|
|
|
|
|
|
|
|
|
|
<p>If the parser pops its stack until the stack is empty, and it still
|
2018-09-18 16:31:37 +00:00
|
|
|
is unable to shift the error symbol, then the
|
|
|
|
|
<tt><a href='#parse_failure'>%parse_failure</a></tt> routine
|
2011-05-06 02:37:34 +00:00
|
|
|
is invoked and the parser resets itself to its start state, ready
|
|
|
|
|
to begin parsing a new file. This is what will happen at the very
|
2018-09-18 16:31:37 +00:00
|
|
|
first syntax error, of course, if there are no instances of the
|
2016-12-05 20:29:15 +00:00
|
|
|
"error" non-terminal in your grammar.</p>
|
2011-05-06 02:37:34 +00:00
|
|
|
|
2021-02-10 16:31:51 +00:00
|
|
|
<a id='history'></a>
|
|
|
|
|
<h2>6.0 History of Lemon</h2>
|
|
|
|
|
|
|
|
|
|
<p>Lemon was originally written by Richard Hipp sometime in the late
|
|
|
|
|
1980s on a Sun4 Workstation using K&R C.
|
|
|
|
|
There was a companion LL(1) parser generator program named "Lime", the
|
|
|
|
|
source code to which as been lost.</p>
|
|
|
|
|
|
|
|
|
|
<p>The lemon.c source file was originally many separate files that were
|
|
|
|
|
compiled together to generate the "lemon" executable. Sometime in the
|
|
|
|
|
1990s, the individual source code files were combined together into
|
|
|
|
|
the current single large "lemon.c" source file. You can still see traces
|
|
|
|
|
of original filenames in the code.</p>
|
|
|
|
|
|
|
|
|
|
<p>Since 2001, Lemon has been part of the
|
|
|
|
|
<a href="https://sqlite.org/">SQLite project</a> and the source code
|
|
|
|
|
to Lemon has been managed as a part of the
|
|
|
|
|
<a href="https://sqlite.org/src">SQLite source tree</a> in the following
|
|
|
|
|
files:</p>
|
|
|
|
|
|
|
|
|
|
<ul>
|
|
|
|
|
<li> <a href="https://sqlite.org/src/file/tool/lemon.c">tool/lemon.c</a>
|
|
|
|
|
<li> <a href="https://sqlite.org/src/file/tool/lempar.c">tool/lempar.c</a>
|
|
|
|
|
<li> <a href="https://sqlite.org/src/file/doc/lemon.html">doc/lemon.html</a>
|
|
|
|
|
</ul>
|
|
|
|
|
|
|
|
|
|
<a id="copyright"></a>
|
|
|
|
|
<h2>7.0 Copyright</h2>
|
|
|
|
|
|
|
|
|
|
<p>All of the source code to Lemon, including the template parser file
|
|
|
|
|
"lempar.c" and this documentation file ("lemon.html") are in the public
|
|
|
|
|
domain. You can use the code for any purpose and without attribution.</p>
|
|
|
|
|
|
|
|
|
|
<p>The code comes with no warranty. If it breaks, you get to keep both
|
|
|
|
|
pieces.</p>
|
|
|
|
|
|
2011-05-06 02:37:34 +00:00
|
|
|
</body>
|
|
|
|
|
</html>
|
