《编译原理》复习题集1．名词解释短语句柄文法上下文无关文法LL（1）文法LR（1）文法语法分析无环路有向图(DAG)后缀式语法制导翻译遍局部优化词法分析语法分析语义分析源语言源程序目标语言中间语言（中间表示）2．简答题编译程序和高级语言有什么区别?编译程序的工作分为那几个阶段?简述自下而上的分析方法。目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？何谓优化？按所涉及的程序范围可分为哪几级优化？简述代码优化的目的和意义。3．叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。(1|01)*0*4．Pascal语言无符号数的正规定义如下：numdigit+(.digit+)?(E(+|-)?digit+)?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。5．画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。6．用状态转换图表示接收(a|b)aa的确定的有限自动机。7．处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。8．某操作系统下合法的文件名为device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，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。试构造识别L的最小化的DFA，并给出描述L的正规表达式。12．写出字母表∑={a,b}上语言L={w|w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。13．有穷自动机M接受字母表∑＝{0,1}上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。14．有正规式b*abb*(abb*)*，(1)构造该正规式所对应的NFA(画出状态转换图)。(2)将所求的NFA确定化(画出确定化的状态转换图)。(3)将所求的NFA最小化.(画出最小化后的状态转换图)。15．求出下列文法所产生语言对应的正规式.SbS|aAAaA|bBBaA|bC|bCbS|aA16．给出与下图的NFA等价的正规式。S0S1S3S217．把下面的NFA确定化。123456101110118．下面两个文法中哪一个不是LR（1）文法？对非LR（1）的那个文法。给出那个有移进－归约冲突的规范的LR（1）项目集。SaAcSaAcAbbA|bAbAb|b0123aababba,b19．将下面的DFA化成最简形式。20．为语言L＝{w|w(a|b)*并且在w的任何前缀中，a的个数不少于b的个数写一个LR（1）文法，不准超过6个产生式。21．写一个文法，使其语言是奇数集，且每个奇数不以0开头。22．考查文法G(s):S→(T)|a+S|aT→T,S|S消除文法的左递归；提取公共左因子；对每个非终结符，写出不带回朔的递归子程序。23．设文法G(S)：S→(L)|aS|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。24．消除下列文法的左递归.SSaP|Sf|PPQbP|QQcSd|e25．已知文法G：AaABe|aBBb|d给出与上述文法等价的LL(1)文法G'。26．已知文法G[A]：A→aAB|aB→Bb|d（1）构造与G[A]等价的LL(1)文法；（2）构造G’[A]的预测分析表。27．程序的文法如下：PDDD;D|id:T|procid;D;S（1）写一个语法制导定义，打印该程序一共声明了多少个id。（2）写一个翻译方案，打印该程序每个变量id的嵌套深度。28．构造下面文法的LL（1）分析表。DTLTint|realLidRR,idR|