簡介

在HTML中，有一個很重要的理論：塊元素和行內(nèi)元素。在CSS中極其重要的一個理論——CSS盒子模型。 在“CSS盒子模型”理論中，頁面中的所有元素都可以看成一個盒子，并且占據(jù)著一定的頁面空間。

一個頁面由很多盒子組成，這些盒子之間會互相影響，因此掌握盒子模型需要從兩個方面來理解：一是理解單獨(dú)一個盒子的內(nèi)部結(jié)構(gòu)（往往是padding），二是理解多個盒子之間的相互關(guān)系（往往是margin）。

2 盒子模型概念

盒模型指的是網(wǎng)頁元素的結(jié)構(gòu)。當(dāng)指定一個元素的寬度或高度時，便設(shè)置了元素內(nèi)容的尺寸，可以把每個元素都看成一個盒子，盒子模型是由4個屬性組成，號稱“盒尺寸四大家族”：

• content（內(nèi)容區(qū)），可以是文本或圖片 —— 變化多端
• padding（內(nèi)邊距），用于定義內(nèi)容與邊框之間的距離 —— 溫和向內(nèi)
• margin（外邊距），用于定義當(dāng)前元素與其它元素之間的距離 —— 激進(jìn)對外
• border（邊框），用于定義元素的邊框 —— 功勛卓越

此外，在盒子模型中，還有寬度（width）和高度（height）兩大輔助性屬性。記住，所有的元素都可以看成一個盒子 。如下圖所示：

2.1 內(nèi)容區(qū)

內(nèi)容區(qū)是CSS盒子模型的中心，它呈現(xiàn)了盒子的主要信息內(nèi)容，這些內(nèi)容可以是文本、圖片等多種類型。內(nèi)容區(qū)是盒子模型必備的組成部分，其他3個部分都是可選的。 內(nèi)容區(qū)有3個屬性：width、height和overflow。使用width和height屬性可以指定盒子內(nèi)容區(qū)的高度和寬度。在這里注意一點(diǎn)，width和height這兩個屬性是針對內(nèi)容區(qū)content而言的，并不包括padding部分。 當(dāng)內(nèi)容過多，超出width和height時，可以使用overflow屬性來指定溢出處理方式。

2.2 內(nèi)邊距

內(nèi)邊距，指的是內(nèi)容區(qū)和邊框之間的空間，可以看成是內(nèi)容區(qū)的背景區(qū)域。padding屬性接受長度值或百分比值，但不允許使用負(fù)值。 關(guān)于內(nèi)邊距的屬性有5種：padding-top、padding-bottom、padding-left、padding-right，以及綜合了以上4個方向的簡寫內(nèi)邊距屬性padding。使用這5種屬性可以指定內(nèi)容區(qū)與各方向邊框之間的距離。

2.2.1 元素的尺寸

因?yàn)镃SS中默認(rèn)的box-sizing是content-box，所以使用padding會增加元素的尺寸。

.box {
　  width: 80px;　  
    padding: 20px;
}

如果不考慮其他CSS干擾，此時.box元素所占據(jù)的寬度就應(yīng)該是120像素（80px+20px×2），這其實(shí)是不符合現(xiàn)實(shí)世界的認(rèn)知的，人們總是習(xí)慣把代碼世界和現(xiàn)實(shí)世界做映射，因此，新人難免會在padding的尺寸問題上踩到點(diǎn)坑。這也導(dǎo)致很多人樂此不疲地設(shè)置box-sizing 為border-box，甚至全局設(shè)置。

2.2.2 標(biāo)簽元素內(nèi)置的padding

• ol/ul列表內(nèi)置padding-left，但是單位是px不是em。
• 很多表單元素都內(nèi)置padding。例如：所有瀏覽器<input>/<textarea>輸入框內(nèi)置padding；所有瀏覽器<button>按鈕內(nèi)置padding；所有瀏覽器<radio>/<chexkbox>單復(fù)選框無內(nèi)置padding。

2.3 外邊距

外邊距，指的是兩個盒子之間的距離，它可能是子元素與父元素之間的距離，也可能是兄弟元素之間的距離。外邊距使得元素之間不必緊湊地連接在一起，是CSS布局的一個重要手段。 外邊距的屬性也有5種：margin-top、margin-bottom、margin-left、margin-right，以及綜合了以上4個方向的簡寫外邊距屬性margin。 同時，CSS允許給外邊距屬性指定負(fù)數(shù)值，當(dāng)外邊距為負(fù)值時，整個盒子將向指定負(fù)值的相反方向移動，以此產(chǎn)生盒子的重疊效果，這就是傳說中的“負(fù)margin技術(shù)”。

2.3.1 margin與元素尺寸

• 元素的內(nèi)部尺寸

只有元素是“充分利用可用空間”狀態(tài)的時候，margin才可以改變元素的可視尺寸。比方說，如下CSS：

.header {
　width: 160px;　
  margin: 0 -5px;
}

此時元素寬度還是160像素，尺寸無變化。因?yàn)橹灰獙挾仍O(shè)定，margin就無法改變元素尺寸，這和padding是不一樣的。

但是，如果是下面這樣的HTML和CSS：

