精读《syntax-parser 源码》

jiezi

6 年前

1. 引言
syntax-parser 是一个 JS 版语法解析器生成器，具有分词、语法树解析的能力。
通过两个例子介绍它的功能。
第一个例子是创建一个词法解析器 myLexer：
import {createLexer} from “syntax-parser”;

const myLexer = createLexer([
{
type: “whitespace”,
regexes: [/^(\s+)/],
ignore: true
},
{
type: “word”,
regexes: [/^([a-zA-Z0-9]+)/]
},
{
type: “operator”,
regexes: [/^(\+)/]
}
]);
如上，通过正则分别匹配了“空格”、“字母或数字”、“加号”，并将匹配到的空格忽略（不输出）。
分词匹配是从左到右的，优先匹配数组的第一项，依此类推。
接下来使用 myLexer：
const tokens = myLexer(“a + b”);

// tokens:
// [
// {“type”: “word”, “value”: “a”, “position”: [0, 1] },
// {“type”: “operator”, “value”: “+”, “position”: [2, 3] },
// {“type”: “word”, “value”: “b”, “position”: [4, 5] },
// ]
‘a + b’ 会按照上面定义的“三种类型”被分割为数组，数组的每一项都包含了原始值以及其位置。
第二个例子是创建一个语法解析器 myParser：
import {createParser, chain, matchTokenType, many} from “syntax-parser”;

const root = () => chain(addExpr)(ast => ast[0]);

const addExpr = () =>
chain(matchTokenType(“word”), many(addPlus))(ast => ({
left: ast[0].value,
operator: ast[1] && ast[1][0].operator,
right: ast[1] && ast[1][0].term
}));

const addPlus = () =>
chain(“+”), root)(ast => ({
operator: ast[0].value,
term: ast[1]
}));

const myParser = createParser(
root, // Root grammar.
myLexer // Created in lexer example.
);
利用 chain 函数书写文法表达式：通过字面量的匹配（比如 + 号），以及 matchTokenType 来模糊匹配我们上面词法解析出的“三种类型”，就形成了完整的文法表达式。
syntax-parser 还提供了其他几个有用的函数，比如 many optional 分别表示匹配多次和匹配零或一次。
接下来使用 myParser：
const ast = myParser(“a + b”);

// ast:
// [{
// “left”: “a”,
// “operator”: “+”,
// “right”: {
// “left”: “b”,
// “operator”: null,
// “right”: null
// }
// }]
2. 精读
按照下面的思路大纲进行源码解读：

词法解析

词汇与概念
分词器

语法解析

词汇与概念
重新做一套“JS 执行引擎”
实现 Chain 函数
引擎执行
何时算执行完
“或”逻辑的实现
many, optional, plus 的实现
错误提示 & 输入推荐
First 集优化

词法解析
词法解析有点像 NLP 中分词，但比分词简单的时，词法解析的分词逻辑是明确的，一般用正则片段表达。
词汇与概念

Lexer：词法解析器。
Token：分词后的词素，包括 value: 值、position: 位置、type: 类型。

分词器
分词器 createLexer 函数接收的是一个正则数组，因此思路是遍历数组，一段一段匹配字符串。
我们需要这几个函数：
class Tokenizer {
public tokenize(input: string) {
// 调用 getNextToken 对输入字符串 input 进行正则匹配，匹配完后 substring 裁剪掉刚才匹配的部分，再重新匹配直到字符串裁剪完
}

private getNextToken(input: string) {
// 调用 getTokenOnFirstMatch 对输入字符串 input 进行遍历正则匹配，一旦有匹配到的结果立即返回
}

private getTokenOnFirstMatch({
input,
type,
regex
}: {
input: string;
type: string;
regex: RegExp;
}) {
// 对输入字符串 input 进行正则 regex 的匹配，并返回 Token 对象的基本结构
}
}
tokenize 是入口函数，循环调用 getNextToken 匹配 Token 并裁剪字符串直到字符串被裁完。
语法解析
语法解析是基于词法解析的，输入是 Tokens，根据文法规则依次匹配 Token，当 Token 匹配完且完全符合文法规范后，语法树就出来了。
词法解析器生成器就是“生成词法解析器的工具”，只要输入规定的文法描述，内部引擎会自动做掉其余的事。
这个生成器的难点在于，匹配“或”逻辑失败时，调用栈需要恢复到失败前的位置，而 JS 引擎中调用栈不受代码控制，因此代码需要在模拟引擎中执行。
词汇与概念

Parser：语法解析器。
ChainNode：连续匹配，执行链四节点之一。
TreeNode：匹配其一，执行链四节点之一。
FunctionNode：函数节点，执行链四节点之一。
MatchNode：匹配字面量或某一类型的 Token，执行链四节点之一。每一次正确的 Match 匹配都会消耗一个 Token。

