首页 » 技术分享 » 【软件分析学习笔记】4:中间表示(Intermediate Representation)

【软件分析学习笔记】4:中间表示(Intermediate Representation)

 

程序源码直接拿来给静态分析器做静态分析是不合适的,像编译一样也需要在程序的中间表示(IR)上进行分析,这样能让静态分析算法比较简洁、高效。IR也没有绝对的标准,这节课学习的是绝大多数静态分析器采取的IR。

1 编译的基本流程

1.1 词法分析

词法分析(Lexical Analysis)会去检查是否输入的源代码是若干合法单词的组合。词法分析器统称Scanner,运行时需要关键字的词典,以及用正则表达式描述的词法规则。

词法分析会为每个合法的单词生成Token

1.2 语法分析

语法分析(Syntax Analysis)会去检查这些Token的组合形式是否符合语法规则。语法分析器统称Parser,相应的描述语法规则的方式是上下文无关文法(Context-Free Grammer)。Context-Free Grammer的表达能力比Context-Sensitive Grammer弱,但是对几乎所有的编程语言而言,这样的表达能力就足够了,如果去使用后者反倒会更慢。

语法分析会生成抽象语法树(AST)

1.3 语义分析

语义分析(Semantic Analysis)会去检查语义是否合理。和自然语言的语义不同,对编译器而言,只具备检查简单的语义的功能,如类型检查器(Type Checker),相应的进行类型检查时描述规则的方法是Attribute Grammer

语义分析会生成Decorate AST

1.4 转换

如果编译器有编译优化的功能,那么就要通过转换器(Translator) 转换成中间表示(IR) 的形式,这里的中间表示IR通常指的都是三地址码形式(3-Address Form)

生成IR之前的部分是编译器前端,生成IR之后的部分是编译器后端。编译优化就是静态分析的一种应用,静态分析是在IR的基础上做的,所以是属于编译器后端。这也说明了,要做静态分析,就不得不走完编译器前端的部分才能拿到IR,接着再在IR的基础上做分析。

1.5 生成

为了能执行,要将上一步的中间表示,通过代码生成器(Code Generator) 生成机器码(Machine Code)

2 AST和三地址码的比较

如对于一段简单do-while循环的程序:

do {
	i = i + 1;
} while(a[i] < v);

2.1 AST

表示成AST是这样的:

转载自原文链接, 如需删除请联系管理员。

原文链接:【软件分析学习笔记】4:中间表示(Intermediate Representation),转载请注明来源!

0