<div class="header">
　  <div class="son">
</div></div>
.header { width: 160px; }
.menu {　margin: 0 -5px; }

則.menu元素的寬度就是165像素了，尺寸通過負(fù)值設(shè)置變大了，因?yàn)榇藭r的寬度表現(xiàn)是“充分利用可用空間”。

• 元素的外部尺寸

只要元素具有塊狀特性，無論有沒有設(shè)置width/height，無論是水平方向還是垂直方向，即使發(fā)生了margin合并，margin對外部尺寸都著著實(shí)實(shí)發(fā)生了影響。

2.3.2 margin合并

塊級元素的上外邊距（margin-top）與下外邊距（margin-bottom）有時會合并為單個外邊距，這樣的現(xiàn)象稱為“margin合并”。

• margin合并一般出現(xiàn)在以下3種場景：（1）相鄰兄弟元素margin合并。這是margin合并中最常見、最基本的。（2）父級和第一個/最后一個子元素。（3）空塊級元素的margin合并。
• margin合并的計(jì)算規(guī)則把margin合并的計(jì)算規(guī)則總結(jié)為：“正正取大值”， “正負(fù)值相加” ，“負(fù)負(fù)最負(fù)值”。
• margin合并的意義對于兄弟元素的margin合并其作用和em類似，都是讓圖文信息的排版更加舒服自然。父子margin合并的意義在于：在頁面中任何地方嵌套或直接放入任何裸<div>，都不會影響原來的塊狀布局。<div>是網(wǎng)頁布局中非常常用的一個元素，其語義是沒有語義，也就是不代表任何特定類型的內(nèi)容，是一個通用型的具有流體特性的容器，可以用來分組或分隔。由于其作用就是分組的，因此，從行為表現(xiàn)上來看，一個純粹的<div>元素是不能夠也不可以影響原先的布局的。自身margin合并的意義在于可以避免不小心遺落或者生成的空標(biāo)簽影響排版和布局。

2.3.3 margin:auto

margin:auto的填充規(guī)則如下。 （1）如果一側(cè)定值，一側(cè)auto，則auto為剩余空間大小。 （2）如果兩側(cè)均是auto，則平分剩余空間。

2.4 邊框

在CSS盒子模型中，邊框與我們之前學(xué)過的邊框是一樣的。 邊框?qū)傩杂衎order-width、border-style、border-color，以及綜合了3類屬性的簡寫邊框?qū)傩詁order。

border屬性總是能解決很多棘手的問題，在在圖形構(gòu)建、體驗(yàn)優(yōu)化以及網(wǎng)頁布局這塊幾大放異彩，，同時保證其良好的兼容性和穩(wěn)定性。下面我們一起看看border都有哪些精彩的特性表現(xiàn)。

2.4.1 為什么border-width不支持百分比值

我們通過比對筆記本、手機(jī)發(fā)現(xiàn)，雖然兩臺設(shè)備的尺寸差異很大，但是邊框的大小相比而言就可以忽略不計(jì)了。邊框是不會因?yàn)樵O(shè)備大就按比例變大的。因此，如果支持百分比值，是不是就意味著設(shè)備大了邊框也跟著變大？有一張圖片，大片區(qū)域都是白色的，在白底背景上和文字混在一起，就會有一片奇怪的空白區(qū)域，會讓人產(chǎn)生沒對齊的假象，此時，我們給這張圖片套個1px灰色邊框，區(qū)域就明顯了，對吧！設(shè)計(jì)的初衷就是為了這么點(diǎn)兒事，沒有需要使用百分比值的場景。于是，綜合這兩點(diǎn)，造成了border-width不支持百分比值。

2.4.2 border與圖形構(gòu)建

border屬性可以輕松實(shí)現(xiàn)兼容性非常好的三角圖形效果，為什么可以呢？其底層原因受inset/outset 等看上去沒有實(shí)用價(jià)值的border-style屬性影響，邊框3D效果在互聯(lián)網(wǎng)早期其實(shí)還是挺潮的，那個時候人們喜歡有質(zhì)感的東西，為了呈現(xiàn)逼真的3D效果，自然在邊框轉(zhuǎn)角的地方一定要等分平滑處理，然后不同的方向賦予不同的顏色。然后，這一轉(zhuǎn)角規(guī)則也被solid類型的邊框給沿用了。因此，我們就不難理解下面的4色邊框的表現(xiàn)了：

div {
　  width: 10px; height: 10px; 　  
    border: 10px solid; 　  
    border-color: #f30 #00f #396 #0f0;
}

運(yùn)行一下上面的代碼看一下效果吧！

2.4.3 border與透明邊框技巧

這是提高用戶體驗(yàn)的一個小技巧，尤其在移動端，我們的操作工具一般就是我們的手指，但是，我們的手指粗細(xì)可以媲美胡蘿卜，而屏幕尺寸就那么點(diǎn)兒，如果我們正在走路，則一些精致的圖標(biāo)和按鈕很容易就點(diǎn)不中甚至誤點(diǎn)。

穩(wěn)妥的方法是外部再嵌套一層標(biāo)簽，專門控制點(diǎn)擊區(qū)域大小。如果對代碼要求較高，則可以使用padding或者透明border增加元素的點(diǎn)擊區(qū)域大小。

