编译原理阶段测试题

1、第一阶段测试卷考试科目:编译原理第1章至第4章（总分100分） 时间：90分钟 学习中心（教学点） 批次： 层次： 专业： 学号： 身份证号： 姓名： 得分： 一、 选择与填充（30）1. 一个正则语言只能对应( )？ A. 一个正则文法 B. 一个最小有限状态自动机C. 一个自然语言 D. 一个上下文有关文法2. 对于编译程序而言，输入数据是源程序，输出数据是_。3. 给出在字母表0,1上的“所有以00结尾的符号串的集合”的语言的正则表达式：_。4. 一个句型中最左的（ ）称为该句型的句柄。A. 简单短语 B. 短语 C. 非终结符号 D. 终结符号5. Micro语言只有三种语句：（ ）、

2、输入语句和输出语句。A. GOTO语句 B. 赋值语句 C. 条件语句 D.循环语句6. 描述高级语言语法的常用方法有_和BNF范式。二、给出与正规式R（ab）*（a|b*）ab等价的NFA。（16）三、简述 DFA 与 NFA 有何区别。（14）四、判断下列文法是否具有二义性：GP: PPaP|PbP|cP|Pe|f (18)五、对于下面的文法GZ，构造句子(i*i+i)*i的最左和最右推导及相应的语法树。（22） (1) Z:=E (2) E:=T+E (3) E:=T (4) T:=F*T (5) T:=F (6) F:=(E) (7) F:=i附：参考答案：一、 选择与填充（30）1.

3、一个正则语言只能对应( B )？ A. 一个正则文法 B. 一个最小有限状态自动机C. 一个自然语言 D. 一个上下文有关文法2.对于编译程序而言，输入数据是源程序，输出数据是_目标程序_。3. 给出在字母表0,1上的“所有以00结尾的符号串的集合”的语言的正则表达式：_(0|1)*00_。4. 一个句型中最左的（ A ）称为该句型的句柄。A. 简单短语 B. 短语 C. 非终结符号 D. 终结符号5. Micro语言只有三种语句：（ B ）、输入语句和输出语句。A.GOTO语句 B. 赋值语句 C.条件语句 D.循环语句6. 描述高级语言语法的常用方法有_语法图_和BNF范式。二、给出与正规

4、式R（ab）*（a|b*）ab等价的NFA。（16）三、简述 DFA 与 NFA 有何区别。（14）解：DFA与NFA的区别主要有两点：1是NFA可以若干个开始状态，而DFA仅只一个开始状态。 2是DFA的映象M是从K到K，而NFA的映象M是从K到K的子集， 即映象M将产生一个状态集合（可能为空集），而不是单个状态。四、判断下列文法是否具有二义性：GP: PPaP|PbP|cP|Pe|f (18)解： 因为文法存在句型fbfbf，此句型有两棵不同的语法树，所以文法具有二义性。五、对于下面的文法GZ，构造句子(i*i+i)*i的最左和最右推导及相应的语法树。（22） (1) Z:=E (2) E

5、:=T+E (3) E:=T (4) T:=F*T (5) T:=F (6) F:=(E) (7) F:=i解：最左：Z=E=T=F*T=(E)*T=(T+E)*T=(F*T+E)*T=(i*T+E)*T=(i*F+E)*T=(i*i+E)*T =(i*i+T)*T=(i*i+F)*T=(i*i+i)*T=(i*i+i)*F=(i*i+i)*i最右：Z=E=T=F*T=F*F=F*i=(E)*i=(T+E)*i=(T+T)*i=(T+F)*i=(T*i)*i=(F*T+i)*i =(F*F+i)*i=(F*i+i)*i=(i*i+i)*i第二阶段测试卷考试科目:编译原理第4章至第7章（总分10

6、0分） 时间：90分钟 学习中心（教学点） 批次： 层次： 专业： 学号： 身份证号： 姓名： 得分： 一、选择与填充（30）1.有限状态自动机能识别( )。A. 上下文无关文法 B. 上下文有关文法 C. 正则文法 D. 短语文法2在语法分析处理中， FIRST集合、 FOLLOW集合、 SELECT集合都是( )。A. 非终极符集 B终极符集 C字母表 D. 状态集3在自底向上的语法分析方法中，分析的关键是( )。A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 消除公共前缀4_是这样一种动作文法，即动作符只出现于产生式的末尾。5文法要满足两个条件：_和_才可以使用自顶向下的语法分析方

