很多人工编写的解析器,会采用 “递归下降” 的解析方法,例如 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