compiler [0] - lexer, lexical analyzer, scanner, tokenizer, 詞法分析器

目不能兩視而明,耳不能兩聽而聰。

向 Donald Knuth 學習, 一次只專心做一件事情, 果然就能突破困難的問題。我在掙扎了幾個禮拜後, 終於有所收穫。

為什麼要學習 compiler 呢? 能把文字變成另外的文字這樣的技術很神奇, 這應該也是本科系要有的技能, 否則怎麼和現在職訓局、補習班的人競爭, 人家可是拼個半年就來和你搶飯碗了, 把基本中的基本學好, 而不隨波逐流, 才能在競爭激烈的時代生存。講的太嚴重了, 其實只是因為「興趣」而已, 就像希臘數學家丟番圖 (Diophantus) 每天都在解數學題目一樣, have fun。自己有興趣的東西哪要什麼理由。

摘錄 Developing Developer

如果這個東西這麼難懂，那麼對很多人來說，是一樣難懂的。你已經花了一段時間跟心力，去發現「它很難懂」。而別人連這段時間都還沒有投入，當未來在實務上真的發生這樣的問題或需求時，你需要暖機的時間就比別人少一點。

在 os 的學習暫時告一個段落後, 我把學習重點轉到了 compiler, 也和 os 一樣, 我挑戰好幾次, 但是都失敗了, 我已經到了《發現它很難懂的境界了》。這次我決定再挑戰一次, 看能不過突破《發現它很難懂的境界了》這關, compiler 有多難呢? 我在《自己动手写编译器、链接器》描述了寫 compiler 的幾個困難之處。

和完成 simple os, simple scheme, simple gui 類似, 我總是得需要一本好的教材, simple libc++ 不同, 沒有書在教人怎麼寫一個 c++ 標準程式庫, 這真的就得靠自己來完成。書買了不少, 結果每本題的實作方式都不太一樣, 各自有自己的花招, 讓學習更困難了。最後以《两周自制脚本语言》這本書為主力。

compiler 這個技術很難很雜, 我一開始費了好大的心力才找出《怎麼學習》這門技術的方法 (找出一個有效的學習方式也不是那麼容易), 一樣是化繁為簡的老招數, 我的目標很簡單, 要學會的有:

1. 四則運算
2. if/eles
3. function call
4. while

網路上找的文章不是太簡單 - 只有四則運算 (學不到 if/else); 要不然就是太難 - 很完整的一個語言實作 (很難看懂); 其實只要有上述的 1, 2, 3 就可以算是一個很豐富的程式語言了, 再把心力集中在數學運算就更簡化了, 不要有太複雜的變數宣告語法。4 的 while 不一定要支援, scheme 沒有 while, 靠 recursive function 來完成 while 這件事。

我想寫個簡單又完整的系列, 希望可以讓對編譯器有興趣的程式員入門, 和學習 os 一樣, 我知道很多人也是挑戰失敗, 大家一起來享受失敗的感覺 (誤)。

「其實只有比 scheme interpreter 多一個 while 而已。」寫出這句話很輕鬆, 實作起來非常辛苦。一樣先用 interpreter 的方式, 之前寫 simple scheme 帶給我不少痛苦經驗, 這時候就派上用場了; 再來才是 compile 成 virtual machine 的 machine code; 如果還有精力的話才是 elf real machine code。

至於語法, 則是 c 的一個小小小子集, 然後我要生出 AST, 我終於體會到靠《自己动手写编译器、链接器》為什麼學不起來, 他還是太複雜了, 雖然這已經簡化了 c 的語法, 但還是有很多的東西, 最後我參考《手把手教你构建 C 语言编译器》更精簡的 c 語法來再一次的降低語法複雜度。

如果不能 compile 自己喜歡的語言, 而只是什麼學習用的語言, 實在是提不起勁來完成, 所以我還是選擇編譯 c 語言, 但簡化到極致來方便學習。我的實作則是用 c++, 其實我想要實作 c++ compiler, 之前有個 C++ Grandmaster Certification, 我知道自己幾兩重; 不過 c 的某部份也算 c++, 就別那麼計較了。

