Yukang's Page

lcc阅读记录

2014-09-14

之前看EOPL感觉收获挺大,最近又花业余时间看了看编译相关的东西,这是我看lcc的时候顺手记下的一些自己的理解。这本书《A Retargetable C Compiler》还挺大头的。lcc代码量不是特别大,更复杂的是tinyCC,tinyCC甚至可以直接运行C代码。

alloc.c

为了尽量的少调用系统调用,在alloc基础上封装了一下。

sym.c

用来存储symbol,注意scope的表示方法。

input.c

为了减少读取文件的开销,用一个buffer来缓存源文件内容。cp表示当前读取出来的字符位置,limit表示缓存的结尾字符位置,如果fillbuf一次以后仍然cp == limit则表示读取文件到EOF了。

注意这里的fread读取的时候是通过stdin的,但是在main.c/main_init函数的时候通过freopen将源文件重定向到了stdin。

fillbuf其实读取的时候是永远先把内容读取到buffer[MAXLINE+1]的位置,如果发现cp < limit就把前面剩下的内容往前移动,这样永远保证buffer足够下一次预读取,这里有点巧妙。

比较复杂的部分是处理resynch,input处理的内容是经过C语言预处理器的,这部分没有包含在这个编译器内。

lex.c

一个完全是手写的C语言Parser,虽然只是兼容C99,但手写还是比较复杂的。码农约架比写Parser是个体现实力的比赛。

getchr逐个字符读取,cp就是input.c里面的当前字符。跳过BLANK,如果碰到NEWLINE则调用input.c读取下一行。

token.h看起来有很多列,这个文件被多个地方用到。是用宏来生成一些Enum里面的代码。比如token type和expr type。

gettok顾名思义在lex运行的时候不断提供一个一个的token,这主要是通过cp匹配map来判断,条件分支很多(依据当前的第一个字符)。register unsigned char* rpc存储当前字符。register作为一个对编译器的提示,尽量用register来存储变量。事实上现在的编译器很多都能做auto register allocation,有的时候编译器的选择可能比人的选择更好。register在老的C代码里面可能更为常见。

这个函数里面很多地方都用到了goto,主要是在匹配关键字的时候区分identifier。主要几大类是: number, keyword, identifier, string。 icon处理数字的前缀,fcon处理浮点数。

Lexical analyzer基本理论是自动状态机,没一个token可以根据相应的正则表达式来表示。有一些工具可以用来自动生成这些繁琐的代码,比如LEX,更新一些的有Flex和re2c。

error.c

终于来到Parser部分了,lcc使用的是recursive-descent,很多商业的编译器都是用的这种直观的算法,事实上对于大部分语言都足够了。recursive-descent是自上而下的递归的,依据当前的token匹配语法结构。一个重要的问题是如何在处理的过程中给出适当的错误信息。error.c里面的函数test和expect用来测试下一个token是否是预期的,expect可以打印出错误信息。

tree.c

最重要的数据结构struct tree,AST中的基本节点,包含子节点,和operator类型(比如AND,OR,NOT等)。在构建AST的时候root函数经常被用到。

expr.c enode.c

parser的一部分,用来识别表达式。代码好复杂,和paresr有些类似,整个过程是构建AST。编译器的前端最重要的事情就是这了,后面的操作都是在这个基础上做的。为什么Scheme/Lisp的front部分比较简单,因为这货代码就和AST有些类似了,括号把一个一个的节点组合了起来。初看起来很难看,其实习惯了还好。

上面说的是语法的识别,在构建AST的过程中另外一个事情就是语意的分析。包括类型检查,类型的转换,操作符优先级等,这些也在构建AST的时候顺便做了。比如在遇到expr1 ? expr2 : expr3的时候,expr1的值最后被cast成一个bool。指针之间的隐式转换也比较复杂。function call比较复杂,这里还做了函数参数的写法是否是老的风格,类型说明放在函数头的最后。assignments和binary operator的分析相对来说简单一些,需要做各种cast。

前些天稍微看了一些Erlang,发现里面的类型推导比较好玩,甚至可以发现一些代码里面的逻辑错误:

比如:

fact(0) -> 1;
fact(N) -> N * fact(N-1).
test() -> fact(-5).

不用运行Erlang的dialyzer就可以发现这里面的死循环,因为可以通过上面的定义推断出fact的参数是non_neg_integer,而-5是不符合的,所以报出来一个错误:

fact(-5) will never return

stmt.c

codelist为双向列表,遇到新的执行块就加到这个列表上。在处理control-flow的过程中有的死代码块是可以被编译器发现的,只是我们平时都被忽略了。

比如C代码:

int loop() {
Loop:
goto Loop;
return -1;
}
int main() {
printf("loop: %d\n", loop());
return 0;
}

loop永远不会返回,Gcc选项-Wsuggest-attribute=noreturn可以报出一个warning。

decl.c

声明是C语言中最难解析的部分,原因是声明涉及到变量和类型,而从C声明中弄出类型信息还是挺复杂的。另外声明还分局部,全局,其中还涉及到函数参数,结构体等。decl.c可能是最复杂的文件了,1100多行代码,里面的函数之间又相互调用。finalize()函数最后检查是否有重复定义的变量。

dag.c

lcc的intermediate code是用listnodes把前面parser的tree转换为DAG,最终整个程序会经过转换变成由多个DAG组合成的森林。listnodes还负责把一些公共的sub-expression简化。

接口为gencode,emitcode。后面每一个代码生成的后端都是一个Interface结构,在function函数里面调用这两个函数生成汇编代码,其中还包含一个Xinterface成员,这是平台相关的接口。

小结

到现在我只是大概看了了前端和中间层,后面lcc跨平台的指令生成还没来得及研究,这本书的电子版不是很清晰,还是买个中文版来再稍微看看。总的来说,lcc是的Parsing和语义分析是同时进行的,就是所谓的one-pass方法。现在很多编译器所用的方法是先建立AST,后面可能要多次遍历整个AST进行分析,LLVM好像就是采用的这种方案。另外代码的优化是一个trade-off,作为教学用途的lcc没有过多做代码优化,这样lcc代码还是可以花不多的时间来一个大概的学习。

使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章