3 總結(jié)

現(xiàn)實(shí)生活中看到的盒子，有正方形、長方形、圓柱形等，依據(jù)形狀特點(diǎn)，可包裹不同物件。CSS中的盒子雖然沒有那么多的形狀，但在視覺呈現(xiàn)上不同類型的盒子還是會有很大的不同，有的盒子要占據(jù)一行，有的盒子不能定義外邊距、寬度和高度，有的盒子寬度和高度能自適應(yīng)。CSS中用display指定盒類型（即框類型），常用的有 block（塊）、inline（行內(nèi)）、inline-block（行內(nèi)塊）、table（表格），以及CSS3新增的flexbox（伸縮盒）。 HTML 元素只有兩種默認(rèn)的盒類型，即塊級元素（block-level element）和行內(nèi)元素（inline-level element）。其中行內(nèi)元素不可定義CSS屬性width、height、上下margin和上下padding。常用的span和div分別是行內(nèi)元素和塊級元素。

由此可見，需要掌握的內(nèi)容太多，要想學(xué)會所有布局相關(guān)的技術(shù)不太現(xiàn)實(shí)。高級的布局話題基于文檔流和盒模型等概念，這些是決定網(wǎng)頁元素的大小和位置的基本規(guī)則。因此理解和掌握如何設(shè)置元素的大小和位置至關(guān)重要。

4 最后的最后

為初學(xué)者提供學(xué)習(xí)指南，為從業(yè)者提供參考價(jià)值。我堅(jiān)信碼農(nóng)也具有產(chǎn)生洞見的能力。關(guān)注【碼農(nóng)洞見】，一起學(xué)習(xí)和交流吧！

先聲明，我不是標(biāo)題黨，我真的是用5000行左右的JS實(shí)現(xiàn)了一個輕量級的關(guān)系型數(shù)據(jù)庫JSDB，核心是一個SQL編譯器，支持增刪改查。
源代碼放到github上了：https://github.com/lavezhang/jsdb

如果你需要修改程序引入新的特性，請嚴(yán)格遵守GPL協(xié)議。

如果轉(zhuǎn)發(fā)此文，請注明來源。

SQL范例

前言

工作太忙，好久沒寫這種長文章了，難得今年國慶超長，又不便外出，這才有時間“不務(wù)正業(yè)”。

為什么要用一周的時間寫這么個玩意兒？看起來也沒什么用處，畢竟，沒有哪個系統(tǒng)需要在瀏覽器中跑一個關(guān)系型數(shù)據(jù)庫。

如果要搞一個"年度最無用項(xiàng)目"的頒獎，估計(jì)JSDB榜上有名。

我一直有一個夢想，要研發(fā)一款咱們中國人自己的列式存儲分布式數(shù)據(jù)庫！（此處應(yīng)有掌聲_）

古人講，不積跬步無以至千里，JSDB就算探索數(shù)據(jù)庫自研的一個開端吧。

為什么用TypeScript？因?yàn)閏oding效率非常高，跟Python差不多，而且有瀏覽器就能運(yùn)行，非常方便，很適合做技術(shù)預(yù)研，正式開發(fā)時再改為C或Rust。

如文章開頭所言，JSDB的核心是一個SQL編譯器，準(zhǔn)確地說，是解釋器。學(xué)習(xí)過《編譯原理》的同學(xué)，對這個不會陌生。

解釋器也是屬于編譯器的范疇，所以，后面仍然會沿用“SQL編譯器”的說法。

概述

按照執(zhí)行順序，JSDB的代碼由四個部分構(gòu)成：

1、詞法分析，得到 token 列表。參見GitHub源代碼，SqlLexer.ts 文件，基于狀態(tài)機(jī)實(shí)現(xiàn)，詳見 lex_state_flow.xlsx 文件。

2、語法語義分析，得到抽象語法數(shù)。參見 SqlParser.ts 文件，自上而下解析，這是行數(shù)最多的一個文件。

3、對抽象語法樹的執(zhí)行。參見SqlDatabase.ts文件，以及ast目錄下的幾十個語法節(jié)點(diǎn)的compute(ctx)方法。

4、單元測試和應(yīng)用范例。test目錄和test.html文件里運(yùn)行著所有的單元測試，index.html文件就是文章開頭的體驗(yàn)頁面，語法高亮功能基于第三方組件codemirror實(shí)現(xiàn)，在 static/codemirror 目錄里。

JSDB確實(shí)是一個關(guān)系型數(shù)據(jù)庫，參照SQL92標(biāo)準(zhǔn)實(shí)現(xiàn)，但它并不完整，只實(shí)現(xiàn)了最核心的一小部分功能，可以滿足日常基本需求。主要特性有：

01、create table 語句

02、insert 語句

03、update 語句

04、delete 語句

05、select 語句，含：distinct / from / join / left join / where / group by / having / order by / limit

06、算數(shù)運(yùn)算符：+、-、*、/、%

07、關(guān)系運(yùn)算符：>、>=、<、<=、=、<>

08、條件運(yùn)算符：and、or、not

09、其它操作符：like、not like、is null、is not null、between

10、動態(tài)占位符：?

