【深入淺出教你寫編譯器（Compiler）】三、語法分析器（Parser）﹣語法分析（Syntactic analysis）（下） by Dukeland

【深入淺出教你寫編譯器（Compiler）】三、語法分析器（Parser）﹣語法分析（Syntactic analysis）（下）

在上一節中，我們處理了 “var” “if” “while”，大家應該學會了如何處理 expression block了，這一節我們將會學習如何處理運算符。處理運算符有兩個基本概念要掌握，第一是運算符的運算次序，第二是運算表達式的表示法。

運算次序（Order or operations）

在數學算式裏，我們有個法則叫做“先乘除，後加減”，意思就是乘除的運算次序比加減高，同樣地在程式語言中，我們也需要定義一下運算符的運算次序。在 Wescript 中，我們會用常用的運算符次序，即如下圖所示：

取自維基

西杰不會處理這裏所列的所有運算符，只會處理第一章所列的運算符，其他就留給讀者們當練習吧。

表示法

西杰相信大部份人都會使用 infix notation（可能用完也不知道它的名稱原來就是 infix notation），但其實這世界上還有兩種運算式表示法，prefix notation 和 postfix notation，看看例子大家就會明白這是什麼概念。

Infix notation: 1 + 2 * 3

Prefix notation: + 1 * 2 3

Postfix notation: 1 2 3 * +

我們日常寫程式時使用的都是 infix notation，但是對電腦來說，postfix notation 比較容易處理（通常會用一個 stack 來處理），因此我們的 Parser 將會讀進 Infix notation，到 compile 時就會轉為 postfix notation。

分項（或稱運算元 operand）

開始寫程式了，第一件事情是要分項，什麼是分項呢？就是把一句 expression 斬成多個項目，怎樣才算是一個項目呢？看看下圖：

項目包括以上所列的幾種：數值（數字和布林值），負數值，包著一堆子項目的括號，變數。根據這個分類法，我們可以改寫出 parse 項目的 function。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

