我的图书馆
留言交流

请选择搜索范围

含  的文章 含  的书籍 含  的随笔 昵称/兴趣为  的馆友

quasiceo / 深入浅出教你... / 【深入淺出教你寫編譯器（Compiler）】二...

分享

   

【深入淺出教你寫編譯器（Compiler）】二、掃描器（Scanner）﹣詞法分析（Lexical analysis）（下） by Dukeland

2014-02-02  quasiceo

【深入淺出教你寫編譯器（Compiler）】二、掃描器（Scanner）﹣詞法分析（Lexical analysis）（下）

繼續上一節未完成的 Scanner 吧，上一節我們寫好了一個 Reader，可以逐個逐個字元讀取，有需要時又可以退回 n 個字元之後再讀（本節將會使用這個功能）。另外，上一節亦寫好了一個簡單的 Scanner，可以讀取七款單字元 Token，並忽略其他字元。本節將會教大家如何建立多字元 Token，過程將會利用 FSM 來分析字元，忘記了什麼是 FSM 的朋友請到上一節回顧一下嚕。

多字元的 Token

首先我們要讀取含有英文字的 Token，含有英文字的 Token 如下：

var VAR_TOKEN

int TYPE_TOKEN

bool TYPE_TOKEN

true, false, TRUE, FALSE BOOLLITERAL_TOKEN

if IF_TOKEN

else ELSE_TOKEN

while WHILE_TOKEN

print PRINT_TOKEN

其他英文字 IDENTIFIER_TOKEN

在程式中先定義一下這些 Token 吧，承接著之前的 Token 定義，增加以下的定義。

1
2
3
4
5
6
7
8
Token.tokens.VAR_TOKEN = Token.tokens.MOD_TOKEN + 1;
Token.tokens.TYPE_TOKEN = Token.tokens.VAR_TOKEN + 1;
Token.tokens.BOOLLITERAL_TOKEN = Token.tokens.TYPE_TOKEN + 1;
Token.tokens.IF_TOKEN = Token.tokens.BOOLLITERAL_TOKEN + 1;
Token.tokens.ELSE_TOKEN = Token.tokens.IF_TOKEN + 1;
Token.tokens.WHILE_TOKEN = Token.tokens.ELSE_TOKEN + 1;
Token.tokens.PRINT_TOKEN = Token.tokens.WHILE_TOKEN + 1;
Token.tokens.IDENTIFIER_TOKEN = Token.tokens.PRINT_TOKEN + 1;

現在要修改我們的 FSM，遇見有英文字的時候我們就要轉換一下 FSM 的狀態，轉到讀取整個英文詞的狀態，我稱它為 IDENTIFIER_STATE 吧。

1
Scanner.IDENTIFIER_STATE = Scanner.START_STATE + 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
case Scanner.START_STATE:
    var c = this.reader.nextChar();
    if ((c >= "a" && c <= "z") || (c >= "A" && c <= "Z")){
        this.state = Scanner.IDENTIFIER_STATE;
        //we need to remember what the token's text is
        bufferStr = c;
    }else{
        switch (c){
            case ":":
                return this.makeToken(Token.tokens.COLON_TOKEN);
            break;
            //...and more written in the previous section
        }
    }
break;

這裏我們修改了先前寫的 START_STATE，現在只要一遇到英文字，FSM 的狀態就會改變為 IDENTIFIER_STATE。除了改變了狀態之外，我們還要記下剛讀進來的字元到 bufferStr 中，因為後面我們可能需要用它來分辨那個 Token 真正的意思，例如 true false，我們只會有一個 Token 叫做 BOOLLITERAL_TOKEN，所以我們需要用 “true” 或者 “false” 來記住這個 Token 真正的意思了。

為什麼不創造兩個 Token，一個叫做 TRUE_TOKEN，一個叫做 FALSE_TOKEN 呢？
其實分別不大，只在乎你想把工作留到 Parser 才處理還是現在就分好，我個人比較偏好把相同類型（即後面處理方法大同小異的）的字合併成一個 Token。

