搜尋

隨機推薦

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

【深入淺出教你寫編譯器(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 定義,增加以下的定義。

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 吧。

Scanner.IDENTIFIER_STATE = Scanner.START_STATE + 1;
 
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 了。

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 都定義過來吧。

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 了。

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 啊!

下周同樣時間,再見!

 


 

 

廣告

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

Please publish modules in offcanvas position.