11、標(biāo)準(zhǔn)函數(shù)，目前只實(shí)現(xiàn)了：ifnull、len、substr、substring、instr、concat。
如果需要增加新的標(biāo)準(zhǔn)函數(shù)，可以在SqlContext類的構(gòu)造函數(shù)中實(shí)現(xiàn)，所有的標(biāo)準(zhǔn)函數(shù)都注冊到SqlContext.standardFunctions字段中。

尚未實(shí)現(xiàn)的重要特性有：

1、with / sub query / exists / alter / truncate 等

2、數(shù)據(jù)存儲。一直在內(nèi)存中運(yùn)行，大家可以修改程序，寫入瀏覽器localStorage中。

3、事務(wù)。這個需要事務(wù)日志來實(shí)現(xiàn)，以后再搞，不過在內(nèi)存中模擬一個，問題也不大。

4、并發(fā)鎖。JS是單線程，沒有真正的并發(fā)，有了一個不用實(shí)現(xiàn)它的好理由。

5、其它功能。詳見大學(xué)時的《數(shù)據(jù)庫原理》。

如果大家多多點(diǎn)贊，我就把它實(shí)現(xiàn)得更加完整。_

本文針對編譯器和數(shù)據(jù)庫的入門讀者，寫了很多小白的內(nèi)容，高手請飄過。

第一章 詞法分析

關(guān)于詞法分析，程序本身并不難。無論何種編程語言，它的詞法分析模塊一般都不超過300行，有些甚至只有幾十行。

很多人喜歡用 lex/yacc/antr 之類的工具來自動生成，我不喜歡，我就是喜歡手?jǐn)]的感覺。

詞法分析就是要識別源代碼中的一個個token，一般包括：關(guān)鍵字、標(biāo)識符、字符串、數(shù)值、布爾值、空值、運(yùn)算符、操作符、分隔符。

例如，一條SQL語句：

<pre style="margin: 0px; padding: 0px; overflow-wrap: break-word; font-family: "Courier New" !important; font-size: 12px !important;">select name, (total_score / 4) as avg_score from student where id = '010123'</pre>

涉及如下token：

關(guān)鍵字：select、as、from、where

標(biāo)識符：name、total_score、avg_score、student、id

字符串：'010123'

數(shù)值：4

運(yùn)算符：/、=

分隔符：, ( )

如何識別這些token呢？兩種辦法：硬實(shí)現(xiàn)、狀態(tài)機(jī)。

硬實(shí)現(xiàn)，就是用一大坨的 if/else 識別每一個字符。

舉例來說，如果當(dāng)前字符是一個單引號，程序就認(rèn)為是一個字符串的開始，于是用一個while循環(huán)來判斷，直到遇到另一個單引號，表示字符串的結(jié)束。

硬實(shí)現(xiàn)的最大問題在于，條件分支太多，很容易遺漏或判斷錯誤。

比如，字符串中是要處理轉(zhuǎn)義符的，遇到換行符則要記錄錯誤。

再比如，'>=' 和 '> =' 是不一樣的，前者表示大于等于號，后者表示兩個運(yùn)算符：大于號和等于號，因?yàn)橹虚g有個空格，而硬寫的程序往往會忽略掉這些空白符，什么時候空白符該忽略，什么時候不該忽略，必須把規(guī)則一條條列出來，針對處理。

類似的情況還非常多，所以，硬寫出來的詞法分析程序，無一例外，都是非常復(fù)雜的。

給大家看一段用 java 硬實(shí)現(xiàn)的字符串識別程序：

View Code

上述java程序是我很久之前寫的，整個詞法程序漏洞百出。

即使是硬實(shí)現(xiàn)，也要提前梳理各種轉(zhuǎn)換關(guān)系，既然這樣，為什么不用狀態(tài)機(jī)呢？

狀態(tài)機(jī)是老一輩計(jì)算機(jī)科學(xué)家發(fā)明的理論，基于狀態(tài)機(jī)和BNF產(chǎn)生式，詞法分析程序完全可以被形式化了。

一個字符串識別的狀態(tài)機(jī)范例如下：

一個字符串就涉及4個狀態(tài)，完整的SQL詞法涉及幾十個狀態(tài)，如果都用狀態(tài)流轉(zhuǎn)圖畫出來，實(shí)在太復(fù)雜，所以，一般都改用等價(jià)的表格來表示。

我在github上放了一個叫 lex_state_flow.xlsx 的Excel文件，截圖如下：

SQL詞法分析狀態(tài)表

需要特別解釋兩點(diǎn)：

1、狀態(tài)2到狀態(tài)6的名字用紫色標(biāo)記，因?yàn)檫@幾個狀態(tài)是中間狀態(tài)，最終不能獨(dú)立存在。

