Debian Codegraph @

www/lemon.html

raw
1 <!DOCTYPE html>
2 <html><head>
3 <meta name="viewport" content="width=device-width, initial-scale=1.0">
4 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
5 <link href="sqlite.css" rel="stylesheet">
6 <title>The Lemon LALR(1) Parser Generator</title>
7 <!-- path= -->
8 </head>
9 <body>
10 <div class=nosearch>
11 <a href="index.html">
12 <img class="logo" src="images/sqlite370_banner.svg" alt="SQLite" border="0">
13 </a>
14 <div><!-- IE hack to prevent disappearing logo --></div>
15 <div class="tagline desktoponly">
16 Small. Fast. Reliable.<br>Choose any three.
17 </div>
18 <div class="menu mainmenu">
19 <ul>
20 <li><a href="index.html">Home</a>
21 <li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
22 <li class='wideonly'><a href='about.html'>About</a>
23 <li class='desktoponly'><a href="docs.html">Documentation</a>
24 <li class='desktoponly'><a href="download.html">Download</a>
25 <li class='wideonly'><a href='copyright.html'>License</a>
26 <li class='desktoponly'><a href="support.html">Support</a>
27 <li class='desktoponly'><a href="prosupport.html">Purchase</a>
28 <li class='search' id='search_menubutton'>
29 <a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
30 </ul>
31 </div>
32 <div class="menu submenu" id="submenu">
33 <ul>
34 <li><a href='about.html'>About</a>
35 <li><a href='docs.html'>Documentation</a>
36 <li><a href='download.html'>Download</a>
37 <li><a href='support.html'>Support</a>
38 <li><a href='prosupport.html'>Purchase</a>
39 </ul>
40 </div>
41 <div class="searchmenu" id="searchmenu">
42 <form method="GET" action="search">
43 <select name="s" id="searchtype">
44 <option value="d">Search Documentation</option>
45 <option value="c">Search Changelog</option>
46 </select>
47 <input type="text" name="q" id="searchbox" value="">
48 <input type="submit" value="Go">
49 </form>
50 </div>
51 </div>
52 <script>
53 function toggle_div(nm) {
54 var w = document.getElementById(nm);
55 if( w.style.display=="block" ){
56 w.style.display = "none";
57 }else{
58 w.style.display = "block";
59 }
60 }
61 function toggle_search() {
62 var w = document.getElementById("searchmenu");
63 if( w.style.display=="block" ){
64 w.style.display = "none";
65 } else {
66 w.style.display = "block";
67 setTimeout(function(){
68 document.getElementById("searchbox").focus()
69 }, 30);
70 }
71 }
72 function div_off(nm){document.getElementById(nm).style.display="none";}
73 window.onbeforeunload = function(e){div_off("submenu");}
74 /* Disable the Search feature if we are not operating from CGI, since */
75 /* Search is accomplished using CGI and will not work without it. */
76 if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
77 document.getElementById("search_menubutton").style.display = "none";
78 }
79 /* Used by the Hide/Show button beside syntax diagrams, to toggle the */
80 function hideorshow(btn,obj){
81 var x = document.getElementById(obj);
82 var b = document.getElementById(btn);
83 if( x.style.display!='none' ){
84 x.style.display = 'none';
85 b.innerHTML='show';
86 }else{
87 x.style.display = '';
88 b.innerHTML='hide';
89 }
90 return false;
91 }
92 var antiRobot = 0;
93 function antiRobotGo(){
94 if( antiRobot!=3 ) return;
95 antiRobot = 7;
96 var j = document.getElementById("mtimelink");
97 if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
98 }
99 function antiRobotDefense(){
100 document.body.onmousedown=function(){
101 antiRobot |= 2;
102 antiRobotGo();
103 document.body.onmousedown=null;
104 }
105 document.body.onmousemove=function(){
106 antiRobot |= 2;
107 antiRobotGo();
108 document.body.onmousemove=null;
109 }
110 setTimeout(function(){
111 antiRobot |= 1;
112 antiRobotGo();
113 }, 100)
114 antiRobotGo();
115 }
116 antiRobotDefense();
117 </script>
118 <div class=fancy>
119 <div class=nosearch>
120 <div class="fancy_title">
121 The Lemon LALR(1) Parser Generator
122 </div>
123 <details class="fancy_toc">
124 <summary>Table Of Contents</summary>
125 <div id="toc_sub"><div class="fancy-toc1"><a href="#overview">1. Overview</a></div>
126 <div class="fancy-toc2"><a href="#lemon_source_files_and_documentation">1.1. Lemon Source Files And Documentation</a></div>
127 <div class="fancy-toc1"><a href="#advantages_of_lemon">2. Advantages of Lemon</a></div>
128 <div class="fancy-toc2"><a href="#use_of_lemon_within_sqlite">2.1. Use of Lemon Within SQLite</a></div>
129 <div class="fancy-toc2"><a href="#lemon_customizations_especially_for_sqlite">2.2. Lemon Customizations Especially For SQLite</a></div>
130 <div class="fancy-toc1"><a href="#history_of_lemon">3. History Of Lemon</a></div>
131 </div>
132 </details>
133 </div>
134
135
136
137
138
139 <h1 id="overview"><span>1. </span>Overview</h1>
140
141 <p>The SQL language parser for SQLite is generated using a code-generator
142 program called "Lemon". The Lemon program reads a grammar of the input
143 language and emits C-code to implement a parser for that language.
144
145
146 </p><h2 id="lemon_source_files_and_documentation"><span>1.1. </span>Lemon Source Files And Documentation</h2>
147
148 <p>Lemon does not have its own source repository. Rather, Lemon consists
149 of a few files in the SQLite source tree:
150
151 </p><ul>
152 <li><p>
153 <a href="https://sqlite.org/src/doc/trunk/doc/lemon.html">lemon.html</a> &rarr;
154 The original detailed usage documentation and programmers reference
155 for Lemon.
156 </p></li><li><p>
157 <a href="https://sqlite.org/src/file/tool/lemon.c">lemon.c</a> &rarr; The source code
158 for the utility program that reads a grammar file and generates
159 corresponding parser C-code.
160 </p></li><li><p>
161 <a href="https://sqlite.org/src/file/tool/lempar.c">lempar.c</a> &rarr; A template
162 for the generated parser C-code. The "lemon" utility program reads this
163 template and inserts additional code in order to generate a parser.
164 </p></li></ul>
165
166 <h1 id="advantages_of_lemon"><span>2. </span>Advantages of Lemon</h1>
167
168 <p>Lemon generates an LALR(1) parser. Its operation is similar to the
169 more familiar tools <a href="https://en.wikipedia.org/wiki/Yacc">Yacc</a> and
170 <a href="https://en.wikipedia.org/wiki/GNU_bison">Bison</a>, but Lemon adds important
171 improvements, including:
172
173 </p><ul>
174 <li><p>
175 The grammar syntax is less error prone - using symbolic names for
176 semantic values rather that the "$1"-style positional notation
177 of Yacc.
178 </p></li><li><p>
179 In Lemon, the tokenizer calls the parser. Yacc operates the other
180 way around, with the parser calling the tokenizer. The Lemon
181 approach is reentrant and threadsafe, whereas Yacc uses global
182 variables and is therefore neither. Reentrancy is especially
183 important for SQLite since some SQL statements make recursive calls
184 to the parser. For example, when parsing a CREATE TABLE statement,
185 SQLite invokes the parser recursively to generate an INSERT statement
186 to make a new entry in the <a href="schematab.html">sqlite_schema</a> table.
187 </p></li><li><p>
188 Lemon has the concept of a non-terminal destructor that can be
189 used to reclaim memory or other resources following a syntax error
190 or other aborted parse.
191 </p></li></ul>
192
193 <h2 id="use_of_lemon_within_sqlite"><span>2.1. </span>Use of Lemon Within SQLite</h2>
194
195 <p>Lemon is used in two places in SQLite.
196
197 </p><p>The primary use of Lemon is to create the SQL language parser.
198 A grammar file (<a href="https://sqlite.org/src/file/src/parse.y">parse.y</a>) is
199 compiled by Lemon into parse.c and parse.h. The parse.c file is
200 incorporated into the <a href="amalgamation.html">amalgamation</a> without further modification.
201
202 </p><p>Lemon is also used to generate the parser for the query pattern
203 expressions in the <a href="fts5.html">FTS5</a> extension. In this case, the input grammar
204 file is <a href="https://sqlite.org/src/file/ext/fts5/fts5parse.y">fts5parse.y</a>.
205
206 </p><h2 id="lemon_customizations_especially_for_sqlite"><span>2.2. </span>Lemon Customizations Especially For SQLite</h2>
207
208 <p>One of the advantages of hosting code generator tools as part of
209 the project is that the tools can be optimized to serve specific needs of
210 the overall project. Lemon has benefited from this effect. Over the years,
211 the Lemon parser generator has been extended and enhanced to provide
212 new capabilities and improved performance to SQLite. A few of the
213 specific enhancements to Lemon that are specifically designed for use
214 by SQLite include:
215
216 </p><ul>
217 <li><p>
218 Lemon has the concept of a "fallback" token.
219 The SQL language contains a large number of keywords and these keywords
220 have the potential to collide with identifier names.
221 Lemon has the ability to designate some keywords as being able to
222 "fallback" to an identifier. If the keyword appears in the input token
223 stream in a context that would otherwise be a syntax error, the token
224 is automatically transformed into its fallback before the syntax error
225 is raised. This feature allows the parser to be very forgiving of
226 reserved words used as identifiers, which is a problem that comes up
227 frequently in the SQL language.
228
229 </p></li><li><p>
230 In support of the <a href="testing.html#mcdc">100% MC/DC testing</a> goal for SQLite,
231 the parser code generated by Lemon has no unreachable branches,
232 and contains extra (compile-time selected) instrumentation useful
233 for measuring test coverage.
234
235 </p></li><li><p>
236 Lemon supports conditional compilation of grammar file rules, so that
237 a different parser can be generated depending on compile-time options.
238
239 </p></li><li><p>
240 As a performance optimization, reduce actions in the Lemon input grammar
241 are allowed to contain comments of the form "/*A-overwrites-Z*/" to indicate
242 that the semantic value "A" on the right-hand side of the rule is allowed
243 to directly overwrite the semantic value "Z" on the left-hand side.
244 This simple optimization reduces the number of stack operations in the
245 push-down automaton used to parse the input grammar, and thus improve
246 performance of the parser. It also makes the generated code a little smaller.
247 </p></li></ul>
248
249 <p>The parsing of SQL statements is a significant consumer of CPU cycles
250 in any SQL database engine. On-going efforts to optimize SQLite have caused
251 the developers to spend a lot of time tweaking Lemon to generate faster
252 parsers. These efforts have benefited all users of the Lemon parser generator,
253 not just SQLite. But if Lemon had been a separately maintained tool, it
254 would have been more difficult to make coordinated changes to both SQLite
255 and Lemon, and as a result not as much optimization would have been
256 accomplished. Hence, the fact that the parser generator tool is included
257 in the source tree for SQLite has turned out to be a net benefit for both
258 the tool itself and for SQLite.
259
260 </p><h1 id="history_of_lemon"><span>3. </span>History Of Lemon</h1>
261
262 <p>Lemon was originally written by D. Richard Hipp (also the creator of SQLite)
263 while he was in graduate school at Duke University between 1987 and 1992.
264 The original creation date of Lemon has been lost, but was probably sometime
265 around 1990. Lemon generates an LALR(1) parser. There was a companion
266 LL(1) parser generator tool named "Lime", but the source code for Lime
267 has been lost.
268
269 </p><p>The Lemon source code was originally written as separate source files,
270 and only later merged into a single "lemon.c" source file.
271
272 </p><p>The author of Lemon and SQLite (Hipp) reports that his C programming
273 skills were greatly enhanced by studying John Ousterhout's original
274 source code to Tcl. Hipp discovered and studied Tcl in 1993. Lemon
275 was written before then, and SQLite afterwards. There is a clear
276 difference in the coding styles of these two products, with SQLite seeming
277 to be cleaner, more readable, and easier to maintain.
278 </p><p align="center"><small><i>This page was last updated on 2022-04-18 02:55:50Z </small></i></p>
279