7、法。6. 文法GE: EE+T|T, TT*P|P, P(E)|I, 则句型P+T+i的短语有（ ）。A. i, P+T B. P, P+T, i, P+T+i C. P+T+i D. P, P+T, i 二、若有文法GS为： S-Ac|aB A-df B-be，请写出语言L(GS)的全部元素。（12）三、文法GS为： （18）SV VT | ViT TF| T+FF)V* |( 试给出句型ViFi( 的短语，简单(直接)短语,句柄。 四、写出表达式(ab*c)/(ab)d的逆波兰表示和三元式序列。（15）五、下面的文法是不是LL(1)文法？若是，请构造相应的LL(1)分析表。（25）S aD

8、 D STe | T bH | H H d | 附：参考答案：一、 选择与填充（30）1. 有限状态自动机能识别（ C ）A. 上下文无关文法 B. 上下文有关文法 C. 正则文法 D. 短语文法2在语法分析处理中， FIRST集合、 FOLLOW集合、 SELECT集合都是( B )。A. 非终极符集 B终极符集 C字母表 D. 状态集3在自底向上的语法分析方法中，分析的关键是( A )。A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 消除公共前缀4_尾动作文法_是这样一种动作文法，即动作符只出现于产生式的末尾。5文法要满足两个条件：_没有左递归_和_没有公共前缀_才可以使用自顶向下的

9、语法分析方法。6. 文法GE: EE+T|T, TT*P|P, P(E)|I, 则句型P+T+i的短语有（ B ）。A. i, P+T B. P, P+T, i, P+T+i C. P+T+i D. P, P+T, i二、若有文法GS为： S-Ac|aB A-df B-be，请写出语言L(GS)的全部元素。（12）解：因为S=Ac=dfc S=aB=abe 所以L(GS)=a b c d e f三、文法GS为： （18）SV VT | ViT TF| T+FF)V* |( 试给出句型ViFi( 的短语，简单(直接)短语,句柄。 解: 句型ViFi(的语法树如下: F是句型ViFi(相对于T的短

10、语、简单短语、句柄 （ 是句型ViFi(相对于F的短语、简单短语（ 是句型ViFi(相对于T的短语ViF是句型ViFi(相对于V的短语ViFi(是句型ViFi(相对于V的短语ViFi(是句型ViFi(相对于S的短语四、写出表达式(ab*c)/(ab)d的逆波兰表示和三元式序列。（15）解：逆波兰表示： abc*ab/d 三元式序列： (1) (*，b，c) (2) (，a，(1) (3) (，a，b) (4) (/，(2)，(3) (5) (，(4)，d)五、下面的文法是不是LL(1)文法？若是，请构造相应的LL(1)分析表。（25） S aD D STe | T bH | H H d | 解

11、: Predict(S aD)=first(aD)=aPredict(D STe)=first(STe)=aPredict(D )=follow(D)=#,b,d,ePredict(T bH)=first(bH)=bPredict(T H)=first(H)follow(T)=d,ePredict(H d)=first(d)=dPridict(H )=follow(H)=e所以该文法是LL(1)文法，LL(1)分析表如下表:aebd#S1D23333T545H76第三阶段测试卷考试科目:编译原理第8章至第10章（总分100分） 时间：90分钟 学习中心（教学点） 批次： 层次： 专业： 学号：

12、 身份证号： 姓名： 得分： 一、选择与填充（30）1. 四元式之间的联系是通过( )来实现的。 A指示器 B临时变量 C符号表 D程序变量2. 优化可生成( )的目标代码。A. 运行时间较短 B. 运行时间短但占用内存空间大C. 占用存储空间较小 D. 运行时间短且占用存储空间小3. 下列( )优化方法不是针对循环优化进行的。A. 强度削弱 B删除归纳变量 C删除多余运算 D代码外提4. 在目标代码生成阶段，符号表用于( )。A目标代码生成 B语义检查 C语法检查 D地址分配5语法分析是依据语言的_规则进行的，中间代码产生是依据语言的_规进行的。6优化可分为局部优化、_和全局优化三种。二、写

13、出表达式A*(B/C-D)+E/F的逆波兰中间代码。(15)三、什么是活动记录？它主要由哪些内容构成？(15)四、试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。(15)五、文法GM及其LR分析表如下，请给出对串dada#的分析过程。 (30)GM: 1) S VdB2) V e3) V 4) B a 5) B Bda 6) B 状态ACTIONGOTOdea#SBV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5附：参考答案：一、选择与填充（30）1. 四元式之间的联系是通过( B )来实现的。 A指示器 B临时变量

14、C符号表 D程序变量2. 优化可生成( D )的目标代码。A. 运行时间较短 B. 运行时间短但占用内存空间大C. 占用存储空间较小 D. 运行时间短且占用存储空间小3. 下列( C )优化方法不是针对循环优化进行的。A. 强度削弱 B删除归纳变量 C删除多余运算 D代码外提4. 在目标代码生成阶段，符号表用于( D )。A目标代码生成 B语义检查 C语法检查 D地址分配5语法分析是依据语言的_语法_规则进行的，中间代码产生是依据语言的_语义_规进行的。6优化可分为局部优化、_循环优化_和全局优化三种。二、写出表达式A*(B/C-D)+E/F的逆波兰中间代码。(15)解： ABC/D-*EF/

15、+三、什么是活动记录？它主要由哪些内容构成？(15)解：一个过程的一次执行所需信息的管理，是通过称为活动记录的连续存储块来实现的。活动记录的主要内容有：(1)临时变量域 存放目标程序临时变量的值；(2)局部数据域 存放过程本次执行时的局部数据、简单变量及数组内情向量等；(3)机器状态域 保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等；(4)存取链 为访问其它活动记录中所存放的非局部数据所提供的链地址；(5)控制链 指向主调过程的活动记录；(6)实参 存放主调过程为被调用过程所提供的实参信息；(7)返回值 为主调过程存放被调过程的返回值四、试写出算术表达式a+b*c-(c*

16、b+a-e)/(b*c+d)优化后的四元式序列。(15)解： 该表达式的四元式序列为：(1) (*, b, c, T1）(2) (+, a, T1, T2)(3) (*, c, b, T3)(4) (+, T3, a, T4)(5) (-, T4, e, T5)(6) (*, b, c, T6)(7) (+, T6, d, T7)(8) (/, T5, T7, T8)(9) (-, T2, T8, T9) 可以对该表达式进行删除公共子表达式的优化。优化后的四元式序列为： (1) (*, b, c, T1）(2) (+, a, T1, T2)(3) (-, T2, e, T5)(4) (+, T1, d, T7)(5) (/, T5, T7, T8)(6) (-, T2, T8, T9)五、文法GM及其LR分析表如下，请给出对串dada#的分析过程。 (30)G