1介绍上次精读《手写 SQL 编译器 - 语法分析》说到如何使用Js函数实现语法分析，有一个回溯问题，即归档和读取文件的问题。我们把解析树看成一个迷宫，有直线也有叉子。我们要想走出迷宫，遇到岔路口就需要提前归档。如果我们稍后出错，我们需要读取文件并尝试另一个分支。此功能称为回溯。上一篇我们实现了branch功能，在branch执行失败后回滚TokenIndex位置重试。但是在函数调用栈中，如果子函数执行完跳出栈，我们就无法找到原来的函数栈，再次执行。为了更详细的描述这个问题，举个例子，有如下的fork：上面描述了两个判断分支，分别是a->b1->b1'->c和a->b2->b2'->c、当forkb1执行失败时，可以将分支功能树恢复到b2位置尝试再次执行。但是想象一下b1->b1'通过，但b1->b1'->c失败的场景。b1'执行完后，分支函数树的调用栈已经退出，不能再尝试b2->b2'这条路线。要解决这个问题，我们需要通过链表手动构造函数执行过程，这样不仅可以在任意位置回溯，还可以解决左递归的问题，因为函数不是立即执行的，我们可以加一些执行前的魔术动作，例如交换执行顺序！本文主要介绍如何通过链表构造函数调用栈，实现回溯。2精读假设我们有这样一个函数链，它可以用更简单的方式来表达连续匹配：当遇到分支条件时，树函数被替换为数组表示：这个链函数有两个特点：非立即执行，我们可以预先生成一条执行链，优化链结构，甚至控制执行顺序，实现回溯功能。无需显示和传递Token，减少了每个匹配步骤所写的代码量。为了封装scanner和matchToken，我们可以创建一个scanner函数来封装对token的操作：scanner有两个主要函数，分别是read读取当前token内容，next将token向下移动一位。我们可以根据这个函数封装一个新的matchToken作用：如果token耗尽或者比对不匹配，返回false，不消耗token；当它匹配时，消耗一个令牌并返回true。现在我们可以使用matchToken函数来写一段匹配代码：我们最终希望表达这样的结构：由于chain函数作为一个线索贯穿了整个过程，因此需要将scanner函数包含在chain函数的闭包中并在内部传递，所以我们需要构造第一条链。封装createChainNodeFactory，我们需要createChainNodeFactory函数将scanner传入，秘密存放在里面，不要传入外部代码，而且chain函数是高阶函数，不会立即执行，所以我们可以封装二阶函数：需要说明两点：chain函数返回第一个链表节点，通过visitor函数可以访问到整个链表。(...elements:any[]):ChainNode是链函数本身，它接收一系列参数，并根据类型对函数进行分类。通过createChainNodeFactory，我们可以生成执行入口：为了支持chain('select','*','from','table',';')语法，我们需要在参数类型为a时自动生成text类型一个matchToken函数作为链表节点，链表节点关联reduce函数：使用reduce函数关联链表的上下节点。这一步比较常规，就忽略了。传入的函数通过createChainChildByElement函数进行分类。如果传入的函数是String，则构造一个matchToken函数插入到当前链表的子元素中，然后在执行链表时执行matchToken函数。重点是我们对链表节点的处理。首先介绍一下链表结构。链表结构体ChainNode是链表节点的定义，这里给出一些与当前文章内容相关的定义。这里使用了双向链表，所以每个node节点都有prev和next属性，分别指向上一个和下一个节点，children是这个链表下挂载的节点，可以是matchToken函数，链表节点,或功能。整个链表结构可能是这样的：对于每个节点，至少有一个子元素。如果有多个子元素，说明该节点是树节点，有分支。而节点类型ChainChild从定义也可以看出，一共有三种类型，我们分别解释：最基本的执行单元，决定了语句能否匹配，也是唯一消耗Token的单元。一个节点类型链表节点的子节点也可以是一个节点，类比一个嵌套函数，由下面代码生成：即chain的一个元素就是链本身，那么这个chain子链表就是作为父节点的子元素，当执行到链表节点时，会进行深度优先遍历。如果执行通过，就会跳转到父节点，继续寻找下一个节点。执行机制类比函数调用栈的出入口关系。函数类型函数类型很特殊，我们不需要递归展开所有的函数类型，因为语法可能有无限递归。就像迷宫一样，很多区域都是相同的，重复的。如果迷宫完全展开，迷宫的大小将达到无穷大。因此，当计算机执行时，我们需要一步一步地扩展这些功能，让迷宫的尽头取决于Token的消耗。走出迷宫，否则令牌无法匹配，而不是在迷宫生成时消耗所有资源。函数类型节点由以下代码生成：所有函数类型节点在执行时都会展开，如果展开时再次遇到函数节点，仍会保留，等待下一次执行展开。分支普通链接只是分支的一个特例。下面的代码是等价的：比较下面的代码：不管是直线还是支路，都可以看成是一条支路，而直线（没有支路）的情况可以看成只有一条分叉的支路，相对于链表节点，对应children中只有一个元素的链表节点。回溯现在chain函数已经支持三个子元素，一个分支表达式：而上面提到的chain函数并没有立即执行，所以我们在执行这些代码的时候，只是生成了一个链表结构，并没有真正执行内容，内容包括在儿童中。我们需要构造execChain函数，获取链表首节点，通过visitor函数遍历链表节点，真正执行。上面代码中，nestedMatch类比嵌套函数，treeChances是回溯的关键。当当前节点执行失败时，由于每个节点包含N个子节点，每当执行失败时，标记本节点的子节点，并判断当前节点是否有子节点可以尝试，一直尝试到所有节点都失败为止。返回假。当前节点执行成功后，该位置被归档。当节点成功后，为了防止后续链接执行失败，需要记录当前执行位置，即使用treeChances保存一个保存点。但是我们不知道整个链表什么时候会遇到失败，所以要等整个访问者执行完才能知道是否执行失败了，所以需要判断一下有没有保存点（treeChances）在每次执行结束：同时我们需要在链表结构中增加一个新的字段tokenIndex进行回溯恢复，同时调用scanner函数的setIndex方法恢复token位置。最后，如果机会耗尽，则匹配失败。只要有机会，或者能用一命通关，就可以配对成功。3总结这篇文章，我们用链表重写了函数执行机制，不仅让匹配的函数具有回溯能力，而且表达更直观：这个构造方法和编译成的方法本质上是一样的根据语法结构编写代码。一样的，但是很多词法分析器是用文本来解析成代码，而我们用代码来表达语法结构，它自己执行的结果就是“编译后的代码”。下一次我们将探讨如何自动解决左递归问题，允许我们这样写表达式：幸运的是，链函数不是立即执行的，我们不会立即陷入堆栈溢出漩涡，但在执行过程中node，会导致函数无限扩展，栈溢出。解决左递归并不容易。除了手动或自动语法重写之外，还有其他解决方案吗？欢迎留言讨论。本文作者：傲享大空阅读原文。本文为云栖社区原创内容，未经许可不得转载。
