编译原理习题目录第一章练习(b)给出句子的分析树(c)给出句子的最左推导给出每次推导后得到的句型的短语,直接短语S(L)(L,S)(S,S)(a,S)(a,(L))短语(L)L,SSaa(L,S)S,Sa,Sa,(L)(S,S)(a,S)(a,(L))(L)直接(L)L,SSaa短语(L)(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a))短语aaaaa,(L,S)a,(S,S)a,(a,S)a,(a,a)(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a))L,SSaa(L,S)S,Sa,Sa,a(S,S)(a,S)(a,a)直接aaaa短语L,SSaaa(d)构造各个句子的最右推导.最右推导(规范推导)(e)这个文法产生的语言是什么?a(a)(a,a)((a,a),a)......a和数据元素为a的广义表全体1.2考虑文法SaSbS|bSaS|(a)试说明此文法是二义性的.(定义1.5)如果一文法的句子存在两棵分析树,则该句子是二义性的.如果一文法包含二义性的句子,则这个文法是二义性的.可以从句子abab有两个不同的最左推导来说明.SaSbSabSabaSbSababSabablmlmlmlmlmSaSbSabSaSbSabaSbSababSabablmlmlmlmlm句子abab有两个不同的最左推导,该句子是二义性的.所以此文法是二义性的.(b)对于句子abab构造两个相应的最右推导.SaSbSaSbabSaSbabSabababrmrmrmrmrmSaSbSaSbaSbSaSbaSbaSbabababrmrmrmrmrm(c)对于句子abab构造两个相应的分析树.SSaSbSaSbSbSaSaSbS(d)此文法产生的语言是什么?由相同个数的a和b组成的字符串.(b)试对于句子not(trueorfalse)构造一棵分析树.(c)试说明此文法产生的语言是全体布尔表达式.练习:长度为n的字符串,分别有多少个前缀,后缀,子串,真前缀,子序列?EE+TT*Fi第三章练习(d)0*10*10*10*3.4对于下列语言分别写出它们的正规表达式:(a)英文字母组成的所有符号串,要求符号串中顺序包含五个元音字母.(c)没有重复出现的数字的数字符号串全体.(e)带有偶数个0和奇数个1的由0和1组成的符号串全体.练习:1.令A,B和C是任意正规式,证明以下关系成立:A|A=A(A*)*=A*A*=|AA*(AB)*A=A(BA)*(A|B)*=(A*B*)*=(A*|B*)*A=b|aA当且仅当A=a*b3.6给出接受下列在字母表{0，1}上的DFA。（a）所有以00结束的符号串的集合；（b）所有具有三个0的符号串的集合。3.7构造等价于下列正规表达式的有限自动机.(a)10|(0|11)0*1(b)((0|1)*|(11))*3.8给定右线性文法G:S0S|1S|1A|0BA1C|１B0C|1C0C|1C|0|1试求一个等价的左线性文法G’.3.9-3.11(d)(a|b)*abb(a|b)*3.13对于下列正规表达式构造最小状态的DFA.(b)(a|b)*a(a|b)(a|b)4.4考虑文法RR‘|’R|RR|R*|(R)|a|b(a)试说明此文法生成在符号a和b之上的所有正规表达式.(b)试说明此文法是二义性的.(c)试构造一个等价的无二义性文法.4.5dangling-else文法:stmtifexprthenstmt|matched-stmtmatched-stmtifexprthenmatched-stmtelsestmt|other试说明此文法是二义性的。4.3对于下面的每一个语言设计一个文法。试问其中哪些语言是正规的？(a)使得在每一个0后至少立即跟随一个1的由0和1组成的符号串的全体。(d)所有形如xy而xy的由0和1组成的符号串。4.5(a)给出一个上下文无关产生式的集合，使它与AB*a(C|D)生成同样的符号串集合。AB’aEB’BB’|EC|D(b)是否可以把ET|E+T写为：ET{+T}是否可以把ET|E+T|E-T写为：ET{(+|-T)}ET{+T}等价于ETT’T’+TT’|4.7对于文法SaSbS|bSaS|构造一个带有回溯的递归下降分析器.问能否构造一个预测分析器.4.9对于文法bexprbexprorbterm|bterm