Parser.prototype.parseOperand = function (){     var token = this.nextToken();     var operandNode;     switch (token){         case Token.tokens.INTLITERAL_TOKEN:             operandNode = new IntNode(this.currentToken.text);         break;         case Token.tokens.BOOLLITERAL_TOKEN:             operandNode = new BoolNode(this.currentToken.text);         break;         case Token.tokens.IDENTIFIER_TOKEN:             operandNode = new IdentifierNode(this.currentToken.text);         break;         case Token.tokens.LEFTPAREN_TOKEN:             operandNode = new ParenNode(this.parseCompoundExpression(0));             //consume the right paren )             if (this.lookahead() == Token.tokens.RIGHTPAREN_TOKEN){                 this.nextToken();             }else{                 Errors.push({                     type: Errors.SYNTAX_ERROR,                     msg: "Missing right paren \")\"",                     line: this.scanner.currLine                 });             }         break;         case Token.tokens.MINUS_TOKEN:             operandNode = new NegateNode(this.parseOperand());         break;         default:             //not valid             Errors.push({                 type: Errors.SYNTAX_ERROR,                 msg: "Unexpected token",                 line: this.scanner.currLine             });             return null;     }     return operandNode; }

頭三款分別為數字，布林值和 identifier（即變數），只是很簡單的讀進一個 token 再建立一個 node。遇到左括號時就有點特別了，這時我們要 parseCompoundExpression，意思就是要處理更複雜的 expression（例如： 1 + 2 * 3），我們待會兒就會寫這個 function。接著當我們遇到 “-” 時，我們就要再讀多一個項目，因為這個 “-” 代表負數值，我們要建立一個 NegateNode。最後如果都不是以上幾款的話就算是 syntax error 了。

之前我們是在 parseExpression 中處理數值的，現在我們要從中抽起，放到 parseOperand 當中！

parseCompoundExpression 的 algorithm 如下，先大約看一看，下面再解釋。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

Parser.prototype.getBindingPower = function (token){     switch (token){         case Token.tokens.PLUS_TOKEN:         case Token.tokens.MINUS_TOKEN:             return 120;         case Token.tokens.MULT_TOKEN:         case Token.tokens.DIV_TOKEN:             return 130;     }     return -1; } Parser.prototype.createOperatorNode = function (operatorToken){     switch (operatorToken){         case Token.tokens.PLUS_TOKEN:             return new OperatorPlusNode();         break;         case Token.tokens.MINUS_TOKEN:             return new OperatorMinusNode();         break;         case Token.tokens.MULT_TOKEN:             return new OperatorMultNode();         break;         case Token.tokens.DIV_TOKEN:             return new OperatorDivNode();         break;     } } Parser.prototype.parseCompoundExpression = function (rightBindingPower){     var operandNode = this.parseOperand();     if (operandNode == null){         return operandNode;     }     var compoundExpressionNode = new CompoundNode();     compoundExpressionNode.push(operandNode);     var operator = this.lookahead();     var leftBindingPower = this.getBindingPower(operator);     if (leftBindingPower == -1){         //not an operator         return compoundExpressionNode;     }     while (rightBindingPower < leftBindingPower){         operator = this.nextToken();         compoundExpressionNode.push(this.createOperatorNode(operator));         var node = this.parseCompoundExpression(leftBindingPower);         compoundExpressionNode.push(node);         var oper = this.lookahead();         leftBindingPower = this.getBindingPower(oper);         if (leftBindingPower == -1){             //not an operator             return compoundExpressionNode;         }     }     return compoundExpressionNode; }

這個 algorithm 是取自 Vaughan Pratt 的（好似係），但我是在 Eli Bendersky 那裏學的。看起來有點複雜了吧，放心，我慢慢地來 。

Binding Power

由於運算符運算時有先後次序之分，我們的 compiler 也需要處理，而 Wescript compiler 處理的方法就是賦予每一個運算符一個 binding power，Binding Power 高的運算符可以佔有其相鄰的項目，如 Eli 的例子所示：

B 比 A 強，所以佔有 E（唉，連電腦的世界裏也是弱肉強食……）。因此，我們需要先設定運算符的 binding power，這就是 getBindingPower 的工作了。到戲肉了，這裏我會用靜態動畫（靜態的動畫）來描述這個 algorithm 的工作。

開始時是這樣的，注意括號的 binding power 是 0，因為我把它當成項目，而不是普通的運算符。

現在開始執行，一開始的 rightBindingPower 是 0，讀取了一個項目（以圓形表示），由於 “+” 的 binding power 較強，所以這句判斷成立：

1	while (rightBindingPower < leftBindingPower){ //0 < 120

注意不要搞錯左和右，這裏的左是指運算符的左面，而不是項目的左面

接下來就是要 recursive 地再運行 parseCompoundExpression。

同樣地，讀取一個項目，檢查一下右面的運算符的 leftBindingPower，發現 rightBindingPower (120) 比 leftBindingPower (130) 小，於是就再運行一個新的 recursion。

接下來的 3 – 4 的處理方法跟上面相似，但有些分別，括號是當成一個項目來處理，所以 binding power 由 0 開始，當讀到 4 的時候，再讀一個運算符時，我們會讀到 “)” 右括號，當我們嘗試拿取它的 binding power 時就會拿到 -1，於是是次 recursion 直接終止。

然後括號也處理好了，也可以 return 了。

由於下一個運算符 “+” 的 binding power (120) 比現在的（130）小，所以也可以 return 了。

可不可以用 rightBindingPower <= leftBindingPower 而不是 rightBindingPower < leftBindingPower 呢？

不可以，想想這個例子，1 – 2 + 3，由於 “-” 和 “+” 的 binding power 一樣，如果用小於或等於的話，parse tree 將會當成 1 – (2 + 3)

現在連 2 * (3 – 4) 也可以 return 了，因為 1 + 2 的 “+” 的 binding power 並不比 + 5 的 “+” 小。返回之後，binding power 為 0 的那個 function 將會繼續讀取運算式直至讀取所有運算式為止。

就是這樣了，很簡單吧？不明白的多看幾次以上的例子吧，再不明白的話就留個言，西杰很快會跟進的了。現在看看這段程式是不是運作正常。

看看 console.log，程式運作正常。現在把餘下的運算符都編寫下來！

這段程式主要編寫了邏輯運算符，看看 console.log，還是運作正常。那我們現在寫餘下的 assignment 運算符吧。

“=” “+=” “-=” 其實沒有什麼特別處理方法，跟之前的運算符差不多，這裏就不詳述了。但是 “++” 和 “–” 就有特別了，它們是 unary 運算符，同時又可以作 pre-in/decrement 或 post-in/decrement，這樣要如何處理呢？西杰就把它們當成 operand 一樣來處理，而且一定要配合 identifier 使用，看看代碼。

1 2 3 4 5 6 7 8 9 10 11 12

case Token.tokens.IDENTIFIER_TOKEN:     operandNode = new IdentifierNode(this.currentToken.text);     if (this.lookahead() == Token.tokens.MINUSMINUS_TOKEN){         //post decrement         this.nextToken();         operandNode = new PostDecrementNode(operandNode);     }else if (this.lookahead() == Token.tokens.PLUSPLUS_TOKEN){         //post increment         this.nextToken();         operandNode = new PostIncrementNode(operandNode);     } break;

首先處理 post-in/decrement，方法很簡單，就是當我們遇到 identifier 時，我們就會 lookahead 一下，看看有沒有 “++” 或者 “–”，有的話就用 PostIn/DecrementNode 來取代原本的 operandNode，沒有就自然不用理會啦。

1 2 3 4 5 6 7 8 9 10 11 12 13

case Token.tokens.PLUSPLUS_TOKEN:     if (this.lookahead() == Token.tokens.IDENTIFIER_TOKEN){         this.nextToken();         operandNode = new PreIncrementNode(new IdentifierNode(this.currentToken.text));     }else{         Errors.push({             type: Errors.SYNTAX_ERROR,             msg: "Expecting an identifier for pre-increment expression",             line: this.scanner.currLine         });         return null;     } break;

之後要增加 PreIn/Decrement 的處理，就是增加一個 case 到 parseOperand 中，遇到 “++” 或 “–” 就會 lookahead 一下看看有沒有 identifier，有的話就是 PreIn/Decrement，沒有的話應該算是 syntax error 了吧。

看看 console.log，還是運作正常，那就大功告成啦！！！

Put it together

現在看看完整的 Parse tree（console.log）

總結

兩個星期的 Syntactic analysis 課程終於完結了，不知道大家吸收了多少，其實編寫 Parser 說難不難，說易不易，基本來說就是一堆 mutual recursion，把大問題斬件成為多個小問題，逐點擊破就可以了，只要大家思緒清晰的話，其實不難（當然要思緒清晰也確實不易）。

大家可以放心，最難捱的時刻已經過了，下一章會比這章容易一點，大家如果仍然未搞清這章的思路的話不妨留下你的問題，西杰一定會盡量解答，拜拜，下星期再見。