好了，現在要寫一寫 IDENTIFIER_STATE 了。

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
case Scanner.IDENTIFIER_STATE:
    var c = this.reader.nextChar();
    if ((c >= "a" && c <= "z") || (c >= "A" && c <= "Z")){
        bufferStr += c;
    }else{
        //stop reading it since it is not a letter anymore
        //retract the last character we read because it does not belong to this identfier
        this.reader.retract();
        //change back the state to read the next token
        this.state = Scanner.START_STATE;
        switch (bufferStr){
            case "var":
                return this.makeToken(Token.tokens.VAR_TOKEN);
            case "int": case "bool":
                //need to pass bufferStr as well to distinguish which type it is
                return this.makeToken(Token.tokens.TYPE_TOKEN, bufferStr);
            case "true": case "false":
            case "TRUE": case "FALSE":
                return this.makeToken(Token.tokens.BOOLLITERAL_TOKEN, bufferStr);
            case "if":
                return this.makeToken(Token.tokens.IF_TOKEN);
            case "else":
                return this.makeToken(Token.tokens.ELSE_TOKEN);
            case "while":
                return this.makeToken(Token.tokens.WHILE_TOKEN);
            case "print":
                return this.makeToken(Token.tokens.PRINT_TOKEN);
            default:
                return this.makeToken(Token.tokens.IDENTIFIER_TOKEN, bufferStr);
        }
    }
break;

在 IDENTIFIER_STATE 中要處理幾件事，第一讀取下一個字元，如果這個字元仍然是英文字的話就把它加到 bufferStr 中，不用改變 FSM 狀態，繼續讀取下一個字元。當讀進來的字元不是英文字的時候，我們就可以改變 FSM 狀態，把它轉變為 START_STATE 以讀取下一個 Token。

切記要把最後一個讀進來的字元退回，因為這個字元並不屬於這個 Token 的，不能鳩佔人家的鵲巢

又，判斷一下 bufferStr 中的字是不是關鍵字（Reserved word），如果是的話就返回相對應的 Token，不然就把它統稱為 IDENTIFIER_TOKEN，留給 Parser 做語法分析時再判斷如何處理它。

現在執行一下我們的 Scanner，看它是否運作正常。

注意，var a:bool = true; 的那個 “=” 沒有被建立為一個 Token，因為我們根本還未處理

現在就把餘下的 Token 都定義過來吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Token.tokens.PLUS_TOKEN = Token.tokens.IDENTIFIER_TOKEN + 1;
Token.tokens.PLUSPLUS_TOKEN = Token.tokens.PLUS_TOKEN + 1;
Token.tokens.PLUSASSIGN_TOKEN = Token.tokens.PLUSPLUS_TOKEN + 1;
Token.tokens.MINUS_TOKEN = Token.tokens.PLUSASSIGN_TOKEN + 1;
Token.tokens.MINUSMINUS_TOKEN = Token.tokens.MINUS_TOKEN + 1;
Token.tokens.MINUSASSIGN_TOKEN = Token.tokens.MINUSMINUS_TOKEN + 1;
Token.tokens.MULT_TOKEN = Token.tokens.MINUSASSIGN_TOKEN + 1;
Token.tokens.DIV_TOKEN = Token.tokens.MULT_TOKEN + 1;
Token.tokens.ASSIGN_TOKEN = Token.tokens.DIV_TOKEN + 1;
Token.tokens.EQUAL_TOKEN = Token.tokens.ASSIGN_TOKEN + 1;
Token.tokens.NOTEQUAL_TOKEN = Token.tokens.EQUAL_TOKEN + 1;
Token.tokens.GREATER_TOKEN = Token.tokens.NOTEQUAL_TOKEN + 1;
Token.tokens.GREATEREQUAL_TOKEN = Token.tokens.GREATER_TOKEN + 1;
Token.tokens.LESS_TOKEN = Token.tokens.GREATEREQUAL_TOKEN + 1;
Token.tokens.LESSEQUAL_TOKEN = Token.tokens.LESS_TOKEN + 1;
Token.tokens.AND_TOKEN = Token.tokens.LESSEQUAL_TOKEN + 1;
Token.tokens.OR_TOKEN = Token.tokens.AND_TOKEN + 1;
Token.tokens.NOT_TOKEN = Token.tokens.OR_TOKEN + 1;
Token.tokens.LINECOMMENT_TOKEN = Token.tokens.NOT_TOKEN + 1;
Token.tokens.BLOCKCOMMENT_TOKEN = Token.tokens.LINECOMMENT_TOKEN + 1;

