编译原理第3章 习题解答

第三章1、L(G[S])={ abc }2、L(G[N])={ n位整数或空字符串| n>0 }3、G[E]：E—>E+D | E-D | DD—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、L(G[Z])={ a n b n | n>0 }5、(1) 考虑不包括“0”的情况G[S]：S—>0S | ABC | 2 | 4| 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8考虑包括“0”的情况：G[S]：S—>AB | CB—>AB | CA—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>0 | 2 | 4 | 6 | 8(2)方法1：G[S]：S—> ABC | 2 | 4 | 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8方法2：G[S]：S—>AB | CB—> AB | 0B | C | 0A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>2 | 4 | 6 | 86、设<表达式>为E，<项>为T，<因子>为F，注：推导过程不能省略，以下均为最左推导(1) E => T => F => i(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I7、<表达式><表达式>*<表达式><表达式>+<表达式>i i i<表达式><表达式>+<表达式>i <表达式>*<表达式>i i8、是有二义性的，因为句子abc 有两棵语法树（或称有两个最左推导或有两个最右推导）最左推导1：S => Ac => abc最左推导2：S => aB => abc9、(1)(2) 该文法描述了变量a 和运算符+、*组成的逆波兰表达式10、(1) 该文法描述了各种成对圆括号的语法结构(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导：最左推导1：S => S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()()最左推导2：S => S(S)S => S(S)S(S)S => (S)S(S)S => ()S(S)S => ()(S)S => ()()S => ()()11、(1) 因为从文法的开始符E 出发可推导出E+T*F ，推导过程如下：E => E+T => E+T*F ，所以E+T*F 是句型。

第3章习题3-1 试构造一右线性文法,使得它与如下得文法等价S→AB A→UT U→aU|a D→bT|b B→cB|c 并根据所得得右线性文法,构造出相应得状态转换图。

3-2 对于如题图3-2所示得状态转换图(1) 写出相应得右线性文法;(2) 指出它接受得最短输入串;(3) 任意列出它接受得另外4个输入串;(4) 任意列出它拒绝接受得4个输入串。

3-3 对于如下得状态转换矩阵:(1) 分别画出相应得状态转换图;(2) 写出相应得3型文法;(3) 用自然语言描述它们所识别得输入串得特征。

3-4 将如下得NFA确定化与最小化:3-5 将如题图3-5所示得具有ε动作得NFA确定化。

题图3-5 具有ε动作得NFA3-6 设有文法G[S]:S→aA A→aA|bB B→bB|cC|c C→cC|c 试用正规式描述它所产生得语言。

3-7 分别构造与如下正规式相应得NFA。

(1) ((0* |1)(1* 0))*(2) b|a(aa*b)*b3-8 构造与正规式(a|b)*(aa|bb)(a|b)*相应得DFA。

第3章习题答案3-1 解:根据文法知其产生得语言就是:L[G]={a m b n c i| m,n,i≧1}可以构造与原文法等价得右线性文法:S→aA A→aA|bB B→bB|cC|c C→cC|c 其状态转换图如下:3-2 解:(1) 其对应得右线性文法就是G[A]:A →0D B→0A|1C C→0A|1F|1D→0B|1C E→0B|1C F→1A|0E|0(2) 最短输入串为011(3) 任意接受得四个输入串为:0110,0011,000011,00110(4) 任意拒绝接受得输入串为:0111,1011,1100,10013-3 解:(1) 相应得状态转换图为:(2) 相应得3型文法为:(ⅰ) S→aA|bS A→aA|bB|b B→aB|bB|a|b(ⅱ) S→aA|bB|a A→bA|aC|a|b B→aB|bC|b C→aC|bC|a|b(ⅲ) S→aA|bB|b A→aB|bA|a B→aB|bB|a|b(ⅳ) S→bS|aA A→aC|bB|a B→aB|bC|b C→aC|bC|a|b(3) 用自然语言描述得输入串得特征为:(ⅰ) 以任意个(包括0个)b开头,中间有任意个(大于1)a,跟一个b,还可以有一个由a,b组成得任意字符串。

3.3.2, 3.3.6, 3.3.7, 3.3.8, 3.3.9,3.6.3, 3.6.4, 3.6.53.7.1, 3.7.2, 3.7.33.8.1, 3.8.23.9.3《编译原理》（龙书）第三章答案3.3.2 描述下列正则表达式代表的语言。

a) a(a|b)*ab) ((ε|a)b*)*c) (a|b)*a(a|b)(a|b)d) a*ba*ba*ba*e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*答案(a)由a开头并结尾的由a和b构成的字符串(b)由a和b构成的字符串(c)倒数第三位为a的由a和b构成的字符串(d)仅含3个b的由a和b构成的字符串(e)含有偶数个a和偶数个b的由a和b构成的字符串注意：请准确描述语言的性质而不是列举满足正则表达式的串3.3.6 写出满足下列定义的字符a) The first ten letters in either upper or lower caseb) The lowercase consonantsc) The “digits” in a hexadecimal numberd) The characters that can appear at the end of a legitimate English sentence答案(a)a-jA-J(b)a-j(c)0-9a-f(d).?!3.3.7 写出匹配字符串“\ 的正则表达式答案：\”\\3.6.3 对于图3.29表示的NFA,列出aabb的所有路径。

