Rebornix

编译原理实验从这周开始了,实现一个类C的编译器。第一步进行词法和语法分析,用到的工具是大家耳熟能详的“lex与yacc”(某次在图书馆看到这本动物书时非常好奇,翻开后发现自己一点都看不懂,不知道这个是干嘛的)。实践时使用的是它们的GNU版本,Flex和Bison。

除了《lex与yacc》这本神书以外,网上还是有很多不错的资源的。“Flex与Bison”可以轻松寻到,不过是英文的。IBM的developWorks上的资料对于快速入门和掌握基本知识是够了的。这里先给出references,权做抛砖引玉,朋友们有好的资源还望留言告知。至于对lex和yacc的个人理解,还有待我实验之后再来扯扯淡。

  • 快速入门:   这篇文章短小精悍,是我见到的最"快速"的入门。
  • 使用 yacc 和 lex 编写文本分析器:非常推荐这篇,全文一共八页,对工具作简短介绍后,从一个计算器开始,用实践的方式帮助理解lex和yacc是如何进行文本分析的。代码样例取的非常好,或许是因为够简单。

喜欢读原版的朋友也可以自行选择英文。而要理解文本分析本身,还是得看龙书。

--------------------------------------------------分割线---------------------------------------------------------

实验的第一部是词法分析。开始编写lex的程序时,最让我困扰的是缩进,一不小心就会出错。《lex & yacc》中有这么一段:“在%{ 和}%外部,lex中的注释必须用空白缩进来正确标示它们。忘记缩进注释,lex会将它们解释为别的东西”。除了注释,几乎每个字符都要小心的注意缩进。

比如,lex第一部分时定义部分,“%{”和“%}”括起C代码,这些代码直接拷贝到之后生成的C文件中。如果我在“%{”前加一个空格,Vim的高亮就立马告诉我不可以:

但是删去空格后,一切恢复了正常:

上图是正确的代码,可以正确的跑起来。那么,来看看下面的这个,差别只有一个空格,但是高亮依旧以迅雷不及掩耳盗铃儿响叮当之势告诉你:“干嘛,都说了不可以!”

--------------------------------------------------分割线---------------------------------------------------------

对于整个词法分析和语法分析来说,用lex实现一个词法分析器难度是比较小的。如果不那么追究细节,几乎可以无bug地写完一个词法分析器。你需要的只是定义好的token。

之后就是开始实现语法分析了,我们使用的工具是GNU Bison(yacc的GNU版本)。在Bison中,对语法进行归约的方式是自底向上的。C++貌似已经不用yacc来实现语法分析了,因为它对错误的恢复支持较弱,C++编译器的开发者更愿意自己手写实现自顶向下的归约方式。

我们依然选择yacc(Bison),主要是它可以给我们减轻很多的代码和设计压力,另一方面,yacc实现的语法分析和错误恢复已经足以支持我们的C-- 语言。对于没有仔细研究龙书的朋友,下面的前两个链接是很不错的,前者是Bison的手册,后者是对yacc理论的通俗解释,原作者不祥。

  • Bison Manual
  • yacc理论
  • 而对于想要自己真正实现一个编译器,且需要最专业的指导,可以参考我们的实验网站 (Click Here)。如需要课程指导、课件等,可以留言与我联系。

yacc中使用的是自底向上的归约方法。在归约的过程中,我们需要维护一个输入缓冲区和一个栈用于存储文法符号。归约时主要分析技术为:

  • 移入:将下个输入符号移动到栈顶
  • 归约:将句柄归约为相应的非终结符号
  • 句柄总是在栈顶
  • 具体操作时弹出句柄,压入被归约到的非终结符号
  • 接受:宣布分析过程成功完成
  • 报错:发现语法错误,调用错误恢复子程序

比如这个归约式: FunDec : ID  LP RP;   栈顶分别存着句柄 ID、LP、RP,归约的过程则是将它们退栈并将FunDec这个结非终符压栈。在yacc中,使用$$代表归约式的非终结符,即FunDec,使用$1,$2,$3等表示归约式的句柄。我们将其类型设置为struct TreeNode 则可以构造一个语法树。

但是在这里,我开始遇上经典的“段错误”。第一次发生bug是因为我把归约时的两个栈给忘了。对每个归约式都实现$$指向$1。但是进行深度遍历时,无论从哪个节点开始,都只能下降一层。面对这个bug,只需将栈考虑进去,当$1被退出栈后,它的生命期也就结束了,但是$$中用于指向$1的地址没有变,它仍然指向原来$1所在的栈的位置,无论如何更替,这个地址都不会变,错误也就不可避免。

出现“段错误” ,多是指针指向了未初始化或者该指针成为了悬浮指针。而这类错误是难以寻觅的。比如我发现错误的地方:

如果我写了这样的if-else结构,输出结果为“sibling: 0x.....”,觉得nextSibling的地址不为0.

Compiler segfault

但当我将else语句注释掉,本应该什么都不输出,但是居然输出了“sibling == NULL”。瞬间感觉自己回到了去年写操作系统的时候,一句printf都可以导致操作系统无法正常地运行。但尼玛,这可是直接操作硬件的阿!只因为我们使用了指针。

Compiler segfault2

这是多么让人蛋疼菊紧的事情阿。除了这一处错误,还有各种“段错误”在最近几天搔扰我,无论是linux进程树输出、数独还是语法分析。过几天对这些段错误做一个总结,并对debug的方法做一些深究。



blog comments powered by Disqus

Published

29 February 2012

Tags