很多人工編寫的解析器，會采用 “遞歸下降” 的解析方法瓷式，例如 typescript脯倚、swc、babel-parser 等等藕夫。
這可能是 “遞歸下降” 方法所編寫的代碼克伊，更利于調(diào)整谆膳，結(jié)構(gòu)上更加清晰。
雖然這種方法無法處理 左遞歸文法脯倒，
但大多數(shù)場景我們都可以采用 左遞歸消除 的辦法实辑，對文法進(jìn)行改寫。
本文用幾個例子藻丢，簡單總結(jié)一下 “遞歸下降解析器” 的常用寫法剪撬。
一、list 解析器
1. 字符串悠反、文法 和 語法樹
遞歸下降解析器是一種自上而下的解析器残黑，由一組相互遞歸的程序（或等價的非遞歸程序）構(gòu)建而成，其中每個程序都實(shí)現(xiàn)了文法中的一個非終結(jié)符斋否。
—— 遞歸下降解析器
這樣說可能比較抽象梨水，我們先寫一個簡單的 list 解析器，來說明情況茵臭。
完整的代碼如下：github: thzt/tiny-parser#list
它可以用來解析如下字符串：
(ab cd
(ee ff gg)
)
文法如下：
list = '(' elements ')'
elements = element | element elements
element = identifier | list
identifier = [a-z]+
whitespace = ' ' | '\n'
它是指疫诽，list 由 括號包圍的 elements 構(gòu)成，而 elements 則是由 一個或多個 element 組成笼恰。
最后踊沸，element 或者是 一個標(biāo)識符 identifier歇终，或者是一個 list（又回到了 list社证，表明結(jié)構(gòu)上是遞歸的）。
比如评凝，上文提到的字符串追葡，
(ab cd
(ee ff gg)
)
ab cd ee ff gg 都是 identifier，(ee ff gg) 是一個 list奕短，
(ab cd (ee ff gg)) 也是一個 list宜肉。
解析的過程，其實(shí)是根據(jù)文法翎碑，將字符串整理成數(shù)據(jù)結(jié)構(gòu)的過程谬返。
整理后的數(shù)據(jù)結(jié)構(gòu)（語法樹）如下，
題外話：
我們看到 字符串 在結(jié)構(gòu)上是遞歸的日杈，所以很自然的我們會想到遣铝，用遞歸的程序來解決問題。這個其實(shí)是跟 上下文無關(guān)語言的 泵引理 有關(guān)莉擒，它指出了 上下文無關(guān)語言 在結(jié)構(gòu)上的自相似性酿炸。上下文無關(guān)語言中的字符串只要足夠長，它的某一部分總能 “坍縮” 到相同的非終結(jié)符上去（即語法樹的樹高不會無限增加）涨冀。
2. TypeScript & namespace
為了方便編寫填硕，我們使用了 TypeScript，且用到了不太常見的 namespace 特性鹿鳖，
所以這里多解釋一下扁眯，
namespace Parser {
// ...
}
namespace 會編譯成一個立即執(zhí)行的函數(shù)（一個閉包）壮莹，
namespace 導(dǎo)出（export） 的函數(shù)，就是閉包向外透出的值恋拍。
編譯產(chǎn)物 可參考這里 github: thzt/tiny-parser#list out/index.js
var Parser;
(function (Parser) { // namespace 的編譯結(jié)果
// ...
function parse(code) { }
Parser.parse = parse; // 導(dǎo)出的 parse 方法
// ...
})(Parser || (Parser = {}));
3. 解析器的結(jié)構(gòu)
解析器 主要有 4 個部分組成：
- （1）解析器的初始化：源碼垛孔、初始位置、結(jié)束位置
- （2）遞歸解析的入口：開始調(diào)用一組互相遞歸的函數(shù)施敢，從 parseList 開始
- （3）一些互相遞歸的函數(shù)：parseList/parseElements/parseElement
- （4）詞法分析器：用來返回 token（單詞）
可參考如下代碼：github: thzt/tiny-parser#list src/parser.ts
namespace Parser {
let sourceText: string;
let pos: number;
let end: number;
let token;
export function parse(code) {
// 1. 解析器的初始化
sourceText = code;
pos = 0;
end = sourceText.length;
// 2. 遞歸解析的入口
nextToken();
assert(SyntaxKind.LeftBracket);
const body = parseList();
nextToken();
assert(SyntaxKind.EndOfFile);
return body;
}
// 3. 一些互相遞歸的函數(shù)：parseList/parseElements/parseElement
function parseList() { }
function parseElements() { }
function parseElement() { }
// 4. 詞法分析器
function nextToken() { }
}
這里值得一提的是周荐，互相遞歸的那些函數(shù)，其實(shí)是跟 文法中的 產(chǎn)生式 一一對應(yīng)的僵娃。
list = '(' elements ')' -> parseList
elements = element | element elements -> parseElements
element = identifier | list -> parseElement
所以只要我們寫出 文法概作，這些互相遞歸的函數(shù)也就有了。
這也是很多 遞歸下降的 “解析器生成器” 常用的代碼生成辦法默怨，例如 peg.js讯榕。
4. 詞法分析器（nextToken）
以上代碼中的詞法分析器，就是一個函數(shù) nextToken匙睹，其實(shí)非常的容易編寫愚屁。
github: thzt/tiny-parser#list src/parser.ts#nextToken
總共也就 30 多行代碼，
function nextToken() {
while (true) {
if (pos >= end) {
return token = createNode(SyntaxKind.EndOfFile, pos, pos, null);
}
let ch = sourceText.charAt(pos);
switch (ch) {
case '(':
return token = createNode(SyntaxKind.LeftBracket, pos++, pos, '(');
case ')':
return token = createNode(SyntaxKind.RightBracket, pos++, pos, ')');
case ' ':
case '\n':
pos++;
continue;
default:
if (isIdentifierStart(ch)) {
return token = scanIdentifier();
}
return token = createNode(SyntaxKind.RightBracket, pos++, pos, ch);
}
}
}
它會逐個字符進(jìn)行判斷痕檬，將不同類型的 “單詞” 切分開霎槐，例如，
(ab cd
(ee ff gg)
)
會被切分成：(梦谜，ab丘跌，cd，(唁桩，ee闭树，ff，gg荒澡，)报辱，) 這樣一系列 token。
效果是：a 和 b 被合并成了一個单山，空格和換行符被忽略了碍现。
5. 互相遞歸的函數(shù)
上文我們提到了互相遞歸的函數(shù)：parseList/parseElements/parseElement，
是跟文法中的 產(chǎn)生式 一一對應(yīng)的饥侵，
list = '(' elements ')' -> parseList
elements = element | element elements -> parseElements
element = identifier | list -> parseElement
其實(shí)鸵赫，不止是函數(shù)名，函數(shù)內(nèi)部的編寫方式躏升，也可以根據(jù)產(chǎn)生式來生成（有套路）辩棒。
我們分別來看一下。
// list = '(' elements ')'
function parseList() { // 進(jìn)來時當(dāng)前 token 是 '('
const elements = parseElements(); // 這里解析 `elements`
const rb = nextToken(); // 這里的 token 為 `)`
// 以上解析完了 `(` elements ')'，返回一睁。我們的 ast 中只保存了 elements
return elements;
}
// elements = element | element elements
function parseElements() {
const elements = []; // 由一個或多個 element 組成钻弄，所以用個數(shù)組來存
while (true) {
nextToken();
if (isElementsTeminate()) { // 向前看一個字符，判斷后面還是不是 element
break;
}
const element = parseElement(); // 解析 element
elements.push(element);
}
return elements; // 將 elements 數(shù)組返回
}
// element = identifier | list
function parseElement() {
if (token.kind === SyntaxKind.LeftBracket) { // 分支判斷
return parseList(); // 如果是 list 就是遞歸調(diào)用 parseList
}
console.assert(token.kind === SyntaxKind.Identifier); // 否則就把標(biāo)識符返回
return token;
}
parseList 會調(diào)用 parseElements者吁，parseElements 會調(diào)用 parseElement窘俺，
最后 parseElement 又有可能遞歸調(diào)用 parseList。
這就是一組互相遞歸的函數(shù)了复凳。
二瘤泪、html 解析器
解析完了最簡單的 list 之后，我們來看一個較為復(fù)雜的例子育八，
<div id="tiny" class="parser">
<span>
abc
</span>
</div>
文法如下：
html = '<' identifier props '>' html '</' identifier '>' | identifier
props = '' | identifier '=' '"' identifier '"'
identifier = [a-z]+
whitespace = ' ' | '\n'
解析器仍然是由 4 部分組成：
- （1）解析器的初始化
- （2）遞歸解析的入口
- （3）一些互相遞歸的函數(shù)
- （4）詞法分析器
所不同的是对途，互相遞歸的函數(shù)變了，變成了 parseHtml/parseProps
namespace Parser {
let sourceText: string;
let pos: number;
let end: number;
let token;
export function parse(code) {
// 1. 解析器的初始化
sourceText = code;
pos = 0;
end = sourceText.length;
// 2. 遞歸解析的入口
nextToken(); // <
assert(SyntaxKind.LeftBracket);
const html = parseHtml();
nextToken(); // eof
assert(SyntaxKind.EndOfFile);
return html;
}
// 3. 一些互相遞歸的函數(shù)：parseList/parseElements/parseElement
function parseHtml() { }
function parseProps() { }
// 4. 詞法分析器
function nextToken() { }
}
完整的代碼：github: thzt/tiny-parser#html
三髓棋、四則運(yùn)算 解析器
文法：
Expr -> Term | Term + Expr
Term -> Factor | Factor * Term
Factor -> NUMBER | ( Expr )
字符串：
((1 + 2) * 3 + 4) * (5 + 6)
語法樹：
完整的代碼：github: thzt/tiny-parser#arithmetic
參考
- list 解析器 github: thzt/tiny-parser#list
- html 解析器 github: thzt/tiny-parser#html
- 四則運(yùn)算 解析器 github: thzt/tiny-parser#arithmetic
- 四則運(yùn)算（左遞歸消除）示例 github: thzt/tiny-parser#arithmetic
