- 自制編程語言
- (日)前橋和彌
- 5628字
- 2021-11-24 18:03:50
2.3 不借助工具編寫計算器
至此我們使用yacc和lex制作了一個計算器，可能會有讀者這樣想：
● 我明明是為了弄清楚編程語言的內部機制才要自制編程語言的，但是卻將yacc和lex等工具當作黑匣子使用，這樣一來豈不是達不到目的了嗎？
● bison和flex雖然都是自由軟件，但是在項目中客戶和上級是不允許使用免費軟件的；
● yacc/lex或bison/flex的版本升級可能會使程序無法工作，這很讓人討厭。
上面每一條理由都足夠充分（上級不允許使用免費軟件可能有點不講理，但是光嘴上說不講理是沒法解決這個問題的）。
因此，以下我們將不會借助yacc/lex來制作計算器。
2.3.1 自制詞法分析器
首先是詞法分析器。
操作本章的計算器時，會將換行作為分割符，把輸入分割為一個個算式。跨復數行的輸入是無法被解析為一個算式的，因此詞法分析器中應當提供以下的函數：
/＊ 將接下來要解析的行置入詞法分析器中 ＊/
void set_line（char ＊line）;
/＊ 從被置入的行中，分割記號并返回
＊ 在行尾會返回END_OF_LINE_TOKEN這種特殊的記號
＊/
void get_token（Token ＊token）;
get_token（）接受的入口參數為一個Token結構體指針，函數中會分割出記號的信息裝入Token結構體并返回。上面兩個函數的聲明以及Token結構體的定義位于token.h文件中。
代碼清單2-6 token.h
1: #ifndef TOKEN_H_INCLUDED
2: #define TOKEN_H_INCLUDED
3：
4: typedef enum {
5: BAD_TOKEN,
6: NUMBER_TOKEN,
7: ADD_OPERATOR_TOKEN,
8: SUB_OPERATOR_TOKEN,
9: MUL_OPERATOR_TOKEN,
10: DIV_OPERATOR_TOKEN,
11: END_OF_LINE_TOKEN
12: } TokenKind;
13：
14: #define MAX_TOKEN_SIZE（100）
15：
16: typedef struct {
17: TokenKind kind;
18: double value;
19: char str[MAX_TOKEN_SIZE];
20: } Token;
21：
22: void set_line（char ＊line）;
23: void get_token（Token ＊token）;
24：
25: #endif /＊ TOKEN_H_INCLUDED ＊/
詞法分析器的源代碼如代碼清單2-7所示。
代碼清單2-7 lexicalanalyzer.c
1: #include <stdio.h＞
2: #include <stdlib.h＞
3: #include <ctype.h＞
4: #include "token.h"
5：
6: static char ＊st_line;
7: static int st_line_pos;
8：
9: typedef enum {
10: INITIAL_STATUS,
11: IN_INT_PART_STATUS,
12: DOT_STATUS,
13: IN_FRAC_PART_STATUS
14: } LexerStatus;
15：
16: void
17: get_token（Token ＊token）
18: {
19: int out_pos = 0;
20: LexerStatus status = INITIAL_STATUS;
21: char current_char;
22：
23: token-＞kind = BAD_TOKEN;
24: while（st_line[st_line_pos] ! = '\0'）{
25: current_char = st_line[st_line_pos];
26: if（（status == IN_INT_PART_STATUS || status == IN_FRAC_
PART_STATUS）
27: && ! isdigit（current_char）&& current_char ! = '.'）{
28: token-＞kind = NUMBER_TOKEN;
29: sscanf（token-＞str, "%lf", &token-＞value）;
30: return;
31: }
32: if（isspace（current_char））{
33: if（current_char == '\n'）{
34: token-＞kind = END_OF_LINE_TOKEN;
35: return;
36: }
37: st_line_pos++;
38: continue;
39: }
40：
41: if（out_pos ＞= MAX_TOKEN_SIZE-1）{
42: fprintf（stderr, "token too long.\n"）;
43: exit（1）;
44: }
45: token-＞str[out_pos] = st_line[st_line_pos];
46: st_line_pos++;
47: out_pos++;
48: token-＞str[out_pos] = '\0';
49：
50: if（current_char == '+'）{
51: token-＞kind = ADD_OPERATOR_TOKEN;
52: return;
53: } else if（current_char == '-'）{
54: token-＞kind = SUB_OPERATOR_TOKEN;
55: return;
56: } else if（current_char == '＊'）{
57: token-＞kind = MUL_OPERATOR_TOKEN;
58: return;
59: } else if（current_char == '/'）{
60: token-＞kind = DIV_OPERATOR_TOKEN;
61: return;
62: } else if（isdigit（current_char））{
63: if（status == INITIAL_STATUS）{
64: status = IN_INT_PART_STATUS;
65: } else if（status == DOT_STATUS）{
66: status = IN_FRAC_PART_STATUS;
67: }
68: } else if（current_char == '.'）{
69: if（status == IN_INT_PART_STATUS）{
70: status = DOT_STATUS;
71: } else {
72: fprintf（stderr, "syntax error.\n"）;
73: exit（1）;
74: }
75: } else {
76: fprintf（stderr, "bad character（%c）\n", current_char）;
77: exit（1）;
78: }
79: }
80: }
81：
82: void
83: set_line（char ＊line）
84: {
85: st_line = line;
86: st_line_pos = 0;
87: }
88：
89: /＊ 下面是測試驅動代碼 ＊/
90: void
91: parse_line（char ＊buf）
92: {
93: Token token;
94：
95: set_line（buf）;
96：
97: for（; ;）{
98: get_token（&token）;
99: if（token.kind == END_OF_LINE_TOKEN）{
100: break;
101: } else {
102: printf（"kind..%d, str..%s\n", token.kind, token.str）;
103: }
104: }
105: }
106：
107: int
108: main（int argc, char ＊＊argv）
109: {
110: char buf[1024];
111：
112: while（fgets（buf, 1024, stdin）! = NULL）{
113: parse_line（buf）;
114: }
115：
116: return 0;
117: }
這個詞法分析器的運行機制為，每傳入一行字符串，就會調用一次get_token（）并返回分割好的記號。由于詞法分析器需要記憶set_line（）傳入的行，以及該行已經解析到的位置，所以設置了靜態變量st_line與st_line_pos（第6～7行）
。
set_line（）函數，只是單純設置了st_line與st_line_pos的值。
get_token（）則負責將記號實際分割出來，即詞法分析器的核心部分。
第24行開始的while語句，會逐一按照字符掃描st_line。
記號中的 +、 -、 ＊、 /四則運算符只占一個字符長度，因此一旦掃描到了，立即返回就可以了。
數值部分要稍微復雜一些，因為數值由多個字符構成。鑒于我們采用的是while語句逐字符掃描這種方法，當前掃描到的字符很有可能只是一個數值的一部分，所以必須想個辦法將符合數值特征的值暫存起來。為了暫存數值，我們采用一個枚舉類型LexerStatus的全局變量status（第20行）。
首先，status的初始狀態是INITIAL_STATUS。當遇到0～9的數字時，這些數字會被放入整數部分（此時狀態為IN_INT_PART_STATUS）中（第64行）。一旦遇到小數點．, status會由IN_INT_PART_STATUS切換為DOT_STATUS（第70行）, DOT_STATUS再遇到數字會切換到小數狀態（IN_FRAC_PART_STATUS，第66行）。在IN_INT_PART_STATUS或IN_FRAC_PART_STATUS的狀態下，如果再無數字或小數點出現，則結束，接受數值并return。
按上面的處理，詞法分析器會完全排除．5或2..3這樣的輸入。而從第32行開始的處理，除換行以外的空白符號全部會被跳過。
由于是用于計算器的詞法分析器，因此除四則運算符與數值外，沒有其他要處理的對象了，但如果考慮到將其擴展并可以支持編程語言的話，最好提前想到以下幾個要點。
1．數值與標識符（如變量名等）可以按照上例的方法通過管理一個當前狀態將其解析出來，比如自增運算符就可以設置一個類似IN_INCREMENT_OPERATOR的狀態，但這樣一來程序會變得冗長。因此對于運算符來說，可能為其準備一個字符串數組會更好。比如做一個下面這樣的數組：
static char ＊st_operator_str[] = {
"++",
"--",
"+",
"-",
（以下省略）
};
當前讀入的記號可以與這個數組中的元素做前向匹配，從而判別記號的種類。指針部分同樣需要比特征對象再多讀入一個字符用以判別（比如輸入i+2，就需要將2也讀入看看有沒有是i++的可能性）。做判別時，像上例這樣將長的運算符放置在數組前面會比較省事。關于額外讀入的一個字符具體應該如何處理，稍后會介紹。
另外，像if、 while這些保留字，比較簡單的做法是先將其判別為標識符，之后再去對照表中查找有沒有相應的保留字。
2．本次的計算器是以行為單位的，st_line會保存一行中的所有信息，但在當下的編程語言中，換行一般和空白字符是等效的，因此不應該以行為單位處理，而是從文件中逐字符（使用getc（）等函數）讀入解析會更好。
那么，上例中用while語句逐字符讀取的地方就需要替換為用getc（）等函數來讀取，比如輸入123.4+2時，判別數值是否結束的時機是讀入 +時。
上例的詞法分析器是通過st_line_pos的自增（第46行st_line_pos++）來實現的。如果直接從文件逐字符讀入，C語言中就需要使用ungetc（）等從讀入的字符回退，從而產生1個字符的備份，達到預先讀入下一字符的效果。
補充知識 保留字（關鍵字）
在C語言中，if與while都是保留字，保留字無法再作為變量名使用【C規范中一般不稱“保留字”（reserved word），而稱為“關鍵字”（keyword），但是關鍵字的指代范圍太廣，所以還是稱保留字更加準確】。
C語言中的保留字是由詞法分析器以特殊的標識符方式處理的。保留字的區分以標識符為單位，比如if不能作為變量名但ifa就可以。
對于習慣了C語言的人來說，這都是理所當然的事情，但站在其他語言的角度看卻未必如此。
比如在我小時候折騰過一門叫BASIC的編程語言，可以這樣寫：
IFA=10THEN...
會解析為：
IF A = 10 THEN ...
向雜志投稿的程序中，注釋（英語為remark）都寫成了下面這樣：
REMARK這里是注釋
BASIC中的注釋只需要寫REM語句，REM之后都會被作為注釋處理，因此即便寫成REMARK也是可以的。
BASIC是從FORTRAN的基礎上發展起來的，以前FORTRAN中空白字符沒有任何意義。GOTO可以寫成GO TO，也可以寫成G OTO，而在寫循環的時候，下例等于寫了一個1到5的循環。
DO 10 I=1,5
處理
10 CONTINUE
如果一不小心將逗號輸入成句號，寫成下面這樣：
DO 10 I=1.5
由于FORTRAN中空白沒有意義，而且上例中也無需聲明變量（D開始的變量默認解析成實數型變量），所以最后會變成DO10I=1.5這樣的賦值語句。有傳聞說就是這樣一個BUG最終導致NASA的火箭失控爆炸，當然這多半是謠傳了。
另外在C#中還有上下文關鍵字（context keyword），是指一些在特殊的區域內才對編譯器有特殊意義的關鍵字（比如定義屬性時使用get等）。內容關鍵字并不等同于保留字，在普通的變量名中可以使用。保留字與關鍵字嚴格講有不同的意義，但本書中沒有特別區分。
補充知識 避免重復包含
在代碼清單2-6中，開頭和結尾處有這樣的語句：
#ifndef TOKEN_H_INCLUDED
#define TOKEN_H_INCLUDED
（中間省略）
#endif /＊ TOKEN_H_INCLUDED ＊/
這是為了防止token.h多次用 #include包含引起多重定義錯誤而采用的技巧。
頭文件經常會用到其他頭文件中定義的類型或宏。比如在a.h中定義的類型在b.h中使用的話，在b.h的開頭處書寫 #include "a.h"就可以了。如果不這樣做，程序用 #include包含b.h時，必須同時書寫 #include a.h與 #include b.h，還會弄得代碼到處都是長串 #include，之后如果依賴關系發生改變的話修改起來非常麻煩。
但僅僅在頭文件的起始處用 #include包含a.h，如果多個頭文件都這樣書寫，會報出類型或宏的重復定義錯誤。因此采用上面的小技巧，一旦token.h用 #include包含后會定義TOKEN_H_INCLUDED，根據開頭的 #ifndef語句，該頭文件將被忽略，也就避免了產生多重定義的錯誤。
下面的兩點是編寫C頭文件的經驗之談，本書中涉及的代碼都默認遵循這兩點：
1．所有的頭文件都必須用 #include包含自己所依賴的其他所有頭文件，最終讓代碼中只需一次 #include；
2．所有的頭文件都必須加入上文的技巧，防止出現多重定義錯誤。
2.3.2 自制語法分析器
接下來終于要開始做語法分析器了。
在我看來，只要是有一定編程經驗的程序員，即使沒有自制編程語言的背景，都可以大致想明白詞法分析器的運行機制。但換成語法分析器，可能很多人就有點摸不著頭腦了。有些人可能會想，總之先只考慮計算器程序，將運算符優先級最低的 +與 -分割出來，然后再處理 ＊和 /……這樣的思路基本是正確的。但是按這樣的思路實際操作時會發現，用來保存分割字符串的空間可能還有其他用途，而加入括號的處理也很難。
對于上面的問題，與其自己想破腦袋，不如借鑒一下前人的智慧。因此我們將使用一種叫遞歸下降分析的方法來編寫語法分析器。
yacc版的計算器曾使用下面的語法規則：
expression /＊ 表達式的規則 ＊/
：term /＊ 表達式 ＊/
| expression ADD term /＊ 或 表達式 + 表達式 ＊/
| expression SUB term /＊ 或 表達式 - 表達式 ＊/
;
term /＊ 表達式的規則 ＊/
：primary_expression /＊ 一元表達式 ＊/
| term MUL primary_expression /＊ 或 表達式 ＊ 表達式 ＊/
| term DIV primary_expression /＊ 或 表達式 / 表達式 ＊/
;
primary_expression /＊ 一元表達式的規則 ＊/
：DOUBLE_LITERAL /＊ 實數的字面常量 ＊/
;
這些語法規則可以用圖2-5這樣的語法圖（syntax graph或syntax diagram）來表示。
圖2-5 計算器的語法圖
語法圖的表示方法應該一看就能明白，比如項目（term）的語法圖代表最初進入一元表達式（primary_expression），一元表達式可以直接結束，也可以繼續進行 ＊或 /運算，然后又有一個一元表達式進入，重復這一流程。作為語法構成規則的說明，語法圖要比BNF更容易理解吧。
本書的語法圖例中，非終結符用長方形表示，終結符（記號）用橢圓形表示。
正如語法圖所示，遞歸下降分析法讀入記號，然后執行語法分析。
比如解析一個項目（term）的函數parse_term（），如代碼清單2-8所示，按照語法圖所示流程工作。
代碼清單2-8 parser.c（節選）
/＊ primary expression的解析函數 ＊/
51: v1 = parse_primary_expression（）;
52: for（; ;）{
53: my_get_token（&token）;
/＊ 循環掃描“＊”、“/”以外的字符 ＊/
54: if（token.kind ! = MUL_OPERATOR_TOKEN
55: && token.kind ! = DIV_OPERATOR_TOKEN）{
/＊ 將記號Token退回 ＊/
56: unget_token（&token）;
57: break;
58: }
/＊ primary expression的解析函數 ＊/
59: v2 = parse_primary_expression（）;
60: if（token.kind == MUL_OPERATOR_TOKEN）{
61: v1 ＊= v2;
62: } else if（token.kind == DIV_OPERATOR_TOKEN）{
63: v1 /= v2;
64: }
65: }
66: return v1;
如同語法圖中最開始的primary_expression進入一樣，第51行的parse_primary_expression（）會被調用。遞歸下降分析法中，一個非終結符總對應一個處理函數，語法圖里出現非終結符就代表這個函數被調用。因此在第52行下面的for語句會構成一個無限循環，如果 ＊（MUL_OPERATOR）與 /（DIV_OPERATOR）進入，循環會持續進行（其他字符進入則通過第57行的break跳出）。而第59行第二次調用parse_primary_expression（），與語法圖中 ＊和 /右邊的primary expression相對應。
比如遇到語句1 ＊ 2 + 3，第51行的parse_primary_expression（）將1讀入，第53行my_get_token（）將 ＊讀入，接下來第59行的parse_primary_expression（）將2讀入。之后的運算符根據種類不同分別執行乘法（第61行）或除法（第63行）。
至此已經計算完畢1 ＊ 2，然后第53行的my_get_token（）讀入的記號是 +。+之后再沒有term進入，用break從循環跳出。但由于此時已經將 +讀進來了，因此還需要用第56行的unget_token（）將這個記號退回。parser. c沒有直接使用lexicalanalyzer.c中寫好的get_token（），而使用了my_get_token（）, my_get_token（）會對1個記號開辟環形緩沖區（Ring Buffer）（代碼清單2-9第7行的靜態變量st_look_ahead_token是全部緩沖），可以借用環形緩沖區將最后讀進來的1個記號用unget_token（）退回。這里被退回的 +，會重新通過parse_expression（）第78行的my_get_token（）再次讀入。
完整代碼如代碼清單2-9所示。
根據語法圖的流程可以看到，當命中非終結符時，會通過遞歸的方式調用其下級函數，因此這種解析器稱為遞歸下降解析器。
這個程序作為一個帶有運算優先級功能的計算器來說，代碼是不是出乎意料地簡單呢。那么請嘗試對各種不同的算式進行真機模擬，用debug追蹤或者printf（）實際調試一下吧。
代碼清單2-9 parser.c
1: #include <stdio.h＞
2: #include <stdlib.h＞
3: #include "token.h"
4：
5: #define LINE_BUF_SIZE（1024）
6：
7: static Token st_look_ahead_token;
8: static int st_look_ahead_token_exists;
9：
10: static void
11: my_get_token（Token ＊token）
12: {
13: if（st_look_ahead_token_exists）{
14: ＊token = st_look_ahead_token;
15: st_look_ahead_token_exists = 0;
16: } else {
17: get_token（token）;
18: }
19: }
20：
21: static void
22: unget_token（Token ＊token）
23: {
24: st_look_ahead_token = ＊token;
25: st_look_ahead_token_exists = 1;
26: }
27：
28: double parse_expression（void）;
29：
30: static double
31: parse_primary_expression（）
32: {
33: Token token;
34：
35: my_get_token（&token）;
36: if（token.kind == NUMBER_TOKEN）{
37: return token.value;
38: }
39: fprintf（stderr, "syntax error.\n"）;
40: exit（1）;
41: return 0.0; /＊ make compiler happy ＊/
42: }
43：
44: static double
45: parse_term（）
46: {
47: double v1;
48: double v2;
49: Token token;
50：
51: v1 = parse_primary_expression（）;
52: for（; ;）{
53: my_get_token（&token）;
54: if（token.kind ! = MUL_OPERATOR_TOKEN
55: && token.kind ! = DIV_OPERATOR_TOKEN）{
56: unget_token（&token）;
57: break;
58: }
59: v2 = parse_primary_expression（）;
60: if（token.kind == MUL_OPERATOR_TOKEN）{
61: v1 ＊= v2;
62: } else if（token.kind == DIV_OPERATOR_TOKEN）{
63: v1 /= v2;
64: }
65: }
66: return v1;
67: }
68：
69: double
70: parse_expression（）
71: {
72: double v1;
73: double v2;
74: Token token;
75：
76: v1 = parse_term（）;
77: for（; ;）{
78: my_get_token（&token）;
79: if（token.kind ! = ADD_OPERATOR_TOKEN
80: && token.kind ! = SUB_OPERATOR_TOKEN）{
81: unget_token（&token）;
82: break;
83: }
84: v2 = parse_term（）;
85: if（token.kind == ADD_OPERATOR_TOKEN）{
86: v1 += v2;
87: } else if（token.kind == SUB_OPERATOR_TOKEN）{
88: v1-= v2;
89: } else {
90: unget_token（&token）;
91: }
92: }
93: return v1;
94: }
95：
96: double
97: parse_line（void）
98: {
99: double value;
100：
101: st_look_ahead_token_exists = 0;
102: value = parse_expression（）;
103：
104: return value;
105: }
106：
107: int
108: main（int argc, char ＊＊argv）
109: {
110: char line[LINE_BUF_SIZE];
111: double value;
112：
113: while（fgets（line, LINE_BUF_SIZE, stdin）! = NULL）{
114: set_line（line）;
115: value = parse_line（）;
116: printf（"＞＞%f\n", value）;
117: }
118：
119: return 0;
120: }
補充知識 預讀記號的處理
本書中采用的遞歸下降解析法，會預先讀入一個記號，一旦發現預讀的記號是不需要的，則通過unget_token（）將記號“退回”。
換一種思路，其實也可以考慮“始終保持預讀一個記號”的方法。按照這種思路，代碼清單2-9可以改寫成代碼清單2-10這樣：
代碼清單2-10 parser.c（始終保持預讀版）
/＊ token變量已經放入了下一個記號 ＊/
parse_primary_expression（）;
for（; ;）{
/＊ 這里無需再讀入記號 ＊/
if（token.kind ! = MUL_OPERATOR_TOKEN
&& token.kind ! = DIV_OPERATOR_TOKEN）{
/＊ 不需要退回處理 ＊/
break;
}
/＊ token.kind之后還會使用，所以將其備份
＊ 而parse_primary_expression（）也就可以讀入新的記號
＊/
kind = token.kind;
my_get_token（&token）;
v2 = parse_primary_expression（）;
if（token.kind == MUL_OPERATOR_TOKEN）{
v1 ＊= v2;
} else if（token.kind == DIV_OPERATOR_TOKEN）{
v1 /= v2;
}
}
比較這兩種實現方式，會發現兩者的實質基本上是一樣的。很多編譯器入門書籍中列舉的實例代碼，和本書中的例子相差無幾。
不過這里還是會有個人偏好，就我而言，更喜歡“邊讀入邊退回”的方法。在“始終保持預讀”的方法中，變量token是一個全局變量，代碼中相隔很遠的地方也會操作其變量值，追蹤數據變化會比較麻煩。
- Building Modern Web Applications Using Angular
- Python高級編程
- Learn Programming in Python with Cody Jackson
- Scratch 3游戲與人工智能編程完全自學教程
- Java程序設計
- Python編程實戰
- Bootstrap 4 Cookbook
- Python Data Science Cookbook
- Python 3.7從入門到精通（視頻教學版）
- Unity 2017 Game AI Programming（Third Edition）
- JavaWeb從入門到精通（視頻實戰版）
- 計算機系統解密：從理解計算機到編寫高效代碼
- Android從入門到精通
- JavaScript設計模式與開發實踐
- TypeScript High Performance