Blame - doc/lemon.html - chromium.googlesource.com/chromium/deps/sqlite

blob: 114526f372ca8b870eb5cf3d1d6fa8d38268c6b1 [file] [log] [blame]

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