Documentation Source Text

Hex Artifact Content
Login

Artifact b99e508c2e9c6627675f51a657bf7ff0d48b6cbe72053d5f80bfd70c95de1b2d:


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 0a 3c 70 3e 4c 65 6d 6f 6e 20 69 73 20 61  ...<p>Lemon is a
0aa0: 6c 73 6f 20 75 73 65 64 20 74 6f 20 67 65 6e 65  lso used to gene
0ab0: 72 61 74 65 20 70 61 72 73 65 20 66 6f 72 20 74  rate parse for t
0ac0: 68 65 20 71 75 65 72 79 20 70 61 74 74 65 72 6e  he query pattern
0ad0: 0a 65 78 70 72 65 73 73 69 6f 6e 73 20 69 6e 20  .expressions in 
0ae0: 74 68 65 20 5b 46 54 53 35 5d 20 65 78 74 65 6e  the [FTS5] exten
0af0: 73 69 6f 6e 2e 20 20 49 6e 20 74 68 69 73 20 63  sion.  In this c
0b00: 61 73 65 2c 20 74 68 65 20 69 6e 70 75 74 20 67  ase, the input g
0b10: 72 61 6d 6d 61 72 0a 66 69 6c 65 20 69 73 20 5b  rammar.file is [
0b20: 68 74 74 70 73 3a 2f 2f 73 71 6c 69 74 65 2e 6f  https://sqlite.o
0b30: 72 67 2f 73 72 63 2f 66 69 6c 65 2f 65 78 74 2f  rg/src/file/ext/
0b40: 66 74 73 35 2f 66 74 73 35 70 61 72 73 65 2e 79  fts5/fts5parse.y
0b50: 7c 66 74 73 35 70 61 72 73 65 2e 79 5d 2e 0a 0a  |fts5parse.y]...
0b60: 3c 68 32 3e 4c 65 6d 6f 6e 20 43 75 73 74 6f 6d  <h2>Lemon Custom
0b70: 69 7a 61 74 69 6f 6e 73 20 45 73 70 65 63 69 61  izations Especia
0b80: 6c 6c 79 20 46 6f 72 20 53 51 4c 69 74 65 3c 2f  lly For SQLite</
0b90: 68 32 3e 0a 0a 3c 70 3e 4f 6e 65 20 6f 66 20 74  h2>..<p>One of t
0ba0: 68 65 20 61 64 76 61 6e 74 61 67 65 73 20 6f 66  he advantages of
0bb0: 20 68 6f 73 74 69 6e 67 20 63 6f 64 65 20 67 65   hosting code ge
0bc0: 6e 65 72 61 74 6f 72 20 74 6f 6f 6c 20 61 73 20  nerator tool as 
0bd0: 70 61 72 74 20 6f 66 0a 74 68 65 20 70 72 6f 6a  part of.the proj
0be0: 65 63 74 20 69 73 20 74 68 61 74 20 74 68 65 20  ect is that the 
0bf0: 74 6f 6f 6c 73 20 63 61 6e 20 62 65 20 6f 70 74  tools can be opt
0c00: 69 6d 69 7a 65 64 20 74 6f 20 73 65 72 76 65 20  imized to serve 
0c10: 73 70 65 63 69 66 69 63 20 6e 65 65 64 73 20 6f  specific needs o
0c20: 66 0a 74 68 65 20 6f 76 65 72 61 6c 6c 20 70 72  f.the overall pr
0c30: 6f 6a 65 63 74 2e 20 20 4c 65 6d 6f 6e 20 68 61  oject.  Lemon ha
0c40: 73 20 62 65 6e 65 66 69 74 65 64 20 66 72 6f 6d  s benefited from
0c50: 20 74 68 69 73 20 65 66 66 65 63 74 2e 20 4f 76   this effect. Ov
0c60: 65 72 20 74 68 65 20 79 65 61 72 73 2c 0a 74 68  er the years,.th
0c70: 65 20 4c 65 6d 6f 6e 20 70 61 72 73 65 72 20 67  e Lemon parser g
0c80: 65 6e 65 72 61 74 6f 72 20 68 61 73 20 62 65 65  enerator has bee
0c90: 6e 20 65 78 74 65 6e 64 65 64 20 61 6e 64 20 65  n extended and e
0ca0: 6e 68 61 6e 63 65 64 20 74 6f 20 70 72 6f 76 69  nhanced to provi
0cb0: 64 65 0a 6e 65 77 20 63 61 70 61 62 69 6c 69 74  de.new capabilit
0cc0: 69 65 73 20 61 6e 64 20 69 6d 70 72 6f 76 65 64  ies and improved
0cd0: 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 74 6f 20   performance to 
0ce0: 53 51 4c 69 74 65 2e 20 20 41 20 66 65 77 20 6f  SQLite.  A few o
0cf0: 66 20 74 68 65 0a 73 70 65 63 69 66 69 63 20 65  f the.specific e
0d00: 6e 68 61 6e 63 65 6d 65 6e 74 73 20 74 6f 20 4c  nhancements to L
0d10: 65 6d 6f 6e 20 74 68 61 74 20 61 72 65 20 73 70  emon that are sp
0d20: 65 63 69 66 69 63 61 6c 6c 79 20 64 65 73 69 67  ecifically desig
0d30: 6e 65 64 20 66 6f 72 20 75 73 65 0a 62 79 20 53  ned for use.by S
0d40: 51 4c 69 74 65 20 69 6e 63 6c 75 64 65 3a 0a 0a  QLite include:..
0d50: 3c 75 6c 3e 0a 3c 6c 69 3e 3c 70 3e 0a 4c 65 6d  <ul>.<li><p>.Lem
0d60: 6f 6e 20 68 61 73 20 74 68 65 20 63 6f 6e 63 65  on has the conce
0d70: 70 74 20 6f 66 20 61 20 22 66 61 6c 6c 62 61 63  pt of a "fallbac
0d80: 6b 22 20 74 6f 6b 65 6e 73 2e 0a 54 68 65 20 53  k" tokens..The S
0d90: 51 4c 20 6c 61 6e 67 75 61 67 65 20 63 6f 6e 74  QL language cont
0da0: 61 69 6e 73 20 61 20 6c 61 72 67 65 20 6e 75 6d  ains a large num
0db0: 62 65 72 20 6f 66 20 6b 65 79 77 6f 72 64 73 20  ber of keywords 
0dc0: 61 6e 64 20 74 68 65 73 65 20 6b 65 79 77 6f 72  and these keywor
0dd0: 64 73 0a 68 61 76 65 20 74 68 65 20 70 6f 74 65  ds.have the pote
0de0: 6e 74 69 61 6c 20 74 6f 20 63 6f 6c 6c 69 64 65  ntial to collide
0df0: 20 77 69 74 68 20 69 64 65 6e 74 69 66 69 65 72   with identifier
0e00: 20 6e 61 6d 65 73 2e 0a 4c 65 6d 6f 6e 20 68 61   names..Lemon ha
0e10: 73 20 74 68 65 20 61 62 69 6c 69 74 79 20 74 6f  s the ability to
0e20: 20 64 65 73 69 67 6e 61 74 65 20 73 6f 6d 65 20   designate some 
0e30: 6b 65 79 77 6f 72 64 73 20 68 61 73 20 62 65 69  keywords has bei
0e40: 6e 67 20 61 62 6c 65 20 74 6f 0a 22 66 61 6c 6c  ng able to."fall
0e50: 62 61 63 6b 22 20 74 6f 20 61 6e 20 69 64 65 6e  back" to an iden
0e60: 74 69 66 69 65 72 2e 20 20 49 66 20 74 68 65 20  tifier.  If the 
0e70: 6b 65 79 77 6f 72 64 20 61 70 70 65 61 72 73 20  keyword appears 
0e80: 69 6e 20 74 68 65 20 69 6e 70 75 74 20 74 6f 6b  in the input tok
0e90: 65 6e 0a 73 74 72 65 61 6d 20 69 6e 20 61 20 63  en.stream in a c
0ea0: 6f 6e 74 65 78 74 20 74 68 61 74 20 77 6f 75 6c  ontext that woul
0eb0: 64 20 6f 74 68 65 72 77 69 73 65 20 62 65 20 61  d otherwise be a
0ec0: 20 73 79 6e 74 61 78 20 65 72 72 6f 72 2c 20 74   syntax error, t
0ed0: 68 65 20 74 6f 6b 65 6e 0a 69 73 20 61 75 74 6f  he token.is auto
0ee0: 6d 61 74 69 63 61 6c 6c 79 20 74 72 61 6e 73 66  matically transf
0ef0: 6f 72 6d 65 64 20 69 6e 74 6f 20 69 74 73 20 66  ormed into its f
0f00: 61 6c 6c 62 61 63 6b 20 62 65 66 6f 72 65 20 74  allback before t
0f10: 68 65 20 73 79 6e 74 61 78 20 65 72 72 6f 72 0a  he syntax error.
0f20: 69 73 20 72 61 69 73 65 64 2e 20 20 54 68 69 73  is raised.  This
0f30: 20 66 65 61 74 75 72 65 20 61 6c 6c 6f 77 73 20   feature allows 
0f40: 74 68 65 20 70 61 72 73 65 72 20 74 6f 20 62 65  the parser to be
0f50: 20 76 65 72 79 20 66 6f 72 67 69 76 69 6e 67 20   very forgiving 
0f60: 6f 66 0a 72 65 73 65 72 76 65 64 20 77 6f 72 64  of.reserved word
0f70: 73 20 75 73 65 64 20 61 73 20 69 64 65 6e 74 69  s used as identi
0f80: 66 69 65 72 73 2c 20 77 68 69 63 68 20 69 73 20  fiers, which is 
0f90: 61 20 70 72 6f 62 6c 65 6d 20 74 68 61 74 20 63  a problem that c
0fa0: 6f 6d 65 73 20 75 70 0a 66 72 65 71 75 65 6e 74  omes up.frequent
0fb0: 6c 79 20 69 6e 20 74 68 65 20 53 51 4c 20 6c 61  ly in the SQL la
0fc0: 6e 67 75 61 67 65 2e 0a 0a 3c 6c 69 3e 3c 70 3e  nguage...<li><p>
0fd0: 0a 49 6e 20 73 75 70 70 6f 72 74 20 6f 66 20 74  .In support of t
0fe0: 68 65 20 5b 4d 43 2f 44 43 7c 31 30 30 25 20 4d  he [MC/DC|100% M
0ff0: 43 2f 44 43 20 74 65 73 74 69 6e 67 5d 20 67 6f  C/DC testing] go
1000: 61 6c 20 66 6f 72 20 53 51 4c 69 74 65 2c 20 0a  al for SQLite, .
1010: 74 68 65 20 70 61 72 73 65 72 20 63 6f 64 65 20  the parser code 
1020: 67 65 6e 65 72 61 74 65 64 20 62 79 20 4c 65 6d  generated by Lem
1030: 6f 6e 20 68 61 73 20 6e 6f 20 75 6e 72 65 61 63  on has no unreac
1040: 68 61 62 6c 65 20 62 72 61 6e 63 68 65 73 2c 0a  hable branches,.
1050: 61 6e 64 20 63 6f 6e 74 61 69 6e 73 20 65 78 74  and contains ext
1060: 72 61 20 28 63 6f 6d 70 69 6c 65 2d 74 69 6d 65  ra (compile-time
1070: 20 73 65 6c 65 63 74 65 64 29 20 69 6e 73 74 72   selected) instr
1080: 75 6d 65 6e 74 61 74 69 6f 6e 20 75 73 65 66 75  umentation usefu
1090: 6c 0a 66 6f 72 20 6d 65 61 73 75 72 69 6e 67 20  l.for measuring 
10a0: 74 65 73 74 20 63 6f 76 65 72 61 67 65 2e 0a 0a  test coverage...
10b0: 3c 6c 69 3e 3c 70 3e 0a 4c 65 6d 6f 6e 20 73 75  <li><p>.Lemon su
10c0: 70 70 6f 72 74 73 20 63 6f 6e 64 69 74 69 6f 6e  pports condition
10d0: 61 6c 20 63 6f 6d 70 69 6c 61 74 69 6f 6e 20 6f  al compilation o
10e0: 66 20 67 72 61 6d 6d 61 72 20 66 69 6c 65 20 72  f grammar file r
10f0: 75 6c 65 73 2c 20 73 6f 20 74 68 61 74 0a 61 20  ules, so that.a 
1100: 64 69 66 66 65 72 65 6e 74 20 70 61 72 73 65 72  different parser
1110: 20 63 61 6e 20 62 65 20 67 65 6e 65 72 61 74 65   can be generate
1120: 64 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 63  d depending on c
1130: 6f 6d 70 69 6c 65 2d 74 69 6d 65 20 6f 70 74 69  ompile-time opti
1140: 6f 6e 73 2e 0a 0a 3c 6c 69 3e 3c 70 3e 0a 41 73  ons...<li><p>.As
1150: 20 61 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 6f   a performance o
1160: 70 74 69 6d 69 7a 61 74 69 6f 6e 2c 20 72 65 64  ptimization, red
1170: 75 63 65 20 61 63 74 69 6f 6e 73 20 69 6e 20 74  uce actions in t
1180: 68 65 20 4c 65 6d 6f 6e 20 69 6e 70 75 74 20 67  he Lemon input g
1190: 72 61 6d 6d 61 72 0a 61 72 65 20 61 6c 6c 6f 77  rammar.are allow
11a0: 65 64 20 74 6f 20 63 6f 6e 74 61 69 6e 20 63 6f  ed to contain co
11b0: 6d 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 66 6f  mments of the fo
11c0: 72 6d 20 22 2f 2a 41 2d 6f 76 65 72 77 72 69 74  rm "/*A-overwrit
11d0: 65 73 2d 5a 2a 2f 22 20 74 6f 20 69 6e 64 69 63  es-Z*/" to indic
11e0: 61 74 65 0a 74 68 61 74 20 74 68 65 20 73 65 6d  ate.that the sem
11f0: 61 6e 74 69 63 20 76 61 6c 75 65 20 22 41 22 20  antic value "A" 
1200: 6f 6e 20 74 68 65 20 72 69 67 68 74 2d 68 61 6e  on the right-han
1210: 64 20 73 69 64 65 20 6f 66 20 74 68 65 20 72 75  d side of the ru
1220: 6c 65 20 69 73 20 61 6c 6c 6f 77 65 64 0a 74 6f  le is allowed.to
1230: 20 64 69 72 65 63 74 6c 79 20 6f 76 65 72 77 72   directly overwr
1240: 69 74 65 20 74 68 65 20 73 65 6d 61 6e 74 69 63  ite the semantic
1250: 20 76 61 6c 75 65 20 22 5a 22 20 6f 6e 20 74 68   value "Z" on th
1260: 65 20 6c 65 66 74 2d 68 61 6e 64 20 73 69 64 65  e left-hand side
1270: 2e 0a 54 68 69 73 20 73 69 6d 70 6c 65 20 6f 70  ..This simple op
1280: 74 69 6d 69 7a 61 74 69 6f 6e 20 72 65 64 75 63  timization reduc
1290: 65 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66  es the number of
12a0: 20 73 74 61 63 6b 20 6f 70 65 72 61 74 69 6f 6e   stack operation
12b0: 73 20 69 6e 20 74 68 65 0a 70 75 73 68 2d 64 6f  s in the.push-do
12c0: 77 6e 20 61 75 74 6f 6d 61 74 6f 6e 20 75 73 65  wn automaton use
12d0: 64 20 74 6f 20 70 61 72 73 65 20 74 68 65 20 69  d to parse the i
12e0: 6e 70 75 74 20 67 72 61 6d 6d 61 72 2c 20 61 6e  nput grammar, an
12f0: 64 20 74 68 75 73 20 69 6d 70 72 6f 76 65 0a 70  d thus improve.p
1300: 65 72 66 6f 72 6d 61 6e 63 65 20 6f 66 20 74 68  erformance of th
1310: 65 20 70 61 72 73 65 72 2e 20 20 49 74 20 61 6c  e parser.  It al
1320: 73 6f 20 6d 61 6b 65 73 20 74 68 65 20 67 65 6e  so makes the gen
1330: 65 72 61 74 65 64 20 63 6f 64 65 20 61 20 6c 69  erated code a li
1340: 74 74 6c 65 20 73 6d 61 6c 6c 65 72 2e 0a 3c 2f  ttle smaller..</
1350: 75 6c 3e 0a 0a 3c 70 3e 54 68 65 20 70 61 72 73  ul>..<p>The pars
1360: 69 6e 67 20 6f 66 20 53 51 4c 20 73 74 61 74 65  ing of SQL state
1370: 6d 65 6e 74 73 20 69 73 20 61 20 73 69 67 6e 69  ments is a signi
1380: 66 69 63 61 6e 74 20 63 6f 6e 73 75 6d 65 72 20  ficant consumer 
1390: 6f 66 20 43 50 55 20 63 79 63 6c 65 73 20 0a 69  of CPU cycles .i
13a0: 6e 20 61 6e 79 20 53 51 4c 20 64 61 74 61 62 61  n any SQL databa
13b0: 73 65 20 65 6e 67 69 6e 65 2e 20 20 4f 6e 2d 67  se engine.  On-g
13c0: 6f 69 6e 67 20 65 66 66 6f 72 74 73 20 74 6f 20  oing efforts to 
13d0: 6f 70 74 69 6d 69 7a 65 20 53 51 4c 69 74 65 20  optimize SQLite 
13e0: 68 61 76 65 20 63 61 75 73 65 64 0a 74 68 65 20  have caused.the 
13f0: 64 65 76 65 6c 6f 70 65 72 73 20 74 6f 20 73 70  developers to sp
1400: 65 6e 64 20 61 20 6c 6f 74 20 6f 66 20 74 69 6d  end a lot of tim
1410: 65 20 74 77 65 61 6b 69 6e 67 20 4c 65 6d 6f 6e  e tweaking Lemon
1420: 20 74 6f 20 67 65 6e 65 72 61 74 65 20 66 61 73   to generate fas
1430: 74 65 72 0a 70 61 72 73 65 72 73 2e 20 20 54 68  ter.parsers.  Th
1440: 65 73 65 20 65 66 66 6f 72 74 73 20 68 61 76 65  ese efforts have
1450: 20 62 65 6e 65 66 69 74 65 64 20 61 6c 6c 20 75   benefited all u
1460: 73 65 72 73 20 6f 66 20 74 68 65 20 4c 65 6d 6f  sers of the Lemo
1470: 6e 20 70 61 72 73 65 72 20 67 65 6e 65 72 61 74  n parser generat
1480: 6f 72 2c 0a 6e 6f 74 20 6a 75 73 74 20 53 51 4c  or,.not just SQL
1490: 69 74 65 2e 20 20 42 75 74 20 69 66 20 4c 65 6d  ite.  But if Lem
14a0: 6f 6e 20 68 61 64 20 62 65 65 6e 20 61 20 73 65  on had been a se
14b0: 70 61 72 61 74 65 6c 79 20 6d 61 69 6e 74 61 69  parately maintai
14c0: 6e 65 64 20 74 6f 6f 6c 2c 20 69 74 0a 77 6f 75  ned tool, it.wou
14d0: 6c 64 20 68 61 76 65 20 62 65 65 6e 20 6d 6f 72  ld have been mor
14e0: 65 20 64 69 66 66 69 63 75 6c 74 79 20 74 6f 20  e difficulty to 
14f0: 6d 61 6b 65 20 63 6f 6f 72 64 69 6e 61 74 65 64  make coordinated
1500: 20 63 68 61 6e 67 65 73 20 74 6f 20 62 6f 74 68   changes to both
1510: 20 53 51 4c 69 74 65 0a 61 6e 64 20 4c 65 6d 6f   SQLite.and Lemo
1520: 6e 2c 20 61 6e 64 20 61 73 20 61 20 72 65 73 75  n, and as a resu
1530: 6c 74 20 6e 6f 74 20 61 73 20 6d 75 63 68 20 6f  lt not as much o
1540: 70 74 69 6d 69 7a 61 74 69 6f 6e 20 77 6f 75 6c  ptimization woul
1550: 64 20 68 61 76 65 20 62 65 65 6e 0a 61 63 63 6f  d have been.acco
1560: 6d 70 6c 69 73 68 65 64 2e 20 20 48 65 6e 63 65  mplished.  Hence
1570: 2c 20 74 68 65 20 66 61 63 74 20 74 68 61 74 20  , the fact that 
1580: 74 68 65 20 70 61 72 73 65 72 20 67 65 6e 65 72  the parser gener
1590: 61 74 6f 72 20 74 6f 6f 6c 20 69 73 20 69 6e 63  ator tool is inc
15a0: 6c 75 64 65 64 0a 69 6e 20 74 68 65 20 73 6f 75  luded.in the sou
15b0: 72 63 65 20 74 72 65 65 20 66 6f 72 20 53 51 4c  rce tree for SQL
15c0: 69 74 65 20 68 61 73 20 74 75 72 6e 65 64 20 6f  ite has turned o
15d0: 75 74 20 74 6f 20 62 65 20 61 20 6e 65 74 20 62  ut to be a net b
15e0: 65 6e 65 66 69 74 20 66 6f 72 20 62 6f 74 68 0a  enefit for both.
15f0: 74 68 65 20 74 6f 6f 6c 20 69 74 73 65 6c 66 20  the tool itself 
1600: 61 6e 64 20 66 6f 72 20 53 51 4c 69 74 65 2e 0a  and for SQLite..
1610: 0a 3c 68 31 3e 48 69 73 74 6f 72 79 20 4f 66 20  .<h1>History Of 
1620: 4c 65 6d 6f 6e 3c 2f 68 31 3e 0a 0a 3c 70 3e 4c  Lemon</h1>..<p>L
1630: 65 6d 6f 6e 20 77 61 73 20 6f 72 69 67 69 6e 61  emon was origina
1640: 6c 20 77 72 69 74 74 65 6e 20 62 79 20 44 2e 20  l written by D. 
1650: 52 69 63 68 61 72 64 20 48 69 70 70 20 28 61 6c  Richard Hipp (al
1660: 73 6f 20 74 68 65 20 63 72 65 61 74 6f 72 20 6f  so the creator o
1670: 66 20 53 51 4c 69 74 65 29 0a 77 68 69 6c 65 20  f SQLite).while 
1680: 68 65 20 77 61 73 20 69 6e 20 67 72 61 64 75 61  he was in gradua
1690: 74 65 20 73 63 68 6f 6f 6c 20 61 74 20 44 75 6b  te school at Duk
16a0: 65 20 55 6e 69 76 65 72 73 69 74 79 20 62 65 74  e University bet
16b0: 77 65 65 6e 20 31 39 38 37 20 61 6e 64 20 31 39  ween 1987 and 19
16c0: 39 32 2e 0a 54 68 65 20 6f 72 69 67 69 6e 61 6c  92..The original
16d0: 20 63 72 65 61 74 69 6f 6e 20 64 61 74 65 20 6f   creation date o
16e0: 66 20 4c 65 6d 6f 6e 20 68 61 73 20 62 65 65 6e  f Lemon has been
16f0: 20 6c 6f 73 74 2c 20 62 75 74 20 77 61 73 20 70   lost, but was p
1700: 72 6f 62 61 62 6c 79 20 73 6f 6d 65 74 69 6d 65  robably sometime
1710: 0a 61 72 6f 75 6e 64 20 31 39 39 30 2e 20 20 4c  .around 1990.  L
1720: 65 6d 6f 6e 20 67 65 6e 65 72 61 74 65 73 20 61  emon generates a
1730: 6e 20 4c 41 4c 52 28 31 29 20 70 61 72 73 65 72  n LALR(1) parser
1740: 2e 20 20 54 68 65 72 65 20 77 61 73 20 63 6f 6d  .  There was com
1750: 70 61 6e 69 6f 6e 20 0a 4c 4c 28 31 29 20 70 61  panion .LL(1) pa
1760: 72 73 65 72 20 67 65 6e 65 72 61 74 6f 72 20 74  rser generator t
1770: 6f 6f 6c 20 6e 61 6d 65 64 20 22 4c 69 6d 65 22  ool named "Lime"
1780: 2c 20 62 75 74 20 74 68 65 20 73 6f 75 72 63 65  , but the source
1790: 20 63 6f 64 65 20 66 6f 72 20 4c 69 6d 65 0a 68   code for Lime.h
17a0: 61 73 20 62 65 65 6e 20 6c 6f 73 74 2e 0a 0a 3c  as been lost...<
17b0: 70 3e 54 68 65 20 4c 65 6d 6f 6e 20 73 6f 75 72  p>The Lemon sour
17c0: 63 65 20 63 6f 64 65 20 77 61 73 20 6f 72 69 67  ce code was orig
17d0: 69 6e 61 6c 6c 79 20 77 72 69 74 74 65 6e 20 61  inally written a
17e0: 73 20 73 65 70 61 72 61 74 65 20 73 6f 75 72 63  s separate sourc
17f0: 65 20 66 69 6c 65 73 2c 0a 61 6e 64 20 6f 6e 6c  e files,.and onl
1800: 79 20 6c 61 74 65 72 20 6d 65 72 67 65 64 20 69  y later merged i
1810: 6e 74 6f 20 61 20 73 69 6e 67 6c 65 20 22 6c 65  nto a single "le
1820: 6d 6f 6e 2e 63 22 20 73 6f 75 72 63 65 20 66 69  mon.c" source fi
1830: 6c 65 2e 0a 0a 3c 70 3e 54 68 65 20 61 75 74 68  le...<p>The auth
1840: 6f 72 20 6f 66 20 4c 65 6d 6f 6e 20 61 6e 64 20  or of Lemon and 
1850: 53 51 4c 69 74 65 20 28 48 69 70 70 29 20 72 65  SQLite (Hipp) re
1860: 70 6f 72 74 73 20 74 68 61 74 20 68 69 73 20 43  ports that his C
1870: 20 70 72 6f 67 72 61 6d 6d 69 6e 67 0a 73 6b 69   programming.ski
1880: 6c 6c 73 20 77 65 72 65 20 67 72 65 61 74 6c 79  lls were greatly
1890: 20 65 6e 68 61 6e 63 65 64 20 62 79 20 73 74 75   enhanced by stu
18a0: 64 79 69 6e 67 20 4a 6f 68 6e 20 4f 75 73 74 65  dying John Ouste
18b0: 72 68 6f 75 74 27 73 20 6f 72 69 67 69 6e 61 6c  rhout's original
18c0: 0a 73 6f 75 72 63 65 20 63 6f 64 65 20 74 6f 20  .source code to 
18d0: 54 63 6c 2e 20 20 48 69 70 70 20 64 69 73 63 6f  Tcl.  Hipp disco
18e0: 76 65 72 65 64 20 61 6e 64 20 73 74 75 64 69 65  vered and studie
18f0: 64 20 54 63 6c 20 69 6e 20 31 39 39 33 2e 20 20  d Tcl in 1993.  
1900: 4c 65 6d 6f 6e 0a 77 61 73 20 77 72 69 74 74 65  Lemon.was writte
1910: 6e 20 62 65 66 6f 72 65 20 74 68 65 6e 2c 20 61  n before then, a
1920: 6e 64 20 53 51 4c 69 74 65 20 61 66 74 65 72 77  nd SQLite afterw
1930: 61 72 64 73 2e 20 20 54 68 65 72 65 20 69 73 20  ards.  There is 
1940: 61 20 63 6c 65 61 72 0a 64 69 66 66 65 72 65 6e  a clear.differen
1950: 63 65 20 69 6e 20 74 68 65 20 63 6f 64 69 6e 67  ce in the coding
1960: 20 73 74 79 6c 65 73 20 6f 66 20 74 68 65 73 65   styles of these
1970: 20 74 77 6f 20 70 72 6f 64 75 63 74 73 2c 20 77   two products, w
1980: 69 74 68 20 53 51 4c 69 74 65 20 73 65 65 6d 69  ith SQLite seemi
1990: 6e 67 0a 74 6f 20 62 65 20 63 6c 65 61 6e 65 72  ng.to be cleaner
19a0: 2c 20 6d 6f 72 65 20 72 65 61 64 61 62 6c 65 2c  , more readable,
19b0: 20 61 6e 64 20 65 61 73 69 65 72 20 74 6f 20 6d   and easier to m
19c0: 61 69 6e 74 61 69 6e 2e 0a                       aintain..