编译原理完整版.docVIP

《编译原理》试题A卷

简答

1．编译程序分为哪几个主要部分？简述各部分的主要功能。

答：编译程序分五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成?

词法分析：输入源程序，对构成源程序的字符串进行扫描和识别。识别出一个个单词，并识别出与其相关的属性,再转换成长度统一的标准形式,以供其他部分使用.?

语法分析:在词法分析的基础上,根据语言的语法规则,把单词符号串分解成各类语法单位(语法范畴),如“短语”,“子句”,“句子”(“语句”),“程序段”和“程序”等.通过语法分析,确定整个输入串是否构成语法上正确的“程序”.?语义分析与中间代码产生:对语法分析所识别出得各类语法范畴,分析其含义,并进行初步翻译(产生中间代码).这一阶段通常包括两个方面的工作:首先对每种语法范畴进行静态语义检查.正确则进行另一方面工作,中间代码的翻译.?优化:对前段产生的中间代码进行加工变换,以期在最后阶段能产生更为高效(省时间和空间)的目标代码.?目标代码生成:把中间代码(或经优化处理之后)变换成特定机器上的低级语言代码.?

2．解释算符优先分析算法。

算符优先文法是一种自下而上的分析方法，其文法的特点是文法的产生式中不含两个相邻的非终结符。自上而下的分析方法，通常要求文法的产生式不含左递归，如LL(I)文法就是一种可以自上而下分析的文法。

定义：

假定G是不含ε-产生式的算符文法。对于任何一对终结符a、b，我们说：

（1）a等于b当且仅当文法G中含有形如P→···ab···或P→···aQb···的产生式；

（2）a小于b当且仅当G中含有形如P→···aR···的产生式，而R(+=)b···或R(+=)Qb···；

（3）a大于b当且仅当G中含有形如P→···Rb···的产生式，而R(+=)···a或R(+=)···aQ；

如果一个算符文法G中的任何终结符对（a,b）最多满足下述三个条件之一：

a=b,ab,ab

则称G是一个算符优先文法。

3．什么是L属性定义？

如果每个产生式A?X1X2…Xn的每条语义规则计算的属性是A的综合属性；或者是Xj的继承属性，1￡j￡n,但它仅依赖：该产生式中Xj左边符号X1,X2,…,Xj-1的属性；A的继承属性。S属性定义属于L属性定义。变量类型声明的语法制导定义是一个L属性定义

4．对中间代码优化时常用哪几种手段？

优化技术概述：优化实质上是对代码进行等价变换，变换后代码结构不同但运行结果相同。?

优化分为两大类：1、与机器无的优化独立于机器的（中间）代码优化。（1）局部优化:（一个入口，一个出口，线性）——基本块。方法：常数合并，冗余子表达式的削除等。（2）循环优化：对循环语句所生成的中间代码序列上所进行的优化。方法：循环展开，频度削弱（循环不变表达式的外提），强度削弱。全局优化：顾名思义，跨越多个基本块的全局范围内的优化。因此它是在非线性程序段上（包括多个基本块,GOTO循环）的优化。2、与机器无的优化目标代码上的优化（与具体机器有关）。

5．L（G）={ancibn︱n，i≥1}，试求上下文无关文法G。

二．证明下面文法消除左递归后是LL（1）文法。

A→A+B︱B

B→B*C︱C

C→(A)︱i

三．构造下列正规式相应的最简DFA

（a︱b）*（aa︱bb）（a︱b）*

四．用语法制导翻译的思想，把下面的语句翻译成三地址码序列。

Whilea＜bandc＜ddo

Ifa＜1orc＜5thenc=c+1

elsec=c+2

《编译原理》试题B卷

简答

1.编译程序分为哪几个主要部分？简述各部分的主要功能。

答：编译程序分五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成?

词法分析：输入源程序，对构成源程序的字符串进行扫描和识别。识别出一个个单词，并识别出与其相关的属性,再转换成长度统一的标准形式,以供其他部分使用.?

语法分析:在词法分析的基础上,根据语言的语法规则,把单词符号串分解成各类语法单位(语法范畴),如“短语”,“子句”,“句子”(“语句”),“程序段”和“程序”等.通过语法分析,确定整个输入串是否构成语法上正确的“程序”.?语义分析与中间代码产生:对语法分析所识别出得各类语法范畴,分析其含义,并进行初步翻译(产生中间代码).这一阶段通常包括两个方面的工作:首先对每种语法范畴进行静态语义检查.正确则进行另一方面工作,中间代码的翻译.?优化:对前段产生的中间代码进行加工变换,以期在最后阶段能产生更为高效(省时间和空间)的目标代码.?目标代码生成:把中间代码(或经优化处理之后)变换成特定机器上的低