资源描述：
《编译原理 试题解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、简答题（15分）1.编译程序与解释程序有何区别？2.何谓素短语？3.过程调用时，主调程序与被调程序之间的信息传递有哪些方式？4.何谓语法制导翻译？5.何谓算符文法？二、选择题（10分）1.描述一个语言的文法是（）A.唯一的B.不唯一的C.可能唯一，也可能不唯一2.若文法G定义的语言是无限集，则文法必然是（）A.前后文无关文法B.正规文法C.二义性文法D.递归文法3.数组的内情向量中肯定不含数组的（）信息A.维数B.类型C.各维的上下界D.各维的界差4.简单优先分析每次归约的是（）A.最左直接短语B.直接短语C.最左素短语D.控制结点5.最适合动态建立数
2、据实体的内存分配方式是（）A.栈式分配B.堆式分配C.编译时预先分配D.以上三种均可三、（10分）给定文法G=（{S,L}，{a，（，）}，{S→(L)
3、aL→L,S
4、S}，S）。给出句型”(S,(a))”的推导和语法树并指出此句型的所有短语、直接短语、句柄和素短语。四、（12分）设语言L是由奇数个a和偶数（可以是0）个b组成的符号串之集。1.构造识别L的DFA；2.给出定义L的正规文法；五、（10分）将文法G[S]：S→[AA→AS
5、B]B→Bi
6、i改写为等价的LL(1)文法，并给出相应的LL(1)分析表。六、（20分）给定文法G[S]：S→(S)
7、a1
8、.构造识别文法G[S]活前缀的LR(1)项目的DFA；2.构造LR(1)分析表；3.合并同心集，构造LALR(1)分析表。七、（8分）某语言算术表达式的文法定义为E→E+E
9、i
10、ifBthenEelseE其中，第三个候选式称为条件算术表达式，B为布尔表达式，then及else后的E均为算术表达式（即简单算术表达式或条件表达式），其语义为，当B为真时，表达式的值取then后的E的值，否则取else的E的值。假定所有表达式是整型的，试将下面关于条件算术表达式的属性翻译文法填写完全： 八、（8分）给定PASCAL程序语句whilea>bdoifa>0thena:
11、=a-1elsea:=a+1; 1.将该语句翻译成逆波兰式；2.给出编译程序扫描到then处及分号处时所得的四元式序列。九、(7分)用DAG图对下面的基本块进行优化（假定出基本块后只有A、G、L是活跃的）：A=B*CD=B/CE=2*3F=E+2G=B*CK=E+FG=K*KL=B/C试题答案参考答案：一、简答题（15分）1.编译程序与解释程序有何区别？答：二者的工作方法不同，后者是边解释边执行，解释所得的代码并不保存；前者是先将高级语言翻译感情上标代码，将其保存到指定的空间中，待需要时再执行之，甚至可以在案一个机器上编译，而在另一台机器上执行。2.何谓素
12、短语？答：素短语是满足下述条件的短语：（1）它至少含有一个终结符号（2）满足条件（1）的“最小”短语3.过程调用时，主调程序与被调程序之间的信息传递有哪些方式？答：形式参数与实在参数结合方式传递（简称参数传递）、返回值传递、共享数据区传递。4.何谓语法制导翻译？答：语法制导翻译是对前后文无关文法的扩充，即对文法中的每个产生式都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序，完成相应的语义分析和翻译工作。5.何谓算符文法？答：当一个
13、文法的所有产生式的右部均不出现两个非终结符号相邻的情况时，该就被称为算符文法。二、选择题（10分）1.描述一个语言的文法是（B）A.唯一的B.不唯一的C.可能唯一，也可能不唯一2.若文法G定义的语言是无限集，则文法必然是（D）A.前后文无关文法B.正规文法C.二义性文法D.递归文法3.数组的内情向量中肯定不含数组的（B）信息A.维数B.类型C.各维的上下界D.各维的界差4.简单优先分析每次归约的是（C）A.最左直接短语B.直接短语C.最左素短语D.控制结点5.最适合动态建立数据实体的内存分配方式是（B）A.栈式分配B.堆式分配C.编译时预先分配D.以上三种
14、均可三、（10分）给定文法G=（{S,L}，{a，（，）}，{S→(L)
15、aL→L,S
16、S}，S）。给出句型”(S,(a))”的推导和语法树并指出此句型的所有短语、直接短语、句柄和素短语。 解：ST(L)T(L,S)T(L,(L))T(L,(S))T(L,(a))T(S,(a))短语有：“a”,“(a)”,“S”，“S,(a)”，“（S,(a)）”。直接短语有：”S”，“a”句柄：“S”素短语：“a“语法树略。四、（12分）设语言L是由奇数个a和偶数（可以是0）个b组成的符号串之集。1.构造识别L的DFA；2.给出定义L的正规文法；解：1。见图：2．S?a
17、A
18、bBA?aS
19、bC
20、eB?bS
21、aCC?bA
22、aB五、（10分