2、狀態(tài)轉(zhuǎn)換的單元格有三種顏色：灰色、白色、紅色。

  灰色表示回到初始狀態(tài)；

  白色表示正數(shù)狀態(tài)，轉(zhuǎn)換狀態(tài)時，前面的緩存內(nèi)容作為一個token，當(dāng)前新字符進(jìn)入新的狀態(tài)；比如，當(dāng)前狀態(tài)是 TK_IDENTITY，這時輸入一個字符 '>'，則緩沖區(qū)的內(nèi)容得到一個標(biāo)識符token，新輸入的 '>' 字符進(jìn)入 TK_GT 狀態(tài)。

  紅色表示負(fù)數(shù)狀態(tài)，轉(zhuǎn)換狀態(tài)時，前面的內(nèi)容加上當(dāng)前字符一起進(jìn)入新的狀態(tài)。比如，當(dāng)前狀態(tài)是 TK_GT，這時輸入一個字符 ‘=’，則緩沖區(qū)的內(nèi)容 '>' 加上新輸入的 '='，得到 '>=' ，進(jìn)入新的狀態(tài) TK_GE，表示大于等于。

詞法分析的核心，正是這個狀態(tài)表格。要完成這樣一張表格，看著容易，實(shí)際并不容易，我也是花了一天時間。因?yàn)橐坏┻z漏了某個狀態(tài)或輸入字符，整個表格都要改一遍，擼得手都起繭子了。

完成狀態(tài)表格后，基于此實(shí)現(xiàn)的詞法掃描程序，就可以非常簡單了。文件名為 SqlLexer.ts，代碼如下：

View Code

細(xì)心的同學(xué)可能會發(fā)現(xiàn)，代碼里的關(guān)鍵字狀態(tài)，并沒有出現(xiàn)在狀態(tài)表格中。

原則上來講，每個關(guān)鍵字都是一個單獨(dú)的狀態(tài)。但是，如果都列入狀態(tài)表格，這個表格就超級復(fù)雜了。比如，為了識別一個關(guān)鍵字select，要依次檢查連續(xù)字符 ‘s’ 'e' 'l' 'e' 'c' 't' ，即使到了最后一個字符 't' ，也不意味著結(jié)束，后面跟上一個數(shù)字 '1'，立馬就不是關(guān)鍵字了，而是一個普通的標(biāo)識符 select1。而JSDEB一共支持38個關(guān)鍵字，都要并入表格，簡直難以想象。所以，通常的做法是，先統(tǒng)一作為標(biāo)識符來識別，完成一個token時，再進(jìn)一步判斷是否為某個關(guān)鍵字，而在狀態(tài)表格中就不畫了。

一個token用一個三元組來表達(dá)，在TypeScript中是Tuple類型，實(shí)際就是JavaScript中的數(shù)組。這里有三個值，分別是number、string、number類型。

第0個值，number類型，表示token的類型，對應(yīng)于狀態(tài)表格中的狀態(tài)id；

第1個值，string類型，表示token的內(nèi)容，對于字符串 'abc' 來說，存的不是 abc，而是 'abc'，也就是說，原原本本保存，后面在執(zhí)行的時候才會翻譯為 abc；

第2個值，number類型，表示token所在的行號，提示詞法錯誤的時候，可以明確告知在哪一行。

有的同學(xué)可能會問，為什么不用一個class來表示。其實(shí)也可以用class表示，但是，掃描一段源代碼，得到的token非常多，如果用class表示，會浪費(fèi)更多的資源，不如用數(shù)組，返璞歸真，簡單實(shí)用。

用一組單元測試來驗(yàn)證程序是否正確。

代碼中的Assert類是一個簡單的斷言類，用于單元測試中的條件檢查。

/test/SqlLexerTest.ts 文件包含了所有詞法掃描的測試用例。截取一段代碼如下：

View Code

到這里詞法分析就結(jié)束了，得到一個token列表，接下來，會對這個token列表進(jìn)行掃描，也就是語法解析。

第二章 語法解析

語法解析也叫語法分析，讀入token列表，輸出抽象語法樹。

在編譯器設(shè)計(jì)中，以抽象語法樹的形式構(gòu)造一條SQL語句。例如SQL：

SELECT id, t.stf_name AS name FROM student t WHERE id = 123

會被解析成如下樹結(jié)構(gòu)：

SELECT語法樹

自上而下，遞歸解析，識別出每一個節(jié)點(diǎn)。

每種語法節(jié)點(diǎn)都是一個單獨(dú)的class，比如，SqlSelectNode、SqlFromNode、SqlWhereNode、SqlIdentityNode、StringNumberNode，等等。

數(shù)量有點(diǎn)多，一共39個。這39個類都是繼承自語法節(jié)點(diǎn)基類SqlNode。

詳細(xì)介紹一下：

value字段，用于保存節(jié)點(diǎn)的值。SqlStringNode存的是類似 'abc'這樣的值，SqlNumber存的是類似 123 這樣的值，SqlSelectNode存的是 select。

line字段，用于保存節(jié)點(diǎn)所在的行號。這個行號是從前一階段的詞法分析中得到的，就是token三元組的最后一個值。

nodes字段，用于保存子節(jié)點(diǎn)。例如，SqlExpAddNode的value是 + 或 - ，它的nodes是兩個表達(dá)式節(jié)點(diǎn)，表示這個表達(dá)式的結(jié)果相加或相減。

compute方法，用于計(jì)算表達(dá)式的值。例如，id = 3，如果運(yùn)行時id的值為3，則運(yùn)行時返回True，否則返回False。再例如，a * 3，如果運(yùn)行時a的值為10，則運(yùn)行時返回30。

