很多人工编写的解析器，会采用 “递归下降” 的解析方法，例如 typescript、swc、babel-parser 等等。
这可能是 “递归下降” 方法所编写的代码，更利于调整，结构上更加清晰。
虽然这种方法无法处理 左递归文法，
但大多数场景我们都可以采用 左递归消除 的办法，对文法进行改写。
本文用几个例子，简单总结一下 “递归下降解析器” 的常用写法。
一、list 解析器
1. 字符串、文法 和 语法树
递归下降解析器是一种自上而下的解析器，由一组相互递归的程序（或等价的非递归程序）构建而成，其中每个程序都实现了文法中的一个非终结符。
—— 递归下降解析器
这样说可能比较抽象，我们先写一个简单的 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 构成，而 elements 则是由 一个或多个 element 组成。
最后，element 或者是 一个标识符 identifier，或者是一个 list（又回到了 list，表明结构上是递归的）。
比如，上文提到的字符串，
(ab cd
(ee ff gg)
)
ab cd ee ff gg 都是 identifier，(ee ff gg) 是一个 list，
(ab cd (ee ff gg)) 也是一个 list。
解析的过程，其实是根据文法，将字符串整理成数据结构的过程。
整理后的数据结构（语法树）如下，
题外话：
我们看到 字符串 在结构上是递归的，所以很自然的我们会想到，用递归的程序来解决问题。这个其实是跟 上下文无关语言的 泵引理 有关，它指出了 上下文无关语言 在结构上的自相似性。上下文无关语言中的字符串只要足够长，它的某一部分总能 “坍缩” 到相同的非终结符上去（即语法树的树高不会无限增加）。
2. TypeScript & namespace
为了方便编写，我们使用了 TypeScript，且用到了不太常见的 namespace 特性，
所以这里多解释一下，
namespace Parser {
// ...
}
namespace 会编译成一个立即执行的函数（一个闭包），
namespace 导出（export） 的函数，就是闭包向外透出的值。
编译产物 可参考这里 github: thzt/tiny-parser#list out/index.js
var Parser;
(function (Parser) { // namespace 的编译结果
// ...
function parse(code) { }
Parser.parse = parse; // 导出的 parse 方法
// ...
})(Parser || (Parser = {}));
3. 解析器的结构
解析器 主要有 4 个部分组成：
- （1）解析器的初始化：源码、初始位置、结束位置
- （2）递归解析的入口：开始调用一组互相递归的函数，从 parseList 开始
- （3）一些互相递归的函数：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. 一些互相递归的函数：parseList/parseElements/parseElement
function parseList() { }
function parseElements() { }
function parseElement() { }
// 4. 词法分析器
function nextToken() { }
}
这里值得一提的是，互相递归的那些函数，其实是跟 文法中的 产生式 一一对应的。
list = '(' elements ')' -> parseList
elements = element | element elements -> parseElements
element = identifier | list -> parseElement
所以只要我们写出 文法，这些互相递归的函数也就有了。
这也是很多 递归下降的 “解析器生成器” 常用的代码生成办法，例如 peg.js。
4. 词法分析器（nextToken）
以上代码中的词法分析器，就是一个函数 nextToken，其实非常的容易编写。
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);
}
}
}
它会逐个字符进行判断，将不同类型的 “单词” 切分开，例如，
(ab cd
(ee ff gg)
)
会被切分成：(，ab，cd，(，ee，ff，gg，)，) 这样一系列 token。
效果是：a 和 b 被合并成了一个，空格和换行符被忽略了。
5. 互相递归的函数
上文我们提到了互相递归的函数：parseList/parseElements/parseElement，
是跟文法中的 产生式 一一对应的，
list = '(' elements ')' -> parseList
elements = element | element elements -> parseElements
element = identifier | list -> parseElement
其实，不止是函数名，函数内部的编写方式，也可以根据产生式来生成（有套路）。
我们分别来看一下。
// list = '(' elements ')'
function parseList() { // 进来时当前 token 是 '('
const elements = parseElements(); // 这里解析 `elements`
const rb = nextToken(); // 这里的 token 为 `)`
// 以上解析完了 `(` elements ')'，返回。我们的 ast 中只保存了 elements
return elements;
}
// elements = element | element elements
function parseElements() {
const elements = []; // 由一个或多个 element 组成，所以用个数组来存
while (true) {
nextToken();
if (isElementsTeminate()) { // 向前看一个字符，判断后面还是不是 element
break;
}
const element = parseElement(); // 解析 element
elements.push(element);
}
return elements; // 将 elements 数组返回
}
// element = identifier | list
function parseElement() {
if (token.kind === SyntaxKind.LeftBracket) { // 分支判断
return parseList(); // 如果是 list 就是递归调用 parseList
}
console.assert(token.kind === SyntaxKind.Identifier); // 否则就把标识符返回
return token;
}
parseList 会调用 parseElements，parseElements 会调用 parseElement，
最后 parseElement 又有可能递归调用 parseList。
这就是一组互相递归的函数了。
二、html 解析器
解析完了最简单的 list 之后，我们来看一个较为复杂的例子，
<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）一些互相递归的函数
- （4）词法分析器
所不同的是，互相递归的函数变了，变成了 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. 一些互相递归的函数：parseList/parseElements/parseElement
function parseHtml() { }
function parseProps() { }
// 4. 词法分析器
function nextToken() { }
}
完整的代码：github: thzt/tiny-parser#html
三、四则运算 解析器
文法：
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
- 四则运算 解析器 github: thzt/tiny-parser#arithmetic
- 四则运算（左递归消除）示例 github: thzt/tiny-parser#arithmetic
网友评论