| 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> → |
| 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> → 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> → 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 |
|