summaryrefslogtreecommitdiffstats
path: root/www/lemon.html
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-13 14:07:11 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-13 14:07:11 +0000
commit63847496f14c813a5d80efd5b7de0f1294ffe1e3 (patch)
tree01c7571c7c762ceee70638549a99834fdd7c411b /www/lemon.html
parentInitial commit. (diff)
downloadsqlite3-63847496f14c813a5d80efd5b7de0f1294ffe1e3.tar.xz
sqlite3-63847496f14c813a5d80efd5b7de0f1294ffe1e3.zip
Adding upstream version 3.45.1.upstream/3.45.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'www/lemon.html')
-rw-r--r--www/lemon.html295
1 files changed, 295 insertions, 0 deletions
diff --git a/www/lemon.html b/www/lemon.html
new file mode 100644
index 0000000..0b01bdd
--- /dev/null
+++ b/www/lemon.html
@@ -0,0 +1,295 @@
+<!DOCTYPE html>
+<html><head>
+<meta name="viewport" content="width=device-width, initial-scale=1.0">
+<meta http-equiv="content-type" content="text/html; charset=UTF-8">
+<link href="sqlite.css" rel="stylesheet">
+<title>The Lemon LALR(1) Parser Generator</title>
+<!-- path= -->
+</head>
+<body>
+<div class=nosearch>
+<a href="index.html">
+<img class="logo" src="images/sqlite370_banner.gif" alt="SQLite" border="0">
+</a>
+<div><!-- IE hack to prevent disappearing logo --></div>
+<div class="tagline desktoponly">
+Small. Fast. Reliable.<br>Choose any three.
+</div>
+<div class="menu mainmenu">
+<ul>
+<li><a href="index.html">Home</a>
+<li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
+<li class='wideonly'><a href='about.html'>About</a>
+<li class='desktoponly'><a href="docs.html">Documentation</a>
+<li class='desktoponly'><a href="download.html">Download</a>
+<li class='wideonly'><a href='copyright.html'>License</a>
+<li class='desktoponly'><a href="support.html">Support</a>
+<li class='desktoponly'><a href="prosupport.html">Purchase</a>
+<li class='search' id='search_menubutton'>
+<a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
+</ul>
+</div>
+<div class="menu submenu" id="submenu">
+<ul>
+<li><a href='about.html'>About</a>
+<li><a href='docs.html'>Documentation</a>
+<li><a href='download.html'>Download</a>
+<li><a href='support.html'>Support</a>
+<li><a href='prosupport.html'>Purchase</a>
+</ul>
+</div>
+<div class="searchmenu" id="searchmenu">
+<form method="GET" action="search">
+<select name="s" id="searchtype">
+<option value="d">Search Documentation</option>
+<option value="c">Search Changelog</option>
+</select>
+<input type="text" name="q" id="searchbox" value="">
+<input type="submit" value="Go">
+</form>
+</div>
+</div>
+<script>
+function toggle_div(nm) {
+var w = document.getElementById(nm);
+if( w.style.display=="block" ){
+w.style.display = "none";
+}else{
+w.style.display = "block";
+}
+}
+function toggle_search() {
+var w = document.getElementById("searchmenu");
+if( w.style.display=="block" ){
+w.style.display = "none";
+} else {
+w.style.display = "block";
+setTimeout(function(){
+document.getElementById("searchbox").focus()
+}, 30);
+}
+}
+function div_off(nm){document.getElementById(nm).style.display="none";}
+window.onbeforeunload = function(e){div_off("submenu");}
+/* Disable the Search feature if we are not operating from CGI, since */
+/* Search is accomplished using CGI and will not work without it. */
+if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
+document.getElementById("search_menubutton").style.display = "none";
+}
+/* Used by the Hide/Show button beside syntax diagrams, to toggle the */
+function hideorshow(btn,obj){
+var x = document.getElementById(obj);
+var b = document.getElementById(btn);
+if( x.style.display!='none' ){
+x.style.display = 'none';
+b.innerHTML='show';
+}else{
+x.style.display = '';
+b.innerHTML='hide';
+}
+return false;
+}
+var antiRobot = 0;
+function antiRobotGo(){
+if( antiRobot!=3 ) return;
+antiRobot = 7;
+var j = document.getElementById("mtimelink");
+if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
+}
+function antiRobotDefense(){
+document.body.onmousedown=function(){
+antiRobot |= 2;
+antiRobotGo();
+document.body.onmousedown=null;
+}
+document.body.onmousemove=function(){
+antiRobot |= 2;
+antiRobotGo();
+document.body.onmousemove=null;
+}
+setTimeout(function(){
+antiRobot |= 1;
+antiRobotGo();
+}, 100)
+antiRobotGo();
+}
+antiRobotDefense();
+</script>
+<div class=fancy>
+<div class=nosearch>
+<div class="fancy_title">
+The Lemon LALR(1) Parser Generator
+</div>
+<div class="fancy_toc">
+<a onclick="toggle_toc()">
+<span class="fancy_toc_mark" id="toc_mk">&#x25ba;</span>
+Table Of Contents
+</a>
+<div id="toc_sub"><div class="fancy-toc1"><a href="#overview">1. Overview</a></div>
+<div class="fancy-toc2"><a href="#lemon_source_files_and_documentation">1.1. Lemon Source Files And Documentation</a></div>
+<div class="fancy-toc1"><a href="#advantages_of_lemon">2. Advantages of Lemon</a></div>
+<div class="fancy-toc2"><a href="#use_of_lemon_within_sqlite">2.1. Use of Lemon Within SQLite</a></div>
+<div class="fancy-toc2"><a href="#lemon_customizations_especially_for_sqlite">2.2. Lemon Customizations Especially For SQLite</a></div>
+<div class="fancy-toc1"><a href="#history_of_lemon">3. History Of Lemon</a></div>
+</div>
+</div>
+<script>
+function toggle_toc(){
+var sub = document.getElementById("toc_sub")
+var mk = document.getElementById("toc_mk")
+if( sub.style.display!="block" ){
+sub.style.display = "block";
+mk.innerHTML = "&#x25bc;";
+} else {
+sub.style.display = "none";
+mk.innerHTML = "&#x25ba;";
+}
+}
+</script>
+</div>
+
+
+
+
+
+<h1 id="overview"><span>1. </span>Overview</h1>
+
+<p>The SQL language parser for SQLite is generated using a code-generator
+program called "Lemon". The Lemon program reads a grammar of the input
+language and emits C-code to implement a parser for that language.
+
+
+</p><h2 id="lemon_source_files_and_documentation"><span>1.1. </span>Lemon Source Files And Documentation</h2>
+
+<p>Lemon does not have its own source repository. Rather, Lemon consists
+of a few files in the SQLite source tree:
+
+</p><ul>
+<li><p>
+ <a href="https://sqlite.org/src/doc/trunk/doc/lemon.html">lemon.html</a> &rarr;
+ The original detailed usage documentation and programmers reference
+ for Lemon.
+</p></li><li><p>
+ <a href="https://sqlite.org/src/file/tool/lemon.c">lemon.c</a> &rarr; The source code
+ for the utility program that reads a grammar file and generates
+ corresponding parser C-code.
+</p></li><li><p>
+ <a href="https://sqlite.org/src/file/tool/lempar.c">lempar.c</a> &rarr; A template
+ for the generated parser C-code. The "lemon" utility program reads this
+ template and inserts additional code in order to generate a parser.
+</p></li></ul>
+
+<h1 id="advantages_of_lemon"><span>2. </span>Advantages of Lemon</h1>
+
+<p>Lemon generates an LALR(1) parser. Its operation is similar to the
+more familiar tools <a href="https://en.wikipedia.org/wiki/Yacc">Yacc</a> and
+<a href="https://en.wikipedia.org/wiki/GNU_bison">Bison</a>, but Lemon adds important
+improvements, including:
+
+</p><ul>
+<li><p>
+ The grammar syntax is less error prone - using symbolic names for
+ semantic values rather that the "$1"-style positional notation
+ of Yacc.
+</p></li><li><p>
+ In Lemon, the tokenizer calls the parser. Yacc operates the other
+ way around, with the parser calling the tokenizer. The Lemon
+ approach is reentrant and threadsafe, whereas Yacc uses global
+ variables and is therefore neither. Reentrancy is especially
+ important for SQLite since some SQL statements make recursive calls
+ to the parser. For example, when parsing a CREATE TABLE statement,
+ SQLite invokes the parser recursively to generate an INSERT statement
+ to make a new entry in the <a href="schematab.html">sqlite_schema</a> table.
+</p></li><li><p>
+ Lemon has the concept of a non-terminal destructor that can be
+ used to reclaim memory or other resources following a syntax error
+ or other aborted parse.
+</p></li></ul>
+
+<h2 id="use_of_lemon_within_sqlite"><span>2.1. </span>Use of Lemon Within SQLite</h2>
+
+<p>Lemon is used in two places in SQLite.
+
+</p><p>The primary use of Lemon is to create the SQL language parser.
+A grammar file (<a href="https://sqlite.org/src/file/src/parse.y">parse.y</a>) is
+compiled by Lemon into parse.c and parse.h. The parse.c file is
+incorporated into the <a href="amalgamation.html">amalgamation</a> without further modification.
+
+</p><p>Lemon is also used to generate the parser for the query pattern
+expressions in the <a href="fts5.html">FTS5</a> extension. In this case, the input grammar
+file is <a href="https://sqlite.org/src/file/ext/fts5/fts5parse.y">fts5parse.y</a>.
+
+</p><h2 id="lemon_customizations_especially_for_sqlite"><span>2.2. </span>Lemon Customizations Especially For SQLite</h2>
+
+<p>One of the advantages of hosting code generator tools as part of
+the project is that the tools can be optimized to serve specific needs of
+the overall project. Lemon has benefited from this effect. Over the years,
+the Lemon parser generator has been extended and enhanced to provide
+new capabilities and improved performance to SQLite. A few of the
+specific enhancements to Lemon that are specifically designed for use
+by SQLite include:
+
+</p><ul>
+<li><p>
+Lemon has the concept of a "fallback" token.
+The SQL language contains a large number of keywords and these keywords
+have the potential to collide with identifier names.
+Lemon has the ability to designate some keywords as being able to
+"fallback" to an identifier. If the keyword appears in the input token
+stream in a context that would otherwise be a syntax error, the token
+is automatically transformed into its fallback before the syntax error
+is raised. This feature allows the parser to be very forgiving of
+reserved words used as identifiers, which is a problem that comes up
+frequently in the SQL language.
+
+</p></li><li><p>
+In support of the <a href="testing.html#mcdc">100% MC/DC testing</a> goal for SQLite,
+the parser code generated by Lemon has no unreachable branches,
+and contains extra (compile-time selected) instrumentation useful
+for measuring test coverage.
+
+</p></li><li><p>
+Lemon supports conditional compilation of grammar file rules, so that
+a different parser can be generated depending on compile-time options.
+
+</p></li><li><p>
+As a performance optimization, reduce actions in the Lemon input grammar
+are allowed to contain comments of the form "/*A-overwrites-Z*/" to indicate
+that the semantic value "A" on the right-hand side of the rule is allowed
+to directly overwrite the semantic value "Z" on the left-hand side.
+This simple optimization reduces the number of stack operations in the
+push-down automaton used to parse the input grammar, and thus improve
+performance of the parser. It also makes the generated code a little smaller.
+</p></li></ul>
+
+<p>The parsing of SQL statements is a significant consumer of CPU cycles
+in any SQL database engine. On-going efforts to optimize SQLite have caused
+the developers to spend a lot of time tweaking Lemon to generate faster
+parsers. These efforts have benefited all users of the Lemon parser generator,
+not just SQLite. But if Lemon had been a separately maintained tool, it
+would have been more difficult to make coordinated changes to both SQLite
+and Lemon, and as a result not as much optimization would have been
+accomplished. Hence, the fact that the parser generator tool is included
+in the source tree for SQLite has turned out to be a net benefit for both
+the tool itself and for SQLite.
+
+</p><h1 id="history_of_lemon"><span>3. </span>History Of Lemon</h1>
+
+<p>Lemon was originally written by D. Richard Hipp (also the creator of SQLite)
+while he was in graduate school at Duke University between 1987 and 1992.
+The original creation date of Lemon has been lost, but was probably sometime
+around 1990. Lemon generates an LALR(1) parser. There was a companion
+LL(1) parser generator tool named "Lime", but the source code for Lime
+has been lost.
+
+</p><p>The Lemon source code was originally written as separate source files,
+and only later merged into a single "lemon.c" source file.
+
+</p><p>The author of Lemon and SQLite (Hipp) reports that his C programming
+skills were greatly enhanced by studying John Ousterhout's original
+source code to Tcl. Hipp discovered and studied Tcl in 1993. Lemon
+was written before then, and SQLite afterwards. There is a clear
+difference in the coding styles of these two products, with SQLite seeming
+to be cleaner, more readable, and easier to maintain.
+</p><p align="center"><small><i>This page last modified on <a href="https://sqlite.org/docsrc/honeypot" id="mtimelink" data-href="https://sqlite.org/docsrc/finfo/pages/lemon.in?m=b11f8f15fd">2022-04-18 02:55:50</a> UTC </small></i></p>
+