重新做一套“JS 执行引擎”
为什么要重新做一套 JS 执行引擎？看下面的代码：
const main = () =>
chain(functionA(), tree(functionB1(), functionB2()), functionC());

const functionA = () => chain(“a”);
const functionB1 = () => chain(“b”, “y”);
const functionB2 = () => chain(“b”);
const functionC = () => chain(“y”, “c”);
输入仍然是 a b y c，看看会发生什么？
线路 functionA -> functionB1 是 a b y 很显然匹配会通过，但连上 functionC 后结果就是 a b y y c，显然不符合输入。
此时正确的线路应该是 functionA -> functionB2 -> functionC，结果才是 a b y c！
我们看 functionA -> functionB1 -> functionC 链路，当执行到 functionC 时才发现匹配错了，此时想要回到 functionB2 门也没有！因为 tree(functionB1(), functionB2()) 的执行堆栈已退出，再也找不回来了。
所以需要模拟一个执行引擎，在遇到分叉路口时，将 functionB2 保存下来，随时可以回到这个节点重新执行。
实现 Chain 函数
用链表设计 Chain 函数是最佳的选择，我们要模拟 JS 调用栈了。
const main = () => chain(functionA, [functionB1, functionB2], functionC)();

const visitNextNodeFromParent = tailCallOptimize(
(
node: Node,
store: VisiterStore,
visiterOption: VisiterOption,
astValue: any
) => {
if (!node.parentNode) {
// 找父节点的函数没有父级时，下面再介绍，记住这个位置叫 END 位。
}

if (node.parentNode instanceof ChainNode) {
// A B <- next node C
// └── node <- current node
// 正如图所示，找到 nextNode 节点调用 `visit`
} else if (node.parentNode instanceof TreeNode) {
// TreeNode 节点直接利用 `visitNextNodeFromParent` 跳过。因为同一时间 TreeNode 节点只有一个分支生效，所以它没有子元素了
}
}
);
可以看到 visitChildNode 与 visitNextNodeFromParent 函数都只处理好了自己的事情，而将其他工作交给别的函数完成，这样函数间职责分明，代码也更易懂。
有了 vist visitChildNode 与 visitNextNodeFromParent，就完成了节点的访问、子节点的访问、以及当没有子节点时，追溯到上层节点的访问。
visit 函数源码
何时算执行完
当 visitNextNodeFromParent 函数访问到 END 位时，是时候做一个了结了：

当 Tokens 正好消耗完，完美匹配成功。
Tokens 没消耗完，匹配失败。
还有一种失败情况，是 Chance 用光时，结合下面的“或”逻辑一起说。

“或”逻辑的实现
“或”逻辑是重构 JS 引擎的原因，现在这个问题被很好解决掉了。
const main = () => chain(functionA, [functionB1, functionB2], functionC)();
比如上面的代码，当遇到 [] 数组结构时，被认为是“或”逻辑，子元素存储在 TreeNode 节点中。
在 visitChildNode 函数中，与 ChainNode 不同之处在于，访问 TreeNode 子节点时，还会调用 addChances 方法，为下一个子元素存储执行状态，以便未来恢复到这个节点继续执行。
addChances 维护了一个池子，调用是先进后出：
function addChances(/* … */) {
const chance = {
node,
tokenIndex,
childIndex
};

store.restChances.push(chance);
}
与 addChance 相对的就是 tryChance。
下面两种情况会调用 tryChances：

MatchNode 匹配失败。节点匹配失败是最常见的失败情况，但如果 chances 池还有存档，就可以恢复过去继续尝试。
没有下一个节点了，但 Tokens 还没消耗完，也说明匹配失败了，此时调用 tryChances 继续尝试。

