编译原理作业答案

1、编译原理第次作业参考答案、下列正则表达式定义了什么语言(用尽可能简短的自然语言描述)1. b*(ab*ab*)*所有含有偶数个a的由a和b组成的字符串.2. 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, ?, | , *,

2、 +,)描述下列语言:1.不包含子串ab的所有字符串.b*a*不包含子串abb的所有字符串.b*(ab)*不包含子序列b*a*ba*注意：关于子串(2.3.abb的所有字符串.substring )和子序列(subsequenee )的区别可以参考课本第119页方框中的内容.(仝w "( W )/仝"( 仝"(仝"( 仝"( 仝"( 仝"( 仝编译原理第次作业参考答案、考虑以下NFA1. 这一 NFA接受什么语言(用自然语言描述)所有只含有字母a和b,并且a出现偶数次或b出现偶数次的字符串.2. 构造接受同一语言的 DFA.

3、答案一(直接构造通常得到这一答案)：startstartb答案二（由NFA构造DFA得到这一答案）：©b b；daa /o二、正则语言补运算3.画出一个DFA该DFA恰好识别所有不含-0start/一 b011子串的所有二进制串>-11.画出一个DFA该DFA恰好识别所有不含011子串的所有二进制串1start规律：构造语言L的补语言L'的DFA可以先构造出接受 L的DFA再把这一 DFA的接受状态改为非接受 状态，非接受状态改为接受状态，就可以得到识别L'的DFA.说明：在上述两题中的 D状态，无论输入什么符号，都不可能再到达接受状态，这样的状态称为“死状态”

4、.在画DFA时，有时为了简明起见，“死状态”及其相应的弧(上图中的绿色部分)也可不画出.2.再证明：对任一正则表达式R, 定存在另一正则表达式R'，使得L(R')是L(R)的补集.证明：根据正则表达式与 DFA的等价性，一定存在识别语言 L(R)的DFA.设这一 DFA为M则将M的所有 接受状态改为非接受状态，所有非接受状态改为接受状态，得到新的DFA M .易知M识别语言L(R)的补集.再由正则表达式与 DFA的等价性知必存在正则表达式 R',使得L(R')是L(R)的补集.z、o、/ (斜杠)3个符号，该语言中的一个注释由/ o开始、以0/结束，并且注释设有

5、一门小小语言仅含禁止嵌套.1. 请给出单个正则表达式，它仅与一个完整的注释匹配，除此之外不匹配任何其他串要求仅使用最基本的正则表达式算子(？，| , *，+,).参考答案一：/o(o*z|/)*o+/思路：基本思路是除了最后一个o/，在注释中不能出现0后面紧跟着/的情况；还有需要考虑的是最后个o/之前也可以出现若干个o.参考答案二(梁晓聪、梁劲、梁伟斌等人提供).书写正则表达式时,2. 给出识别上述正则表达式所定义语言的确定有限自动机(械的算法从上一小题的正则表达式转换得到DFA.:/o/*(z/*|o)*o/DFA .你可根据问题直接构造DFA不必运用机sta 1cr cr O '（

6、仝 P ）/ （仝W ）/（仝W ）/（仝w ）/（仝w "-（仝 p ）/（仝w "（仝w "编译原理第三次作业参考答案一、考虑以下DFA的状态迁移表，其中 0, 1为输入符号，AH代表状态:其中A为初始状态, 状态的子集.ABABACCDBDDAEDFFGEGFGHGDD为接受状态，请画出与此DFA等价的最小DFA并在新的DFA状态中标明它对应的原 DFA说明：有些同学没有画出状态果根据算法的步骤执行，最后是应该有状态H,因为无法从初始状态到达状态H.从实用上讲，这是没有问题的.不过，如H的.二、考虑所有含有3个状态（设为P, q, r ）的DFA.设只有r是

7、接受状态.至于哪一个状态是初始状态与本问题 无关.输入符号只有0和1.这样的DFA总共有729种不同的状态迁移函数， 号，可能迁移到 3个状态中的一个，所以总共有3人6=729种可能.可区分的（indistinguishable）解释你的答案.解：考虑对于P和q，在输入符号为0时的情况，在这种情况下有 0时同时迁移到r （1种可能），或者P和q在输入0时，都迁移到 类似地，在输入符号为 1时，也有5种可能使P和q无法区分.如果再考虑r的迁移，r的任何迁移对问题没有影响.于是r在输入0和输入1时各有3种可能的迁移，总共 有3*3=9种迁移.因此，总共有 5*5*9=225个DFA其中p和q是不可

8、区分的.因为对于每一状态和每一输入符 在这729个DFA中，有多少个 P和q是不5种可能使P和q无法区分：P和q在输入 P或q （4种可能）.三、证明：所有仅含有字符a，且长度为素数的字符串组成的集合不是正则语言证明：用反证法.假设含有素数个a的字符串组成的集合是正则语言，则必存在一个 的状态数有限，而素数有无限多个，所以必存在两个不同的素数DFA接受这一语言，设此 DFA为D.由于D P和q （设P<q）,使得从D的初始状态出发，s经过P个a和q个a后到达同一状态 s,且s为接受状态.由于DFA每一步的迁移都是确定的，所以从状态 出发，经过（q-P）个a，只能到达状态 s.考虑仅含有字

9、母 a，长度为p+p（q-p）的字符串T. T从初始状态出发，经过a仍然到达s;同样，经过P（q-P）状态 s.由于 P+P（q-p）=p（q-p+1）P个a到达状态s，再经过（q-P）个 个a后仍然到达s.因此，从初始状态出发，经过 P+P（q-P）个a后必然到达 是合数，而s为接受状态，因而得出矛盾 .原命题得证.（仝w）/（ 仝w ）/（ w ”仝w）/（ 仝w）/（ 仝w）/（ 仝w）/（ 仝w）/（ 仝编译原理第四次作业参考答案一、用上下文无关文法描述下列语言:1.定义在字母表刀=a, b上，所有首字符和尾字符相同的非空字符串.S ? aTa | bTb | a | bT ? aT

10、| bT | ?说明：1. 用T来产生定义在字母表刀 =a, b上的任意字符串；2. 注意不要漏了单个 a和单个b的情况.L=0i1j|i <j <2i 且 i >0.S ? 0S1 | 0S11 | ?定义在字母表刀=0, 1上，所有含有相同个数的 0和1的字符串（包括空串）.S ? 0S1 |1S0|SS | ?思路：分两种情况考虑.1）如果首尾字母不同，那么这一字符串去掉首尾字母仍应该属于我们要定义的语言，因此有S ? 0S1 | 1S0；2）如果首尾字母相同，那么这一字符串必定可以分成两部分，每一部分都属于我们要定义的语言，因此 有 S ? SS.二、考虑以下文法：S

11、?aABeA ? Abc|bB ? d.3.用最左推导(leftmost derivation )推导出句子S => aABe => aAbcBe => abbcBe => abbcde 用最右推导(rightmost derivation)推导出句子S => aABe => aAde => aAbcde => abbcde 画出句子 abbcde对应的分析树(parse tree ).abbcde.abbcde.SA B eAbed三、考虑以下文法：S ? aSbS ? aSS ? ?1. 这一文法产生什么语言（用自然语言描述）所

12、有n个a后紧接m个b,且n>=m的字符串.2. 证明这一文法是二义的.对于输入串aab,有如下两棵不同的分析树3. 写出一个新的文法，要求新文法无二义且和上述文法产生相同的语言 答案一：S ? aSb | TT ? aT | ?答案二：S ? TS 'T ? aT | ? S' ? aS ' b | ?(仝w"-( 仝w"( 仝w "-( 仝w"-( 仝w"( 仝w"( 仝w"编译原理第五次作业参考答案一、考虑以下文法：S?aTUV|bVT ? U | UUU ? ? | bVV ? ? | c

13、V写出每个非终端符号的FIRST集和FOLLOW!.FIRST(S)=a, b FIRST(T)=?, b FIRST(U)= ?, b FIRST(V)=?, c二、考虑以下文法:S ? (L) | aL ? L, S | S1.FOLLOW(S)=$ FOLLOW(T)= b, c, $ FOLLOW(U)= b, c, $ FOLLOW(V)=b, c , $消除文法的左递归.S ? (L) | aL ? SL 'L' ? ,SL '| ?2.构造文法的LL(1)分析表.FIRST(S) = ( ,a' FIRST(L) = ( ,a' FIRST

14、(L ' ) = , ', ?FOLLOW(S) = $', ' ,') ' FOLLOW(L) = ') ' FOLLOW(L ' ) = ') ' NON-TERMINALINPUT SYMBOL()aJ$SS ? (L)S ? aLL ? SL 'L ? SL 'L'L' ? ?L'? ,SL '对于句子(a, (a, a)，给出语法分析的详细过程(参照课本228页的图).MATCHEDSTACKINPUTACTIONS$(a, (a, a)$(L)$(

15、a, (a, a)$out put S ? (L)(L)$a, (a, a)$(SL' )$a, (a, a)$out put L ? SL '(aL' )$a, (a, a)$out put S ? a(aL' )$,(a, a)$(a,SL ' )$,(a, a)$out put L ' ? ,SL '(a,SL' )$(a, a)$(a,(L)L ' )$(a, a)$out put S ? (L)(a,(L)L ' )$a, a)$(a,(SL'儿')$a, a)$out put L ? S

16、L '(a,(aL' )L ' )$a, a)$out put S ? a(a,(aL' )L ' )$,a)$(a,(a,SL ' )L ' )$,a)$out put L ' ? ,SL '(a,(a,SL'儿 )$a)$(a,(a,aL' )L ' )$a)$out put S ? a(a,(a,aL' )L ' )$)$(a,(a,a儿)$)$out put L ' ? ?(a,(a,a)L' )$)$(a,(a,a)$)$out put L ' ?

17、?(a,(a,a)$三、考虑以下文法：S ? aSbS | bSaS | ?这一文法是否是 LL(1)文法给出理由.这一文法不是 LL(1)文法，因为 S有产生式 S ? ?，但FIRST(S) = a, b, ?, FOLLOW(S) = a, b，因而FIRST(S) n FOLLOW(S产？.根据LL(1)文法的定义知这一文法不是LL(1)文法.(仝w"(仝w"( 仝w "-( 仝w"-(仝w"( 仝w"( 仝w"(仝 W )/编译原理第六次作业参考答案、考虑以下文法：(0) E ' ? E(1) E ? E+

18、T(2) E ? T(3) T ? TFT ? F(5) F ? F*(6) F ? a(7) F ? b1. 写出每个非终端符号的FIRST集和FOLLOWI.FIRST(E' )= FIRST(E)= FIRST(T)= FIRST(F)=a, bFOLLOW(E )=$ FOLLOW(E)=+, $ FOLLOW(T)=+, $, a, b FOLLOW(F)= +, *, $, a, b2. 构造识别这一文法所有活前缀(viable prefixes )的LR(0) 自动机(参照课本节图)17STATEACTIONGOTOab+*$ETF0s4s51231s6accept2s4

19、s5r2r273r4r4r4s8r44r6r6r6r6r65r7r7r7r7r76s4s5937r3r3r3s8r38r5r5r5r5r59s4s5r1r173.构造这一文法的SLR分析表（参照课本节图）12IQE9E-TE今TTTFTFF尸FXFbE* T*FF今T科FaF->-bA I；F沁E| 口ETEE沁一T*accepta15F”TXF刁*bTTF-FTP： 曲JjsF今F"EE+TT 今T<FF严卜今F今七ETE+TTTFF产Fb19164.给出SLR分析器识别输入串a+ab*的过程（参照课本节图）STACKSYMBOLSINPUTACTION(1)0a+ab

20、*$shift04a+ab*$reduce by F?a03F+ab*$reduce by T?F02T+ab*$reduce by E?T(5)01E+ab*$shift016E+ab*$shift0164E+ab*$reduce by F?a(8)0163E+Fb*$reduce by T?F(9)0169E+Tb*$shift(10)01695E+Tb*$reduce by F?b(11)01697E+TF*$shift(12)016978E+TF*$reduce by F?F*(13)01697E+TF$reduce by T?TF(14)0169E+T$reduce by E?E+T

21、(15)01E$accept（仝 p"-（仝w"（仝w"-（仝w"（仝w "-（仝 p"-（仝w"（仝w"编译原理第八次作业参考答案语法规则语义规则S? ABCD=+ + +A ? gBa=* 5B ? Bb=* 2B ? b=2C ? Cc=* 3C ? c=3D ? d=1一、考虑以下语法制导定义（Syn tax Directed Defini tion）：对于输入串gbbabbccd构造带注释的分析树（annotated parse tree ）.最终答案：34二、以下文法定义了二进制浮点数常量的语法规则：S

22、 ? | LL ? LB | BB ? 0 | 1试给出一个S属性的语法制导定义，其作用是求出该二进制浮点数的十进制值，并存放在开始符号 S相关联的一个综合属性value中。例如，对于输入串，S的value属性值结果应该是。要求在编写语法制导定义时，不得改写文法！参见05级期末考答案.（他答案3注意遠类脸UM常存4若种合理的答杂在语法制导S文屮.B的Stt值V屛W工戒B祁対0戍1本CI的tt; L冇3 -tHftfft： rrLts-egzsal 记录L作为格数那分时的倩. 三工4 0二L匚E 记录L作勺小数部时的值. lengtL Ll2A L ft >/小数岀m时的度T便il算B向右

23、朋11时-ri-tion的值.语法规则语乂规蝸5 T L1" LcS”vsl止总 二 工亠.int三寸芒a2 + L；, tr邑烂工.1:九5 T LSv忑111丘=L * intigxaIL f L1BL*iTi=wyra丄 = Lt, intgrsi * 二 + E，吕Im总L-丄wng二？1 - Ijl.丄mngth 十 1L ” fracuiiHii = l： . f r&ction + 5 .vaiu* /L -> EL * integral 3, vciluL »lenijh = 1I. - f 工 au= j-on = 兰-ya 二 MP /B 0E .Veil list = <)E T 1= 1片 种更特帶同语（餵聊