【深入淺出教你寫編譯器(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 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 真正的意思了。
好了,現在要寫一寫 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。

又,判斷一下 bufferStr 中的字是不是關鍵字(Reserved word),如果是的話就返回相對應的 Token,不然就把它統稱為 IDENTIFIER_TOKEN,留給 Parser 做語法分析時再判斷如何處理它。
現在執行一下我們的 Scanner,看它是否運作正常。
現在就把餘下的 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 的狀態。
然後在 START_STATE 增加一個 case,遇到 “/” 時就要轉到 SLASH_STATE。
最後在 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 之後就可以返回了。
錯誤匯報
做完了沒有?細心閱讀的話就會發現還欠了 “&” 和 “|” 的處理,因為它們都有別於以上情況。看看以下代碼:
那就好了嗎?不!如果遇上一個 “&” 或者一個 “|” 的話,在 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 一下所有錯誤並告訴用家了。現在看看運行結果。
大功告成!Scanner 終於寫好了,感受到 FSM 帶來的好處了沒有?使用 FSM 模式來開發,代碼簡單易明,亦很 scalable,要隨時加多兩種 Token 都可以。現在大家也可以試試自己開發一個 Scanner,創造一種屬於你自己的語言啦(其實還有很長的一段路……)!下周會開始寫 Parser,大家記得先讀熟這章的 Scanner 啊!
下周同樣時間,再見!