typeDeriva方法，用于類型推導(dǎo)。如果數(shù)據(jù)庫列id是number類型，那么 id + 100 的結(jié)果也應(yīng)該是numer類型；如果 id列是varchar類型，那么 id + 100也是varchar類型。這就是類型推導(dǎo)。

類型推導(dǎo)非常重要，主要用于類型安全檢查。比如，count()的結(jié)果一定是numer類型，如果寫出 substr(count(),1) 這樣的表達(dá)式，就應(yīng)該給出語法錯誤。此外，類型推導(dǎo)還可以用于提前確定查詢結(jié)果集中每一列的類型，構(gòu)造好結(jié)果集，以容納接下來返回的數(shù)據(jù)。比如，對于C#或Java，查詢數(shù)據(jù)庫后得到DataTable或RecordSet，可以獲取到每一列的類型信息，這些類型信息在正式查詢數(shù)據(jù)庫之前通過語法分析就已經(jīng)得到了。

推導(dǎo)出的類型，理論上來說，應(yīng)該跟compute方法返回的值，保持一致。

實(shí)現(xiàn)各個語法節(jié)點(diǎn)子類的時候，重點(diǎn)是重寫compute和typeDeriva這兩個方法。

接下來講如何構(gòu)造這些語法節(jié)點(diǎn)。

有的節(jié)點(diǎn)具有明確的特征，比如 select節(jié)點(diǎn)，以關(guān)鍵字SELECT開頭，只要掃描這個關(guān)鍵字，就可以認(rèn)為是一條SELECT語句，然后按照SELECT語句的規(guī)則繼續(xù)往下掃描。

有的節(jié)點(diǎn)則不那么容易判斷，具有二義性。

比如 減號 -，如果是 a - b，則表示相減；如果是a = -b，則表示負(fù)號。

再比如關(guān)鍵字 AND，如果是 a AND b，則表示條件與；如果是 a BETWEEN b AND c，則表示一個數(shù)值范圍或字符串范圍。

這種情況下，需要通過上下文分析、優(yōu)先級判斷、消除文法左遞歸的辦法，來消除二義性。

JSDB實(shí)現(xiàn)的只是SQL92的子集，SELECT語法如下：

狀態(tài)表格

由于簡化了SELECT語法，所以相對來說還算簡單。唯一有難度的地方，在于表達(dá)式的解析，采用的方法是抄自“龍書”《編譯原理》。

自上而下，根據(jù)優(yōu)先級，依次解析 exp_or、exp_and、exp_eq、exp_rel、exp_add、exp_mult、exp_unary、factor。

先看一個簡單點(diǎn)的方法，parseExpRefNode，用于解析類似 t.id 這樣的字段引用表達(dá)式。

先嘗試解析第一個標(biāo)識符，然后是一個分隔符點(diǎn)，最后是結(jié)尾的標(biāo)識符。如果解析失敗，則添加一個SqlError。

接下來看parseExpOrNode、parseExpAndNode兩個方法，分別用于解析條件OR和AND的節(jié)點(diǎn)。由于函數(shù)是一層層調(diào)用進(jìn)去的，所以，實(shí)際上的構(gòu)造節(jié)點(diǎn)順序是反過來的，從factor開始，然后才依次是 unary、mult、add、rel、req、and、or 。

先是從左到右挨個解析，放到一個列表中，然后把列表中的元素轉(zhuǎn)換為一棵二叉樹，函數(shù)返回的是這棵二叉樹的根節(jié)點(diǎn)。

parseExpOrNode類：

parseExpAndNode類：

看著有點(diǎn)暈？沒關(guān)系，我畫一張圖，演示一下表達(dá)式 a OR b AND c OR d OR e 是如何轉(zhuǎn)換為二叉樹的。

測試代碼：

Assert.runCase('parse exp', function () {
    let parser = new SqlParser("a OR b AND c OR d OR e");
    let node = parser.parseExpOrNode(null);
    console.log(node.toString());
});

輸出如下二叉樹結(jié)構(gòu)：

|--SqlExpOrNode@1：or
    |--SqlExpOrNode@1：or
        |--SqlExpOrNode@1：or
            |--SqlIdentityNode@1：a
            |--SqlExpAndNode@1：and
                |--SqlIdentityNode@1：b
                |--SqlIdentityNode@1：c
        |--SqlIdentityNode@1：d
    |--SqlIdentityNode@1：e

構(gòu)造該二叉樹的步驟如下圖所示：

表達(dá)式二叉樹構(gòu)造順序

構(gòu)造完抽象語法樹后，不用生成機(jī)器碼，直接在語法樹上計(jì)算。

第三章 計(jì)算語法樹

前面提到過，語法樹節(jié)點(diǎn)基類SqlNode里有一個compute方法，用于計(jì)算節(jié)點(diǎn)的值，子類會重寫該方法，實(shí)現(xiàn)具體的計(jì)算邏輯。

語法節(jié)點(diǎn)太多了，咱們只講幾個關(guān)鍵節(jié)點(diǎn)的計(jì)算邏輯：

SqlNumberNode類，根據(jù)value字段的值是否有小數(shù)點(diǎn)，相應(yīng)返回parseInt(this.value)或parseFloat(this,value)。

