博客

标签内容，如 123 / abc/ !@#$% 等

结束标签，如  /

‘},{type:’TagOpen’,val:’

‘},{type:’Value’,val:’world’},{type:’TagClose’,val:’

‘}// …]

语法分析

语法分析是将上面得到的 tokens 数组构造为一棵语法树的过程，实现语法分析器 Parser 也是实现简单编译器时的难点。Parser 的算法有自顶向下(LL)和自底向上(LR)之分，对比讨论暂且略过，下面介绍这个简单编译器的 Parser 实现：

首先，词法分析中得到的 Tokens 所得到的 TagOpen / Value / TagClose 这三种类型，在语法树中的位置是有区别的。例如，只有 Value 能成为叶子节点，而 TagOpen 和 TagClose 这两种类型只能用来包裹出一个 HTML 标签 Tag 类型。而一个或多个 Tag 类型又能够组成 Tags 类型。而一棵语法树的根节点则是一个只有一个 Tags 子节点的 Html 类型。

现在我们有了五种类型：即 TagOpen / Value / TagClose / Tag / Tags。这五种类型中，前三种是从词法分析直接得到的，称他们为【终止符】，而后两种为构建语法树过程中的 “抽象” 类型，称它们为【非终止符】

这个 Parser 采用了最简单的递归下降算法来解析 Tokens 数组。递归下降的过程是这样的：

首先从语法树顶部的根节点开始，向前【匹配非终止符】。每个【匹配非终止符】的过程，都是调用一个函数的过程。例如匹配 Tag 需要调用 tag() 函数，匹配 Tags 需要调用 tags() 函数等

每个非终止符的函数中，都按照这个非终止符的语法结构，依次匹配各种终止符或非终止符。例如 tag() 函数需要依次匹配 TagOpen – Value – TagClose 三个终止符，或者 TagOpen – Tag – TagClose 这样两个终止符和一个非终止符。如果在 tag() 函数中遇到了又需要匹配 Tag 的情况(这就是 HTML 标签嵌套的情形)时，就需要再次调用 tag() 函数来向下匹配一个新的 Tag，这也就是所谓的递归下降了。

当所有的 Token 都被吃入并匹配后，完成匹配。

教科书级的代码示例是这样的(但是这不是伪代码，是能够实际执行语法分析的)：

// 简化的 parser.js// tokens 为输入的词法 Token 数组// currIndex 为当前语法分析过程所匹配到的下标，只会逐个向前递增，不回退// lookahead 为当前语法分析遇到的 Token，即 tokens[currIndex]vartokens,currIndex,lookahead// 返回下一个 token 并将下标前移一位functionnextToken(){returntokens[++currIndex]}// 按照所需匹配的终止符类型，匹配下一个终止符// 若下一个终止符和需要匹配的类型不一直，则说明代码中存在语法错误// 如在解析 123 这三个 Token 时，最后需要 match(‘TagClose’)// 但此时最后一个 Token 类型为 TagOpen，这时就会抛出语法错误functionmatch(terminalType){if(lookahead&&terminalType===lookahead.type)lookahead=nextToken()elsethrow’SyntaxError’}// LL 中的函数均是用于匹配非终止符的函数// 如果有更复杂的非终止符，在此添加它们所对应的函数即可constLL={// 匹配 Html 类型非终止符的函数html(){// 当存在 lookahead 时，不停向前匹配 Tag 标签while(lookahead)LL.tag()// 当完成对所有 Token 的匹配后，lookahead 为越界的 undefined// 这时退出循环，在此结束语法分析过程console.log(‘parse complete!’)},// 匹配 Tag 类型非终止符的函数tag(){// HTML 标签的第一个 Token 一定是 TagOpen 类型match(‘TagOpen’)// 匹配完成 TagOpen 后，可能需要匹配一个嵌套的标签// 也可能需要匹配一个标签的 Value// 这时候就需要通过向前看符号 lookahead 来判断怎样匹配// 若需要匹配嵌套的标签，那么下一个符号必然是 TagOpen 类型lookahead.type==’TagOpen’?LL.tag():match(‘Value’)// 最后匹配一个结束标签，即 TagClose 类型的 Tokenmatch(‘TagClose’)// 执行到这里时，就完成了对一个 HTML 标签的语法解析console.log(‘tag matched’)}}exportdefault{parse(inputTokens){// 初始化各变量tokens=inputTokens,currIndex=0,lookahead=tokens[currIndex]// 开始语法分析，目标是将 Tokens 解析为一整个 HTML 类型LL.html()}}

