2016年4月26日 星期二

幾本編譯器書籍

20140823 購於高雄若水堂 266nt
在編譯原理的討論上都會提到 compile 的過程會建立一棵 ast (Abstract syntax tree), 可是在我看到的實作上卻很少有產生 ast 的資料結構。

而用 yacc 產生的 ast 你又知道要如何操作它嗎? 所以還是自己產生好了, 自己寫的自然知道怎麼操作這棵 ast。

原來 ast 並不是必須的, 請參考: 《符号表和抽象语法树是什么关系? 两者在编译器设计中是否必需?》

ast 的妙用: AST - 像lisp一样自定义代码行为

而這本《两周自制脚本语言》實作的 parser 就會產生一棵 ast, 這是我比較有興趣的實作方式。

本書雖然說是用兩周的時間來學習, 但實際上需要的時間絕對是超過兩周的, 把它想成總共大概要 14 個章節來介紹會適合點。

可惜本書是用 java 來實作這個腳本語言, 我對 java 非常不熟, 連要編譯書中的範例程式都讓我大傷腦筋, 臨時惡補了一些 java 的知識。

我一直以為我會用《自己动手写编译器、链接器》來學習 compiler, 《自己动手写编译器、链接器》有建立符號表, 不過目前是《两周自制脚本语言》幫了我最大的忙。讓我得以突破 lexer, parser, ast 的困難。

目录

第1部分 　基础篇
第1天 来，我们一起做些什么吧　　1
1.1 机器语言与汇编语言　　2
1.2 解释器与编译器　　3
1.3 开发语言处理器　　5
1.4 语言处理器的结构与本书的框架　　6
第2天 设计程序设计语言　　10
2.1 麻雀虽小、五脏俱全的程序设计语言　　11
2.2 句尾的分号　　12
2.3 含糊不得的语言　　14
第3天 分割单词　　17
3.1 Token对象　　18
3.2 通过正则表达式定义单词　　19
3.3 借助java.util.regex设计词法分析器　　22
3.4 词法分析器试运行　　27
第4天 用于表示程序的对象　　30
4.1 抽象语法树的定义　　31
4.2 设计节点类　　34
4.3 BNF　　38
4.4 语法分析与抽象语法树　　42
第5天 设计语法分析器　　44
5.1 Stone语言的语法　　45
5.2 使用解析器与组合子　　46
5.3 由语法分析器生成的抽象语法树　　53
5.4 测试语法分析器　　59
第6天 通过解释器执行程序　　62
6.1 eval方法与环境对象　　63
6.2 各种类型的eval方法　　65
6.3 关于GluonJ　　69
6.4 执行程序　　72
第7天 添加函数功能　　75
7.1 扩充语法规则　　76
7.2 作用域与生存周期　　81
7.3 执行函数　　83
7.4 计算斐波那契数　　89
7.5 为闭包提供支持　　90
7.6 实现闭包　　92
第8天 关联Java语言　　95
8.1 原生函数　　96
8.2 编写使用原生函数的程序　　98
第9天 设计面向对象语言　　101
9.1 设计用于操作类与对象的语法　　102
9.2 实现类所需的语法规则　　103
9.3 实现eval方法　　104
9.4 通过闭包表示对象　　110
9.5 运行包含类的程序　　114
第10天 无法割舍的数组　　115
10.1 扩展语法分析器　　116
10.2 仅通过修改器来实现数组　　119


