编译原理作业

《编译原理》第一次作业参照答案一、以下正则表达式定义了什么语言（用尽可能简洁的自然语言描绘）b*(ab*ab*)*全部含有偶数个a的由a和b构成的字符串.c*a(a|c)*b(a|b|c)*|c*b(b|c)*a(a|b|c)*答案一：全部起码含有1个a和1个b的由a，b和c构成的字符串.答案二：全部含有子序列ab或子序列ba的由a，b和c构成的字符串.说明：答案一要比答案二更好，因为用自然语言描绘是为了便于和非专业的人员沟通，而非专业人员很可能不知道什么是“子序列”，所以对比较而言，答案一要更“自然”.二、设字母表∑={a,b}，用正则表达式（只使用a，b，，|，*，+，）描绘以下语言：不包含子串ab的全部字符串.b*a*不包含子串abb的全部字符串.b*(ab)*不包含子序列abb的全部字符串.b*a*ba*注意：对于子串（substring）和子序列（subsequence）的差别能够参照课本第119页方框中的内容.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第二次作业参照答案一、考虑以下NFA：这一NFA接受什么语言（用自然语言描绘）全部只含有字母a和b，而且a出现偶数次或b出现偶数次的字符串.结构接受同一语言的DFA.答案一（直接结构往常获得这一答案）：答案二（由NFA结构DFA获得这一答案）：二、正则语言补运算3.画出一个DFA，该DFA恰巧辨别全部不含011子串的全部二进制串.1.画出一个DFA，该DFA恰巧辨别全部不含011子串的全部二进制串.规律：结构语言L的补语言L’的DFA，能够先结构出接受L的DFA，再把这一DFA的接受状态改为非接受状态，非接受状态改为接受状态，就能够获得辨别L’的DFA.说明：在上述两题中的D状态，不论输入什么符号，都不行能再抵达接受状态，这样的状态称为“死状态”.在画DFA时，有时为了简洁起见，“死状态”及其相应的弧（上图中的绿色部分）也可不画出.2.再证明：对任一正则表达式R，必定存在另一正则表达式R'，使得L(R')是L(R)的补集.证明：依据正则表达式与DFA的等价性，必定存在辨别语言L(R)的DFA.设这一DFA为M，则将M的全部接受状态改为非接受状态，全部非接受状态改为接受状态，获得新的DFAM’.易知M’辨别语言L(R)的补集.再由正则表达式与DFA的等价性知必存在正则表达式R’，使得L(R’)是L(R)的补集.三、设有一门小小语言仅含z、o、/（斜杠）3个符号，该语言中的一个说明由/o开始、以o/结束，而且说明严禁嵌套.1.请给出单个正则表达式，它仅与一个完好的说明般配，除此以外不般配任何其余串.书写正则表达式时，要求仅使用最基本的正则表达式算子（，|，*，+，）.参照答案一：/o(o*z|/)*o+/思路：基本思路是除了最后一个o/，在说明中不可以出现o后边紧随着/的状况；还有需要考虑的是最后一个o/以前也能够出现若干个o.参照答案二（梁晓聪、梁劲、梁伟斌等人供给）：/o/*(z/*|o)*o/2.给出辨别上述正则表达式所定义语言确实定有限自动机（DFA）.你可依据问题直接结构DFA，不用运用机械的算法从上一小题的正则表达式变换获得DFA.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第三次作业参照答案一、考虑以下DFA的状态迁徙表，此中0，1为输入符号，A~H代表状态：01ABABACCDBDDAEDFFGEGFGHGD此中A为初始状态，D为接受状态，请画出与此DFA等价的最小DFA，并在新的DFA状态中注明它对应的原DFA状态的子集.说明：有些同学没有画出状态H，因为没法从初始状态抵达状态H.从适用上讲，这是没有问题的.可是，如果依据算法的步骤履行，最后是应当有状态H的.二、考虑全部含有3个状态（设为p，q，r）的DFA.设只有r是接受状态.至于哪一个状态是初始状态与本问题没关.输入符号只有0和1.这样的DFA总合有729种不一样的状态迁徙函数，因为对于每一状态和每一输入符号，可能迁徙到3个状态中的一个，所以总合有3^6=729种可能.在这729个DFA中，有多少个p和q是不可划分的（indistinguishable）解说你的答案.解：考虑对于p和q，在输入符号为0时的状况，在这类状况下有5种可能使p和q没法划分：p和q在输入0时同时迁徙到r（1种可能），或许p和q在输入0时，都迁徙到p或q（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和q（设p<q），使得从D的初始状态出发，经过p个a和q个a后抵达同一状态s，且s为接受状态.因为DFA每一步的迁徙都是确立的，所以从状态s出发，经过(q-p)个a，只好抵达状态s.考虑仅含有字母a，长度为p+p(q-p)的字符串T.T从初始状态出发，经过p个a抵达状态s，再经过(q-p)个a仍旧抵达s；相同，经过p(q-p)个a后仍旧抵达s.所以，从初始状态出发，经过p+p(q-p)个a后必然抵达状态s.因为p+p(q-p)=p(q-p+1)是合数，而s为接受状态，因此得出矛盾.原命题得证.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第四次作业参照答案一、用上下文没关文法描绘以下语言：1.定义在字母表∑={a,b}上，全部首字符和尾字符相同的非空字符串.aTa|bTb|a|baT|bT|说明：1.用T来产生定义在字母表∑={a,b}上的随意字符串；2.注意不要漏了单个a和单个b的状况.L={0i1j|i≤j≤2i且i≥0}.S0S1|0S11|3.定义在字母表∑={0,1}上，全部含有相同个数的

0和

1的字符串（包含空串）

.S0S1|1S0|SS|思路：分两种状况考虑.1)假如首尾字母不一样，那么这一字符串去掉首尾字母仍应当属于我们要定义的语言，所以有S0S1|1S0；假如首尾字母相同，那么这一字符串必然能够分红两部分，每一部分都属于我们要定义的语言，所以有SSS.二、考虑以下文法：aABeAAbc|bBd1.用最左推导（leftmostderivation）推导出句子abbcde.S==>aABe==>aAbcBe==>abbcBe==>abbcde2.用最右推导（rightmostderivation）推导出句子abbcde.S==>aABe==>aAde==>aAbcde==>abbcde画出句子abbcde对应的剖析树（parsetree）.三、考虑以下文法：aSbSaSS这一文法产生什么语言（用自然语言描绘）全部n个a后紧接m个b，且n>=m的字符串.证明这一文法是二义的.对于输入串aab，有以下两棵不一样的剖析树3.写出一个新的文法，要求新文法无二义且和上述文法产生相同的语言答案一：

.SaSb|TTaT|答案二：TS’aT|S’aS’b|~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第五次作业参照答案一、考虑以下文法：SaTUV|bVTU|UUU|bVV|cV写出每个非终端符号的FIRST集和FOLLOW集.FIRST(S)={a,b}FIRST(T)={,b}FIRST(U)={,b}FIRST(V)={,c}FOLLOW(S)={$}FOLLOW(T)={b,c,$}FOLLOW(U)={b,c,$}

FOLLOW(V)={b,c,$}二、考虑以下文法：S(L)|a除去文法的左递归.S(L)|aLSL’L’,SL’|结构文法的LL(1)剖析表.FIRST(S)={‘(‘FIRST(L),‘a’=}{‘(‘FIRST(L,‘a’}),=}{‘,’FOLLOW(S)={,‘,’,$‘’)’}FOLLOW(L)={‘)FOLLOW(L’}’)={‘)’}NON-TERMINALINPUTSYMBOL()a,$SS(L)SaLLSL’LSL’L’L’L’,SL’3.对于句子(a,(a,a))，给出语法剖析的详尽过程（参照课本228页的图）.MATCHEDSTACKINPUTACTIONS$(a,(a,a))$(L)$(a,(a,a))$outputS(L)(L)$a,(a,a))$(SL’)$a,(a,a))$outputLSL’(aL’)$a,(a,a))$outputSa(aL’)$,(a,a))$(a,SL’)$,(a,a))$outputL’,SL’(a,SL’)$(a,a))$(a,(L)L’)$(a,a))$outputS(L)(a,(L)L’)$a,a))$(a,(SL’)L’)$a,a))$outputLSL’(a,(aL’)L’)$a,a))$outputSa(a,(aL’)L’)$,a))$(a,(a,SL’)L’)$,a))$outputL’,SL’(a,(a,SL’)L’)$a))$(a,(a,aL’)L’)$a))$outputSa(a,(a,aL’)L’)$))$(a,(a,a)L’)$))$outputL’(a,(a,a)L’)$)$(a,(a,a))$)$outputL’(a,(a,a))$$三、考虑以下文法：SaSbS|bSaS|这一文法是不是LL(1)文法给出原因.这一文法不是LL(1)文法，因为S有产生式S，但FIRST(S)={a,b,}，FOLLOW(S)={a,b}，因此FIRST(S)∩FOLLOW(S)≠.依据LL(1)文法的定义知这一文法不是LL(1)文法.~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~~\(≧▽≦)/~《编译原理》第六次作业参照答案一、考虑以下文法：E’EEE+TETTTFTFFF*FaFb写出每个非终端符号的FIRST集和FOLLOW集.FIRST(E’)=FIRST(E)=FIRST(T)=FIRST(F)={a,b}FOLLOW(E’)={$}

FOLLOW(E)={+,$}FOLLOW(T)={+,$,a,b}

FOLLOW(F)={+,*,$,a,b}2.结构辨别这一文法全部活前缀（

viableprefixes）的LR(0)

自动机（参照课本节图）

.结构这一文法的SLR剖析表（参照课本节图）.STATEACTIONGOTOab+*$ETF0s4s51231s6accept2s4s5r2r273r4r4r4s8r44r6r6r6r6r65r7r7r7r7r76s4s5937r3r3r3s8r38r5r5r5r5r59s4s5r1r17给出SLR剖析器辨别输入串a+ab*的过程（参照课本节图）STACKSYMBOLSINPUTACTION(1)0a+ab*$shift(2)04a+ab*$reducebyFa(3)03F+ab*$reducebyTF(4)02T+ab*$reducebyET(5)01E+ab*$shift(6)016E+ab*$shift(7)0164E+ab*$reducebyFa(8)0163E+Fb*$reducebyTF(9)0169E+Tb*$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=+++AgBa=*5BBb=*21Bb=2CCc=*31Cc=3Dd=1对于输入串gbbabbccd结构带说明的剖析树（annotatedparsetree）.最后答案：34二、以下文法定义了二进制浮点数常量的语法例则：|LLLB|BB0|1试给出一个S属性的语法制导定义，其作用是求出该二进制浮点数的十进制值，并寄存在开始符号S有关系的一个综合属性value中。比如，对于输入串，S的value属性值结果应当是。要求在编写语法制导定义时，不得改写文法！拜见05级期末