繼續上一節未完成的 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 真正的意思了。
好了,現在要寫一寫 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。
又,判斷一下 bufferStr 中的字是不是關鍵字(Reserved word),如果是的話就返回相對應的 Token,不然就把它統稱為 IDENTIFIER_TOKEN,留給 Parser 做語法分析時再判斷如何處理它。
現在執行一下我們的 Scanner,看它是否運作正常。
現在就把餘下的 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 之後就可以返回了。
錯誤匯報
做完了沒有?細心閱讀的話就會發現還欠了 “&” 和 “|” 的處理,因為它們都有別於以上情況。看看以下代碼:
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 一下所有錯誤並告訴用家了。現在看看運行結果。
大功告成!Scanner 終於寫好了,感受到 FSM 帶來的好處了沒有?使用 FSM 模式來開發,代碼簡單易明,亦很 scalable,要隨時加多兩種 Token 都可以。現在大家也可以試試自己開發一個 Scanner,創造一種屬於你自己的語言啦(其實還有很長的一段路……)!下週會開始寫 Parser,大家記得先讀熟這章的 Scanner 啊!
下周同樣時間,再見!
- 一、簡介 by Dukeland
- 二、掃瞄器(Scanner)﹣詞法分析(Lexical analysis)(上)
- 二、掃瞄器(Scanner)﹣詞法分析(Lexical analysis)(下)
- 三、語法分析器(Parser)﹣語法分析(Syntactic analysis)(上)
- 三、語法分析器(Parser)﹣語法分析(Syntactic analysis)(中)
- 三、語法分析器(Parser)﹣語法分析(Syntactic analysis)(下)
- 四、語意分析(Semantic analysis)
- 五、虛擬機(Virtual Machine)
- 六、編譯器(Compiler)﹣生成代碼(Code Generation)(上)
- 六、編譯器(Compiler)﹣生成代碼(Code Generation)(下)
廣告
