Artifact afbdb32535d14665db065052cb0c9f37f76ef5235b23af7d3bb17645bc98721b:
- File
pages/lemon.in
— part of check-in
[62f434c8b8]
at
2018-01-22 17:53:36
on branch trunk
— Fix typos in the lemon.html document.
(user:
drh
size: 6766)
0000: 3c 74 69 74 6c 65 3e 54 68 65 20 4c 65 6d 6f 6e <title>The Lemon
0010: 20 4c 41 4c 52 28 31 29 20 50 61 72 73 65 72 20 LALR(1) Parser
0020: 47 65 6e 65 72 61 74 6f 72 3c 2f 74 69 74 6c 65 Generator</title
0030: 3e 0a 3c 74 63 6c 3e 68 64 5f 6b 65 79 77 6f 72 >.<tcl>hd_keywor
0040: 64 73 20 7b 4c 65 6d 6f 6e 20 70 61 72 73 65 72 ds {Lemon parser
0050: 20 67 65 6e 65 72 61 74 6f 72 7d 20 7b 4c 65 6d generator} {Lem
0060: 6f 6e 7d 20 5c 0a 20 20 20 20 20 20 20 20 20 20 on} \.
0070: 20 20 20 20 20 20 20 7b 4c 65 6d 6f 6e 20 4c 41 {Lemon LA
0080: 4c 52 20 70 61 72 73 65 72 20 67 65 6e 65 72 61 LR parser genera
0090: 74 6f 72 7d 3c 2f 74 63 6c 3e 0a 0a 3c 74 61 62 tor}</tcl>..<tab
00a0: 6c 65 5f 6f 66 5f 63 6f 6e 74 65 6e 74 73 3e 0a le_of_contents>.
00b0: 0a 3c 68 31 3e 4f 76 65 72 76 69 65 77 3c 2f 68 .<h1>Overview</h
00c0: 31 3e 0a 0a 3c 70 3e 54 68 65 20 53 51 4c 20 6c 1>..<p>The SQL l
00d0: 61 6e 67 75 61 67 65 20 70 61 72 73 65 72 20 66 anguage parser f
00e0: 6f 72 20 53 51 4c 69 74 65 20 69 73 20 67 65 6e or SQLite is gen
00f0: 65 72 61 74 65 64 20 75 73 69 6e 67 20 61 20 63 erated using a c
0100: 6f 64 65 2d 67 65 6e 65 72 61 74 6f 72 0a 70 72 ode-generator.pr
0110: 6f 67 72 61 6d 20 63 61 6c 6c 65 64 20 22 4c 65 ogram called "Le
0120: 6d 6f 6e 22 2e 20 20 54 68 65 20 4c 65 6d 6f 6e mon". The Lemon
0130: 20 70 72 6f 67 72 61 6d 20 72 65 61 64 73 20 61 program reads a
0140: 20 67 72 61 6d 6d 61 72 20 6f 66 20 74 68 65 20 grammar of the
0150: 69 6e 70 75 74 0a 6c 61 6e 67 75 61 67 65 20 61 input.language a
0160: 6e 64 20 65 6d 69 74 73 20 43 2d 63 6f 64 65 20 nd emits C-code
0170: 74 6f 20 69 6d 70 6c 65 6d 65 6e 74 20 61 20 70 to implement a p
0180: 61 72 73 65 72 20 66 6f 72 20 74 68 61 74 20 6c arser for that l
0190: 61 6e 67 75 61 67 65 2e 0a 0a 0a 3c 68 32 3e 4c anguage....<h2>L
01a0: 65 6d 6f 6e 20 53 6f 75 72 63 65 20 46 69 6c 65 emon Source File
01b0: 73 20 41 6e 64 20 44 6f 63 75 6d 65 6e 74 61 74 s And Documentat
01c0: 69 6f 6e 3c 2f 68 32 3e 0a 0a 3c 70 3e 4c 65 6d ion</h2>..<p>Lem
01d0: 6f 6e 20 64 6f 65 73 20 6e 6f 74 20 68 61 76 65 on does not have
01e0: 20 69 74 73 20 6f 77 6e 20 73 6f 75 72 63 65 20 its own source
01f0: 72 65 70 6f 73 69 74 6f 72 79 2e 20 20 52 61 74 repository. Rat
0200: 68 65 72 2c 20 4c 65 6d 6f 6e 20 63 6f 6e 73 69 her, Lemon consi
0210: 73 74 73 0a 6f 66 20 61 20 66 65 77 20 66 69 6c sts.of a few fil
0220: 65 73 20 69 6e 20 74 68 65 20 53 51 4c 69 74 65 es in the SQLite
0230: 20 73 6f 75 72 63 65 20 74 72 65 65 3a 0a 0a 3c source tree:..<
0240: 75 6c 3e 0a 3c 6c 69 3e 3c 70 3e 0a 20 20 20 20 ul>.<li><p>.
0250: 20 5b 68 74 74 70 73 3a 2f 2f 73 71 6c 69 74 65 [https://sqlite
0260: 2e 6f 72 67 2f 73 72 63 2f 64 6f 63 2f 74 72 75 .org/src/doc/tru
0270: 6e 6b 2f 64 6f 63 2f 6c 65 6d 6f 6e 2e 68 74 6d nk/doc/lemon.htm
0280: 6c 7c 6c 65 6d 6f 6e 2e 68 74 6d 6c 5d 20 26 72 l|lemon.html] &r
0290: 61 72 72 3b 0a 20 20 20 20 20 54 68 65 20 6f 72 arr;. The or
02a0: 69 67 69 6e 61 6c 20 64 65 74 61 69 6c 65 64 20 iginal detailed
02b0: 75 73 61 67 65 20 64 6f 63 75 6d 65 6e 74 61 74 usage documentat
02c0: 69 6f 6e 20 61 6e 64 20 70 72 6f 67 72 61 6d 6d ion and programm
02d0: 65 72 73 20 72 65 66 65 72 65 6e 63 65 0a 20 20 ers reference.
02e0: 20 20 20 66 6f 72 20 4c 65 6d 6f 6e 2e 0a 3c 6c for Lemon..<l
02f0: 69 3e 3c 70 3e 0a 20 20 20 20 20 5b 68 74 74 70 i><p>. [http
0300: 73 3a 2f 2f 73 71 6c 69 74 65 2e 6f 72 67 2f 73 s://sqlite.org/s
0310: 72 63 2f 66 69 6c 65 2f 74 6f 6f 6c 2f 6c 65 6d rc/file/tool/lem
0320: 6f 6e 2e 63 7c 6c 65 6d 6f 6e 2e 63 5d 20 26 72 on.c|lemon.c] &r
0330: 61 72 72 3b 20 54 68 65 20 73 6f 75 72 63 65 20 arr; The source
0340: 63 6f 64 65 0a 20 20 20 20 20 66 6f 72 20 74 68 code. for th
0350: 65 20 75 74 69 6c 69 74 79 20 70 72 6f 67 72 61 e utility progra
0360: 6d 20 74 68 61 74 20 72 65 61 64 73 20 61 20 67 m that reads a g
0370: 72 61 6d 6d 61 72 20 66 69 6c 65 20 61 6e 64 20 rammar file and
0380: 67 65 6e 65 72 61 74 65 73 20 0a 20 20 20 20 20 generates .
0390: 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 70 61 corresponding pa
03a0: 72 73 65 72 20 43 2d 63 6f 64 65 2e 0a 3c 6c 69 rser C-code..<li
03b0: 3e 3c 70 3e 0a 20 20 20 20 20 5b 68 74 74 70 73 ><p>. [https
03c0: 3a 2f 2f 73 71 6c 69 74 65 2e 6f 72 67 2f 73 72 ://sqlite.org/sr
03d0: 63 2f 66 69 6c 65 2f 74 6f 6f 6c 2f 6c 65 6d 70 c/file/tool/lemp
03e0: 61 72 2e 63 7c 6c 65 6d 70 61 72 2e 63 5d 20 26 ar.c|lempar.c] &
03f0: 72 61 72 72 3b 20 41 20 74 65 6d 70 6c 61 74 65 rarr; A template
0400: 0a 20 20 20 20 20 66 6f 72 20 74 68 65 20 67 65 . for the ge
0410: 6e 65 72 61 74 65 64 20 70 61 72 73 65 72 20 43 nerated parser C
0420: 2d 63 6f 64 65 2e 20 20 54 68 65 20 22 6c 65 6d -code. The "lem
0430: 6f 6e 22 20 75 74 69 6c 69 74 79 20 70 72 6f 67 on" utility prog
0440: 72 61 6d 20 72 65 61 64 73 20 74 68 69 73 0a 20 ram reads this.
0450: 20 20 20 20 74 65 6d 70 6c 61 74 65 20 61 6e 64 template and
0460: 20 69 6e 73 65 72 74 73 20 61 64 64 69 74 69 6f inserts additio
0470: 6e 61 6c 20 63 6f 64 65 20 69 6e 20 6f 72 64 65 nal code in orde
0480: 72 20 74 6f 20 67 65 6e 65 72 61 74 65 20 61 20 r to generate a
0490: 70 61 72 73 65 72 2e 0a 3c 2f 75 6c 3e 0a 0a 3c parser..</ul>..<
04a0: 68 31 3e 41 64 76 61 6e 74 61 67 65 73 20 6f 66 h1>Advantages of
04b0: 20 4c 65 6d 6f 6e 3c 2f 68 31 3e 0a 0a 3c 70 3e Lemon</h1>..<p>
04c0: 4c 65 6d 6f 6e 20 67 65 6e 65 72 61 74 65 73 20 Lemon generates
04d0: 61 6e 20 4c 41 4c 52 28 31 29 20 70 61 72 73 65 an LALR(1) parse
04e0: 72 2e 20 20 49 74 27 73 20 6f 70 65 72 61 74 69 r. It's operati
04f0: 6f 6e 20 69 73 20 73 69 6d 69 6c 61 72 20 74 6f on is similar to
0500: 20 74 68 65 0a 6d 6f 72 65 20 66 61 6d 69 6c 69 the.more famili
0510: 61 72 20 74 6f 6f 6c 73 20 5b 68 74 74 70 73 3a ar tools [https:
0520: 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e 6f //en.wikipedia.o
0530: 72 67 2f 77 69 6b 69 2f 59 61 63 63 7c 59 61 63 rg/wiki/Yacc|Yac
0540: 63 5d 20 61 6e 64 0a 5b 68 74 74 70 73 3a 2f 2f c] and.[https://
0550: 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e 6f 72 67 en.wikipedia.org
0560: 2f 77 69 6b 69 2f 47 4e 55 5f 62 69 73 6f 6e 7c /wiki/GNU_bison|
0570: 42 69 73 6f 6e 5d 2c 20 62 75 74 20 4c 65 6d 6f Bison], but Lemo
0580: 6e 20 61 64 64 73 20 69 6d 70 6f 72 74 61 6e 74 n adds important
0590: 0a 69 6d 70 72 6f 76 65 6d 65 6e 74 73 2c 20 69 .improvements, i
05a0: 6e 63 6c 75 64 69 6e 67 3a 0a 0a 3c 75 6c 3e 0a ncluding:..<ul>.
05b0: 3c 6c 69 3e 3c 70 3e 0a 20 20 20 20 20 54 68 65 <li><p>. The
05c0: 20 67 72 61 6d 6d 61 72 20 73 79 6e 74 61 78 20 grammar syntax
05d0: 69 73 20 6c 65 73 73 20 65 72 72 6f 72 20 70 72 is less error pr
05e0: 6f 6e 65 20 2d 20 75 73 69 6e 67 20 73 79 6d 62 one - using symb
05f0: 6f 6c 20 6e 61 6d 65 73 20 66 6f 72 0a 20 20 20 ol names for.
0600: 20 20 73 65 6d 61 6e 74 69 63 20 76 61 6c 75 65 semantic value
0610: 73 20 72 61 74 68 65 72 20 74 68 61 74 20 74 68 s rather that th
0620: 65 20 22 24 31 22 2d 73 74 79 6c 65 20 70 6f 73 e "$1"-style pos
0630: 69 74 69 6f 6e 61 6c 20 6e 6f 74 61 74 69 6f 6e itional notation
0640: 0a 20 20 20 20 20 6f 66 20 59 61 63 63 2e 0a 3c . of Yacc..<
0650: 6c 69 3e 3c 70 3e 0a 20 20 20 20 20 49 6e 20 4c li><p>. In L
0660: 65 6d 6f 6e 2c 20 74 68 65 20 74 6f 6b 65 6e 69 emon, the tokeni
0670: 7a 65 72 20 63 61 6c 6c 73 20 74 68 65 20 70 61 zer calls the pa
0680: 72 73 65 72 2e 20 20 59 61 63 63 20 6f 70 65 72 rser. Yacc oper
0690: 61 74 65 73 20 74 68 65 20 6f 74 68 65 72 0a 20 ates the other.
06a0: 20 20 20 20 77 61 79 20 61 72 6f 75 6e 64 2c 20 way around,
06b0: 77 69 74 68 20 74 68 65 20 70 61 72 73 65 72 20 with the parser
06c0: 63 61 6c 6c 69 6e 67 20 74 68 65 20 74 6f 6b 65 calling the toke
06d0: 6e 69 7a 65 72 2e 20 20 54 68 65 20 4c 65 6d 6f nizer. The Lemo
06e0: 6e 0a 20 20 20 20 20 61 70 70 72 6f 61 63 68 20 n. approach
06f0: 69 73 20 72 65 65 6e 74 72 61 6e 74 20 61 6e 64 is reentrant and
0700: 20 74 68 72 65 61 64 73 61 66 65 2c 20 77 68 65 threadsafe, whe
0710: 72 65 61 73 20 59 61 63 63 20 75 73 65 73 20 67 reas Yacc uses g
0720: 6c 6f 62 61 6c 20 0a 20 20 20 20 20 76 61 72 69 lobal . vari
0730: 61 62 6c 65 73 20 61 6e 64 20 69 73 20 74 68 65 ables and is the
0740: 72 65 66 6f 72 65 20 6e 65 69 74 68 65 72 2e 20 refore neither.
0750: 20 52 65 65 6e 74 72 61 6e 63 79 20 69 73 20 65 Reentrancy is e
0760: 73 70 65 63 69 61 6c 6c 79 0a 20 20 20 20 20 69 specially. i
0770: 6d 70 6f 72 74 61 6e 74 20 66 6f 72 20 53 51 4c mportant for SQL
0780: 69 74 65 20 73 69 6e 63 65 20 73 6f 6d 65 20 53 ite since some S
0790: 51 4c 20 73 74 61 74 65 6d 65 6e 74 73 20 6d 61 QL statements ma
07a0: 6b 65 20 72 65 63 75 72 73 69 76 65 20 63 61 6c ke recursive cal
07b0: 6c 73 0a 20 20 20 20 20 74 6f 20 74 68 65 20 70 ls. to the p
07c0: 61 72 73 65 72 2e 20 20 46 6f 72 20 65 78 61 6d arser. For exam
07d0: 70 6c 65 2c 20 77 68 65 6e 20 70 61 72 73 69 6e ple, when parsin
07e0: 67 20 61 20 43 52 45 41 54 45 20 54 41 42 4c 45 g a CREATE TABLE
07f0: 20 73 74 61 74 65 6d 65 6e 74 2c 0a 20 20 20 20 statement,.
0800: 20 53 51 4c 69 74 65 20 69 6e 76 6f 6b 65 73 20 SQLite invokes
0810: 74 68 65 20 70 61 72 73 65 72 20 72 65 63 75 72 the parser recur
0820: 73 69 76 65 6c 79 20 74 6f 20 67 65 6e 65 72 61 sively to genera
0830: 74 65 20 61 6e 20 49 4e 53 45 52 54 20 73 74 61 te an INSERT sta
0840: 74 65 6d 65 6e 74 0a 20 20 20 20 20 74 6f 20 6d tement. to m
0850: 61 6b 65 20 61 20 6e 65 77 20 65 6e 74 72 79 20 ake a new entry
0860: 69 6e 20 74 68 65 20 5b 73 71 6c 69 74 65 5f 6d in the [sqlite_m
0870: 61 73 74 65 72 5d 20 74 61 62 6c 65 2e 0a 3c 6c aster] table..<l
0880: 69 3e 3c 70 3e 0a 20 20 20 20 20 4c 65 6d 6f 6e i><p>. Lemon
0890: 20 68 61 73 20 74 68 65 20 63 6f 6e 63 65 70 74 has the concept
08a0: 20 6f 66 20 61 20 6e 6f 6e 2d 74 65 72 6d 69 6e of a non-termin
08b0: 61 6c 20 64 65 73 74 72 75 63 74 6f 72 20 74 68 al destructor th
08c0: 61 74 20 63 61 6e 20 62 65 0a 20 20 20 20 20 75 at can be. u
08d0: 73 65 64 20 74 6f 20 72 65 63 6c 61 69 6d 20 6d sed to reclaim m
08e0: 65 6d 6f 72 79 20 6f 72 20 6f 74 68 65 72 20 72 emory or other r
08f0: 65 73 6f 75 72 63 65 73 20 66 6f 6c 6c 6f 77 69 esources followi
0900: 6e 67 20 61 20 73 79 6e 74 61 78 20 65 72 72 6f ng a syntax erro
0910: 72 0a 20 20 20 20 20 6f 72 20 6f 74 68 65 72 20 r. or other
0920: 61 62 6f 72 74 65 64 20 70 61 72 73 65 2e 0a 3c aborted parse..<
0930: 2f 75 6c 3e 0a 0a 3c 68 32 3e 55 73 65 20 6f 66 /ul>..<h2>Use of
0940: 20 4c 65 6d 6f 6e 20 57 69 74 68 69 6e 20 53 51 Lemon Within SQ
0950: 4c 69 74 65 3c 2f 68 32 3e 0a 0a 3c 70 3e 4c 65 Lite</h2>..<p>Le
0960: 6d 6f 6e 20 69 73 20 75 73 65 64 20 69 6e 20 74 mon is used in t
0970: 77 6f 20 70 6c 61 63 65 73 20 69 6e 20 53 51 4c wo places in SQL
0980: 69 74 65 2e 0a 0a 3c 70 3e 54 68 65 20 70 72 69 ite...<p>The pri
0990: 6d 61 72 79 20 75 73 65 20 6f 66 20 4c 65 6d 6f mary use of Lemo
09a0: 6e 20 69 73 20 74 6f 20 63 72 65 61 74 65 20 74 n is to create t
09b0: 68 65 20 53 51 4c 20 6c 61 6e 67 75 61 67 65 20 he SQL language
09c0: 70 61 72 73 65 72 2e 0a 41 20 67 72 61 6d 6d 61 parser..A gramma
09d0: 72 20 66 69 6c 65 20 28 5b 68 74 74 70 73 3a 2f r file ([https:/
09e0: 2f 73 71 6c 69 74 65 2e 6f 72 67 2f 73 72 63 2f /sqlite.org/src/
09f0: 66 69 6c 65 2f 73 72 63 2f 70 61 72 73 65 2e 79 file/src/parse.y
0a00: 7c 70 61 72 73 65 2e 79 5d 29 20 69 73 0a 63 6f |parse.y]) is.co
0a10: 6d 70 69 6c 65 64 20 62 79 20 4c 65 6d 6f 6e 20 mpiled by Lemon
0a20: 69 6e 74 6f 20 70 61 72 73 65 2e 63 20 61 6e 64 into parse.c and
0a30: 20 70 61 72 73 65 2e 68 2e 20 20 54 68 65 20 70 parse.h. The p
0a40: 61 72 73 65 2e 63 20 66 69 6c 65 20 69 73 0a 69 arse.c file is.i
0a50: 6e 63 6f 72 70 6f 72 61 74 65 64 20 69 6e 74 6f ncorporated into
0a60: 20 74 68 65 20 5b 61 6d 61 6c 67 61 6d 61 74 69 the [amalgamati
0a70: 6f 6e 5d 20 77 69 74 68 6f 75 74 20 66 75 72 74 on] without furt
0a80: 68 65 72 20 6d 6f 64 69 66 69 63 61 74 69 6f 6e her modification
0a90: 2e 0a 54 68 65 20 70 61 72 73 65 2e 68 20 66 69 ..The parse.h fi
0aa0: 6c 65 20 69 73 20 70 6f 73 74 2d 70 72 6f 63 65 le is post-proce
0ab0: 73 73 65 64 20 62 79 20 74 68 65 0a 5b 68 74 74 ssed by the.[htt
0ac0: 70 73 3a 2f 2f 73 71 6c 69 74 65 2e 6f 72 67 2f ps://sqlite.org/
0ad0: 73 72 63 2f 66 69 6c 65 2f 74 6f 6f 6c 2f 61 64 src/file/tool/ad
0ae0: 64 6f 70 63 6f 64 65 73 2e 74 63 6c 7c 61 64 64 dopcodes.tcl|add
0af0: 6f 70 63 6f 64 65 73 2e 74 63 6c 5d 20 73 63 72 opcodes.tcl] scr
0b00: 69 70 74 0a 62 65 66 6f 72 65 20 62 65 69 6e 67 ipt.before being
0b10: 20 69 6e 63 6f 72 70 6f 72 61 74 65 64 20 69 6e incorporated in
0b20: 74 6f 20 74 68 65 20 5b 61 6d 61 6c 67 61 6d 61 to the [amalgama
0b30: 74 69 6f 6e 5d 2e 0a 0a 3c 70 3e 4c 65 6d 6f 6e tion]...<p>Lemon
0b40: 20 69 73 20 61 6c 73 6f 20 75 73 65 64 20 74 6f is also used to
0b50: 20 67 65 6e 65 72 61 74 65 20 70 61 72 73 65 20 generate parse
0b60: 66 6f 72 20 74 68 65 20 71 75 65 72 79 20 70 61 for the query pa
0b70: 74 74 65 72 6e 0a 65 78 70 72 65 73 73 69 6f 6e ttern.expression
0b80: 73 20 69 6e 20 74 68 65 20 5b 46 54 53 35 5d 20 s in the [FTS5]
0b90: 65 78 74 65 6e 73 69 6f 6e 2e 20 20 49 6e 20 74 extension. In t
0ba0: 68 69 73 20 63 61 73 65 2c 20 74 68 65 20 69 6e his case, the in
0bb0: 70 75 74 20 67 72 61 6d 6d 61 72 0a 66 69 6c 65 put grammar.file
0bc0: 20 69 73 20 5b 68 74 74 70 73 3a 2f 2f 73 71 6c is [https://sql
0bd0: 69 74 65 2e 6f 72 67 2f 73 72 63 2f 66 69 6c 65 ite.org/src/file
0be0: 2f 65 78 74 2f 66 74 73 35 2f 66 74 73 35 70 61 /ext/fts5/fts5pa
0bf0: 72 73 65 2e 79 7c 66 74 73 35 70 61 72 73 65 2e rse.y|fts5parse.
0c00: 79 5d 2e 0a 0a 3c 68 32 3e 4c 65 6d 6f 6e 20 43 y]...<h2>Lemon C
0c10: 75 73 74 6f 6d 69 7a 61 74 69 6f 6e 73 20 45 73 ustomizations Es
0c20: 70 65 63 69 61 6c 6c 79 20 46 6f 72 20 53 51 4c pecially For SQL
0c30: 69 74 65 3c 2f 68 32 3e 0a 0a 3c 70 3e 4f 6e 65 ite</h2>..<p>One
0c40: 20 6f 66 20 74 68 65 20 61 64 76 61 6e 74 61 67 of the advantag
0c50: 65 73 20 6f 66 20 68 6f 73 74 69 6e 67 20 63 6f es of hosting co
0c60: 64 65 20 67 65 6e 65 72 61 74 6f 72 20 74 6f 6f de generator too
0c70: 6c 20 61 73 20 70 61 72 74 20 6f 66 0a 74 68 65 l as part of.the
0c80: 20 70 72 6f 6a 65 63 74 20 69 73 20 74 68 61 74 project is that
0c90: 20 74 68 65 20 74 6f 6f 6c 73 20 63 61 6e 20 62 the tools can b
0ca0: 65 20 6f 70 74 69 6d 69 7a 65 64 20 74 6f 20 73 e optimized to s
0cb0: 65 72 76 65 20 73 70 65 63 69 66 69 63 20 6e 65 erve specific ne
0cc0: 65 64 73 20 6f 66 0a 74 68 65 20 6f 76 65 72 61 eds of.the overa
0cd0: 6c 6c 20 70 72 6f 6a 65 63 74 2e 20 20 4c 65 6d ll project. Lem
0ce0: 6f 6e 20 68 61 73 20 62 65 6e 65 66 69 74 65 64 on has benefited
0cf0: 20 66 72 6f 6d 20 74 68 69 73 20 65 66 66 65 63 from this effec
0d00: 74 2e 20 4f 76 65 72 20 74 68 65 20 79 65 61 72 t. Over the year
0d10: 73 2c 0a 74 68 65 20 4c 65 6d 6f 6e 20 70 61 72 s,.the Lemon par
0d20: 73 65 72 20 67 65 6e 65 72 61 74 6f 72 20 68 61 ser generator ha
0d30: 73 20 62 65 65 6e 20 65 78 74 65 6e 64 65 64 20 s been extended
0d40: 61 6e 64 20 65 6e 68 61 6e 63 65 64 20 74 6f 20 and enhanced to
0d50: 70 72 6f 76 69 64 65 0a 6e 65 77 20 63 61 70 61 provide.new capa
0d60: 62 69 6c 69 74 69 65 73 20 61 6e 64 20 69 6d 70 bilities and imp
0d70: 72 6f 76 65 64 20 70 65 72 66 6f 72 6d 61 6e 63 roved performanc
0d80: 65 20 74 6f 20 53 51 4c 69 74 65 2e 20 20 41 20 e to SQLite. A
0d90: 66 65 77 20 6f 66 20 74 68 65 0a 73 70 65 63 69 few of the.speci
0da0: 66 69 63 20 65 6e 68 61 6e 63 65 6d 65 6e 74 73 fic enhancements
0db0: 20 74 6f 20 4c 65 6d 6f 6e 20 74 68 61 74 20 61 to Lemon that a
0dc0: 72 65 20 73 70 65 63 69 66 69 63 61 6c 6c 79 20 re specifically
0dd0: 64 65 73 69 67 6e 65 64 20 66 6f 72 20 75 73 65 designed for use
0de0: 0a 62 79 20 53 51 4c 69 74 65 20 69 6e 63 6c 75 .by SQLite inclu
0df0: 64 65 3a 0a 0a 3c 75 6c 3e 0a 3c 6c 69 3e 3c 70 de:..<ul>.<li><p
0e00: 3e 0a 4c 65 6d 6f 6e 20 68 61 73 20 74 68 65 20 >.Lemon has the
0e10: 63 6f 6e 63 65 70 74 20 6f 66 20 61 20 22 66 61 concept of a "fa
0e20: 6c 6c 62 61 63 6b 22 20 74 6f 6b 65 6e 73 2e 0a llback" tokens..
0e30: 54 68 65 20 53 51 4c 20 6c 61 6e 67 75 61 67 65 The SQL language
0e40: 20 63 6f 6e 74 61 69 6e 73 20 61 20 6c 61 72 67 contains a larg
0e50: 65 20 6e 75 6d 62 65 72 20 6f 66 20 6b 65 79 77 e number of keyw
0e60: 6f 72 64 73 20 61 6e 64 20 74 68 65 73 65 20 6b ords and these k
0e70: 65 79 77 6f 72 64 73 0a 68 61 76 65 20 74 68 65 eywords.have the
0e80: 20 70 6f 74 65 6e 74 69 61 6c 20 74 6f 20 63 6f potential to co
0e90: 6c 6c 69 64 65 20 77 69 74 68 20 69 64 65 6e 74 llide with ident
0ea0: 69 66 69 65 72 20 6e 61 6d 65 73 2e 0a 4c 65 6d ifier names..Lem
0eb0: 6f 6e 20 68 61 73 20 74 68 65 20 61 62 69 6c 69 on has the abili
0ec0: 74 79 20 74 6f 20 64 65 73 69 67 6e 61 74 65 20 ty to designate
0ed0: 73 6f 6d 65 20 6b 65 79 77 6f 72 64 73 20 68 61 some keywords ha
0ee0: 73 20 62 65 69 6e 67 20 61 62 6c 65 20 74 6f 0a s being able to.
0ef0: 22 66 61 6c 6c 62 61 63 6b 22 20 74 6f 20 61 6e "fallback" to an
0f00: 20 69 64 65 6e 74 69 66 69 65 72 2e 20 20 49 66 identifier. If
0f10: 20 74 68 65 20 6b 65 79 77 6f 72 64 20 61 70 70 the keyword app
0f20: 65 61 72 73 20 69 6e 20 74 68 65 20 69 6e 70 75 ears in the inpu
0f30: 74 20 74 6f 6b 65 6e 0a 73 74 72 65 61 6d 20 69 t token.stream i
0f40: 6e 20 61 20 63 6f 6e 74 65 78 74 20 74 68 61 74 n a context that
0f50: 20 77 6f 75 6c 64 20 6f 74 68 65 72 77 69 73 65 would otherwise
0f60: 20 62 65 20 61 20 73 79 6e 74 61 78 20 65 72 72 be a syntax err
0f70: 6f 72 2c 20 74 68 65 20 74 6f 6b 65 6e 0a 69 73 or, the token.is
0f80: 20 61 75 74 6f 6d 61 74 69 63 61 6c 6c 79 20 74 automatically t
0f90: 72 61 6e 73 66 6f 72 6d 65 64 20 69 6e 74 6f 20 ransformed into
0fa0: 69 74 73 20 66 61 6c 6c 62 61 63 6b 20 62 65 66 its fallback bef
0fb0: 6f 72 65 20 74 68 65 20 73 79 6e 74 61 78 20 65 ore the syntax e
0fc0: 72 72 6f 72 0a 69 73 20 72 61 69 73 65 64 2e 20 rror.is raised.
0fd0: 20 54 68 69 73 20 66 65 61 74 75 72 65 20 61 6c This feature al
0fe0: 6c 6f 77 73 20 74 68 65 20 70 61 72 73 65 72 20 lows the parser
0ff0: 74 6f 20 62 65 20 76 65 72 79 20 66 6f 72 67 69 to be very forgi
1000: 76 69 6e 67 20 6f 66 0a 72 65 73 65 72 76 65 64 ving of.reserved
1010: 20 77 6f 72 64 73 20 75 73 65 64 20 61 73 20 69 words used as i
1020: 64 65 6e 74 69 66 69 65 72 73 2c 20 77 68 69 63 dentifiers, whic
1030: 68 20 69 73 20 61 20 70 72 6f 62 6c 65 6d 20 74 h is a problem t
1040: 68 61 74 20 63 6f 6d 65 73 20 75 70 0a 66 72 65 hat comes up.fre
1050: 71 75 65 6e 74 6c 79 20 69 6e 20 74 68 65 20 53 quently in the S
1060: 51 4c 20 6c 61 6e 67 75 61 67 65 2e 0a 0a 3c 6c QL language...<l
1070: 69 3e 3c 70 3e 0a 49 6e 20 73 75 70 70 6f 72 74 i><p>.In support
1080: 20 6f 66 20 74 68 65 20 5b 4d 43 2f 44 43 7c 31 of the [MC/DC|1
1090: 30 30 25 20 4d 43 2f 44 43 20 74 65 73 74 69 6e 00% MC/DC testin
10a0: 67 5d 20 67 6f 61 6c 20 66 6f 72 20 53 51 4c 69 g] goal for SQLi
10b0: 74 65 2c 20 0a 74 68 65 20 70 61 72 73 65 72 20 te, .the parser
10c0: 63 6f 64 65 20 67 65 6e 65 72 61 74 65 64 20 62 code generated b
10d0: 79 20 4c 65 6d 6f 6e 20 68 61 73 20 6e 6f 20 75 y Lemon has no u
10e0: 6e 72 65 61 63 68 61 62 6c 65 20 62 72 61 6e 63 nreachable branc
10f0: 68 65 73 2c 0a 61 6e 64 20 63 6f 6e 74 61 69 6e hes,.and contain
1100: 73 20 65 78 74 72 61 20 28 63 6f 6d 70 69 6c 65 s extra (compile
1110: 2d 74 69 6d 65 20 73 65 6c 65 63 74 65 64 29 20 -time selected)
1120: 69 6e 73 74 72 75 6d 65 6e 74 61 74 69 6f 6e 20 instrumentation
1130: 75 73 65 66 75 6c 0a 66 6f 72 20 6d 65 61 73 75 useful.for measu
1140: 72 69 6e 67 20 74 65 73 74 20 63 6f 76 65 72 61 ring test covera
1150: 67 65 2e 0a 0a 3c 6c 69 3e 3c 70 3e 0a 4c 65 6d ge...<li><p>.Lem
1160: 6f 6e 20 73 75 70 70 6f 72 74 73 20 63 6f 6e 64 on supports cond
1170: 69 74 69 6f 6e 61 6c 20 63 6f 6d 70 69 6c 61 74 itional compilat
1180: 69 6f 6e 20 6f 66 20 67 72 61 6d 6d 61 72 20 66 ion of grammar f
1190: 69 6c 65 20 72 75 6c 65 73 2c 20 73 6f 20 74 68 ile rules, so th
11a0: 61 74 0a 61 20 64 69 66 66 65 72 65 6e 74 20 70 at.a different p
11b0: 61 72 73 65 72 20 63 61 6e 20 62 65 20 67 65 6e arser can be gen
11c0: 65 72 61 74 65 64 20 64 65 70 65 6e 64 69 6e 67 erated depending
11d0: 20 6f 6e 20 63 6f 6d 70 69 6c 65 2d 74 69 6d 65 on compile-time
11e0: 20 6f 70 74 69 6f 6e 73 2e 0a 0a 3c 6c 69 3e 3c options...<li><
11f0: 70 3e 0a 41 73 20 61 20 70 65 72 66 6f 72 6d 61 p>.As a performa
1200: 6e 63 65 20 6f 70 74 69 6d 69 7a 61 74 69 6f 6e nce optimization
1210: 2c 20 72 65 64 75 63 65 20 61 63 74 69 6f 6e 73 , reduce actions
1220: 20 69 6e 20 74 68 65 20 4c 65 6d 6f 6e 20 69 6e in the Lemon in
1230: 70 75 74 20 67 72 61 6d 6d 61 72 0a 61 72 65 20 put grammar.are
1240: 61 6c 6c 6f 77 65 64 20 74 6f 20 63 6f 6e 74 61 allowed to conta
1250: 69 6e 20 63 6f 6d 6d 65 6e 74 73 20 6f 66 20 74 in comments of t
1260: 68 65 20 66 6f 72 6d 20 22 2f 2a 41 2d 6f 76 65 he form "/*A-ove
1270: 72 77 72 69 74 65 73 2d 5a 2a 2f 22 20 74 6f 20 rwrites-Z*/" to
1280: 69 6e 64 69 63 61 74 65 0a 74 68 61 74 20 74 68 indicate.that th
1290: 65 20 73 65 6d 61 6e 74 69 63 20 76 61 6c 75 65 e semantic value
12a0: 20 22 41 22 20 6f 6e 20 74 68 65 20 72 69 67 68 "A" on the righ
12b0: 74 2d 68 61 6e 64 20 73 69 64 65 20 6f 66 20 74 t-hand side of t
12c0: 68 65 20 72 75 6c 65 20 69 73 20 61 6c 6c 6f 77 he rule is allow
12d0: 65 64 0a 74 6f 20 64 69 72 65 63 74 6c 79 20 6f ed.to directly o
12e0: 76 65 72 77 72 69 74 65 20 74 68 65 20 73 65 6d verwrite the sem
12f0: 61 6e 74 69 63 20 76 61 6c 75 65 20 22 5a 22 20 antic value "Z"
1300: 6f 6e 20 74 68 65 20 6c 65 66 74 2d 68 61 6e 64 on the left-hand
1310: 20 73 69 64 65 2e 0a 54 68 69 73 20 73 69 6d 70 side..This simp
1320: 6c 65 20 6f 70 74 69 6d 69 7a 61 74 69 6f 6e 20 le optimization
1330: 72 65 64 75 63 65 73 20 74 68 65 20 6e 75 6d 62 reduces the numb
1340: 65 72 20 6f 66 20 73 74 61 63 6b 20 6f 70 65 72 er of stack oper
1350: 61 74 69 6f 6e 73 20 69 6e 20 74 68 65 0a 70 75 ations in the.pu
1360: 73 68 2d 64 6f 77 6e 20 61 75 74 6f 6d 61 74 6f sh-down automato
1370: 6e 20 75 73 65 64 20 74 6f 20 70 61 72 73 65 20 n used to parse
1380: 74 68 65 20 69 6e 70 75 74 20 67 72 61 6d 6d 61 the input gramma
1390: 72 2c 20 61 6e 64 20 74 68 75 73 20 69 6d 70 72 r, and thus impr
13a0: 6f 76 65 0a 70 65 72 66 6f 72 6d 61 6e 63 65 20 ove.performance
13b0: 6f 66 20 74 68 65 20 70 61 72 73 65 72 2e 20 20 of the parser.
13c0: 49 74 20 61 6c 73 6f 20 6d 61 6b 65 73 20 74 68 It also makes th
13d0: 65 20 67 65 6e 65 72 61 74 65 64 20 63 6f 64 65 e generated code
13e0: 20 61 20 6c 69 74 74 6c 65 20 73 6d 61 6c 6c 65 a little smalle
13f0: 72 2e 0a 3c 2f 75 6c 3e 0a 0a 3c 70 3e 54 68 65 r..</ul>..<p>The
1400: 20 70 61 72 73 69 6e 67 20 6f 66 20 53 51 4c 20 parsing of SQL
1410: 73 74 61 74 65 6d 65 6e 74 73 20 69 73 20 61 20 statements is a
1420: 73 69 67 6e 69 66 69 63 61 6e 74 20 63 6f 6e 73 significant cons
1430: 75 6d 65 72 20 6f 66 20 43 50 55 20 63 79 63 6c umer of CPU cycl
1440: 65 73 20 0a 69 6e 20 61 6e 79 20 53 51 4c 20 64 es .in any SQL d
1450: 61 74 61 62 61 73 65 20 65 6e 67 69 6e 65 2e 20 atabase engine.
1460: 20 4f 6e 2d 67 6f 69 6e 67 20 65 66 66 6f 72 74 On-going effort
1470: 73 20 74 6f 20 6f 70 74 69 6d 69 7a 65 20 53 51 s to optimize SQ
1480: 4c 69 74 65 20 68 61 76 65 20 63 61 75 73 65 64 Lite have caused
1490: 0a 74 68 65 20 64 65 76 65 6c 6f 70 65 72 73 20 .the developers
14a0: 74 6f 20 73 70 65 6e 64 20 61 20 6c 6f 74 20 6f to spend a lot o
14b0: 66 20 74 69 6d 65 20 74 77 65 61 6b 69 6e 67 20 f time tweaking
14c0: 4c 65 6d 6f 6e 20 74 6f 20 67 65 6e 65 72 61 74 Lemon to generat
14d0: 65 20 66 61 73 74 65 72 0a 70 61 72 73 65 72 73 e faster.parsers
14e0: 2e 20 20 54 68 65 73 65 20 65 66 66 6f 72 74 73 . These efforts
14f0: 20 68 61 76 65 20 62 65 6e 65 66 69 74 65 64 20 have benefited
1500: 61 6c 6c 20 75 73 65 72 73 20 6f 66 20 74 68 65 all users of the
1510: 20 4c 65 6d 6f 6e 20 70 61 72 73 65 72 20 67 65 Lemon parser ge
1520: 6e 65 72 61 74 6f 72 2c 0a 6e 6f 74 20 6a 75 73 nerator,.not jus
1530: 74 20 53 51 4c 69 74 65 2e 20 20 42 75 74 20 69 t SQLite. But i
1540: 66 20 4c 65 6d 6f 6e 20 68 61 64 20 62 65 65 6e f Lemon had been
1550: 20 61 20 73 65 70 61 72 61 74 65 6c 79 20 6d 61 a separately ma
1560: 69 6e 74 61 69 6e 65 64 20 74 6f 6f 6c 2c 20 69 intained tool, i
1570: 74 0a 77 6f 75 6c 64 20 68 61 76 65 20 62 65 65 t.would have bee
1580: 6e 20 6d 6f 72 65 20 64 69 66 66 69 63 75 6c 74 n more difficult
1590: 79 20 74 6f 20 6d 61 6b 65 20 63 6f 6f 72 64 69 y to make coordi
15a0: 6e 61 74 65 64 20 63 68 61 6e 67 65 73 20 74 6f nated changes to
15b0: 20 62 6f 74 68 20 53 51 4c 69 74 65 0a 61 6e 64 both SQLite.and
15c0: 20 4c 65 6d 6f 6e 2c 20 61 6e 64 20 61 73 20 61 Lemon, and as a
15d0: 20 72 65 73 75 6c 74 20 6e 6f 74 20 61 73 20 6d result not as m
15e0: 75 63 68 20 6f 70 74 69 6d 69 7a 61 74 69 6f 6e uch optimization
15f0: 20 77 6f 75 6c 64 20 68 61 76 65 20 62 65 65 6e would have been
1600: 0a 61 63 63 6f 6d 70 6c 69 73 68 65 64 2e 20 20 .accomplished.
1610: 48 65 6e 63 65 2c 20 74 68 65 20 66 61 63 74 20 Hence, the fact
1620: 74 68 61 74 20 74 68 65 20 70 61 72 73 65 72 20 that the parser
1630: 67 65 6e 65 72 61 74 6f 72 20 74 6f 6f 6c 20 69 generator tool i
1640: 73 20 69 6e 63 6c 75 64 65 64 0a 69 6e 20 74 68 s included.in th
1650: 65 20 73 6f 75 72 63 65 20 74 72 65 65 20 66 6f e source tree fo
1660: 72 20 53 51 4c 69 74 65 20 68 61 73 20 74 75 72 r SQLite has tur
1670: 6e 65 64 20 6f 75 74 20 74 6f 20 62 65 20 61 20 ned out to be a
1680: 6e 65 74 20 62 65 6e 65 66 69 74 20 66 6f 72 20 net benefit for
1690: 62 6f 74 68 0a 74 68 65 20 74 6f 6f 6c 20 69 74 both.the tool it
16a0: 73 65 6c 66 20 61 6e 64 20 66 6f 72 20 53 51 4c self and for SQL
16b0: 69 74 65 2e 0a 0a 3c 68 31 3e 48 69 73 74 6f 72 ite...<h1>Histor
16c0: 79 20 4f 66 20 4c 65 6d 6f 6e 3c 2f 68 31 3e 0a y Of Lemon</h1>.
16d0: 0a 3c 70 3e 4c 65 6d 6f 6e 20 77 61 73 20 6f 72 .<p>Lemon was or
16e0: 69 67 69 6e 61 6c 20 77 72 69 74 74 65 6e 20 62 iginal written b
16f0: 79 20 44 2e 20 52 69 63 68 61 72 64 20 48 69 70 y D. Richard Hip
1700: 70 20 28 61 6c 73 6f 20 74 68 65 20 63 72 65 61 p (also the crea
1710: 74 6f 72 20 6f 66 20 53 51 4c 69 74 65 29 0a 77 tor of SQLite).w
1720: 68 69 6c 65 20 68 65 20 77 61 73 20 69 6e 20 67 hile he was in g
1730: 72 61 64 75 61 74 65 20 73 63 68 6f 6f 6c 20 61 raduate school a
1740: 74 20 44 75 6b 65 20 55 6e 69 76 65 72 73 69 74 t Duke Universit
1750: 79 20 62 65 74 77 65 65 6e 20 31 39 38 37 20 61 y between 1987 a
1760: 6e 64 20 31 39 39 32 2e 0a 54 68 65 20 6f 72 69 nd 1992..The ori
1770: 67 69 6e 61 6c 20 63 72 65 61 74 69 6f 6e 20 64 ginal creation d
1780: 61 74 65 20 6f 66 20 4c 65 6d 6f 6e 20 68 61 73 ate of Lemon has
1790: 20 62 65 65 6e 20 6c 6f 73 74 2c 20 62 75 74 20 been lost, but
17a0: 77 61 73 20 70 72 6f 62 61 62 6c 79 20 73 6f 6d was probably som
17b0: 65 74 69 6d 65 0a 61 72 6f 75 6e 64 20 31 39 39 etime.around 199
17c0: 30 2e 20 20 4c 65 6d 6f 6e 20 67 65 6e 65 72 61 0. Lemon genera
17d0: 74 65 73 20 61 6e 20 4c 41 4c 52 28 31 29 20 70 tes an LALR(1) p
17e0: 61 72 73 65 72 2e 20 20 54 68 65 72 65 20 77 61 arser. There wa
17f0: 73 20 63 6f 6d 70 61 6e 69 6f 6e 20 0a 4c 4c 28 s companion .LL(
1800: 31 29 20 70 61 72 73 65 72 20 67 65 6e 65 72 61 1) parser genera
1810: 74 6f 72 20 74 6f 6f 6c 20 6e 61 6d 65 64 20 22 tor tool named "
1820: 4c 69 6d 65 22 2c 20 62 75 74 20 74 68 65 20 73 Lime", but the s
1830: 6f 75 72 63 65 20 63 6f 64 65 20 66 6f 72 20 4c ource code for L
1840: 69 6d 65 0a 68 61 73 20 62 65 65 6e 20 6c 6f 73 ime.has been los
1850: 74 2e 0a 0a 3c 70 3e 54 68 65 20 4c 65 6d 6f 6e t...<p>The Lemon
1860: 20 73 6f 75 72 63 65 20 63 6f 64 65 20 77 61 73 source code was
1870: 20 6f 72 69 67 69 6e 61 6c 6c 79 20 77 72 69 74 originally writ
1880: 74 65 6e 20 61 73 20 73 65 70 61 72 61 74 65 20 ten as separate
1890: 73 6f 75 72 63 65 20 66 69 6c 65 73 2c 0a 61 6e source files,.an
18a0: 64 20 6f 6e 6c 79 20 6c 61 74 65 72 20 6d 65 72 d only later mer
18b0: 67 65 64 20 69 6e 74 6f 20 61 20 73 69 6e 67 6c ged into a singl
18c0: 65 20 22 6c 65 6d 6f 6e 2e 63 22 20 73 6f 75 72 e "lemon.c" sour
18d0: 63 65 20 66 69 6c 65 2e 0a 0a 3c 70 3e 54 68 65 ce file...<p>The
18e0: 20 61 75 74 68 6f 72 20 6f 66 20 4c 65 6d 6f 6e author of Lemon
18f0: 20 61 6e 64 20 53 51 4c 69 74 65 20 28 48 69 70 and SQLite (Hip
1900: 70 29 20 72 65 70 6f 72 74 73 20 74 68 61 74 20 p) reports that
1910: 68 69 73 20 43 20 70 72 6f 67 72 61 6d 6d 69 6e his C programmin
1920: 67 0a 73 6b 69 6c 6c 73 20 77 65 72 65 20 67 72 g.skills were gr
1930: 65 61 74 6c 79 20 65 6e 68 61 6e 63 65 64 20 62 eatly enhanced b
1940: 79 20 73 74 75 64 79 69 6e 67 20 4a 6f 68 6e 20 y studying John
1950: 4f 75 73 74 65 72 68 6f 75 74 27 73 20 6f 72 69 Ousterhout's ori
1960: 67 69 6e 61 6c 0a 73 6f 75 72 63 65 20 63 6f 64 ginal.source cod
1970: 65 20 74 6f 20 54 63 6c 2e 20 20 48 69 70 70 20 e to Tcl. Hipp
1980: 64 69 73 63 6f 76 65 72 65 64 20 61 6e 64 20 73 discovered and s
1990: 74 75 64 69 65 64 20 54 63 6c 20 69 6e 20 31 39 tudied Tcl in 19
19a0: 39 33 2e 20 20 4c 65 6d 6f 6e 0a 77 61 73 20 77 93. Lemon.was w
19b0: 72 69 74 74 65 6e 20 62 65 66 6f 72 65 20 74 68 ritten before th
19c0: 65 6e 2c 20 61 6e 64 20 53 51 4c 69 74 65 20 61 en, and SQLite a
19d0: 66 74 65 72 77 61 72 64 73 2e 20 20 54 68 65 72 fterwards. Ther
19e0: 65 20 69 73 20 61 20 63 6c 65 61 72 0a 64 69 66 e is a clear.dif
19f0: 66 65 72 65 6e 63 65 20 69 6e 20 74 68 65 20 63 ference in the c
1a00: 6f 64 69 6e 67 20 73 74 79 6c 65 73 20 6f 66 20 oding styles of
1a10: 74 68 65 73 65 20 74 77 6f 20 70 72 6f 64 75 63 these two produc
1a20: 74 73 2c 20 77 69 74 68 20 53 51 4c 69 74 65 20 ts, with SQLite
1a30: 73 65 65 6d 69 6e 67 0a 74 6f 20 62 65 20 63 6c seeming.to be cl
1a40: 65 61 6e 65 72 2c 20 6d 6f 72 65 20 72 65 61 64 eaner, more read
1a50: 61 62 6c 65 2c 20 61 6e 64 20 65 61 73 69 65 72 able, and easier
1a60: 20 74 6f 20 6d 61 69 6e 74 61 69 6e 2e 0a to maintain..