loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

[总结]中间/目标代码生成

语法制导翻译、中间代码生成、目标代码生成在很多时候并不存在严格的划分。对于目标
代码是某个简单的虚拟机代码而言,中间代码完全可以就是目标代码。中间代码生成中结
合了语法制导翻译,讲述了大部分常规的编程语言结构是怎样被翻译成一种接近目标代码
的形式(所谓的中间代码形式)。本身,汇编代码就是对应于机器码的一种字符表示形式,
而中间代码的大部分表示形式--三地址码,也是一种接近汇编代码的形式。

简单来说,词法分析阶段将字符整理为单词;语法分析则将这些代码整理为一种层次结构
(识别了程序代码要表达的意思);那么,在接下来的阶段里,则是将这些层次结构翻译
为线性结构。也就是类似于汇编代码这种格式。这种格式容易被机器识别:机器只需要顺
序地一条一条地取指令并执行之即可。这种简单直接性也使得要实现类似的虚拟机变得容
易。

翻译过程并不需要先生成语法树,在语法分析阶段的语法识别过程中,即可以对应地翻译。
因为无论是自顶向下还是自底向上的语法分析,都可以先去识别叶子节点。在自顶向下中,
可以使用语法树(并不真实存在)的后续遍历,使得叶子节点先于父节点翻译;而在自底
向上的分析中,因为其本身就是先识别叶子节点(所谓的规约),所以可以更自然地翻译。

因为我也是想实践下这些东西,所以还是使用lex/yacc来进行练习,省得自己去写词法和
语法分析。不过在使用yacc的过程中,经常会出现一些shift/reduce conflicts的警告/错
误,解决这些问题也费了不少时间。不过,也可能是我对LALR细节不熟悉,加之于文法本
身写的有问题,才弄得如此折腾。现在我觉得上下文无关文法在整个编译原理理论中非常
重要。一个好的文法可以准确无误地描述一种编程语言的语法,还可以指导编译器的开发。
当然,大部分常规的语言都可以找到现成的文法。

例子程序构造了一个简单的翻译程序,支持简单的算术表达式、整数变量、if、while、以
及仅用于if和while的逻辑表达式。为了省力,虚拟机用的是《编译原理与实践》中现成的。
目标代码也就直接是该虚拟机对应的代码。该虚拟机主要有5个寄存器:指令指针寄存器、
2个累加寄存器、全局变量基址寄存器、临时变量基址寄存器。这里的临时变量不同于编
程语言说的临时变量,它是表达式计算的临时值,例如a+b+c,a+b的结果值就可以被实现
为存储到一个临时值中。

对于算术表达式,其实翻译起来很简单。主要是if/while和逻辑表达式的翻译。逻辑表达
式的翻译例子中我甚至没有处理短路代码:a && func(1)中如果已经计算出a为false了,
就没必要计算func(1)了。这可能是受限于yacc,暂不深究。对于if和while,则主要涉及
到所谓的“回填”技术。

回填主要是应对向前跳转这种问题。例如在if的代码生成中,需要测试if的逻辑表达式的
真假,如果为假,则需要跳转到then-part之后。这里的then-part也就是if为真时要执行
的代码序列。而这个跳转指令具体要跳到哪里,则需要在生成完then-part之后才能确定。
回填的解决方法,就是预留下这个跳转指令的位置,等到then-part生成完了,得到了具
体的跳转位置,再回去填写那个跳转指令。

在这个问题上,yacc也让我折腾了一番。在if文法中:

selection_statement
: IF '(' logical_or_expr ')' {
  // 本来想在这里预留这个跳转指令的位置
} statement %prec IFX {
   }

结果,yacc又给我conflicts和never reduced之类的警告,并且最终生成的代码也不正常
(果然是无法忽略的警告)。看起来,yacc似乎不支持在文法内部添加action。通过一个
空文法符号效果一样。对于这个问题,我甚至莫名其妙地在某个晚上的梦里当面问了yacc
的作者。他肯定地告诉我:支持,当然支持(中文)。今天仔细地在yacc文档里找了下,
还真支持。而且对于空符号的使用,似乎也有些规则:$Sign: {action }。

后来解决这个问题的方法,算是我取巧了:
selection_statement
: IF '(' logical_or_expr IfBracket statement %prec IFX { ....}
IfBracket
: ')' {
     // 邪恶地利用了这个括号
   }
另外,因为需要支持嵌套的if/while,还专门使用了一个栈,用于保存这些需要回填的预留地址。

 

下载例子

posted on 2010-04-09 20:22 Kevin Lynx 阅读(7090) 评论(2)  编辑 收藏 引用 所属分类: 编译原理

评论

# re: [总结]中间/目标代码生成 2010-04-10 13:37 陈梓瀚(vczh)

其实不会受限于yacc,你应该在yacc只导出语法树结构,剩下的在语法树里面做。  回复  更多评论   

# re: [总结]中间/目标代码生成 2010-04-10 17:04 Kevin Lynx

@陈梓瀚(vczh)
我当时想试试直接生成代码的感觉,因为看到lua就是这样做的。:D。所以就折腾了下自己。
PS,美帝不错吧。  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理