南平网站怎么做seo,楚雄做网站,自己做第一个网站,建设一个百度百科类网站摘要#xff1a; 1 引言 上回 精读《手写 SQL 编译器 - 语法分析》 说到了如何利用 Js 函数实现语法分析时#xff0c;留下了一个回溯问题#xff0c;也就是存档、读档问题。 我们把语法分析树当作一个迷宫#xff0c;有直线有岔路#xff0c;而想要走出迷宫#xff0c;在…摘要 1 引言 上回 精读《手写 SQL 编译器 - 语法分析》 说到了如何利用 Js 函数实现语法分析时留下了一个回溯问题也就是存档、读档问题。 我们把语法分析树当作一个迷宫有直线有岔路而想要走出迷宫在遇到岔路时需要提前进行存档在后面走错时读档换下一个岔路进行尝试这个功能就叫回溯。
1 引言
上回 精读《手写 SQL 编译器 - 语法分析》 说到了如何利用 Js 函数实现语法分析时留下了一个回溯问题也就是存档、读档问题。
我们把语法分析树当作一个迷宫有直线有岔路而想要走出迷宫在遇到岔路时需要提前进行存档在后面走错时读档换下一个岔路进行尝试这个功能就叫回溯。
上一篇我们实现了 分支函数在分支执行失败后回滚 TokenIndex 位置并重试但在函数调用栈中如果其子函数执行完毕堆栈跳出我们便无法找到原来的函数栈重新执行。
为了更加详细的描述这个问题举一个例子存在以下岔路
a - tree() - c- b1 - b1- b2 - b2
上面描述了两条判断分支分别是 a - b1 - b1 - c 与 a - b2 - b2 - c当岔路 b1 执行失败后分支函数 tree 可以复原到 b2 位置尝试重新执行。
但设想 b1 - b1 通过但 b1 - b1 - c 不通过的场景由于 b1 执行完后分支函数 tree的调用栈已经退出无法再尝试路线 b2 - b2 了。
要解决这个问题我们要 通过链表手动构造函数执行过程这样不仅可以实现任意位置回溯还可以解决左递归问题因为函数并不是立即执行的在执行前我们可以加一些 Magic 动作比如调换执行顺序这文章主要介绍如何通过链表构造函数调用栈并实现回溯。
2 精读
假设我们拥有了这样一个函数 chain可以用更简单的方式表示连续匹配
const root (tokens: IToken[], tokenIndex: number) match(a, tokens, tokenIndex) match(b, tokens, tokenIndex) match(c, tokens, tokenIndex)
↓ ↓ ↓ ↓ ↓ ↓
const root (chain: IChain) chain(a, b, c)
遇到分支条件时通过数组表示取代 tree 函数
const root (tokens: IToken[], tokenIndex: number) tree(line(match(a, tokens, tokenIndex) match(b, tokens, tokenIndex)),line(match(c, tokens, tokenIndex) match(d, tokens, tokenIndex))
)
↓ ↓ ↓ ↓ ↓ ↓
const root (chain: IChain) chain([chain(a, b),chain(c, d)
])
这个 chain 函数有两个特质
非立即执行我们就可以 预先生成执行链条 并对链条结构进行优化、甚至控制执行顺序实现回溯功能。无需显示传递 Token减少每一步匹配写的代码量。
封装 scanner、matchToken
我们可以制作 scanner 函数封装对 token 的操作
const query select * from table;;
const tokens new Lexer(query);
const scanner new Scanner(tokens);
scanner 拥有两个主要功能分别是 read 读取当前 token 内容和 next 将 token 向下移动一位我们可以根据这个功能封装新的 matchToken 函数
function matchToken(scanner: Scanner,compare: (token: IToken) boolean
): IMatch {const token scanner.read();if (!token) {return false;}if (compare(token)) {scanner.next();return true;} else {return false;}
}
如果 token 消耗完或者与比对不匹配时返回 false 且不消耗 token当匹配时消耗一个 token 并返回 true。
现在我们就可以用 matchToken 函数写一段匹配代码了
const query select * from table;;
const tokens new Lexer(query);
const scanner new Scanner(tokens);
const root matchToken(scanner, token token.value select) matchToken(scanner, token token.value *) matchToken(scanner, token token.value from) matchToken(scanner, token token.value table) matchToken(scanner, token token.value ;);
我们最终希望表达成这样的结构
const root (chain: IChain) chain(select, *, from, table, ;);
既然 chain 函数作为线索贯穿整个流程那 scanner 函数需要被包含在 chain 函数的闭包里内部传递所以我们需要构造出第一个 chain。
封装 createChainNodeFactory
我们需要 createChainNodeFactory 函数将 scanner 传进去在内部偷偷存起来不要在外部代码显示传递而且 chain 函数是一个高阶函数不会立即执行由此可以封装二阶函数
const createChainNodeFactory (scanner: Scanner, parentNode?: ChainNode) (...elements: any[]
): ChainNode {// 生成第一个节点return firstNode;
};
需要说明两点
chain 函数返回第一个链表节点就可以通过 visiter 函数访问整条链表了。(...elements: any[]): ChainNode 就是 chain 函数本身它接收一系列参数根据类型进行功能分类。
有了 createChainNodeFactory我们就可以生成执行入口了
const chainNodeFactory createChainNodeFactory(scanner);
const firstNode chainNodeFactory(root); // const root
(chain: IChain) chain(select, *, from, table, ;)
为了支持 chain(select, *, from, table, ;) 语法我们需要在参数类型是文本类型时自动生成一个 matchToken 函数作为链表节点同时通过 reduce 函数将链表节点关联上
const createChainNodeFactory (scanner: Scanner, parentNode?: ChainNode) (...elements: any[]
): ChainNode {let firstNode: ChainNode null;elements.reduce((prevNode: ChainNode, element) {const node new ChainNode();// ... Link nodenode.addChild(createChainChildByElement(node, scanner, element));return node;}, parentNode);return firstNode;
};
使用 reduce 函数对链表上下节点进行关联这一步比较常规所以忽略掉通过 createChainChildByElement 函数对传入函数进行分类如果 传入函数是字符串就构造一个 matchToken 函数塞入当前链表的子元素当执行链表时再执行 matchToken 函数。
重点是我们对链表节点的处理先介绍一下链表结构。
链表结构
class ChainNode {public prev: ChainNode;public next: ChainNode;public childs: ChainChild[] [];
}class ChainChild {// If type is function, when run it, will expend.public type: match | chainNode | function;public node?: IMatchFn | ChainNode | ChainFunctionNode;
}
ChainNode 是对链表节点的定义这里给出了和当前文章内容相关的部分定义。这里用到了双向链表因此每个 node 节点都拥有 prev 与 next 属性分别指向上一个与下一个节点而 childs 是这个链表下挂载的节点可以是 matchToken 函数、链表节点、或者是函数。
整个链表结构可能是这样的
node1 - node2 - node3 - node4|- function2-1|- matchToken2-1|- node2-1 - node2-2 - node2-3|- matchToken2-2-1
对每一个节点都至少存在一个 child 元素如果存在多个子元素则表示这个节点是 tree 节点存在分支情况。
而节点类型 ChainChild 也可以从定义中看到有三种类型我们分别说明
matchToken 类型
这种类型是最基本类型由如下代码生成
chain(word);
链表执行时match 是最基本的执行单元决定了语句是否能匹配也是唯一会消耗 Token 的单元。
node 类型
链表节点的子节点也可能是一个节点类比嵌套函数由如下代码生成
chain(chain(word));
也就是 chain 的一个元素就是 chain 本身那这个 chain 子链表会作为父级节点的子元素当执行到链表节点时会进行深度优先遍历如果执行通过会跳到父级继续寻找下一个节点其执行机制类比函数调用栈的进出关系。
函数类型
函数类型非常特别我们不需要递归展开所有函数类型因为文法可能存在无限递归的情况。
好比一个迷宫很多区域都是相同并重复的如果将迷宫完全展开那迷宫的大小将达到无穷大所以在计算机执行时我们要一步步展开这些函数让迷宫结束取决于 Token 消耗完、走出迷宫、或者 match 不上 Token而不是在生成迷宫时就将资源消耗完毕。函数类型节点由如下代码生成
chain(root);
所有函数类型节点都会在执行到的时候展开在展开时如果再次遇到函数节点仍会保留等待下次执行到时再展开。
分支
普通的链路只是分支的特殊情况如下代码是等价的
chain(a);
chain([a]);
再对比如下代码
chain([a]);
chain([a, b]);
无论是直线还是分支都可以看作是分支路线而直线无分支的情况可以看作只有一条分叉的分支对比到链表节点对应 childs 只有一个元素的链表节点。
回溯
现在 chain 函数已经支持了三种子元素一种分支表达方式
chain(a); // MatchNode
chain(chain(a)); // ChainNode
chain(foo); // FunctionNode
chain([a]); // 分支 - [MatchNode]
而上文提到了 chain 函数并不是立即执行的所以我们在执行这些代码时只是生成链表结构而没有真正执行内容内容包含在 childs 中。
我们需要构造 execChain 函数拿到链表的第一个节点并通过 visiter 函数遍历链表节点来真正执行。
function visiter(chainNode: ChainNode,scanner: Scanner,treeChances: ITreeChance[]
): boolean {const currentTokenIndex scanner.getIndex();if (!chainNode) {return false;}const nodeResult chainNode.run();let nestedMatch nodeResult.match;if (nodeResult.match nodeResult.nextNode) {nestedMatch visiter(nodeResult.nextNode, scanner, treeChances);}if (nestedMatch) {if (!chainNode.isFinished) {// Its a new chance, because child match is true, so we can visit next node, but current node is not
finished, so if finally falsely, we can go back here.treeChances.push({chainNode,tokenIndex: currentTokenIndex});}if (chainNode.next) {return visiter(chainNode.next, scanner, treeChances);} else {return true;}} else {if (chainNode.isFinished) {// Game over, back to root chain.return false;} else {// Try againscanner.setIndex(currentTokenIndex);return visiter(chainNode, scanner, treeChances);}}
}
上述代码中nestedMatch 类比嵌套函数而 treeChances 就是实现回溯的关键。
当前节点执行失败时
由于每个节点都包含 N 个 child所以任何时候执行失败都给这个节点的 child 打标并判断当前节点是否还有子节点可以尝试并尝试到所有节点都失败才返回 false。
当前节点执行成功时进行位置存档
当节点成功时为了防止后续链路执行失败需要记录下当前执行位置也就是利用 treeChances 保存一个存盘点。
然而我们不知道何时整个链表会遭遇失败所以必须等待整个 visiter 执行完才知道是否执行失败所以我们需要在每次执行结束时判断是否还有存盘点treeChances
while (!result treeChances.length 0) {const newChance treeChances.pop();scanner.setIndex(newChance.tokenIndex);result judgeChainResult(visiter(newChance.chainNode, scanner, treeChances),scanner);
}
同时我们需要对链表结构新增一个字段 tokenIndex以备回溯还原使用同时调用 scanner 函数的 setIndex 方法将 token 位置还原。
最后如果机会用尽则匹配失败只要有任意一次机会或者能一命通关则匹配成功。
3 总结
本篇文章我们利用链表重写了函数执行机制不仅使匹配函数拥有了回溯能力还让其表达更为直观
chain(a);
这种构造方式本质上与根据文法结构编译成代码的方式是一样的只是许多词法解析器利用文本解析成代码而我们利用代码表达出了文法结构同时自身执行后的结果就是 “编译后的代码”。
下次我们将探讨如何自动解决左递归问题让我们能够写出这样的表达式
const foo (chain: IChain) chain(foo, bar);
好在 chain 函数并不是立即执行的我们不会立即掉进堆栈溢出的漩涡但在执行节点的过程中会导致函数无限展开从而堆栈溢出。
解决左递归并不容易除了手动或自动重写文法还会有其他方案吗欢迎留言讨论。
原文链接
本文为云栖社区原创内容未经允许不得转载。
