代码简单，功能强大在编译过程中，一个非常重要的步骤就是语法分析（也称为语法分析，Parsing）。解析器（Parser）负责将Token流转换成抽象语法树（AST）。本文介绍一种Parser实现算法：PrattParsing，又名TopDownOperatorPrecedenceParsing，并使用TypeScript实现。PrattParsing实现起来非常简单，大家可以看看TypeScript的实现结果，核心代码不到40行！应用背景实现parser一般有两种方式：使用Parsergenerator手动实现Parsergenerator和使用Parsergenerator。使用DSL（比如BNF）来描述你的文法，将描述文件输入Parsergenerator，Parsergenerator会输出解析这个文法的代码。这种方法非常方便，足以满足大多数需求。但在某些场景下，它不够灵活（例如，不能提供更有用的带有上下文的错误信息），性能不够好，生成的代码较长。而且，在描述一个表达式的运算符优先级和结合性时，语法描述会变得非常复杂和难以阅读，比如维基百科的例子：expression::=equality-expressionequality-expression::=additive-expression(('=='|'!=')加法表达式)*加法表达式::=乘法表达式(('+'|'-')乘法表达式)*乘法表达式::=primary(('*'|'/')primary)*primary::='('表达式')'|编号|变量|'-'primary你需要为每个优先级创建一个规则，导致表达式的语法描述非常复杂。所以有时候需要使用第二种方式：手动实现。手动实现递归下降算法手动实现解析器的常用方法是递归下降算法。递归下降算法更擅长解析语句（Statement），因为创建者在设计语句时有意将语句类型标识放在开头，如if(expression)...,while(expression)...。得益于此，Parser通过开头识别出句型后，就知道需要依次解析哪些结构，只需要依次调用相应的结构解析函数即可，实现起来非常简单。然而，由于递归下降算法需要从上到下理解代码结构，因此它在表达式上很吃力。当Parser读取表达式的开头时，它无法知道它在什么样的表达式中，因为运算符（Operator）往往在表达式的中间（甚至末尾），比如+另外，函数调用().为了从上到下解析表达式，需要将每个运算符优先级视为一个单独的级别，为其编写解析函数，并手动处理关联性，因此解析函数会更多，相当复杂。比如wikipedia的例子中，expression负责处理加减，term负责处理乘除，前者调用后者（乘除term在下层）。可以想象，当优先级越多时，代码会越复杂，递归调??用层次也会更深。例如，即使输入字符串只是1，此解析器也需要递归调用以下解析函数：program->block->statement->expression->term->factor。后面两层的调用本来应该避免的，因为输入根本就没有加减乘除！因此，在手动实现Parser时，一般会将表达式的解析交给其他算法来避免递归下降的弊端。PrattParsing就是这样一种擅长解析表达式的算法。PrattParsingPrattParsing，也称为TopDownOperatorPrecedenceParsing，是一种非常聪明的算法。实现简单，性能好，易于定制和扩展。它特别擅长解析表达式和处理表达式运算符的优先级。和结合性。算法介绍概念介绍PrattParsing将token分为两类：prefix（正式术语是nud）。如果令牌可以放在表达式的最开头，则它就是“前缀”。比如123，(，或者-表示负数。以这个token为中心，在构建表达式节点的时候，不需要知道token左边的表达式，它们构建的表达式节点是类似的对此：//Negativeofnegativenumbersnumberprefix//不需要知道它左边的表达式{type:"unary",operator:"-",body:rightExpression,}infix(正式术语是led)。如果一个记号在构建一个表达式节点，它必须知道它左边的子表达式，那么它就是一个“中缀”。这意味着中缀不能放在任何表达式的开头。例如加减乘除运算符.他们这样构建表达式节点：//减法运算符//需要提前解析其左边的表达式得到leftExpression，才能构建减法节点{type:"binary",operator:"-",left:leftExpression,right:rightExpression,}注意虽然-可以是前缀也可以是中缀，但是事实上，当你从左到右阅读输入的字符串时，你可以立即判断你遇到的是什么——应该算是前缀还是中缀，不用担心混淆（比如——1-2）。理解了下面的算法之后，你会更好的理解这一点。代码解释PrattParsing算法的核心实现是parseExp函数：/*1*/functionparseExp(ctxPrecedence:number):Node{/*2*/letprefixToken=scanner.consume();/*3*/if(!prefixToken)thrownewError(`expecttokenbutfoundnone`);/*4*//*5*///因为我们的扫描器太天真了，/*6*///我们对待所有非操作员令牌作为值（例如数字）/*7*/constprefixParselet=/*8*/prefixParselets[prefixToken]??prefixParselets.__value;/*9*/letleft:Node=prefixParselet.handle(prefixToken,parser);/*10*//*11*/while(true){/*12*/constinfixToken=scanner.peek();/*13*/if(!infixToken)break;/*14*/constinfixParselet=infixParselets[infixToken];/*15*/if(!infixParselet)break;/*16*/if(infixParselet.precedence<=ctxPrecedence)break;/*17*/scanner.consume();/*18*/left=infixParselet.handle(left,infixToken,parser);/*19*/}/*20*/returnleft;/*21*/}让我们逐行解释这个算法是如何工作的。Lines2~10:Parsingprefix首先，这个方法会从令牌流中吃掉一个令牌。这个token必须是一个前缀（比如encounter——应该理解为前缀）。请注意，consume表示吃，peek表示扫视。在第7行，我们找到这个前缀对应的表达式构建器（prefixParselet）并调用它。prefixParselet的作用是构造一个以这个前缀为中心的表达式节点。我们先假设一个简单的情况，假设第一个token是123，会触发默认的prefixParselet(prefixParselets.__value)，直接返回一个值节点：{type:"value",value:"123",}即我们在第9行分配给left的值（已经构建的表达式节点）。在更复杂的情况下，prefixParselet递归调用parseExp。比如负号-的prefixParselets是这样注册的：//设置负号前缀的优先级为150，其作用后面会介绍prefixParselets["-"]={handle(token,解析器）{constbody=解析器。解析表达式（150）；返回{类型：“一元”，运算符：“-”，正文，}；},};它会递归调用parseExp将其右侧的表达式节点解析为自己的主体。注意它并不关心它左边的表达式是什么，这是前缀的基本特征。这里递归调用parseExp(150)传递的参数150，可以理解为它与右子表达式的绑定强度。比如解析-1+2时，prefix-调用parseExp(150)得到的body是1而不是1+2，这是因为参数150的缘故。优先级的具体机制后面会讲到。第11~19行：解析中缀得到prefix的表达式节点后，进入while循环，负责解析出后续的中缀操作。例如-1+2+3+4，接下来的三个加号将在这个循环中被解析。它首先从令牌流中瞥见一个令牌作为中缀，找到其对应的表达式构建器（infixParselet），调用infixParselet.handle，并获得一个新的表达式节点。请注意，调用infixParselet时会传入当前左侧，因为infix需要其左侧的表达式节点才能构造自身。新的表达式节点再次分配给左侧。左边继续积累，成为更大的节点树。比如-的infixParselet是这样注册的：//加减法的优先级定义为120infixParselets["-"]={precedence:120,handle(left,token,parser){constright=parser.解析表达式(120);返回{类型：“二进制”，运算符：“-”，左，右，};},};与prefixParselet类似，也是递归调用parseExp来解析右边的表达式节点。不同的是它还有一个可读的precedence属性，在构造表达式节点时使用left参数。继续下去，理解第13行到第16行的三个判断是理解整个算法的关键。第一次判断if(!infixToken)break；很容易理解，说明读到了输入的结尾，解析自然就结束了。第二次判断if(!infixParselet)break；也比较好理解，说明遇到了非中缀运算符，可能是输入的语法错误，也可能遇到）或者;，需要将当前解析的表达式返回到节点调用者进行处理。第三个判断if(infixParselet.precedence<=ctxPrecedence)break;是整个算法的核心。上面提到的parseExp的参数ctxPrecedence对于这一行是存在的。它的作用是限制这个parseExp调用只解析优先级大于ctxPrecedence的中缀运算符。如果遇到的中缀优先级小于等于ctxPrecedence，则停止解析，将当前解析结果返回给调用者，让调用者处理后续的token。最初，ctxPrecedence的值为0，这意味着将解析所有操作，直到遇到结束（或遇到未知运算符）。比如前面的-1+2的例子中，前缀为-的prefixParselet递归调用了parseExp(150)。递归parseExp执行时，ctxPrecedence为150，大于+infix的优先级120，所以本次递归调用遇到+就结束了，使得前缀-绑定到1，而不是1+2。这样就可以得到正确的结果(-(1))+2。infixParselet递归调用parseExp时也会传入这个参数。你可以把prefixParselet和infixParselet递归调用parseExp的行为理解为用一块“磁铁”吸引后续的token，递归参数ctxPrecedence代表磁铁的“吸引力”。只有当后面的中缀与其左边的token紧密结合时（infixParselet.precedence足够大），中缀才会被“吸”到一起。否则，中缀会和它左边的token“分离”，它左边的token会参与parseExp构造表达式节点的过程，而infix不会参与。算法总结综上所述，PrattParsing是一种结合了循环和递归的算法。parseExp的执行结构大致是这样的：以一个token为前缀，调用它的prefixParselet，得到左边（已经构造好的表达式节点）prefixParselet递归调用parseExp，解析需要的部分，构造表达式节点while在令牌处循环作为一个中缀，只有当它的优先级足够高时，处理才会继续。否则，跳出循环并吃掉infixtoken，调用它的infixParselet，将left传递给它。infixParselet递归调用parseExp，解析你需要的部分，构建表达式节点得到一个新的leftreturnleft现在，你应该能理解“你从左到右读取输入字符串时，可以立即判断遇到什么-到底应该当作前缀还是中缀，不用担心混淆（比如-1-2）”，因为在读取下一个token之前，算法已经知道下一个token应该作为前缀还是中缀！PrattParsing的精妙之处在于，看到最初的原子表达式后，可以直接构造它对应的节点，而无需知道它在更高层的表达式结构中是怎样的。如果扫描后发现左边的表达式属于某个中缀，则将其交给中缀的处理函数，构造更高层的表达式。也就是说，PrattParsing从表达式树的叶子节点开始，然后根据后续扫描的结果，将其放置在合适的上下文（更高层的表达式结构）中。这就是它如此擅长处理表达式的根本原因。相比之下，前面提到的递归下降算法需要对表达式结构有自上而下的理解：程序->块->语句->表达式->项->因子。例子的执行过程现在以1+2*3-4为例来理解PrattParsing算法的执行过程：首先定义每个中缀的优先级（即infixParselet.precedence）：例如加法和减法是120，乘法和除法是130（乘法和除法的“绑定强度”更高）。初始调用parseExp(0)，即ctxPrecedence=0吃一个token1，调用prefixParselet，得到表达式节点1，赋值到left，进入while循环，看到+，找到它的infixParselet，优先级为120，大于ctxPrecedence。所以这个中缀也被“吸走”吃掉了+，调用了+的中缀Parselet.handle。此时left为1+的infixParselet.handle递归调用parser.parseExp(120)，即ctxPrecedence=120吃一个token2，调用prefixParselet，得到表达式节点2，赋值给left，进入while循环，看到*，找到它的infixParselet，优先级为130，大于ctxPrecedence。所以这个中缀也被“吸走”吃掉了*，调用了*的infixParselet.handle。此时left为2*的infixParselet.handle递归调用parser.parseExp(130)，即ctxPrecedence=130吃一个token3，调用prefixParselet，得到表达式节点3，赋值给left，进入while循环，看-，找到它的infixParselet，优先级是120，不大于ctxPrecedence，所以这个infix不会一起被吸走，while循环结束parser.parseExp(130)返回3*的infixParselet.handle返回2*3（将parser.parseExp的返回值与left合并）赋值给left继续while循环，见-，找到它的infixParselet，优先级为120，不大于ctxPrecedence。所以这个infix不会一起被吸走，while循环结束parser.parseExp(120)returnssubexpression2*3+infixParselet.handlereturns1+(2*3)(将parser.parseExp的返回值和leftGet合并up)，赋值给left继续while循环，看-，找到它的infixParselet，优先级为120，大于ctxPrecedence。所以，这个中缀也被“吸走”，一起吃-，调用-的infixParselet.handle，此时左边是1+(2*3)和之前一样，-的返回结果infixParselet.handle为(1+(2*3))-4（将parser.parseExp的返回值与left合并），赋值给leftwhile循环继续，发现后面没有token，所以退出while循环,returnleftparseExp(0)return(1+(2*3))-4如何处理结合运算符的结合性（associativity），意思是当表达式中连续出现多个相同优先级的运算符时，运算符左边是第一个组合(left-associative)或right-associative。根据上面描述的算法，1+1+1+1是左结合的，也就是说，它会被解析为((1+1)+1)+1，这是我们所期望的。但是有些运算符是右结合的，比如赋值符号=（比如a=b=1应该解析为a=(b=1)），求幂符号^（比如a^b^c应该解析为作为^(b^c))。这里，我们使用^作为求幂符号，而不是像Javascript中那样使用**，是为了避免一个运算符恰好是另一个运算符的前缀，导致当前实现的一个缺陷：遇到的第一个字符**是急切的确定为乘法。其实这个bug很容易修复，你能尝试提高PR吗？如何实现这个正确的关联运算符？答案只需要一行：在infixParselet中，递归调用parseExp时，传递一个稍小的ctxPrecedence。这是我们用于注册中缀的实用函数：(associateRight2Left?precedence-1:precedence);返回{类型：“二进制”，运算符：中缀，左，右，};},};}这样递归parseExp的“吸力”就弱了。当遇到相同优先级的算子时，右边的算子结合得更紧密，所以也被“吸”到一起（没有分离）。完整实现的Github存储库。它包括测试（100%覆盖率）和更多的运算符实现（例如括号、函数调用、分支运算符...?...:...、右结合求幂运算符^等）。参考DesmosHowusesPrattParsers本文带领读者从头开始推导Pratt算法，并给出他们在选择PrattParsing时的权衡。PrattParsers:ExpressionParsingMadeEasy也是一篇很好的介绍文章，带读者进入Pratt算法的推导过程。箭头函数打破JavaScript解析器让我们思考一个非常有趣的问题：JavaScript箭头函数(arg1=...)=>{...}是如何解析的？可能比你想象的更难！