接著就是在 START_STATE 裏增加一段辨認以上字元的 logic 了。

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
case "!":
    if (this.reader.nextChar() == "="){
        return this.makeToken(Token.tokens.NOTEQUAL_TOKEN);
    }else{
        this.reader.retract();
        return this.makeToken(Token.tokens.NOT_TOKEN);
    }
break;
case "+":
    var d = this.reader.nextChar();
    if (d == "="){
        return this.makeToken(Token.tokens.PLUSASSIGN_TOKEN);
    }else if (d == "+"){
        return this.makeToken(Token.tokens.PLUSPLUS_TOKEN);
    }else{
        this.reader.retract();
        return this.makeToken(Token.tokens.PLUS_TOKEN);
    }
break;
case "-":
    var d = this.reader.nextChar();
    if (d == "="){
        return this.makeToken(Token.tokens.MINUSASSIGN_TOKEN);
    }else if (d == "-"){
        return this.makeToken(Token.tokens.MINUSMINUS_TOKEN);
    }else{
        this.reader.retract();
        return this.makeToken(Token.tokens.MINUS_TOKEN);
    }
break;
case "*":
    return this.makeToken(Token.tokens.MULT_TOKEN);
break;
case "=":
    if (this.reader.nextChar() == "="){
        return this.makeToken(Token.tokens.EQUAL_TOKEN);
    }else{
        this.reader.retract();
        return this.makeToken(Token.tokens.ASSIGN_TOKEN);
    }
break;
case ">":
    if (this.reader.nextChar() == "="){
        return this.makeToken(Token.tokens.GREATEREQUAL_TOKEN);
    }else{
        this.reader.retract();
        return this.makeToken(Token.tokens.GREATER_TOKEN);
    }
break;
case "<":
    if (this.reader.nextChar() == "="){
        return this.makeToken(Token.tokens.LESSEQUAL_TOKEN);
    }else{
        this.reader.retract();
        return this.makeToken(Token.tokens.LESS_TOKEN);
    }
break;

這裏有幾個字元還未被處理，因為它們比較特別，待會再談。以上一段程式有很多個 case，但它們做的大致上都差不多，就是當遇到某個字元（例如 “+”）時，就多讀一個字元，如果這個兩個字元連在一起是有特別意思的話就先返回這個”詞“（例如 “++”），否則就只返回自己成為單字元 Token。現在再看看如何處理 “/” 這個特別字元。

SLASH_STATE

第一步是要增加一個叫做 SLASH_STATE 的狀態。

1
Scanner.SLASH_STATE = Scanner.IDENTIFIER_STATE + 1;

然後在 START_STATE 增加一個 case，遇到 “/” 時就要轉到 SLASH_STATE。

1
2
3
case "/":
    this.state = Scanner.SLASH_STATE;
break;

最後在 SLASH_STATE 處理三個情況，line comment，block comment 及除號。

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
case Scanner.SLASH_STATE:
    var d = this.reader.nextChar();
    if (d == "/"){
        //line comment
        bufferStr = "";
        //reading 1 more char here can prevent the case that a // is followed by a line break char immediately
        d = this.reader.nextChar();
        if (d != "\r" && d != "\n"){
            while (d != "\r" && d != "\n"){
                bufferStr += d;
                d = this.reader.nextChar();
            }
            //to retract the line break char
            this.reader.retract();
        }
        this.state = Scanner.START_STATE;
        return this.makeToken(Token.tokens.LINECOMMENT_TOKEN, bufferStr);
    }else if (d == "*"){
        //block comment
        bufferStr = "";
        var end = false;
        while (! end){
            d = this.reader.nextChar();
            if (d != -1){
                if (d == "\r" || d == "\n"){
                    this.currLine++;
                }
                if (d == "*"){
                    var e = this.reader.nextChar();
                    if (e == "/"){
                        //meet */
                        end = true;
                    }else{
                        bufferStr += "*" + e;
                    }
                }else{
                    bufferStr += d;
                }
            }else{
                end = true;
            }
        }
        this.state = Scanner.START_STATE;
        return this.makeToken(Token.tokens.BLOCKCOMMENT_TOKEN, bufferStr);
    }else{
        this.state = Scanner.START_STATE;
        this.reader.retract();
        return this.makeToken(Token.tokens.DIV_TOKEN);
    }
break;