大概只能使用

f1

 1 int i,j;
 2 
 3 int func(int x, char dd)
 4 {
 5   char a,b;
 6   1+2;
 7   9+5*6;
 8   if (a>1)
 9   {
10     5+6;
11     55+66;
12   }
13   else
14   {
15     7*9;
16     77*99;
17   }
18 
19   while(x>1)
20   {
21     a *b;
22     5-1;
23   }
24 
25   -10;
26 }

int (*getfp())(int, int) 這種複雜的宣告當然目前是 parse 不出來的, 這可不是表面上看來的那麼簡單, N1570 6.7.6 有 c 宣告的參考資料, 可惜我有看沒有懂, 這種宣告只好不支援了。http://cdecl.org/ 可以分析這些複雜的宣告。

目前僅僅支援這樣的語法。沒有 "abc" string 用法, 不能處理字串, 還好, 不能就不能; 沒有 int arr[] array 的語法, 這問題不大, 因為有支援指標, 用指標來代替 array 就好, 當然他們兩個是有點不一樣, 不過就別計較了。

「疑! 你不是說要簡化嗎? 怎麼要支援指標?」 因為指標是 c 語言的重點, 不能用指標還能算是 c 語言嗎?

另外一個不好學的原因是書中的程式碼在講解上幾乎都不是很清楚, 我都是將原始碼編譯執行再透過 gdb single step 後才真的理解其行為, 不怪作者, 要怎麼在書中清楚說明原始碼的行為真的不是太容易, 所以取得書中的範例程式碼很重要, 我只買有付程式碼的編譯器書籍。

有的人說現在 compier 技術超複雜的, 最佳化才是重點, 也許是吧? 不過我還是想一條鞭的把整個技術串起來, 我不求精通, 求的是從頭到尾做一次。

os 的學習是這樣, gui MVC 架構的學習是這樣, compiler 的學習也打算這麼做。

os 和 compiler 哪個難呢? 這問題還真難? 很多技術都很難, 演算法和資料結構也是, 處理大量的網路連線是, 人工智慧, big data 也是 ... 難難難 ...

第一關是 lexical analyzer, 它有好幾個名字: lexer, scanner, tokenizer, 中文是詞法分析器。

《两周自制脚本语言》chapter 15 教了我使用自動機的方式來寫 lexer, 花點心力理解之後, 很容易就完成了, 完全不會迷失在那些 state 上。

這是以 regular expression 來思考的方式, 把 regular expression 轉成如 fig 3 的圖。其對應的 regular expression 是:

\s*([0-9][0-9]*|[A-Za-z][A-Za-z0-9]*|=|==)

我先看圖想著程式邏輯, 想清楚後再轉成程式碼, 有點小難, 但應該難不倒你的, 這才是第一關而己。指向別的號碼就是用 if, 指回自己的號碼就是用 while, 想懂之後會發現:「媽呀! 怎麼這麼簡單, 好想來寫 html 的 lexer。」自己開工試試看, 只看文章是學不會的。

c++ 11 有了 regex, 可以用來處理 lexer, 還有 flex 這種工具也可以, 不過手工寫的爽度爆表。

=, == 這是最奧妙的地方。

一開始先挑戰簡單的詞法定義: ex: 字串, 用 "" 包起來的就是; 或是 /* */ c 註解格式, 再來就可以挑戰複雜一點的, ex: html, terminal escape sequence。

fig 3