语义分析

上面的语法分析过程中，并没有显式构建一棵语法树的代码。实际上，语法树是在 LL 中各个匹配非终止符的函数的互相调用中，隐式地构建出来的。要将这棵语法树转换为虚拟 DOM，只需要在 tag() 和 html() 等互相调用的函数中传入参数即可。

例如将 tag() 函数签名修改为如下的形式，即可实现

tag(currNode){match(‘TagOpen’)// 在遇到嵌套标签的情况时，递归向下解析if(lookahead.type==’TagOpen’){// 将当前节点作为参数，调用 tags 匹配掉嵌套的标签// 将会返回挂载完成了所有子节点的当前节点currNode=NT.tags(currNode)}else{// 当前标签是一个叶子节点，这时直接修改当前节点的值// 这时 lookahead 指向的已经是一个 Value 类型的 Token 了currNode.val=lookahead.val// 匹配掉这个 Value 类型，match(‘Value’)// 这时的 lookahead 指向 TagClose 类型}match(‘TagClose’)// 最后返回计算完成的节点给上层returncurrNode}

所以，这种语法分析方式下，语义计算的完整代码实际上耦合在了语法分析器中。最后 html() 函数返回的结果，就是一棵虚拟 DOM 语法树了。

要将获得的虚拟 DOM 渲染为真实 DOM，是非常容易的。只需要深度遍历这棵虚拟 DOM 树，将每个节点通过 API 插入 DOM 中即可：

// generator.jsfunctionrenderNode(target,nodes){// nodes 由调用者传入，是调用者的全部子节点nodes.forEach(node=>{// trim 用于修剪标签的首尾文本，例如将

剪为 p// 然后生成一个全新的 DOM 节点 newNodeletnewNode=document.createElement(trim(node.type))// node.val 不存在时，说明当前节点不是子节点// 此时传入 node 的子节点递归调用自己，深度优先遍历树if(!node.val)newNode=renderNode(newNode,node.children)// node.val 存在时，说明当前 node 是叶子节点// 此时 node.val 就是当前 DOM 元素的 innerHTMLelsenewNode.innerHTML=node.val// 将新生成的节点挂载到 DOM 上target.appendChild(newNode)})// 向调用者返回挂载后的元素returntarget}

TODO

上面的一套流程走完后，实际上就实现了从 HTML 字符串到虚拟 DOM 再到真实 DOM 的流程了。由于虚拟 DOM 的抽象性，因此可以在 HTML 字符串中通过模板语法来绑定若干变量，然后在这些变量改变后，修改虚拟 DOM 对应的位置，并将虚拟 DOM 的相应部分重新渲染到真实 DOM，从而减少手动重新绘制 DOM 的冗余代码，并通过尽量少地重绘 DOM 来提高性能。

当然了，这个编译器的语法分析部分采用的是教科书中最简单的递归下降算法，递归的方式在很多时候性能都不是最好的。如果希望语法分析能够有尽可能高的性能，那么表驱动的 LR 分析可以做到这一点。不过 LR 分析中构造分析表的过程是相当复杂的，在此并没有杀鸡用牛刀的必要。

最后，这个玩具级的编译器能支持的文法其实相当有限，只是 HTML 的一个子集而已。希望它能够为编写其它更有趣的 Parser 提供一些启发吧。