第2部分 　性能优化篇
第11天 优化变量读写性能　　123
11.1 通过简单数组来实现环境　　124
11.2 用于记录全局变量的环境　　127
11.3 事先确定变量值的存放位置　　130
11.4 修正eval方法并最终完成性能优化　　134
第12天 优化对象操作性能　　137
12.1 减少内存占用　　138
12.2 能否通过事先查找变量的保存位置来优化性能　　141
12.3 定义lookup方法　　144
12.4 整合所有修改并执行　　147
12.5 内联缓存　　152
第13天 设计中间代码解释器　　156
13.1 中间代码与机器语言　　157
13.2 Stone虚拟机　　158
13.3 通过栈实现环境　　167
13.4 寄存器的使用　　170
13.5 引用变量的值　　173
13.6 if语句与while语句　　173
13.7 函数的定义与调用　　175
13.8 转换为虚拟机器语言　　177
13.9 通过虚拟机执行　　184
第14天 为Stone语言添加静态类型支持以优化性能　　187
14.1 指定变量类型　　188
14.2 通过数据类型检查发现错误　　193
14.3 运行程序时执行类型检查　　204
14.4 对类型省略的变量进行类型推论　　208
14.5 Java二进制代码转换　　214
14.6 综合所有修改再次运行程序　　226
第3部分 　解说篇（自习时间）
第15天 手工设计词法分析器 229
15.1 修改自动机　　230
15.2 自动机程序　　233
15.3 正则表达式的极限　　235
第16天 语法分析方式　　236
16.1 正则表达式与BNF　　237
16.2 语法分析算法　　238
16.3 LL语法分析　　239
16.4 算符优先分析法与自底向上语法分析　　244
第17天 Parser库的内部结构　　251
17.1 组合子分析　　252
17.2 解析器组合子的内部　　252
第18天 GluonJ的使用方法　　263
18.1 设定类路径　　264
18.2 启动设定　　265
18.3 GluonJ语言　　267
18.4 功能总结　　268
第19天 抽象语法树与设计模式　　271
19.1 理想的设计　　272
19.2 Interpreter模式　　273
19.3 Visitor模式　　276
19.4 使用反射　　282
19.5 面向切面语言　　284

chapter 3 做了一個 lexer, 使用了 regular expression 的 library 來實作。而 chapter 15 會說明如何手工打造 lexer。

chapter 5 實作出產生 ast 的 parser。可惜我還是不知道那棵 ast 長什麼樣。這章並沒有提到實作細節, 而是解說 parser library 的使用方式, 這其實等於沒解釋怎麼寫出 parser, parser library 的原理則是 chapter 17 才說明, 使用的是一種 combinator 的作法, 我就沒特別研究了。我最後沒能看懂程式, 而是參考 chapter 16 的作法。

一般談到 ast 都會有類似 fig 1 的圖, 表示 13 + x * 2,

fig 1

不過若是 

if (x>1)
  1+2;
else
  5*3;

的 ast 應該長的怎麼樣呢? 我相信應該難倒你了。

長的像 fig 2 這樣。

fig 2

如果 if/else 難不倒你, 那 function declare 的 ast 應該長怎麼樣呢? 我不信還難不倒你。list 1 是我的表示方法, 我也不知道是不是對的。

list 1 - function declare AST
descent@debian64:simple_compiler$ cat f1 
int i,j;

int func(int x)
{
  char a,b;
}
descent@debian64:simple_compiler$ ./c_parser < f1| ~/git/progs/tree/tree/tree 
token: int
token: i
token: ,
token: j
token: ;
token: int
token: func
token: (
token: int
token: x
token: )
token: {
token: char
token: a
token: ,
token: b
token: ;
token: }
     root
      |
     prog
 _____|_____
 |         |
var       func
_|__   ____|_____
|  |   |        |
i  j  para  func_body
       |        |
       x       var
               _|__
               |  |
               a  b

有了 ast 之後該怎麼辦呢?

chapter 6 則是實作 eval 來對那棵 ast 求值。

讓每個 node 執行 eval(), 求出每個 node 該有的值就可以了, if node 則是在 eval() predicate 後, 選擇 then node, 或是 else node 來 eval(), 層層下去後, 就可以計算出這個 expression 了。while node 也是一樣的道理。

這章用到了 gluonj, 對於一本教學書來說, 這無疑是大大的進入門檻, 我要學的是 compiler 技術, 你卻導入了很多 java 的額外特殊功能, 我要看懂這些程式碼, 還需要去看這些東西, 大大增加了學習曲線。我覺得這不是很好的教學方式。對於不懂 java 的人來說, 額外負擔太大了。我花了點時間終於編譯出使用 gluonj 的 java 程式。又花了一點時間才知道怎麼執行。