我们看看神奇的存档回复函数 tryChances 是如何做的：
function tryChances(
node: Node,
store: VisiterStore,
visiterOption: VisiterOption
) {
if (store.restChances.length === 0) {
// 直接失败
}

const nextChance = store.restChances.pop();

// reset scanner index
store.scanner.setIndex(nextChance.tokenIndex);

visit({
node: nextChance.node,
store,
visiterOption,
childIndex: nextChance.childIndex
});
}
tryChances 其实很简单，除了没有 chances 就失败外，找到最近的一个 chance 节点，恢复 Token 指针位置并 visit 这个节点就等价于读档。
addChance 源码
tryChances 源码
many, optional, plus 的实现
这三个方法实现的也很精妙。
先看可选函数 optional:
export const optional = (…elements: IElements) => {
return chain([chain(…elements)(/**/)), true])(/**/);
};
可以看到，可选参数实际上就是一个 TreeNode，也就是：
chain(optional(“a”))();
// 等价于
chain([“a”, true])();
为什么呢？因为当 ‘a’ 匹配失败后，true 是一个不消耗 Token 一定成功的匹配，整体来看就是“可选”的意思。
进一步解释下，如果 ‘a’ 没有匹配上，则 true 一定能匹配上，匹配 true 等于什么都没匹配，就等同于这个表达式不存在。
再看匹配一或多个的函数 plus：
export const plus = (…elements: IElements) => {
const plusFunction = () =>
chain(chain(…elements)(/**/), optional(plusFunction))(/**/);
return plusFunction;
};
能看出来吗？plus 函数等价于一个新递归函数。也就是：
const aPlus = () => chain(plus(“a”))();
// 等价于
const aPlus = () => chain(plusFunc)();
const plusFunc = () => chain(“a”, optional(plusFunc))();
通过不断递归自身的方式匹配到尽可能多的元素，而每一层的 optional 保证了任意一层匹配失败后可以及时跳到下一个文法，不会失败。
最后看匹配多个的函数 many：
export const many = (…elements: IElements) => {
return optional(plus(…elements));
};
many 就是 optional 的 plus，不是吗？
这三个神奇的函数都利用了已有功能实现，建议每个函数留一分钟左右时间思考为什么。
optional plus many 函数源码
错误提示 & 输入推荐
错误提示与输入推荐类似，都是给出错误位置或光标位置后期待的输入。
输入推荐，就是给定字符串与光标位置，给出光标后期待内容的功能。
首先通过光标位置找到光标的上一个 Token，再通过 findNextMatchNodes 找到这个 Token 后所有可能匹配到的 MatchNode，这就是推荐结果。
那么如何实现 findNextMatchNodes 呢？看下面：
function findNextMatchNodes(node: Node, parser: Parser): MatchNode[] {
const nextMatchNodes: MatchNode[] = [];

let passCurrentNode = false;

const visiterOption: VisiterOption = {
onMatchNode: (matchNode, store, currentVisiterOption) => {
if (matchNode === node && passCurrentNode === false) {
passCurrentNode = true;
// 调用 visitNextNodeFromParent，忽略自身
} else {
// 遍历到的 MatchNode
nextMatchNodes.push(matchNode);
}

// 这个是画龙点睛的一笔，所有推荐都当作匹配失败，通过 tryChances 可以找到所有可能的 MatchNode
tryChances(matchNode, store, currentVisiterOption);
}
};

newVisit({node, scanner: new Scanner([]), visiterOption, parser });

return nextMatchNodes;
}
所谓找到后续节点，就是通过 Visit 找到所有的 MatchNode，而 MatchNode 只要匹配一次即可，因为我们只要找到第一层级的 MatchNode。
通过每次匹配后执行 tryChances，就可以找到所有 MatchNode 节点了！
再看错误提示，我们要记录最后出错的位置，再采用输入推荐即可。
但光标所在的位置是期望输入点，这个输入点也应该参与语法树的生成，而错误提示不包含光标，所以我们要执行两次 visit。
举个例子：
select | from b;
| 是光标位置，此时语句内容是 select from b; 显然是错误的，但光标位置应该给出提示，给出提示就需要正确解析语法树，所以对于提示功能，我们需要将光标位置考虑进去一起解析。因此一共有两次解析。
findNextMatchNodes 函数源码
First 集优化
构建 First 集是个自下而上的过程，当访问到 MatchNode 节点时，其值就是其父节点的一个 First 值，当父节点的 First 集收集完毕后，，就会触发它的父节点 First 集收集判断，如此递归，最后完成 First 集收集的是最顶级节点。
篇幅原因，不再赘述，可以看这张图。
generateFirstSet 函数源码
3. 总结
这篇文章是对《手写 SQL 编译器》系列的总结，从源码角度的总结！
该系列的每篇文章都以图文的方式介绍了各技术细节，可以作为补充阅读：

精读《手写 SQL 编译器 – 词法分析》
精读《手写 SQL 编译器 – 文法介绍》
精读《手写 SQL 编译器 – 语法分析》
精读《手写 SQL 编译器 – 回溯》
精读《手写 SQL 编译器 – 语法树》
精读《手写 SQL 编译器 – 错误提示》
精读《手写 SQL 编译器 – 性能优化之缓存》
精读《手写 SQL 编译器 – 智能提示》

讨论地址是：精读《syntax-parser 源码》· Issue #133 · dt-fe/weekly

如果你想参与讨论，请点击这里，每周都有新的主题，周末或周一发布。前端精读 – 帮你筛选靠谱的内容。