编译原理与技术练习题汇总

《编译原理与技术》练习题1练习11.1为什么高级程序语言需要编译程序？1.2解释下列术语：源程序，目标程序，翻译程序，编译程序，解释程序1.3简单叙述编译程序的主要工作过程。1.4编译程序的典型体系结构包括哪些构件，主要关系如何，请用辅助图示意。1.5编译程序的开发有哪些途径？了解你熟悉的高级编程语言编译程序的开发方式。1.6运用编译技术的软件开发和维护工具有许多类，简单叙述每一类的主要用途。1.7了解一个真实编译系统的组成和基本功能。1.8简单说明学习编译程序的意义和作用。1.9如果机器H上有两个编译：一个把语言A翻译成语言B，另一个把B翻译成C，那么可以把第一个编译的输出作为第二个编译的输入，结果在同一类机器上得到从A到C的编译。请用T形图示意过程和结果。《编译原理与技术》练习题2练习22.1词法分析器的主要任务是什么？2.2下列各种语言的输入字母表是什么？(1)C(2)Pascal(3)Java(4)C#2.3可以把词法分析器写成一个独立运行的程序，也可以把它写成一个子程序，请比较各自的优劣。2.4用高级语言编写一个对C#或Java程序的预处理程序，它的作用是每次调用时都把下一个完整的句子送到扫描缓冲区，去掉注释和无用的空格、制表符、回车、换行。2.5用高级语言实现图2.5所示的Pascal语言数的状态转换图。2.6用高级语言编程实现图2.6所示的小语言的词法扫描器。2.7用自然语言描述下列正规式所表示的语言：(1)0(0|1)*0(2)((|0)1)*)*(3)(a|b)*a(a|b|)(4)(A|B|...|Z)(a|b|...|z)*(5)(aa|b)*(a|bb)*(6)(0|1|...|9|A|B|C|D|E)+(t|T)2.8为下列语言写正规式(1)所有以小写字母a开头和结尾的串。(2)所有以小写字母a开头或者结尾（或同时满足这两个条件）的串。(3)所有表示偶数的串。(4)所有不以0开始的数字串。(5)能被5整除的10进制数的集合。(6)没有出现重复数字的全体数字串。2.9试构造下列正规式的NFA，并且确定化，然后最小化。(1)(a|b)*a(a|b)(2)(a||b)*a(a|b)*(3)ab((ba|ab)*(bb|aa))*ab(4)00|(0|1)*|11(5)1(0|1)*01(6)1(1010*|1(010)*1*02.10请分别使用下面的技术证明(a|b)*，(a*|b*)*以及((a|)b*)*这三个正规式是等价的：(1)仅用正规式的定义及其代数性质；(2)从正规式构造的最小DFA的同构来证明正规式的等价。《编译原理与技术》练习题32.11构造有限自动机M，使得(1)L(M)={anbn|n1}；(2)L(M)={anbncn|n1}；(3)它能识别＝{0,1}上0和1的个数都是偶数的串；(4)它能识别字母表{0,1}上的串，但是串不含两个连续的0和两个连续的1；(5)它能接受形如dd*，d*E和dd的实数，其中d={0，1，2，3，4，5，6，7，8，9}。(6)它能识别{a,b}上不含子串aba的所有串。2.12分别将下列NFA确定化，并画出最小化的DFA：(a)(b)(c)2.13下面是URL的一个极其简化的扩展正规式的描述：letter→[A-Za-z]digit→[0-9]letgit→letter|digitletgit_hyphen→letgit|_letgit_hyphen_string→letgit_hyphen|letgit_hyphenletgit_hyphen_stringlabel→letter(letgit_hyphen_string?letgit)？URL→(label.)*label(1)请将这个URL的扩展正规改写成只含字母表{A,B,0,1,_,.}上符号的正规式；(2)构造出识别（1）更简化的URL串的有限自动机。2.14用某种高级语言实现(1)将正规式转换成NFA的算法；(2)将NFA确定化的算法；(3)将DFA最小化的算法。2.15描述下列语言词法记号的正规表达式：(1)描述C浮点数的正规表达式。(2)描述Java表达式的正规表达式。2.16Pascal语言的注释允许两种不同的形式：花括弧对{...}，以及括弧星号对(*...*)。(1)构造一个识别这两种注释形式的DFA；(2)用Lex的符号构造它的一个正规式。2.17写一个Lex输入源程序，它将产生一个把C语言程序中（注释除外）的保留字全部大写。abFAa,bBCDbbaSEa40a,ba123abbbaa10a,bb《编译原理与技术》练习题4练习33.1对于文法G3.26[E]E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明(i+T)*i是它的一个句型。3.2给定文法G3.27[S]S→aAcB|BdSB→aScA|cAB|bA→BaB|aBc|a试检验下列符号串中哪些是G3.27[S]中的句子。(1)aacb(2)aabacbadcd(3)aacbccb(4)aacabcbcccaacdca(5)aacabcbcccaacbca3.3考虑文法G3.28[S]S→(L)|aL→L,S|S(1)指出该文法的终结符号及非终结符号。(2)给出下列各句子的语法分析树：①(a,a)②(a,(a,a))③(a,((a,a),(a,a)))(3)分别构造(b)中各句子的一个最左推导和最右推导。3.4考虑文法G3.29[S]S→aSbS|bSaS|ε(1)讨论句子abab的最左推导，说明该文法是二义性的。(2)对于句子abab构造两个相应的最右推导。(3)对于句子abab构造两棵相应的分析树。(4)此文法所产生的语言是什么？3.5文法G3.30[S]为：S→Ac|aBA→abB→bc写出L(G3.30)的全部元素。3.6试描述由下列文法G[S]所产生的语言。(1)S→10S0|aAA→bA|a(2)S→SS|1A0A→1A0|ε(3)S→1A|B0A→1A|CB→B0|CC→1C0|ε(4)S→bAdcA→AS|a《编译原理与技术》练习题5(5)S→aSSS→a(6)A→0B|1CB→1|1A|0BBC→0|0A|1CC3.7设已给文法G3.31=(VN,VT,P,S)，其中：VN={S}VT={a1,a2,…,an,∨,∧,~,[,]}P={S→ai|i=1,2,…,n}∪{S→~S,S→[S∨S］,S→[S∧S］}，试指出此文法所产生的语言。3.8已知文法G3.32=({A,B,C},{a,b,c},A,P)，其中P由以下产生式组成：AabcAaBbcBbbBBcCbccbCCbaCaaBaCaa问：此文法表式的语言是什么？3.9已知文法G3.33[P]:P→aPQR|abRRQ→QRbQ→bbbR→bccR→cc证明aaabbbccc是该文法的一个句子。3.10构造一个文法，使其产生的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合。3.12已知语言L={anbbn|n≥1},写出产生语言L的文法。3.13写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头。(2)不允许0打头。3.14文法G3.34[S]为：S→Ac|aB,A→abB→bc该文法是否为二义的？为什么？（提示：找一个句子，使之有两棵不同的分析树。）3.15证明下述文法G3.35［〈表达式〉］是二义的：〈表达式〉→a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉→+|-|*|/3.16下面的文法产生a的个数和b的个数相等的非空a、b串S→aB|bAB→bS|aBB|bA→aS|bAA|a其中非终结符B推出b比a的个数多1个的串，A则反之。(1)证明该文法是二义的。(2)修改上述文法，不增加非终结符，使之成为非二义文法，并产生同样的语言。《编译原理与技术》练习题63.17考虑文法G3.36[R]R→R'|'R|RR|R*|(R)|a|b其中R'|'R表示R或R；RR表示R与R的连接；R*表示R的闭包。(1)证明此文法生成={a,b}上的除了和ε的所有正规表达式。(2)试说明此文法是二义性的。(3)构造一个等价的无二义性文法，该文法给出*、连接和|等运算符号的优先级和结合规则。3.18给出产生下述语言的上下文无关文法：(1){anbnambm|n,m≥0}。(2){1n0m1m0n|n,m≥0}。(3){cT|∈{a,b}*}，其中T是的逆。(4){w|w∈{a,b}+，且w中a的个数恰好比b多1}。(4){w|w∈{a,b}+，且|a|≤|b|≤2|a|}。(5){w|w是不以0开始的奇数集}。3.19设G=(VN,VT,P,S)为CFG，α1,α2,…,αn为V上的符号串，试证明：若α1α2…αnβ则存在V上的符号串β1,β2，…,βn，使β=β1β2…βn，且有aiβi(i=1,2,…,n)。3.20设G=(VN,VT,P,S)为CFG，α和β都是V上的符号串，且αβ，试证明：(1)当α的首符号为终结符号时，β的首符号也必为终结符号；(2)当β的首符号为非终结符号时，则α的首符号也必为非终结符号。3.21写出下列语言的3型文法：(a){an|n≥0}(b){anbm|n,m≥1}(c){anbmck|n,m,k≥1}3.22已知文法G3.37[S]：S→dABA→aA|aB→ε|Bb给出相应的正规式和等价的正规文法。3.23给出下列文法G[A]消除左递归后的等价文法：(1)A→BaC|CbBB→Ac|cC→Bb|b(2)A→Ba|Aa|cB→Bb|Ab|d(3)S→SA|AA→SB|B|(S)|()B→[S]|[](4)S→AS|bA→SA|a(5)S→(T)|a|εT→S|T,S《编译原理与技术》练习题7练习44.1证明：含有左递归的文法不是LL(1)文法。4.2对于文法G4.11[S]S→uBDzB→Bv|wD→EFE→y|F→x|(1)计算文法G4.11各非终结符的FIRST集和FOLLOW集，以及各产生式的SELLECT集。(2)判断该文法是否是LL(1)文法。(3)若不是LL(1)文法，则修改此文法,使其成为能产生相同语言的LL(1)文法。4.3已知布尔表达式文法G4.12[bexpr]bexpr→bexprorbterm|btermbterm→btermandbfactor|bfactorbfactor→notbfactor|(bexpr)|true|false改写文法G4.12为扩充的巴克斯范式，并为每个非终结符构造递归下降分析子程序。4.4已知用EBNF表示的文法G4.13[A]A→[BB→X]{A}X→(a|b){a|b}试用类C或类PASCAL语言写出其递归下降子程序。4.5已知文法G4.14[S]S→(L)|aL→L,S|S(1)消除文法G4.14的左递归，并为每个非终结符构造不带回溯的递归子程序。(2)经改写后的文法是否是LL(1)文法？给出它的预测分析表。(3)给出输入串(a,a)$的分析过程，并说明该符号串是否为文法G4.14的句子。4.6对于文法G4.15[R]《编译原理与技术》练习题8R→R'|'T|TT→TF|FF→F*|CC→(R)|a|b(1)消除文法的左递归。(2)计算文法G4.15各非终结符的FIRST集和FOLLOW集。(3)构造LL(1)分析表。4.7已知文法G4.16[A]A→aABe|aB→Bb|d(1)判断该文法是否为LL(1)文法。(2)写出输入串aade$的分析过程。《编译原理与技术》练习题9练习55.1设文法G5.10[E]为E→E+T|E-T|TT→T*F|T/F|FF→F↑P|PP→(E)|i求以下句型的短语、直接短语、素短语、句柄和最左素短语：（1）E-T/F+i（2）E+F/T-P↑i（3）T*(T-i)+P（4）(i+i)/i-i5.2根据下列优先关系矩阵计算其优先函数，并说明优先函数是否存在。SABabcS≯A≮≮≌≮≮B≌a≌≮≮≯b≯≯≯≯≯≌c≯5