SqlStringNode類，根據(jù)value字段的值返回字符串，去掉首尾的單引號，如果有轉(zhuǎn)義符，要進(jìn)行轉(zhuǎn)義。

SqlExpRelNode類，計(jì)算左右兩個子節(jié)點(diǎn)的值，比較其大小，返回True或False。

SqlExpAddNode類，計(jì)算左右兩個子節(jié)點(diǎn)的值，根據(jù)value字段的值是 '+' 還是 '-'，相應(yīng)執(zhí)行相加或相減。

SqlExpMulNode類，計(jì)算左右兩個子節(jié)點(diǎn)的值，根據(jù)value字段的值是 '*' 、'/' 還是 '%'，相應(yīng)執(zhí)行相乘、相除、取余。

SqlExpAndNode類，計(jì)算左右兩個子節(jié)點(diǎn)的值，如果都為True，才返回True，否則返回False。

SqlExpOrNode類，計(jì)算左右兩個子節(jié)點(diǎn)的值，如果都為False，才返回False，否則返回True。

SqlExpUnaryNode類，一元操作符，只有一個節(jié)點(diǎn)，計(jì)算其值。根據(jù)操作符的值是'+'、'-'、'not'，執(zhí)行相應(yīng)的取正、取負(fù)、取反邏輯。

SqlExpFuncNode類，執(zhí)行函數(shù)。首先從SqlContext.standardFunctions字段取一下，如果取到了，說明是標(biāo)準(zhǔn)函數(shù)，直接執(zhí)行，否則再看是不是聚合函數(shù)。聚合函數(shù)的執(zhí)行比較復(fù)雜，咱們單獨(dú)講。

SqlInsertNode類，執(zhí)行插入邏輯，返回受影響行數(shù)。

SqlUpdateNode類，執(zhí)行更新邏輯，返回受影響行數(shù)。

SqlDeleteNode類，執(zhí)行刪除邏輯，返回受影響行數(shù)。

SqlSelectNode類，執(zhí)行查詢邏輯，返回一個二維表SqlDataTable實(shí)例。這個最復(fù)雜，咱們接下來重點(diǎn)講。

其它語法節(jié)點(diǎn)的執(zhí)行邏輯，請參見源代碼。

接下來，重點(diǎn)講一下SqlSelectNode類和SqlExpFuncNode類的實(shí)現(xiàn)邏輯，也就是SELECT語句到底是怎么實(shí)現(xiàn)數(shù)據(jù)查詢的，這貨老復(fù)雜了，燒了不少腦細(xì)胞，大伙一定要給個贊。

第四章 SELECT語句

一條SELECT語句的執(zhí)行，可以分為如下幾個步驟：

1、根據(jù) from 節(jié)點(diǎn)，以及可能存在的 join 節(jié)點(diǎn)，合并出一張寬表（fullTable）。這里我沒有做任何優(yōu)化，直接生成一個笛卡爾積，所以，測試的數(shù)據(jù)量千萬不要太大，否則，運(yùn)行的速度夠你酸爽的~~~

2、如果有 join節(jié)點(diǎn)，執(zhí)行聯(lián)結(jié)規(guī)則。JSDB只支持 join 和 left join 這兩種最常用的聯(lián)結(jié)方式，其它聯(lián)結(jié)方式暫不支持。執(zhí)行on條件節(jié)點(diǎn)，如果返回False，表示沒有join上，這時再判斷是join還是left join，如果是join，就直接刪除；如果是left join，就填上null值。

不太好理解的是repeatJoinRows這個字段，這是為了處理重復(fù)join的問題。比如，from表有一條記錄，外鍵ID對應(yīng)一個 join表中的兩條記錄，也就是說，join表存在id重復(fù)的情況。針對這種情況，需要把重復(fù)join的數(shù)據(jù)也保留下來。

3、如果有 where 節(jié)點(diǎn)，執(zhí)行篩選規(guī)則。就是執(zhí)行SqlWhereNode節(jié)點(diǎn)，不符合條件的記錄，直接刪除。

4、如果有 group by 節(jié)點(diǎn)，則執(zhí)行分組規(guī)則。這個最復(fù)雜，分為以下幾個步驟：

4.1 首先要提取出 fields、having、orderby 這三個節(jié)點(diǎn)中的聚合表達(dá)式。

4.2 根據(jù) group by的節(jié)點(diǎn)，以及上一步得到的聚合表達(dá)式列表，構(gòu)造一張分組計(jì)算中間表，寫入上下文中，后面聚合函數(shù)計(jì)算時會用到。

4.3 遍歷寬表fullTable，計(jì)算分組中間表的值，得到分組中間表groupByMidTable。這段代碼不好理解，實(shí)際邏輯是在SqlExpFuncNode類中。為了遍歷一次就能算出所有聚合表達(dá)式的值，我封裝了一個SqlGroupByValue類，該類用于記錄一個聚合表達(dá)式的當(dāng)前最新的count行數(shù)、sum匯總、distinctValues去重值列表，以及當(dāng)前最新值，這個當(dāng)前最新值可以是行數(shù)、匯總，也可以是最大值、最小值、平均值，取決于具體的聚合函數(shù)。所以，一定要注意，普通SqlDataTable的單元值是string或number，但是分組中間表的單元值是SqlGroupByValue。

