编译原理作业答案

计算机科学系2010春天学期《编译原理》第一次作业参照答案一、以下正则表达式定义了什么语言(用尽可能简洁的自然语言描绘）?1.b*（ab＊ab＊）＊全部含有偶数个a的由a和b组成的字符串。2.c*a（a|c)＊（a｜b｜＊|c*b（b|c)*a(a|b｜c)*答案一：全部最少含有1个a和1个b的由，b和c组成的字符串.答案二：全部含有子序列ab或子序列ba的由a，b和c组成的字符串.说明：答案一要比答案二更好,因为用自然语言描绘是为了便于和非专业的人员沟通，而非专业人员很可能不知道什么是“子序列”,所以比较较而言答案一要更“自然”。二、设字母表={a,b，b,，|，*,+，？)描绘以下语言：1.不包含子串ab的全部字符串。＊a*2.不包含子串abb的全部字符串。＊(ab？)＊3.不包含子序列abb的全部字符串。＊a*b？a＊注意：对于子串（substring）和子序列(subsequence）的差别能够参照课本第119页方框中的内容.~\(≧▽≦)/～～\(≧▽≦（≧▽≦)/～（≧▽≦（≧▽≦)/~～\(≧▽≦)/~~\(≧▽≦)/~～（≧▽≦)/～《编译原理》第二次作业参照答案一、考虑以下NFA:1.这一NFA接受什么语言（用自然语言描绘）？全部只含有字母a和b，而且a出现偶数次或b出现偶数次的字符串。2.结构接受同一语言的DFA.答案一（直接结构平时获得这一答案）：1计算机科学系2010春天学期答案二由NFA结构DFA获得这一答案）：二、正则语言补运算3.画出一个DFA，该恰巧鉴识全部不含011子串的全部二进制串.1.画出一个DFA，该恰巧鉴识全部不含011子串的全部二进制串。2计算机科学系2010春天学期规律:结构语言L的补语言L’的DFA，能够先结构出接受L的DFA，再把这一DFA的接受状态改为非接受状态，非接受状态改为接受状态,就能够获得鉴识L'的DFA.说明：在上述两题中的D状态，不论输入什么符号，都不行能再抵达接受状态,这样的状态称为“死状态"。在画时,有时为了简洁起见，“死状态”及其相应的弧（上图中的绿色部分)也可不画出。2.再证明：对任一正则表达式R,必定存在另一正则表达式’，使得L(R'）是L(R)的补集。证明：依据正则表达式与DFA的等价性,必定存在鉴识语言L(R)的DFA.设这一DFA为M的全部接受状态改为非接受状态,全部非接受状态改为接受状态，获得新的DFAM'.易知’鉴识语言（R)的补集。再由正则表达式与的等价性知必存在正则表达式R',使得L(R')是L(R）的补集.三、设有一门小小语言仅含z、o、/（斜杠）3个符号，该语言中的一个说明由/o开始、以o/结束，而且说明严禁嵌套。1.请给出单个正则表达式,它仅与一个完好的说明般配，除此以外不般配任何其余串。书写正则表达式时,要求仅使用最基本的正则表达式算子(｜，＊，+参照答案一：/o（o*z|/）＊o+/思路：基本思路是除了最后一个o/o后边紧随着/的状况;还有需要考虑的是最后一个o/以前也能够出现若干个。参照答案二（梁晓聪、梁劲、梁伟斌等人供给）：/o/＊（z/*|o)*o/2.给出鉴识上述正则表达式所定义语言确实定有限自动机（DFA你可依据问题直接结构DFA，不用运用机械的算法从上一小题的正则表达式变换获得DFA.～\(≧▽≦)/~～\(≧▽≦）/～~\(≧▽≦)/～~\(≧▽≦）/~~\(≧▽≦）/～～（≧▽≦)/~~\(≧▽≦（≧▽≦)/~《编译原理》第三次作业参照答案一、考虑以下DFA的状态迁徙表此中，1为输入符号,A～H代表状态:3计算机科学系2010春天学期01ABABACCDBDDAEDFFGEGFGHGD此中A为初始状态，D为接受状态，请画出与此DFA等价的最小DFA,并在新的DFA状态中注明它对应的原DFA状态的子集。说明有些同学没有画出状态H,因为没法从初始状态抵达状态H。从适用上讲，这是没有问题的。可是，如果依据算法的步骤履行，最后是应当有状态H的。二、考虑全部含有3个状态(设为，q，r）的DFA.设只有r是接受状态。至于哪一个状态是初始状态与本问题没关.输入符号只有0和1.这样的总合有729种不同样的状态迁徙函数，因为对于每一状态和每一输入符号,可能迁徙到3个状态中的一个，所以总合有3^6=729种可能。在这729个DFA中，有多少个p和q是不可划分的(indistinguishable）？解说你的答案。解考虑对于p和在输入符号为0时的状况，在这类状况下有5种可能使p和q没法划分：p和q在输入0时同时迁徙到r(1种可能），或许p和q在输入0时，都迁徙到p或（4种可能）。近似地，在输入符号为1时，也有5种可能使p和q没法划分.假如再考虑r的迁徙，r的任何迁徙对问题没有影响。于是r在输入0和输入1时各有3种可能的迁徙总合有3*3=9种迁徙。所以，总合有5*5*9=225个DFA，此中p和q是不行划分的。三、证明：全部仅含有字符a，且长度为素数的字符串组成的会合不是正则语言.证明:用反证法。假定含有素数个a的字符串组成的会合是正则语言，则必存在一个DFA接受这一语言，设此DFA为D.因为D的状态数有限，而素数有无穷多个，所以必存在两个不同样的素数p和（设〈qD的初始状态出发，经过p个a和q个a后抵达同一状态s，且s为接受状态。因为DFA每一步的迁徙都是确立的，所以从状态s出发，经过(q—）个a,只好抵达状态s.考虑仅含有字母a，长度为p+p(q-p)的字符串T.T从初始状态出发，经过p个a抵达状态s，再经过(q-p）个a仍旧抵达s；相同，经过（q-p)个a后仍旧抵达s.所以，从初始状态出发，经过p+p（—p）个a后必然抵达状态s。因为p+p（—p)=p（—p+1)是合数，而s为接受状态，因此得出矛盾。原命题得证.~\(≧▽≦（≧▽≦)/～～（≧▽≦)/~～\(≧▽≦）/～～（≧▽≦）/～~\(≧▽≦)/～～\(≧▽≦)/~4计算机科学系2010春天学期（≧▽≦）/～《编译原理》第四次作业参照答案一、用上下文没关文法描绘以下语言：1.定义在字母表={a,b｝上，全部首字符和尾字符相同的非空字符串。SaTa｜bTb|a｜bTaT｜bT|?说明：。用T来产生定义在字母表={a,b｝上的随意字符串；。注意不要漏了单个a和单个b的状况。2.L=｛0ij|ij2i且i0}。S0S1｜0S11|?3.定义在字母表｛0,1}上，全部含有相同个数的0和1的字符串（包含空串）.S0S1｜1S0|SS|?思路:分两种状况考虑。1)假如首尾字母不同样，那么这一字符串去掉首尾字母仍应当属于我们要定义的语言所以有S0S1｜1S0；2)假如首尾字母相同，那么这一字符串必定能够分红两部分，每一部分都属于我们要定义的语言，所以有SSS。二、考虑以下文法：SaABeAAbc|bBd1.用最左推导(leftmostderivation）推导出句子abbcde。S==〉aABe==>aAbcBe==〉abbcBe==>abbcde2.用最右推导（rightmostderivation）推导出句子abbcde.S==〉aABe==〉aAde==>aAbcde==>abbcde3.画出句子abbcde对应的解析树（parsetree三、考虑以下文法:SaSbSaSS1.这一文法产生什么语言（用自然语言描绘）？全部n个a后紧接m个，且n>=m的字符串.2.证明这一文法是二义的.对于输入串aab，有以下两棵不同样的解析树5计算机科学系2010春天学期3.写出一个新的文法，要求新文法无二义且和上述文法产生相同的语言.答案一:SaSb｜TTaT｜答案二：STS’TaT|’aSb|（≧▽≦)/～（≧▽≦）/~～（≧▽≦）/～（≧▽≦)/~～\(≧▽≦）/～～\(≧▽≦）/～~\(≧▽≦)/～《编译原理》第五次作业参照答案一、考虑以下文法：SaTUV|bVTU|UUU|bVV|cV写出每个非终端符号的FIRST集和集。FIRST（S)=｛a,b｝FIRST(T)=｛，｝FIRST(U）={，b}FIRST（V)={c}FOLLOW(S)=｛＄｝FOLLOW(T）={b，c,＄}FOLLOW（U)=｛b,c,＄｝FOLLOW（），c,＄}二、考虑以下文法：S(L）｜aL，S｜S1.除去文法的左递归.S（L)|aLSL’L',SL'｜2.结构文法的LL(1)解析表.FIRST(S）=｛‘，(a’FIRST（L)=,‘’)={‘,’FOLLOW（）={’,,FOLLOW(L)={‘’){NON—TERMINALINPUTSYMBOL（)a，$6计算机科学系2010春天学期SS(L)SaLLSL'LSL’’L'’,SL’3.对于句子(a,（a,a,给出语法解析的详尽过程（参照课本228页的图。21MATCHEDSTACKINPUTACTIONS$（a，（a，a))＄（）＄(a，（a,a）)＄outputS(L）(L)$a,(a,a）)$（SL')$a，(a，a))$outputLSL'（aL)$a,(a，a）)$outputSa（a,（a,a$（a,SL$,(a,a)）$outputL'，SL’(a，SL)＄（a，a$（a,(L）(a，a）)$outputS(L）（，(））$a，a$(a，(SL')L')$a,a))$outputLSL’(a,(aLa，a)）＄outputSa（a,（aL')＄,a(a，(a，SLL'）＄,a）)$outputL',SL’（，(a，SLL')＄a)）＄（a,（，aLL'）$a）)$outputSa（，(a,a）＄）)＄(a,（a,a）＄)）＄outputL’(a,(a,a)）＄（a,(a,a)）$）＄outputL’(a，a)）$＄三、考虑以下文法：SaSbS|bSaS|这一文法是不是LL(1）文法？给出原因.这一文法不是LL（1）文法，因为S有产生式S，但FIRST(S）={a，b，},FOLLOW（）=｛，b}，因此FIRST（S)∩FOLLOW（）≠。依据文法的定义知这一文法不是LL(1）文法.～（≧▽≦）/~～（≧▽≦）/～~\(≧▽≦)/～~\(≧▽≦)/～～\(≧▽≦）/～~\(≧▽≦)/～~\(≧▽≦）/~~\(≧▽≦)/~《编译原理》第六次作业参照答案一、考虑以下文法：(0)’E(1）EE+T(2）ET(3)TTF(4）TF（5)F＊7计算机科学系2010春天学期（6)Fa(7)Fb。写出每个非终端符号的FIRST集和FOLLOW集。FIRST(E)=FIRST（E)=FIRST(T)=FIRST(F=｛a,b}FOLLOW(E={$｝FOLLOW(E）={+,$}FOLLOW（T)={+，＄，a,b｝FOLLOW（）=｛+,＊，$，a,｝2.结构鉴识这一文法全部活前缀（viableprefixes）的LR(0）自动机（参照课本4.6。2节图4.313.结构这一文法的解析表（参照课本节图。37STATEACTIONGOTOab+＊$ETF0s4s51231s6accept2s4s5r2r273r4r4r4s8r44r6r6r6r6r65r7r7r7r7r76s4s5937r3r3r3s8r38r5r5r5r5r59s4s5r1r174.给出解析器鉴识输入串a+ab*的过程（参照课本节图4.38)8计算机科学系2010春天学期STACKSYMBOLSINPUTACTION（）0a+ab*$shift(2）04a+ab＊$reducebyFa（）03F＊＄reducebyTF（4)02T＊＄reducebyET（5)01E＊＄shift(6）016E+ab＊＄shift(7）0164E+ab*$reducebyFa(8)0163E+Fb＊$reducebyTF(9)0169E+T＊＄shift(10）01695E+Tb＊$reducebyFb(11)01697E+TF＊＄shift（12）016978E+TF＊＄reducebyFF*（13）01697E+TF$reducebyTTF(14)0169E+T$reducebyEE+T（15）01E$accept～\(≧▽≦（≧▽≦）/~～\(≧▽≦）/～～（≧▽≦）/～～\(≧▽≦）/～～\(≧▽≦）（≧▽≦）/～～（≧▽≦)/～《编译原理》第八次作业参照答案一、考虑以下语法制导定义(SyntaxDirectedDefinition）:语法例则语义规则SABCD。val=A.val+B.val+。val+。valAgBaA。val=B。val*5B1b。val=B1。val＊2BbB.val=2C1cC.val=.val*3Cc。val=3DdD。val=1对于输入串gbbabbccd结构带说明的解析树（annotatedparsetree）.最后答案:34二、以下文法定义了二进制浮点数常量的语法例则：SL.L|LLLB|BB0｜1试给出一个S属性的语法制导定义其作用是求出该二进制浮点数的十进制值并寄存在开始符号S有关系的一个综合属性value中。比方对于输入串101.101的value属性值结果应当是5.625定义时不得改写文法！拜见05级期末考答案.9计算机科学系2010春天学期三