1、1装订线华南农业大学期末考试题库（含参考答案）考试科目： 编译原理 考试时间： 120 分钟学号 姓名 年级专业 题号 一 二 三 四 五 总分得分评阅人一、本题共 6 小题，每小题 5 分，共 30 分。1、写出下面右线性正规文法所对应的正规式。2、给出下面语言集合的上下文无关文法。 （2010 2014）L1= anbm | nm12、为正规集 L2=anbm ck | n1,m1,k1构造一右线性正规文法。（2010）3、按照编译过程的 5 个阶段得到编译程序的逻辑结构框图如下：得分S aDD bD | aA | bA aD 文法所对应的正规式为：a(b|aa)*b文法： S aS |
2、DD aDb | abS aS | aAA bA | bBB cB | c23装订线4、简述编译过程的 5 个阶段及各阶段的主要功能。 （多年必考）5、 “含有优化部分的编译程序的执行效率更高。 ”这句话对吗？为什么？。6、简述语法制导翻译技术的基本思想。 （2013）7、简述算符优先分析方法。 （2013）8、简要说明翻译程序与编译程序的异同、编译程序与解释程序的异同。（2011）编译过程即编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；语法分析，根
3、据语言的语法规则，把单词符号串组合成各类语法单位；语义分析与中间代码产生，即对各类语法单位，分析其含义并进行初步翻译；代码优化，对代码进行等价变换，以期产生更高效的代码；目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。这句话是错的。优化不是编译程序必须的一个部分，含有优化的编译程序功能更强、算法更复杂，因而开发效率和执行效率低些，但得到的目标代码的效率通常更高。语法制导翻译技术的基本思想是，对文法中的每个产生式都附加一个语义动作或语义子程序，在执行语法分析的过程中，当运用该产生式进行推导或归约时，就执行相应的语义动作，从而完成预定的翻译工作。算符优先分析方法是一种移进-归约的语法分
4、析方法，这种分析方法首先要根据文法来确定终结符之间的优先关系，然后借助这种优先关系，在移进-归约过程中通过比较相邻终结符之间的优先关系来确定句型的可归约串（最左素短语）并进行归约。它不是一种规范归约的分析方法，只适用于分析算符优先文法。翻译程序是将一种语言程序（源）转换成另一种语言程序（目标） ，对源语言和目标语言没特别要求，编译程序特指将高级语言的源程序转换成低级语言程序，是翻译程序的一种。编译程序与解释程序都是将高级语言翻译成低级语言，但编译程序要先编译生成目标代码、再执行目标代码，解释程序边转换边执行，不生成目标代码。49、判断下图 FA 是 NFA 还是 DFA，并用正规式来描述它所识
5、别的语言。10、判断下图 FA 是 NFA 还是 DFA，并用正规式来描述它所识别的语言。（2011）11、有文法及其语义子程序如下：S T print(T.h) T T 1*E T.h= T 1.h +E.h T E T.h=E.h E（ T） E.h= T.hE a E.h= 1 采用移进归约的分析方法，当分析器的输入为(a)*(a*a) 时，画出其语法树（可以带注释、也可以不带注释） ，并求输出的结果。1A B001 是 DFA(1 分)，对应的正规式为：1*01*(01*01*)* (4 分)语法树（略） ，输入为(a)*(a*a) 时，输出的结果为：30A B0,10是 NFA,因为
6、 A 状态输入 0 可以转换到 A 或 B 两状态。等价正规式：0*(0|1)(00*(0|1)*5装订线12（2014） 、空心圆柱体的表面积计算公式如S=2*3.1416*(R+r)*(R-r)+ 2*3.1416*(R+r)*h采用 LR 语法制导翻译技术生成相应的三地址代码，然后运用 DAG 对其进行局部优化，试写出能生成最优目标代码的优化后的三地址代码序列。13、试求表达式 A+B*(-C)+B/(-C)对应的后缀式和三地址代码。 （2011）14、考虑如下的三地址语句序列：（2011）(1). 将该代码序列划分成基本块，并给每个基本块一个序号；(2). 画出该代码序列的流图，每个基
7、本块用(1)的序号表示；(3). 若有循环，列出构成循环的节点(基本块)。 （10 分）(1).如图分成四个基本块 B1、B2、B3、B4(2).流图：(3).构成循环的基本块是B2, B315、有翻译模式如下：可以采用合并已知量、删除公共子表达式、删除无用赋值、交换语句位置等优化方法，得到三地址代码序列如下：(1) T1=R+r (2) T2=6.2832*T1 (3) T3=T2*h(4) T4=R-r (5) T5=T2*T4 (6) S=T5+T3后缀式：ABC-*+BC-/+三地址代码：T1=-C T2=B*T1 T3=A+T2 T4=-C T5=B/T4 T6=T3+T5 L1:
8、read C;A=0;B=1;L2: A=A+B;if BC goto L3;B=B+1;goto L2;goto L1;L3: write A;halt;B1B2B3多余的语句，删去B4B1B2B3 B46S S print(S.h) S a S.h=0 S（T） S.h= T.h+1T T 1，S T.h= T 1.h +S.h T S T.h= S.h 采用移进归约的分析方法，当分析器的输入为(a,(a) 时，画出其语法树（可以带注释、也可以不带注释） ，并求输出的结果。 （2011）输出结果是：2语法树： S( T )T , SSa( T )Sa7装订线二、构造识别下列语言的最小 DF
9、A（共 20 分）：00100102、以 101 结尾的二进制串；（8 分）得分1、正规式 1（0|1） * 0 | 0；（7 分）3、不以 101 结尾的二进制串。 （5 分）A1B D00C1 01A B C D0 11 01A B C D0111求出 NFA 得 4 分，确定化了得 6 分，最小 DFA 的状态错漏一个扣 1 分，弧错漏一条扣 0.5 分。求出 NFA 得 4 分，确定化了得 6 分，最小 DFA 的状态错漏一个扣 1 分，弧错漏一条扣 0.5 分。8构造识别下列语言的最小 DFA（共 15 分）：（2011）ABC0 000111D100114、正规式（0|1） * （
10、00 | 11） （0|1） *；（5 分）5、含有奇数个 1 或奇数个 0 的二进制串；（5 分）6、能被 2 整除的二进制串。 （5 分）得分1、2、 001 1A CB D3、 1A B0109装订线构造下列正规式相应的 DFA（用状态转换图表示） （15） （2008）（7） 1（0 | 1）*1（8） 0*10*10*10*1（9） letter（letter | digit）*（7）（8）(9)1020,1131120 0301401 1 51letterletter2digit107、将下图 NFA 确定化。 （10 分） （2013）8、将下图 DFA 化简。 （5 分） （2013）a01得分01b3a2bbbB D0ECA0011 01确定化：（可以给状态换名）0,1,3ab31,2ab 1,2，32bbb首先将 DFA 的状态集划分成终态集和非终态集E、A,B,C,D;由于A,B,C,D 0=B,C,C,E，所以再分划成A,B,C、D;对于输入符号 1，A,B,C 1= ,D,D，所以再次分划成A、B,C; B,C0=C,C，B,C 1=D,D，所以不用再分，B、C 是等价状态。得到最小的 DFA 如下：01B D0EA01 01（确定化后再化简也不扣分，但要有说明）