大家可以研究一下 SLASH_STATE 的 source code，但其實當中的 logic 都不太困難，如果下一個字元是 “*” 或者 “/” 的話就代表它是 comment，那就一直讀到“完畢”為止，否則就代表它只是除號 “/”，retract 之後就可以返回了。

為什麼處理 “/” 時要用一個新的狀態來處理，其他如 “+” 又不用呢？
其實用不用另一個狀態來處理都可以，沒有一個客觀的標準，西杰只能說兩個”可能“需要另開狀態的例子。第一個是當 logic 比較長的時候，就要考慮使用新的狀態，以避免代碼太過混亂或者太多縮排（indentation）。第二個情況是，如果開一個新狀態可以減少代碼重複的話就要開了，本教程沒有這種情況，大家想知更多的話看看 Actionscript compiler 的 Scanner 吧，當中處理 exponent 就會被整數和小數 literal 重用。

錯誤匯報

做完了沒有？細心閱讀的話就會發現還欠了 “&” 和 “|” 的處理，因為它們都有別於以上情況。看看以下代碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
case "&":
    if (this.reader.nextChar() == "&"){
        return this.makeToken(Token.tokens.AND_TOKEN);
    }else{
        this.reader.retract();
    }
break;
case "|":
    if (this.reader.nextChar() == "|"){
        return this.makeToken(Token.tokens.OR_TOKEN);
    }else{
        this.reader.retract();
    }
break;

那就好了嗎？不！如果遇上一個 “&” 或者一個 “|” 的話，在 Wescript 來說是 syntax error！那有 syntax error 要怎麼辦？當然是告訴用家啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
case "&":
    if (this.reader.nextChar() == "&"){
        return this.makeToken(Token.tokens.AND_TOKEN);
    }else{
        this.reader.retract();
        Errors.push({
            type: Errors.SYNTAX_ERROR,
            msg: "You have only one &",
            line: this.currLine
        });
    }
break;
case "|":
    if (this.reader.nextChar() == "|"){
        return this.makeToken(Token.tokens.OR_TOKEN);
    }else{
        this.reader.retract();
        Errors.push({
            type: Errors.SYNTAX_ERROR,
            msg: "You have only one |",
            line: this.currLine
        });
    }
break;

在最後就是在 Tester 中 iterate 一下所有錯誤並告訴用家了。現在看看運行結果。

這裏沒有提及數字處理部份，因為數字的處理方法沒有什麼特別之處，只要一直讀進來讀到沒有數字就可以了。
修正：網友指出如果程式末端不是空白的話會出現無限循環，原因是當程式語法在程式的末端出錯時，retract 會把 reader 退到上一個字元，永遠停不了！
解決方法有二：一、每次編譯前都在程式前後加一個空白字元；二、在 retract 時檢查程式到了末端沒有，到了就不能再 retract，現提供修正檔案！感謝網友”KJlmfe”指出問題。

大功告成！Scanner 終於寫好了，感受到 FSM 帶來的好處了沒有？使用 FSM 模式來開發，代碼簡單易明，亦很 scalable，要隨時加多兩種 Token 都可以。現在大家也可以試試自己開發一個 Scanner，創造一種屬於你自己的語言啦（其實還有很長的一段路……）！下周會開始寫 Parser，大家記得先讀熟這章的 Scanner 啊！

下周同樣時間，再見！

Share this:




Comments

  1. 你好，发现了一个严重的bug，在最后一个demo中，如果把测试数据
    //line comment
    /* block comment
    */
    + – * / ++ += — -= % = == != ! && ||
    & |
    中最后’|‘字符后的换行删除。

    则当程序在case ‘|’ 中，reader.nextChar() , 会返回-1且currPos并不会+1, 所以下面的retract会导致currPos又指向’|‘字符.

    Log in to Reply

    • 你好，感謝匯報問題！
      我想到的解決方案有二：
      一、在每次編譯前都自動加入一個空白字元（簡單但好像有點不負責任…）
      二、在 retract() 中判斷如果已到達程式末端的話就不能再 retract

      Log in to Reply

Leave a Reply

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。

    来自： quasiceo > 《深入浅出教你写编译器》

    举报

    推一荐：发原创得奖金，“原创奖励计划”来了！

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付：

    开通即同意《个图VIP服务协议》

    全部>>