這裡有個困難點是《環境》, 就是 sicp 4.1 講的東西, 這是變數名稱和變數直對應的東西, 由於我已經在 sicp 4.1 痛苦過了, 這部份就沒覺得那麼難了。用 std::map 來搞定《環境》吧!

最後發現 chapter 18 就談到這些東西了, 害我花了大量時間找資料, 應該要寫在同一章的。 

javac -cp .:../gluonj.jar chap6/BasicEvaluator.java
javac -cp .:../gluonj.jar chap6/BasicInterpreter.java
javac   chap6/BasicEnv.java
javac -cp .:../gluonj.jar chap6/Runner.java

執行: 

java -cp .:../gluonj.jar chap6.Runner
ref:

chapter 15 講解了自動機程式, 手工寫出 lexer, 不像 chapter 3 那樣使用 regular library 那麼好寫, 但我很容易就可以看著 fig3 就寫出程式, 這是寫出 lexer 的方法之一, 很好用, lexer 雖然沒有 parser 那麼難寫, 但也不是那麼容易, 我覺得是很有趣的程式。

lexer.cpp L38 就是實作 fig 3 的 lexer。

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。

chapter 16 手工打造 parser, 不是使用原本的 combinator 作法, 使用 recursive descent 來做示範, 這是我最想知道的作法, recursive descent 是由上到下的作法, 以下面的 BNF 來說 

expression: term {("+" | "-") term}
term: factor { ("*" | "/") factor}
factor: NUMBER | "(" expression ")"

就是從 expression 開始往 factor 去 match。由 factor 去對應到 expression 就是由下到上, yacc 產生的 parser 就是這樣的行為。

對照其 java code, 我打造了 c++ 的版本: https://github.com/descent/progs/tree/master/compiler 已經可以建立 ast, 並轉出 post order, in order, prefix order。那個範例程式雖小, 卻幫了我很大的忙, 讓我得以突破 parser 的困難點。

ret 
 1 inorder to postorder
 2 descent@debian64:compiler$ ./parser
 3 2*(3+1)
 4 token: 2
 5 token: *
 6 token: (
 7 token: 3
 8 token: +
 9 token: 1
10 token: )
11 ast node type: MUL
12 ( 2 ( 3 1 + )* )
13
14
15 inorder to prefix order
16 descent@debian64:compiler$ ./parser
17 2*(3+1)
18 token: 2
19 token: *
20 token: (
21 token: 3
22 token: +
23 token: 1
24 token: )
25 ast node type: MUL
26 ( * 2 ( + 3 1 ))

operator precedence parsing 是運算符號的優先順序處理方法, 一般都是使用 BNF 規則來定義運算符號的優先順序, 不過每增加一個規則, 程式就要重寫, 有點麻煩, 所以才有了這個方法, 我喜歡這個作法, 可以省下不少 bnf rule, 這對於手工撰寫程式的我來說, 可以省下撰寫大量的 bnf function, 所以我努力的把它看懂, 事實上也不算是太難。

expr 可以省略到這樣。

expr : factor {OP factor}

加入新的運算符號只要這麼做就好, 左結合或是右結合都沒問題。

operators.insert({"=", new Precedence{1, false}});
operators.insert({"==", new Precedence{2, true}});
operators.insert({">", new Precedence{2, false}});
operators.insert({"<", new Precedence{2, false}});
operators.insert({"+", new Precedence{3, true}});
operators.insert({"*", new Precedence{4, true}});

我其實沒有看懂 java 建立 ast 的程式碼, 看懂觀念後, 靠著這章的 java 範例實作。

辛苦了很久, 目前到 if/else 階段, 這個有點問題, 更新如下 if_ast

if/else ast

 
 1 if (x>2)
 2 {
 3 1+2*3;
 4 }
 5 else
 6 {
 7 7*8;
 8 }
 9 
