总复习v 编译原理 考试题.pptVIP

第一章 引 论 第一章 引论 一、 什么叫编译程序？编译程序和解释程序的区别是什么？ 解：编译程序:是指这样的程序，它能够把某种“高级语言”的程序转换成另一种“低级语言”的程序，而后者与前者在逻辑上是等价的。 编译程序和解释程序的区别：解释程序是以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身，两者本质区别是否产生目标程序 二、 描述一下编译程序的工作过程。 解：编译程序的工作过程分为5个阶段： 1.词法分析 2.语法分析 3.语义分析中间代码生成 4.优化 5.目标代码生成 三、 描述一下编译器生成的几种方法。 解：生成编译器的方法有3种： 1.用L1语言编写L2的编译程序 2.采用移植的方法进行编译程序的开发 3. 自编译方式 第二章 高级程序设计语言 一、 构造一个文法G使 L(G)={anbm|n≥1,m ≥1} 解： S→AB A→aA|a B→bB|b 二、 构造一个文法G使 L(G)={anbn|n≥0} 解： S→aSb| ? 三、 已知语言L={anbbn| n ?1}, 写出产生L的文法。 解： G[S]: S ?aAb A ?aAb|b 四、 试构造生成语言L={anbnci|n?0, i ?1}的文法 解：G(Z): Z?AB A ?aAb| ? B ?cB|c 五、 已知语言L={x | x?{a,b,c}*,且x的排列是对称的（aabcbaa,aabbaa,等) 写出该语言的文法。 解：G(Z)： Z ?aZa|bZb|cZc|a|b|c|? 第三章 词法分析 ③NFA确定为DFA过程： 二、试求与下图所示NFA等价的化简了的DFA。 三、试构造与正则式R=(a*|b*)b(ba)*等价的状态最少的DFA。 NFA确定为DFA: 最小化的DFA: 四、已知有限自动机如图 解： （1） L={W |W ?{0,1},并且W至少有两个连续的1} （2） 正则式为（0|1)*11(0|1)* 正则文法G(Z)为： A?0A|1A|1B B?1C|1 C?0C|1C|0|1 I I0 I1 (1) {A} (1) {A} (2) {A,B} (2) {A,B} (1) {A} (3){A,B,C} (3) {A,B,C} (4) {A,C} (3){A,B,C} (4) {A,C} (4) {A,C} (3){A,B,C} 其相应的DFA如下图： （4）将这个DFA最小化： 首先分终态和非终态两个集 K1={1,2} 和 K2={3,4} 由于状态1输入1到达状态K1集，而状态2输入1到达K2集故将k1分为 K11={1}, K12={2} 由于状态3，和 4 输入1，或0 都到达k2集所以状态3，4等价。 则可以分割成三个子集： {1}，{2}，{3，4} 所以将DFA最小化的状态图如下： 第四章 自上而下语法分析 一、给出语言L={1na0n1ma0m|n0, m=0} 的LL(1)文法G[S]并说明其理由。 解：观察句子,发现可分成两部分 1na0n 和 1ma0m两部分中符号的个数n和m没有制约关系。则可定义为下列文法： S ?AB A ?1A0 |1a0 B ? 1B0 |a 第四章 自上而下语法法分析 对于产生式 A ? 1A0 |1a0 两个候选式 FIRST(1A0)?FIRST(1a0)={1}? 所以上述文法不是LL(1)文法：需左提公因子，得到 G[S] ：S ?AB A ?1C C ? A0 |a0 B ? 1B0 |a 一、 对于下列文法