编译原理 上海交通大学期末考试.doc

.上海交通大学期末考试编译原理试题及答案一、对于文法 GS ： S 1A | 0B | A 0S | 1AA B 1S | 0BB (3 分 ) 请写出三个关于 GS 的句子； (4 分 ) 符号串 11A0S 是否为 G S 的句型？试证明你的结论。 (3 分 ) 试画出 001B 关于 G S 的语法树。 二、请构造一个文法，使其产生这样的表达式 E ：表达式中只含有双目运算符 + 、 * ，且 + 的优先级高于 * ， + 采用右结合， * 采用左结合，运算对象只有标识符 i ，可以用括号改变运算符优先级。要求给出该文法的形式化描述。 三、设有语言 L= | 0,1 + ，且不以 0 开头，但以 00 结尾 。 试写出描述 L 的正规表达式； 构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NDFA 、 DFA 的状态转换图，以及 DFA 的形式化描述 ) 。 四、给定文法 GS ： S AB A aB | bS | c B AS | d (6 分 ) 请给出每一个产生式右部的 First 集； (3 分 ) 请给出每一个非终结符号的 Follow 集； (8 分 ) 请构造该文法的 LL(1) 分析表； (8 分 ) 什么是 LL(1) 文法？该文法是 LL(1) 文法吗？为什么？ 五、给定文法 GS ： S SaA|a A AbS|b 请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 请构造该文法的 LR(0) 分析表。 什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？ 什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？ 六、给定下列语句： if a+bc then x := a*(b-c) + (b*c-d)/e 写出其等价的逆波兰表示； 写出其等价的四元式序列。 七、已知下列 C 语言程序：int * f() int a = 100; return &a; main() int * i = f(); char a = “compiler”; printf(“the result is %dn”, *i); 程序运行结果为： the result is 26157, 请解释为什么程序运行的结果不是期望的“ the result is 100 ”？1.1 三个 0 和 1 数量相等的串 1.2 S = 1A = 11AA = 11A 0S 1.3 第二题 构造文法如下 : GE=(+,*,(,),i, E,F,T, P, E) ， 其中 P 为： EE*F|F FT+F|T T(E)|i第三题 （ 1 ）正规表达式： 1(0|1) * 00 （ 2 ）第一步：将正规表达式转换为 NDFA 第二步：将 NDFA 确定化为 DFA ： 造表法确定化（ 3 分） 确定化后 DFA M 的状态转换表 (2 分 ) 状态 输入 I 0 I 1 t 0 1 S A,D,B q 0 q 1 A,D,B D,B,C D,B 重新命名 q 1 q 2 q 3 D,B,C D,B,C,Z D,B q 2 q 4 q 3 D,B D,B,C D,B q 3 q 2 q 3 D,B,C,Z D,B,C,Z D,B q 4 q 4 q 3 DFA 的状态转换图（ 3 分） 第三步：给出 DFA 的形式化描述 DFA M = （ q 0 , q 1 , q 2 , q 3 , q 4 , 0,1, t, q 0 , q 4 ） t 的定义见 M 的状态转换表。第四题 （ 1 ） First(AB) = a, b, c First(aB) = a First(bS) = b First(c) = c First(AS) = a, b, c First(d) = d （ 2 ） Follow(S) = #, a, b, c, d Follow(A) = a, b, c, d Follow(B) = #, a, b, c, d （ 3 ） LL(1) 分析表（ 8 分） V N V T a b c d # S S ? AB S ? AB S ? AB A A ? aB A ? bS A ? C B B ? AS B ? AS B ? AS B ? d （ 4 ）对于文法 G 的每一个非终结符 U 的产生式 U ? 1 | 2 | n ， 如果 SELECT(U ? i ) ? SELECT(U ? j ) = ? （ ij, i,j=1, 2, , n ）， 则文法 G 是一个 LL(1) 文法。 该文法是 LL(1) 文法。 因为 SELECT(A ? aB) ? SELECT(A ? bS) ? SELECT(A ? C) = ? SELECT(B ? AS) ? SELECT(B ? d) = ?第五题 拓广文法 1 分 GS : S S S SaA S a A AbS A b 该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA ： 该文法的 LR(0) 分析表： 状态 ACTION GOTO a b # S A 0 S 2 1 1 S 3 acc 2 r 3 r 3 r 3 3 S 5 4 4 r 2 r 2 /S 6 r 2 5 r 5 r 5 r 5 6 S 2 7 7 r 4 /S 3 r 4 r 4 LR(0) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突状态。 该文法不是 LR(0) 文法 因为存在冲突状态： I 4 和 I 7 SLR(1) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突状态，冲突可用 FOLLOW 集解决。 该文法不是 SLR(1) 文法。 因为 FOLLOW(S)=a,b,# ，所以无法解决冲突 第六题 （ 1 ） (1) ab+c (23) jumpf (8) xabc-*bc*d-e/+:= (23) . （ 2 ） 第七题C 语言采用栈式存储分配方法作为其运行环境； f() 返回的是指向其活动记录某一位置的指针； f() 返回后，其活动记录被释放，并且，其对应的存储空间被数组 a 占用， 再次引用该指针时，其结果由于对回收的活动记录所占用的内存空间的再分配，其所指的值 发生了改变。释放在前，引用在后的现象称 : Dangling Reference 。历年试题及答案一 （每项选择2分，共20分）选择题1将编译程序分成若干个“遍”是为了_。a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率2构造编译程序应掌握_。a.源程序 b.目标语言c.编译方法 d.以上三项都是3变量应当。a.持有左值 b.持有右值c.既持有左值又持有右值 d.既不持有左值也不持有右值4编译程序绝大多数时间花在_上。a.出错处理 b.词法分析c.目标代码生成 d.管理表格5词法分析器的输出结果是_。a.单词的种别编码 b.单词在符号表中的位置c.单词的种别编码和自身值 d.单词自身值6正规式MI和M2等价是指_。a. MI和M2的状态数相等 b.Ml和M2的有向弧条数相等。C.M1和M2所识别的语言集相等 d. Ml和M2状态数和有向弧条数相等7中间代码生成时所依据的是。 a语法规则 b词法规则 c语义规则 d等价变换规则8后缀式ab+cd+/可用表达式_来表示。 a a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d9程序所需的数据空间在程序运行前就可确定，称为_管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储10.堆式动态分配申请和释放存储空间遵守_原则。 a.先请先放 b.先请后放 c.后请先放 d.任意二（每小题10分，共80分）简答题1.画出编译程序的总体结构图，简述各部分的主要功能。2.已知文法GE: EET+|TTTF* | FFF | a 试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄. 3为正规式(a|b) *a(a|b)构造一个确定的有限自动机。4设文法G(S)： S(L)|a S|a LL，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。5 已知文法 A-aAd| aAb| 判断该文法是否SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。6构造算符文法GH的算符优先关系（含）。 GH：HH;M|M Md|aHb7已构造出文法G（S）（1）S BB（2）B aB（3）B b1）。给出DFA图2）.给出LR分析表3）假定输入串为abaab，请给出LR分析过程（即状态，符号，输入串的变化过程）。8将下面的语句翻译成四元式序列： while ACBA(1) A-aAd(2)A- aAb(3)A- (2)构造识别活前缀的DFA FOLLOW(A)=d,b,# 对于状态I0：FOLLOW(A)a= 对于状态I1：FOLLOW(A)a= 因为，在DFA中无冲突的现象，所以该文法是SLR(1)文法。 (3)SLR(1)分析表 状态 ACTION GOTO a B d # A 0 S2 r3 r3 r3 1 1 acc 2 S2 r3 r3 r3 3 3 S5 S4 4 r1 r1 r1 5 r2 r2 r2 (4)串ab#的分析过程 步骤 状态栈 符号栈 当前字符 剩余字符串 动作 1 0 # a b# 移进 2 02 #a b # 归约A- 3 023 #aA b # 移进 4 0235 #aAb # 归约A- aAb 5 01 #A # 接受 6 【解答】 由Md和Ma得：FIRSTVT(M)=d,a； 由H-H;得：FIRSTVT(H)=； 由HM得：FIRSTVT(M) cFIRSTVT(H)，即FIRSTVT(H)=;,d,a 由Md和Mb得：LASTVT(M)=d,b； 由H-，；m得：LASTVT(H)=； 由HM得：LASTVT（M）cLASTVT(H），即LASTVT(H)=;,d,b 对文法开始符H,有#H#存在，即有=，#,也即；，#d. #, b#。 对形如Pab，或PaQb，有a=b，由Ma|b得：a=b； 对形如PaR，而bFIRSTVT(R)，有ab。 由H；M得：；FIRSTVT(M)，即：d，：a 由MaH得：aFIRSTVT(H)，即：a；，a;，即：；，d；，b； 由MHb得：LASTVT(H)b，即：；b，db，bb 由此得到算符优先关系表，见表3.5。7 【解答】（1）LR分析表如下：（2）分析表状态 ACTION GOTO a b # S B0 s3 s4 1 21 acc 2 S3 S4 53 s3 s4 64 r3 r3 5 R1 R1 r1 6 R2 R2 R2 (3) 句子abaab的分析过程表:句子abaab的分析过程步骤 状态 符号栈 输入串 所得产生式0 #0 # abaad# 1 #03 #a baad# 2 #034 #ab aab# Bb3 #036 #aB aab# BaB4 #02 #B aab# 5 #023 #Ba ab# 6 #0233 #Baa b# 7 #02334 #Baab # 8 #02336 #BaaB # 9 #0236 #BaB ad# 10 #025 #BB ad# 11 #01 #S d# 12 # # d# 13 识别成功 8 【解答】该语句的四元式序列如下（其中E1、E2和E3分别对应：ACBD, A=1和AD并且关系运算符优先级高）： 100 (j,A,C,102) 101(j,_,_,113） /*E1为F*/ 102 (j2，4-3 (3)求出流图中的循环: 回边5-2对应的循环：2、5、3、4； 回边4-3对应的循环：3、4装订线 参考答案一、单项选择题(共10小题，每小题2分，共20分)1语言是A句子的集合 B产生式的集合 C符号串的集合 D句型的集合2编译程序前三个阶段完成的工作是A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化3一个句型中称为句柄的是该句型的最左 A非终结符号 B短语 C句子 D直接短语4下推自动机识别的语言是A0型语言 B1型语言 C2型语言 D3型语言5扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A 字符 B单词 C句子 D句型6对应Chomsky四种文法的四种语言之间的关系是 AL0L1L2L3 BL3L2L1L0 CL3=L2L1L0 DL0L1L2=L37词法分析的任务是 A识别单词 B分析句子的含义 C识别句子 D生成目标代码8常用的中间代码形式不含 A三元式 B四元式 C逆波兰式 D语法树9 代码优化的目的是 A节省时间 B节省空间 C节省时间和空间 D把编译程序进行等价交换10代码生成阶段的主要任务是 A把高级语言翻译成汇编语言 B把高级语言翻译成机器语言 C把中间代码变换成依赖具体机器的目标代码 D把汇编语言翻译成机器语言二、填空题（本大题共5小题，每小题2分，共10分）1编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。 2编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。3通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。5对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。三、名词解释题(共5小题，每小题4分，共20分)1词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。2LL(1)文法 若文法的任何两个产生式A a | b都满足下面两个条件：（1）FIRST(a ) FIRST(b ) = f；（2）若b * e ，那么FIRST(a ) FOLLOW( A ) = f。 我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。3语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S。(2)每个节点的标记都是V中的一个符号。(3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2AR，那么AA1A2AR一定是P中的一条产生式。(4)若一标记为A的节点至少有一个除它以外的子孙，则AVN。(5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。4LR(0)分析器 所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。5语言和文法文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G定义为四元组的形式：G=(VN，VT，P，S)其中：VN 是非空有穷集合，称为非终结符号集合；VT 是非空有穷集合，称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。这里，VNVT=，SVN。V=VNVT，称为文法G的字母表，它是出现文法产生式中的一切符号的集合。文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即L(G)=x| S*x，其中S为文法开始符号，且 简单的说，文法描述的语言是该文法一切句子的集合。四、简答题(共4小题，每小题5分，共20分)1编译程序和高级语言有什么区别? 用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。 编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的对话，随时可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，在过程中，不能进行人机对话修改。FORTR