这个NFA能否接受aabb? 答案：aabb的所有路径01223 00111 012000 00000 01222 00011 00123存在路径1223和0123所以能接受aabb3.6.4 对于图3.30表示的NFA,列出aabb的所有路径。

这个NFA能否接受aabb? 答案：01012301012120301230301212030303232030303212303030321212由于存在03210这样的环,所以这里有无数种路径存在路径终止于3,所以能接受aabb3.6.5 给出以下NFA的Transition Table(a) 图3.29(b) 图3.30(c) 图3.26答案:3.7.1 把下列NFA转化为DFA(a)图3.26(b)图3.29(c)图3.30答案:(a)(b)注意:以上答案并不唯一,等价即可3.7.2 用算法3.22模拟NFA(输入为aabb)(a)图3.29(b)图3.30答案:F={3} 所以返回yesF={3},所以返回yes3.7.3 用算法3.23和3.20把下列正则表达式转换为DFAa) (alb)*b) (a*lb* )*c) ((ela)b*)*d) (alb)*abb(alb)*答案：a) NFAb) NFAc) NFAd) NFA注意：这道题要求大家按照算法构造NFA和DFA，有些同学的NFA没有完全按照算法构造。

第三章语法分析3.1 完成下列选择题：(1) 文法G：S→xSx|y所识别的语言是。

a. xyxb. (xyx)*c. xnyxn(n≥0)d. x*yx*(2) 如果文法G是无二义的，则它的任何句子α。

　a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同(3) 采用自上而下分析，必须。

