编译原理复习及典型题解

《编译原理复习及典型题解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理复习及典型题解一、单选题1．文法所描述的语言是的集合。A.文法的字汇表V中符号组成的符号串B.文法的字汇表V中终结符号组成的符号串C.由文法开始符推导的符号串D.由文法开始符推导的终结符号串D2．生成能被5整除的正整数的文法G[Z]是________。A.G[Z]:Z→AC,A→BA

2、B,B→0

3、1

4、2

5、…

6、9,C→0

7、5B.G[Z]:Z→AC,A→BA

8、ε,B→0

9、1

10、2

11、…

12、9,C→0

13、5C.G[Z]：Z→DA0

14、A5，A→BA

15、ε，B→0

16、D，D→1

17、2

18、…

19、9D.G[Z]：Z→AC

20、

21、C,A→BA

22、B,B→0

23、1

24、2

25、…

26、9,C→0

27、5C3．符号串ab1b2是文法G[A]：A→aB,B→bB

28、b的句子，该句子的句柄是________。A.b1B.b2C.aD.b1b2Aa解释：Bb1Bb2B4．LL(1)文法中第一个L表示________。A.最左推导B.最左归约C.从左到右识别输入串D.规范归约C5．对于LR(0)分析法，语法分析栈中存放的状态是识别规范句型_______的DFA状态。A．前缀B.活前缀C.LR(0)项目D.句柄B6．算符文法是指的文法。①没有形如U→...VW

29、...的规则（U，V，WVN）②VT中任意两个符号之间至多存在一种算符优先关系③没有相同右部的规则④没有形如U→ε的规则A.①B.①和②C.①、②和③D.①、②、③和④A7．下述语句类中，____________在编译阶段通常不产生可执行代码。A.变量说明语句B.流程控制语句C.输入输出语句D.赋值语句A8．在编译程序采用的优化方法中，是在循环语句范围内进行的。①合并已知常量②删除多余运算③删除归纳变量④运算强度削弱⑤代码外提A.①④B.①⑤C.①④⑤D.③④⑤D9．程序的基本块是指_______

30、。A.不含无条件转移语句的程序段B.不含条件转移语句的程序段C.不含停机的语句程序段D.仅含有一个入口语句和一个出口语句的顺序程序段D二、多选题1．符号串dbb是给定文法G[A]：A→dBC，B→aB

31、ε，C→bC

32、b的句子，试问其活前缀包括。A.εB.dC.dbD.dbb2．已知字母表Σ=｛a，b｝,下列________是字母表Σ上的正规式。A.ab+aB.abc

33、b*C.(a

34、b)*D.εA、B注解：符号串dbb可归约前缀为d。C、D3．常见的自底而上语法分析方法有。A.递归下降分析B.算符优先

35、分析C.LL(1)预测分析D.LR分析B、D4．一个文法是LR(0)文法一定也是。A.SLR(1)文法B.LR(1)文法C.LALR(1)文法D.二义文法A、B、C注解：SLR(0)⊊SSLR(1)⊊SLALR(1)⊊SLR(1)1．设A是符号串集，则A0＝ε。（）2．在形式语言中，最右推导的逆过程称为规范归约。（）3．一个语言的文法是唯一的。（）4．句型的每个直接短语都是某规则的右部。（）5．如果语言的文法是二义性，则该语言也是二义性的。（）6．任何正规文法都是上下文无关文法。（）7．符号表的主要

36、作用是辅助语义分析和代码生成。（）三、判断题×√×√×√√1．构造一个高级语言的词法分析程序的基本技术线路是什么？四、简述题简答：依据给定的源语言之单词集，设计其正规文法或正规式，之后等价地转换成非确定有穷自动机，再通过子集法将其确定化，最终将确定有穷自动机最小化，最后依据最小化的确定有穷自动机，设计词法分析程序。五、填空题1．编译程序是一种翻译程序，它将用户用高级语言编写的_______翻译成等价的_________________的目标程序。2．有这样一个推导过程，其每一步推导都是对符号串中最右

37、的非终结符进行替换，我们把这种推导过程称为____________________。3．属性文法中的属性分为综合属性和__________两种。源程序汇编语言或机器语言最右推导（或规范推导）继承属性4．已知文法G[A]：A→(B)

38、a

39、ε，B→B，A

40、A，该文法的开始符号是___，非终结符号集合为______，终结符号集合为_______。5．自下而上的语法分析方法的基本思想是从待识别的输入串开始逐步______到文法的______。6．已知文法G[S]：S→AB,A→aAb

41、c,B→aBb

42、d，则

43、对于非终结符A，FOLLOW(A)=______。A{A,B}{(,),a}归约开始符{a,b,d}注解：FOLLOW可以采用依据定义直接计算，或依据教材所给算法计算。13六、解答题1.已知文法G[S]：S→*A，A→*∣0A1。(1)求文法G非终结符的FIRSTVT集和LASTVT集；(2)构造文法G算符优先关系分析表，并判断G是否为算符优先文法。解：（1）计算FIRSTVT集和LASTVT集FIRSTVT(S)={*},LASTVT(S)={*,1}FIRSTVT