yacc/bison 系列 (3) - c parser

看人挑擔不吃力, 自己挑擔壓斷肩。

馬上就要挑戰 c parser 嗎? 是也不是, 最主要只處理合法的 c 語言輸入, 並沒有要輸出組合語言、AST 或是語意分析之類的動作, 這樣就簡單很多。

麻煩的是 c yacc 語法規則要怎麼寫, 我自己是寫不出來的, The c programming language 附錄 A 有一個這樣的 yacc 語法, 稍加修改就可以用了。但我不會修改, 也不想輸入那麼多字, 在網路上找到了範例。至於為什麼 The c programming language 附錄 A 會有 yacc 文法, 因為 yacc 也是那時候開發出來的, Dennis MacAlistair Ritchie 沒理由不用的, 不只 c 用了, 連 c++ 也有用 yacc, 畢竟是同時期的貝爾實驗室同事。

https://www.lysator.liu.se/c/ANSI-C-grammar-y.html, 只有這個當然不行, 還得有搭配的 lexer, 在這邊 https://www.lysator.liu.se/c/ANSI-C-grammar-l.html。

我本來想找 usenet/net.sources/ansi.c.grammar.Z, 但是找了 ftp.uu.net mirror 站台都找不到, 只好自己拼湊了。只要補上相關的 code 就可以了,

完成這個不難, 最難的部份人家都寫好了, 我只是補上可以編譯的 code 而已, 測試了一些很複雜的宣告, 例如:

list 1. pthread_create

1 int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);

A, 有錯耶, 奇怪, 失敗了嗎? 後來發現是 pthread_attr_t, 這些都不是內建型別, 需要先用 typedef 宣告之後才能用, 然後我就發現 typedef 也不能用。思考一下之後就發現問題了, 之後稍加改 code, typedef 可以用了, 證實是我想的那樣。不過不用管 typedef, 先把這些非內建型別換成 int 就好, 這就通過 c 語法檢查了。

之前的 simple_compiler 我有一點沒有做好, 型別紀錄, 就是符號表 (symbol table), 每個符號有其屬性, 這邊我沒有特別處理, 舉例來說 str="xyz";, "xyz" type 是 const char*, str type 也要是 const char *, 所以做 assign (=) 是一個合法的 statement, 如果沒有紀錄 type, 就無法判定是不是正確的 assign。另外還有 scope 的問題, str 這時候是在合法的 scope 嗎?

{
  {
    const char *str;
  }
  str = "abc";
}

像這樣就不合法了。

型別的另外一個難點是怎麼用程式碼紀錄這些型別, 我想不到一個好的辦法, 畢竟型別的組合是無限多種。

list 1 在處理 int xyz;, 開啟 debug mode, 可以觀察到僅僅是這麼簡單的宣告, 就執行了好多次的文法規則。

list 1 d.txt

 1 descent@debian64:hoc$ ./c -d 1
 2 enable bison debug mode
 3 Starting parse
 4 Entering state 0
 5 Reading a token: int
 6 Next token is token INT ()
 7 Shifting token INT ()
 8 Entering state 9
 9 Reducing stack by rule 95 (line 243):
10    $1 = token INT ()
11 int
12 cc INT
13 -> $$ = nterm type_specifier ()
14 Stack now 0
15 Entering state 24
16 Reading a token: 
17 xyz
18 Next token is token IDENTIFIER ()
19 Reducing stack by rule 79 (line 208):
20    $1 = nterm type_specifier ()
21 -> $$ = nterm declaration_specifiers ()
22 Stack now 0
23 Entering state 22
24 Next token is token IDENTIFIER ()
25 Shifting token IDENTIFIER ()
26 Entering state 32
27 Reducing stack by rule 132 (line 327):
28    $1 = token IDENTIFIER ()
29 xyz
30 dd IDENTIFIER: xyz, type_data.storage_class_: (null), type_data.type_specifier_: 291
31 -> $$ = nterm direct_declarator ()
32 Stack now 0 22
33 Entering state 39
34 Reading a token: 
35 ;
36 Next token is token ';' ()
37 Reducing stack by rule 131 (line 323):
38    $1 = nterm direct_declarator ()
39 -> $$ = nterm declarator ()
40 Stack now 0 22
41 Entering state 38
42 Next token is token ';' ()
43 Reducing stack by rule 85 (line 223):
44    $1 = nterm declarator ()
45 -> $$ = nterm init_declarator ()
46 Stack now 0 22
47 Entering state 37
48 Reducing stack by rule 83 (line 218):
49    $1 = nterm init_declarator ()
50 -> $$ = nterm init_declarator_list ()
51 Stack now 0 22
52 Entering state 36
53 Next token is token ';' ()
54 Shifting token ';' ()
55 Entering state 55
56 Reducing stack by rule 76 (line 202):
57    $1 = nterm declaration_specifiers ()
58    $2 = nterm init_declarator_list ()
59    $3 = token ';' ()
60 -> $$ = nterm declaration ()
61 Stack now 0
62 Entering state 21
63 Reading a token: ;

source code:

• https://bitbucket.org/dsung/hoc/src/master/c.l
• https://bitbucket.org/dsung/hoc/src/master/c.y