资源描述：
《编译原理复习题集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《编译原理》复习题集1．名词解释短语句柄文法上下文无关文法LL（1）文法LR（1）文法语法分析无环路有向图(DAG)后缀式语法制导翻译遍局部优化词法分析语法分析语义分析源语言源程序目标语言中间语言（中间表示）2．简答题(1)编译程序和高级语言有什么区别?(2)编译程序的工作分为那几个阶段?(3)简述自下而上的分析方法。(4)目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？(5)何谓优化？按所涉及的程序范围可分为哪几级优化？(6)简述代码优化的目的和意义。3．叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。(1
2、0
3、1)*0*4．Pascal语言无符号数的正规定义如下：num®digit+(.digit+)?(E(+
4、-)?digit+)?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。5．画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。6．用状态转换图表示接收(a
5、b)*aa的确定的有限自动机。7．处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。8．某操作系统下合法的文件名为device:name.extension其中第一部分（device:）和第三部分（.extension
6、）可缺省，device,name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。9．构造一个DFA，它接受å={0,1}上0和1的个数都是偶数的字符串。10．设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，δ，{A}，{C})，其中：δ(A，0)={C}δ(A，1)={A，B}δ(B，1)={C}δ(C，1)={C}。请画出状态转换距阵和状态转换图。11．设LÍ{a,b,c}*是满足下述条件的符号串构成的语言：(1)若出现a，则其后至少紧跟两个c；(2)若出现b，其后至少紧跟一个c。试构造
7、识别L的最小化的DFA，并给出描述L的正规表达式。12．写出字母表∑={a,b}上语言L={w
8、w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。13．有穷自动机M接受字母表∑＝{0,1}上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。14．有正规式b*abb*(abb*)*，(1)构造该正规式所对应的NFA(画出状态转换图)。(2)将所求的NFA确定化(画出确定化的状态转换图)。(3)将所求的NFA最小化.(画出最小化后的状态转换图)。15．求出下列文法所产生语言对应的正规式.Sàb
9、S
10、aAAàaA
11、bBBàaA
12、bC
13、bCàbS
14、aA16．给出与下图的NFA等价的正规式。S0S1S3S217．把下面的NFA确定化。123456101110118．下面两个文法中哪一个不是LR（1）文法？对非LR（1）的那个文法。给出那个有移进－归约冲突的规范的LR（1）项目集。S®aAcS®aAcA®bbA
15、bA®bAb
16、b0123aababba,b19．将下面的DFA化成最简形式。20．为语言L＝{w
17、wÎ(a
18、b)*并且在w的任何前缀中，a的个数不少于b的个数}写一个LR（1）文法，不准超过6个产生式。21．写一个文法，使其语言是奇数
19、集，且每个奇数不以0开头。22．考查文法G(s):S→(T)
20、a+S
21、aT→T,S
22、S(1)消除文法的左递归；(2)提取公共左因子；(3)对每个非终结符，写出不带回朔的递归子程序。23．设文法G(S)： S→(L)
23、aS
24、a L→L，S
25、S (1)消除左递归和回溯； (2)计算每个非终结符的FIRST和FOLLOW； (3)构造预测分析表。24．消除下列文法的左递归.SàSaP
26、Sf
27、PPàQbP
28、QQàcSd
29、e25．已知文法G：AàaABe
30、aBàBb
31、d给出与上述文法等价的LL(1)文法G'。26．已知文法G[A]：A→aAB
32、
33、aB→Bb
34、d（1）构造与G[A]等价的LL(1)文法；（2）构造G’[A]的预测分析表。27．程序的文法如下：P®DD®D;D
35、id:T
36、procid;D;S（1）写一个语法制导定义，打印该程序一共声明了多少个id。（2）写一个翻译方案，打印该程序每个变量id的嵌套深度。28．构造下面文法的LL（1）分析表。D®TLT®int
37、realL®idRR®,idR
38、e29．考虑下文法：DàTVTàint｜floatVàid,V
39、ida.在该文法中提取左公因子。b.为所得文法的非终结符构造First和Follow集合。c.说明所得的文法是LL(1)文
40、法。d.为所得文法构造LL(1)分析表。e.假设有输入串intx,y,z写出相应LL(1)分析程序的动作。30．说明如下文法是否是LL（1）文法，若不
