搜尋

隨機推薦

23 十一月 2010
12 八月 2013
23 十一月 2010
24 十二月 2010

【深入淺出教你寫編譯器(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(newIdentifierNode(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,把大問題斬件成為多個小問題,逐點擊破就可以了,只要大家思緒清晰的話,其實不難(當然要思緒清晰也確實不易)。

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

 


 

 

廣告

无觅相关文章插件,快速提升流量

Please publish modules in offcanvas position.