a. 消除左递 a. 必有ac归b. 消除右递归c. 消除回溯d. 提取公共左因子(4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则。

b. 必有cac. 必有bad. a～c都不一定成立(5) 在规范归约中，用来刻画可归约串。

a. 直接短语b. 句柄c. 最左素短语d. 素短语(6) 若a为终结符，则A→α·aβ为项目。

a. 归约b. 移进c. 接受d. 待约(7) 若项目集Ik含有A→α· ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α· ”动作的一定是。

a. LALR文法b. LR(0)文法c. LR(1)文法d. SLR(1)文法(8) 同心集合并有可能产生新的冲突。

a. 归约b. “移进”/“移进”c.“移进”/“归约”d. “归约”/“归约”【解答】(1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法G[N]为G[N]: N→D|NDD→0|1|2|3|4|5|6|7|8|9(1) G[N]的语言L(G[N])是什么?(2) 给出句子0127、34和568的最左推导和最右推导。

【解答】(1) G[N]的语言L(G[N])是非负整数。

(2) 最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D685683.3 已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。

第三章习题参考解答3.1 构造自动机A，使得①②③当从左至右读入二进制数时，它能识别出读入的奇数；④它识别字母表{a, b}上的符号串，但符号串不能含两个相邻的a，也不含两个相邻的b；⑤它能接受字母表{0, 1}上的符号串，这些符号串由任意的1、0和随后的任意的11、00对组成。

⑥它能识别形式如±dd*⋅ d*E ±dd的实数，其中，d∈{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。

3.2 构造下列正规表达式的DFSA：① xy*∣yx*y∣xyx；② 00∣(01)*∣11；③ 01((10∣01)*(11∣00))*01；④ a(ab*∣ba*)*b。

3.3 消除图3.24所示自动机的空移。

bεq1q2q3aba,bqaq6q4q5abεεε图3.24 含空移的自动机3.4 将图3.25所示NDFSA确定化和最小化。

xyqq1q2q4q3xyxyx,yx图3.25 待确定化的NDFSA3.5 设e、e1、e2是字母表∑上的正规表达式，试证明① e∣e=e；② {{e}}={e}；③ {e}=ε∣e{e}；④ {e1 e2} e1= e1{e2 e1};⑤ {e1∣e2}={{e1}{e2}}={{e1}∣{e2}}。

3.6 构造下面文法G[Z]的自动机，指明该自动机是不是确定的，并写出它相应的语言： G[Z]:Z→A0A→A0∣Z1∣03.7 设NDFSA M=({x, y},{a, b},f, x, {y}), 其中，f(x, a)={x, y}, f(x, b)={y}, f(y, a)=∅, f(y, b)={x, y}。

试对此NDFSA确定化。

3.8 设文法G[〈单词〉]：〈单词〉→〈标识符〉∣〈无符号整数〉〈标识符〉→〈字母〉∣〈标识符〉〈字母〉∣〈标识符〉〈数字〉〈无符号整数〉→〈数字〉∣〈无符号整数〉〈数字〉〈字母〉→a∣b〈数字〉→1∣2试写出相应的有限自动机和状态图。

第3 章文法和语言第1 题文法G＝({A,B,S},{a,b,c},P,S)其中P 为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

答案：L(G[S])={abc}第2 题文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案: G[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D......D或者：允许0 开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。

答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第4 题已知文法G[Z]：Z→aZb|ab写出L(G[Z])的全部元素。

答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={anbn|n>=1}第5 题写一文法，使其语言是偶正整数的集合。

要求：(1) 允许0 打头；(2)不允许0 打头。

答案：(1)允许0 开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0 开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第6 题已知文法G：<表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。

（５）i+(i+i)（６）i+i*i答案：(5) <表达式>=><表达式>＋<项>=><表达式>＋<因子>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）=><项>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）(6) <表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子> =><表达式>＋<项>*i=><表达式>＋<因子>*i =><表达式>＋i*i=><项>＋i*i=><因子>＋i*i=>i＋i*i<表达式><表达式> + <项><因子><表达式><表达式> + <项><因子>i<项><因子>i<项><因子>i（)<表达式><表达式> + <项><项> * <因子><因子> i<项><因子>ii第7 题证明下述文法G[〈表达式〉]是二义的。

第 3 章习题3-1 试构造一右线性文法，使得它与如下的文法等价4AB A f UT U faU|a D fbT|b B fcB|c并根据所得的右线性文法，构造出相应的状态转换图。

3-2 对于如题图3-2 所示的状态转换图(1) 写出相应的右线性文法；(2) 指出它接受的最短输入串；(3) 任意列出它接受的另外 4 个输入串；(4) 任意列出它拒绝接受的 4 个输入串。

3-3 对于如下的状态转换矩阵：(1) 分别画出相应的状态转换图；(2) 写出相应的 3 型文法；(3) 用自然语言描述它们所识别的输入串的特征。

3-4 将如下的NFA确定化和最小化:3-5 将如题图3-5所示的具有£动作的NFA确定化。

题图3-5 具有£动作的NFA试用正规式描述它所产生的语言。

3-7 分别构造与如下正规式相应的 NFA(1) ((0 |1)(1 0)) ⑵ b|a(aa *b)*b3-8 构造与正规式(a|b) *(aa|bb)(a|b)*相应的 第3章习题答案3-1 解：根据文法知其产生的语言是L[G]={am 3n c i| m,n,i 仝 1}可以构造与原文法等价的右线性文法其状态转换图如下：3-2 解:4 aA L aA|bB 4 bB|cC|c C^ cC|cDFAA ^ aA|bB4 bB|cC|cC^ cC|cc4 0A|1C0110,0011,000011,00110Df0B|1CEf0B|1CFf 1A|0E|0(2) 最短输入串为 O11(3) 任意接受的四个输入串为：(1) 其对应的右线性文法是 G[A]:0A|1F|1 (4) 任意拒绝接受的输入串为： 0111，1011，1100，10013-3 解:(1) 相应的状态转换图为：(2) 相应的 3 型文法为： (i ) S f aA|bS AfaA|bB| b Bf aB|bB|a|b(ii) S f aA|bB| AfbA|aC| a|b BfaB|bC| b Cf aC|bC|a|b(iii) S f aA|bB| AfaB|bA| a BfaB|bB|a|b (iv) S f bS|aAAfaC|bB| aBfaB|bC| bCf aC|bC|a|b（3） 用自然语言描述的输入串的特征为：（i ）以任意个（包括0个）b 开头，中间有任意个（大于1） a ,跟一个b ,还可以有一个由 a,b 组成的任意字符串。

The exercises of Chapter Three3.2 Given the grammar A →AA|(A)|εa. Describe the language it generates;b. Show that it is ambiguous.[Solution]:a. Generates a string of balanced parenthesis, including the empty string.b. parse trees of ():3.3 Given the grammar exp → exp addop term | termaddop → + | -term → term mulop factor| factormulop → *factor → ( exp ) | numberWrite down leftmost derivations, parse trees, and abstract syntax trees for the following expression:a. 3+4*5-6b. 3*(4-5+6)c. 3-(4+5*6)[Solution]:a. The leftmost derivations for the expression3+4*5-6:Exp => exp addop term =>exp addop term addop term=>term addop term addop term=> factor addop term addop term=>3 addop term addop term => 3 + term addop term=>3+term mulop factor addop term =>3+factor mulop factor addop term=>3+4 mulop factor addop term => 3+4* factor addop termA ( ) ε A AA AA ( ) ε ε=>3+4*5 addop term => 3+4*5-term=> 3+4*5-factor=>3+4*5-63.5 Write a grammar for Boolean expressions that includes the constants true and false, the operators and, or and not, and parentheses. Be sure to give or a lower precedence than and and and a lower precedence that not and to allow repeated not’s, as in the Boolean expression not not true. Also be sre your grammar is not ambiguous.[solution]bex p→bexp or A | AA→ A and B | BB→ not B | CC→ (bexp) | true | falseEx: not not trueboolExp → A→ B→ not B→ not not B→ not not C→ not not true3.8 Given the following grammarstatement→if-stmt | other | εif-stmt→ if ( exp ) statement else-partelse-part→ else statement | εexp→ 0 | 1a. Draw a parse tree for the stringif(0) if (1) other else else otherb. what is the purpose of the two else’s?The two else’s allow the programmer to associate an else clause with the outmost else, when two if statements are nested and the first does not have an else clause.c. Is similar code permissible in C? Explain.The grammar in C looks like:if-stmt→if ( exp ) statement | if (exp) statement else statement the way to override “dangling else”problem is to enclose the inner if statement in {}s. e.g. if (0) { if(1) other } else other.3.10 a. Translate the grammar of exercise 3.6 into EBNF.b. Draw syntax diagramms for the EBNF of part (a).[Solution]a. The original grammarlexp→atom|listatom→number|identifierlist→(lexp-seq)lexp-seq→lexp-seq lexp| lexpThe EBNF of the above grammar:lexp→atom|listatom→number|identifierlist→(lexp-seq)lexp-seq→lexp {lexp}b. The syntax diagramms for the above EBNF:3.12. Unary minuses can be added in several ways to the simple arithmetic expression grammar of Exercise 3.3. Revise the BNF for each of the cases that follow so that it satisfies the stated rule.a. At most one unary minus is allowed in each expression, and it must come at the beginning of an expression, so -2-3 is legal ( and evaluates to -5 ) and -2-(-3) is legal, but -2--3 is not.exp →exp addop term | termaddop →+ | -term → term mulop factor| factormulop →*factor →( exp) | (-exp) | number |b. At most one unary minus are allowed before a number or left parenthesis, so -2--3 is legal but --2 and -2---3 are not.exp →exp addop term | termaddop →+ | -term → term mulop factor| factormulop →*factor →( exp) | -(exp) | number | -numberc. Arbitrarily many unary minuses are allowed before numbers and left parentheses, so everything above is legal.3.19 In some languages ( Modula-2 and Ada are examples), a procedure declaration is expected to be terminated by syntax that includes the name of the procedure. For example, in Modular-2 a procedure is declared as follows:PROCEDURE P;BEGIN……END P;Note the use of the procedure name P alter the closing END. Can such a requirement be checked by a parser? Explain.[Answer]This requirement can not be handled as part of the grammar without making a new rule for each legal variable name, which makes it intractable for all practical purposes, even if variable names are restricted to a very short length. The parser will just check the structure, that an identifier follows the keyword PROCEDURE and an identifier also follows the keyword END, however checking that it is the same identifier is left for semantic analysis. See the discussion on pages 131-132 of your text.3.20 a. Write a regular expression that generate the same language as the following grammar:A→aA|B|εB→bB|Ab. Write a grammar that generates the same language as the following regularexpression:(a|c|ba|bc)*(b|ε)[Solution]a. The regular expression:(a|b)*b. The grammar:Step 1:A→BCB→aB|cB|baB|bcB|εC→b|εStep 2:A→Bb|BB→aB|cB|baB|bcB|ε。