lexer.cpp

  1 #include <cstdio>
  2 #include <string>
  3 #include <cctype>
  4
  5 #include <iostream>
  6
  7 using namespace std;
  8
  9 #define OK 0
 10 #define ERR 1
 11
 12 // printable ascii, but not (, )
 13 static inline int isgraph_ex(int c)
 14 {
 15 #if 1
 16   if (c == '(')
 17     return 0;
 18   if (c == ')')
 19     return 0;
 20 #endif
 21   return isgraph(c);
 22 }
 23
 24 int la=-1;
 25
 26 int getchar_la()
 27 {
 28   if (la != -1)
 29   {
 30     int tmp=la;
 31     la = -1;
 32     return tmp;
 33   }
 34   else
 35     return getchar();
 36 }
 37
 38 int get_token(string &token)
 39 {
 40   int c;
 41
 42   do
 43   {
 44     c = getchar_la();
 45   }while(isspace(c));
 46
 47   if (c == EOF)
 48     return EOF;
 49   else if (isdigit(c))
 50        {
 51          do
 52          {
 53            token.push_back(c);
 54            c = getchar_la();
 55          }while(isdigit(c));
 56        }
 57        else if (isalpha(c))
 58             {
 59               do
 60               {
 61                 token.push_back(c);
 62                 c = getchar_la();
 63               } while(isalnum(c));
 64             }
 65             else if (c == '=')
 66                  {
 67                    c = getchar_la();
 68                    if (c == '=')
 69                    {
 70                      token = "==";
 71                    }
 72                    else
 73                    {
 74                      la = c;
 75                      token = "=";
 76                    }
 77                    return OK;
 78                  }
 79                  else
 80                  {
 81                    return ERR;
 82                  }
 83   if (c != EOF)
 84     la = c;
 85   return OK;
 86 }
 87
 88 int get_se_token(string &token)
 89 {
 90   int c;
 91
 92   do
 93   {
 94     c = getchar_la();
 95   }while(isspace(c));
 96
 97   if (c == EOF)
 98     return EOF;
 99   else if (c == '(')
100        {
101          token = '(';
102          return OK;
103        }
104        else if (c == ')')
105             {
106               token = ')';
107               return OK;
108             }
109             else if (isgraph_ex(c)) // printable ascii, but not (, )
110                  {
111                    do
112                    {
113                      token.push_back(c);
114                      c = getchar_la();
115                    }while(isgraph_ex(c));
116                  }
117                  else
118                  {
119                    return ERR;
120                  }
121
122
123   if (c != EOF)
124     la = c;
125   return OK;
126 }
127
128 int main(int argc, char *argv[])
129 {
130   while(1)
131   {
132     string token;
133
134     //int ret = get_token(token);
135     int ret = get_se_token(token);
136     if (ret == EOF)
137     {
138       break;
139     }
140     if (ret == OK)
141     {
142       cout << "token: " << token << endl;
143     }
144     else
145     {
146       cout << "token error" << endl;
147     }
148     token.clear();
149   }
150
151   return 0;
152 }

後來畫了一張 scheme 的自動機圖, 難得畫的這麼好看 , 發現很快就可以寫出正確分割 token 的程式, 比之前的胡思亂想更有可讀性。

fig4

lexer.cpp L88 就是實作 fig 4 的 lexer。

另外一個重要的觀念是「放回去」, ex: =, == 需要判斷到第二個 = 的時候才知道是 =, 還是 ==, 這時候需要放回去的能力。

ex: =1, 就需要把 1 放回去, 下次從 1 開始比對。

c function 有個 ungetc(), 我本來想要是沒這個怎麼辦, 後來想到自己用個變數存起來就好了, 就不需要使用 ungetc(), 如果需要放回多個, 用 c++ 的容器 queue 就可以搞定。為什麼不用 ungetc(), 這樣我的 simple libc++ 就要支援這個了 (雖然我已經寫好了)。

執行結果

1 descent@debian64:lexer$ ./lexer
2 123 ab09==7 x=5
3 token: 123
4 token: ab09
5 token: ==
6 token: 7
7 token: x
8 token: =
9 token: 5

我最後寫了 /* */, "abc aaa", 現在想挑戰 html, terminal escape sequence。

後來我有個詞法上色的功能, 就是《自己动手写编译器、链接器》裡頭的想法, 本來打算用 ncurses 來上色, 不過殺雞用屠龍刀太浪費了, 印出終端機色碼來完成這件事。