10 if (y>2)
11 {
12 (1+2)*3;
13 }
14 else
15 {
16 7*(8+2);
17 }
18 
19 
20                root
21        _________|_________
22        |                 |
23        if                if
24  ______|______     ______|______
25  |     |     |     |     |     |
26  >     +     *     >     *     *
27 _|__  _|__  _|__  _|__  _|__  _|__
28 |  |  |  |  |  |  |  |  |  |  |  |
29 x  2  1  *  7  8  y  2  +  3  7  +
30         _|__           _|__     _|__
31         |  |           |  |     |  |
32         2  3           1  2     8  2

以下是修改後的版本:

if_ast
descent@debian64:compiler$ cat if3 

if (x>2)
{
1+2*3;
(11+9)*5
}
else
{
7*8;
13+9*5
}

if (y>2)
{
(1+2)*3;
}
else
{
7*(8+2);
}

descent@debian64:compiler$ ./parser < if3 |/home/descent/git/progs/tree/tree/tree
                               root
               _________________|_________________
               |                                 |
               if                                if
 ______________|______________       ____________|____________
 |             |             |       |           |           |
 >         then_block    else_block  >       then_block  else_block
_|__      _____|_____     ___|____  _|__         |           |
|  |      |         |     |      |  |  |         *           *
x  2      +         *     *      +  y  2        _|__        _|__
         _|__      _|__  _|__  __|__            |  |        |  |
         |  |      |  |  |  |  |   |            +  3        7  +
         1  *      +  5  7  8  13  *           _|__           _|__
           _|__  __|__            _|__         |  |           |  |
           |  |  |   |            |  |         1  2           8  2
           2  3  11  9            9  5

chapter 13 則是將原本的 interpreter 轉成 vm 的 machine code, 所以還會介紹如何實作一個 vm, 這裡才真的有「編譯」的動作。

不過我打算使用《實作一個簡單的 virtual machine》這個 vm, 這個簡單不少。

chapter 15/16 我認為才是這本書的重點, 我從這兩章的內容終於知道怎麼把 ast 建立出來。

書中範例: http://www.csg.ci.i.u-tokyo.ac.jp/~chiba/files/


20140818 購於台南若水堂 356nt
這本書是用 c 來完成兩個程式語言, 分別是: diksam, crowbar, 一本書完成兩個語言, 真酷, 不過在我告訴你他是用 flex, yacc 後你應該就不會這麼想了。

「阿! 原來用了 flex, yacc, 可是我想自己完成這兩部份阿!」我也是這麼想的。不過書中其他主題也很有趣, 也是有參考價值。

yacc 是 yat another compiler compiler, 不過他只完成了 parser, 這只是 compiler 的某個部份而已, 卻自稱自己是 compiler, 口氣未免太大了。

chapter 2 不可免俗的提到計算機, 提供用了 flex/yacc 和不用 flex/yacc 的作法, 2.4 提到了 ll(1), lalr(1) 的少許理論, 對我而言算是受用。

chapter 5 日文原文書本來是講解日文編碼, 不過譯者把他改成中文編碼了, 當然簡體中文不是繁體中文, 立意雖好, 不過我還是想看看日文編碼的相關知識。

ref:

fig 21
fig 22
fig 23
fig 24
fig 25 C编译器剖析
fig 26 自制编译器
fig 27 自己动手构造编译系统：编译、汇编与链接
fig 28
fig 29

fig 30
官網: http://www.ituring.com.cn/book/1308

編譯其 java code 需要安裝:

  • javacc
  • jdk
  • ant

我在編譯 java code 就吃了不少苦頭,


ucc
https://github.com/descent/ucc-code

我做了些修改, 可以在 linux/x86 32 bit 環境編譯
/usr/local/lib/ucc/ucc -o h h.c

cit
https://github.com/fanzhidongyzby/cit
張貼者： descent 於 4/26/2016 06:20:00 下午
標籤： ,

沒有留言:

張貼留言

使用 google 的 reCAPTCHA 驗證碼, 總算可以輕鬆留言了。

我實在受不了 spam 了, 又不想讓大家的眼睛花掉, 只好放棄匿名留言。這是沒辦法中的辦法了。留言的朋友需要有 google 帳號。

訂閱： 張貼留言 (Atom)