4.4 基于分組中間表groupByMidTable，根據(jù)fields節(jié)點(diǎn)進(jìn)行計(jì)算，得到結(jié)果表resultTable。為什么要再算一遍？因?yàn)椋瑢τ?count(*) * 10 這樣的表達(dá)式，在4.3小節(jié)中實(shí)際只計(jì)算了count(*)，乘以10的步驟是在這里計(jì)算的。另外，并不是所有聚合表達(dá)式都是要返回的，有些聚合表達(dá)式是在having或order節(jié)點(diǎn)中出現(xiàn)的，并不在fields節(jié)點(diǎn)中，所以，必須在這一步中集中處理一下。

涉及的函數(shù)表達(dá)式，尤其是聚合函數(shù)表達(dá)式，計(jì)算代碼如下：

5、如果沒有 group by 節(jié)點(diǎn)，直接在where篩選后的fullTable上根據(jù)fields節(jié)點(diǎn)進(jìn)行計(jì)算，得到結(jié)果表resultTable。這個就簡單很多了。

6、如果有 order by 節(jié)點(diǎn)，則對結(jié)果表resultTable進(jìn)行排序。由于排序規(guī)則可能包含多個條件，這里要分為三個步驟來計(jì)算：

6.1 遍歷resultTable表，每一行數(shù)據(jù)都得到一個orderByValues數(shù)組，包含了排序要用的值。如果是多個排序條件，數(shù)組就包含多個值。

6.2 計(jì)算每個排序條件的方向，默認(rèn)是asc。

6.3 根據(jù)排序表達(dá)式的值，以及排序方向，對數(shù)據(jù)行進(jìn)行排序。這里調(diào)用的是Array類的sort方法，傳入一個function，實(shí)現(xiàn)自定義排序。

7、如果有 limit 節(jié)點(diǎn)，則返回指定范圍的數(shù)據(jù)，也就是分頁時要用的東西。如果是limit n，則返回前面n行數(shù)據(jù)；如果是limit m, n，則從第m行開始，返回n行數(shù)據(jù)的。

到這里就得到最終的結(jié)果表了。

相對于SELECT語句，其它語句就簡單多了。

第五章 其它語句

DELETE語句的執(zhí)行分為兩步：執(zhí)行where篩選，然后根據(jù)row.id進(jìn)行刪除。

UPDATE語句也分為兩步：執(zhí)行where篩選，然后set規(guī)則更新指定列的數(shù)據(jù)。

INSERT語句也分為兩步：根據(jù)表構(gòu)造創(chuàng)建一個空行，然后更新指定列的數(shù)據(jù)。

CREATE TABLE語句，在 SqlDatabase 中創(chuàng)建一個新的 SqlDataTable 實(shí)例。

至此，幾個主要的語句都介紹了。

最后，我們寫幾個測試范例，展示一下運(yùn)行結(jié)果，這幾個測試范例，在文章開頭的“體驗(yàn)頁面”上都有展示。

第六章 程序展示

通過JS創(chuàng)建三張表：t_gender（性別字典表）、t_dept（部門字典表）、t_staff（員工表）。

var database = new SqlDatabase();
database.execute("create table t_gender(id number, name varchar(100))");
database.execute("create table t_dept(dept_id number, dept_name varchar)");
database.execute("create table t_staff(id varchar, name varchar, gender number, dept_id number)");

database.execute("insert into t_gender(id, name)values(1, 'Male')");
database.execute("insert into t_gender(id, name)values(2, 'Female')");

database.execute("insert into t_dept(dept_id, dept_name)values(101, 'Tech')");
database.execute("insert into t_dept(dept_id, dept_name)values(102, 'Finance')");

database.execute("insert into t_staff(id, name, gender, dept_id)values('016001', 'Jack', 1, 102)");
database.execute("insert into t_staff(id, name, gender, dept_id)values('016002', 'Bruce', 1, null)");
database.execute("insert into t_staff(id, name, gender, dept_id)values('016003', 'Alan', null, 101)");
database.execute("insert into t_staff(id, name, gender, dept_id)values('016004', 'Hellen', 2, 103)");
database.execute("insert into t_staff(id, name, gender, dept_id)values('016005', 'Linda', 2, 101)");
database.execute("insert into t_staff(id, name, gender, dept_id)values('016006', 'Royal', 3, 104)");

然后準(zhǔn)備幾條范例sql，方便大家執(zhí)行查詢，也可以自己寫一個新的sql。

SELECT s.id,
    s.name,
    ifnull(s.gender, '--') AS gender_id, /*處理空值*/ (CASE g.name WHEN 'Male' THEN '男' WHEN 'Female' THEN '女' ELSE '未知' END) AS gender_name,
    s.dept_id,
    d.dept_name FROM t_staff s LEFT JOIN t_gender g ON g.id=s.gender LEFT JOIN t_dept d ON d.dept_id=s.dept_id WHERE d.dept_name IS NOT NULL LIMIT 3

執(zhí)行結(jié)果：

SQL結(jié)果

文章到這里就結(jié)束了，歡迎大家指正，多給Star，多給贊 _

作者：Lave Zhang
出處：http://www.cnblogs.com/lavezhang/