071编译原理习题(全)@北工大

1语言和文法重重点点与与难难点点重点：文法、推导与归约、短语与句柄。难点：文法、推导、归约、短语、句柄、文法的二义性、用文法表示语言。基基本本要要求求掌握语言的描述、形式定义、文法、文法分类的概念以及形式文法的应用，了解二义性文法，熟练掌握推导与规约、短语与句柄及用文法描述语言、正则语言、上下文无关文法、语法分析树。例例题题解解析析例1设有文法G[S]:S→a|（T）|εT→T,S|S（1）试给出句子(a,a,a)的最左推导。（2）试给出句子(a,a,a)的分析树（3）试给出句子(a,a,a)的最右推导和最右推导的逆过程(即最左规约)的每一步的句柄。【解】(1)(a,a,a)的最左推导S=(T)=(T,S)=(T,S,S)=(S,S,S)=(a,S,S)=(a,a,S)=(a,a,a)（2）(a,a,a)的分析树S(T)T，SSaT，Saa(3)(a,a,a)最右推导最左规约每一步的句柄S=(T)句柄为：(T)=(T,S)句柄为：T,S=(T,a)句柄为：a=(T,S,a)句柄为：T,S=(T,a,a)句柄为：第一个a=(S,a,a)句柄为：S=(a,a,a)句柄为：第一个a例2已知文法G[Z]:2Z→0U|1VU→1Z|1V→0Z|0（1）请写出此文法描述的只含有４个符号的全部句子。（2）G[Z]产生的语言是什么？（3）该文法在Chomsky文法分类中属于几型文法？【解】（1）0101，0110，1010，1001（2）分析G[Z]所推导出的句子的特点：由Z开始的推导不外乎图1所示的四种情形。图1文法G[Z]可能的几种推导Z01UZU0Z1Z1V0ZZ10V由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出相同的符号串：10或01。所以G[Z]产生的语言L(G[Z])={x|x∈(10|01)+(3)该文法属于3型文法。}例3已知文法G=({A,B,C}，{a,b,c}，P，A),P由以下产生式组成:A→abcA→aBbcBb→bBBc→CbccbC→CbaC→aaBaC→aa此文法所表示的语言是什么？【解】分析文法的规则：每使用一次Bc→Cbcc，b、c的个数各增加一个；每使用一次aC→aaB或aC→aa,a的个数就增加一个；产生式Bb→bB、bC→Cb起连接转换作用。由于A是开始符号，由产生式A→abc推导得到终结符号串abc；由产生式A→aBbc推导得到B后，每当使用产生式Bb→bB、Bc→Cbcc、bC→Cb、aC→aaB就会递归调用B一次，所产生的a、b、c的个数分别增加一个，因此推导所得的终结符号串为abc、aabbcc、aaabbbccc、…所以文法描述的语言为{anbncn|n0}.例4构造描述语言L(G[S])={（n）n【解】(1)找出语言的一些典型句子:|n≥0}的文法。n=0εn=1()n=2(())…所以,L(G[S])={ε、()(())、((()))、…}3(2)分析句子的特点:只含有(和),(和)的个数相同且对称,句子中所含的符号数可无限,句子的个数可无限。(3)凑规则:由S→ε|()得到ε|()，由A→(S)得到(())，(())是在（）的两边再加上一对（）得到，((()))是在(())的两边再加上一对（）得到，…所以将上述产生式合并为S→(S)|ε。(4)得到文法G[S]:S→(S)|ε(5)检验:语言所有的句子均可由文法G[S]推导出来,文法G[S]推导出来的所有终结符号串均为语言的句子.例5构造描述语言L(G[S])={ambn【解】找出语言的一些典型句子:abb、abbb、…、aabbb、aabbbb、…,语言的句子的特点是仅含有a、b,a在b的左边，b的个数大于a的个数，a的个数至少是1。|nm0}的文法。单独生成ck句子中要求b的个数大于a的个数，所以得到文法：,k1可用产生式C→c|CcG[S]:S→Ab|SbA→aAb|ab检验:语言所有的句子均可由文法G[S]推导出来,文法G[S]推导出来的所有终结符号串均为语言L(G[S])的句子.例6设有文法G[S]:S→S*S|S+S|(S)|i该文法是否为二义文法？【解】该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图2所示.。SS*SSS(1)+iiiSS+SSS(2)*iii图2句子i*i+i的语法树例7写一个文法，使其语言是奇数集，且每个奇数不以0开头。【解】解题思路首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用3个非终结符来产生句子的第1位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。解答：4G(S)：S→CD｜DC→CB｜AB→A｜0A→2｜4｜6｜8｜DD→1｜3｜5｜7｜9例8写一个上下文无关文法CFG，使其语言是能被5整除且不以0开头的无符号整数的集合。（如｛5,10,15，….｝）【解】解答：能被5整除的数从形式上看，是以0,5结尾的数字串。题目要求的不以0开头，并要注意0不是该语言的句子。所求文法为：G(S)：S→MF｜5F→5｜0M→MD｜ND→N｜0N→1｜2｜3｜4｜5｜6｜7｜8｜9例9证明下面的文法是二义的：S→ｉSｅS｜ｉS｜ｉ【解】解题思路：根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程序语言的了解，不难发现，这个文法应该是用来表示if….else….结构的（用“i”代表“if”或语句集，“e”代表“else”）。因此我们就要到if….else…结构中去找二义性。我们知道，程序语言一般都规定else部分是和它前面离它最近的没有被匹配的的if语句进行匹配。而上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else前面有两个if（如句子iiiei），else和不同的if进行匹配时就会产生不同的语义。解答：考虑句子iiiei，存在如下两个最右推导：S=iSeS=iSei=iiSei=iiieiS=iS=iiSeS=iiSei=iiiei例10某程序设计语言的表达式由运算符θ1、θ2、θ3、标识符、（、）组成，其中θ1和θ2的优先级相同，θ3的优先级低于θ1、θ2设E为识别符号，终结符号集={θ的优先级，优先级相同的运算符从右往左计算，可以用括号改变运算的顺序，则下述四种文法中哪一个可以描述上述的表达式文法？1、θ2、θ3a.E→T|Eθ、（、）、I}，非终结符号集={E、T、F}。1T|Eθ2T→F|TθT3F→(E)|IFb.E→T|Tθ1E|Tθ2T→F|FθE3F→(E)|ITc.E→T|Eθ3T→F|TθT1F|Tθ2F5F→(E)|Id.E→T|Tθ3T→F|FθE1T|Fθ2F→(E)|IT【解】对于一个包含运算符的语言，运算符的结合顺序、运算符的优先级在文法中反映为递归的方向和推导（或规约）的先后，左递归表明左边的运算先处理，对应的运算符左结合；右递归表明右边的运算先处理，对应的运算符右结合。两个运算符连续出现，后推导出（或先被规约）的，表明其运算先被处理，因此优先级高；反之，先推导出（或后被规约）的，表明其运算后被处理，因此优先级低。题意要求：θ1和θ2的优先级相同，θ3的优先级低于θ1、θ2的优先级，因此θ3θ比1、θ2UUθ3UVV(1)θ1UUθ3UVV(2)θ1UUθ3UVV(3)θ2UUθ3UVV(4)θ2先推导出来，即应为图3所示的四种情形。图3可能的文法推导顺序因此a和b不成立。又因为优先级相同的运算符从右往左计算，应采用右递归，即应为图4所示的情形。UUθ1VWV(1)θ1UUθ2VWV(2θ2UUθ3VWV(3)θ3图4可能的文法递归结构故c不成立,应为d。1词法分析重重点点与与难难点点重点：词法分析器的输入、输出，用于识别符号的状态转移图的构造，根据状态转移图实现词法分析器。难点：词法的正规文法表示、正规表达式表示、状态转移图表示，它们之间的转换。基基本本要要求求明确词法分析的任务，熟练掌握词法的正规文法表示、正规表达式表示、状态转移图表示及它们之间的转换，掌握词法分析器的设计与实现，重点掌握根据状态转移图实现词法分析器。例例题题解解析析例1用正规表达式标识符的文法。【解】设标识符是由字母和数字组成的有限长的符号串，且第一个符号只能是字母。用l表示字母:a,b,…,z,A,B,…,Z;d表示数字:0,1,…|9。标识符的正规表达式表示为：l(l|d)*例２用正规文法描述标识符的文法。【解】用l表示字母:a,b,…,z,A,B,…,Z;d表示数字:0,1,…|9。定义文法G,G=({d,l},{S,T},P,S)P:S→l|lTT→l|lTT→d|dS得到标识符文法的右线性文法表示。或者定义文法G,G=({d,l},{S,T},P,S)P:S→lS→SdS→Sl得到标识符文法的左线性文法表示或者通过正规表达式转换为正规文法的方法得到标识符文法的正规文法。引入开始符号S，构造S→→l(l|d)*引入非终结符T，分分解解““连连接接””的的正正规规式式构构造造S→→lT,T→→(l|d)*(l|d)，，因因为为*=εε||(l|d)+=εε||(l|d)(l|d)*得得到到产产生生式式的的集集合合PP::SS→→llTTTT→→εε||llTT||ddTT=εε||llTT||ddTT构构成成右右线线性性文文法法::ＧＧ＝＝（（{{ll,,dd}}，，{{SS,,TT}}，，PP，，SS））例3用状态图描述标识符（变量名等）的文法。【解】用正规文法转换为状态图的方法。标识符的正规文法SS→→llTTTT→→εε||llTT||ddTT，是一个右线性文法,按照由右线性正规文法构造状态转换图的方法,构造标识符的状态转换图如下:①②③ｌl,d其它终态初态2例４写出正规式a(a|b)*(ε|((.|_)(a|b)(a|b)*))相应的正规文法。【解】引入开始符号S，构造S→a(a|b)*ε|((.|_)(a|b)(a|b)*),a(a|b)*ε|((.|_)(a|b)(a|b)*)=a(a|b)*|a(a|b)*.(a(a|b)*|b(a|b)*)|a(a|b)*_(a(a|b)*|b(a|b)*)=aA|aC引入非终结符A，Ｂ，CA→(a|b)*→εε||(a|b)*+C→(a|b)*.(a(a|b)*|b(a|b)*)|(a|b)*_(a(a|b)*|b(a|b)*)→εε||(a|b)(a|b)*→εε||(a|b)A→(εε||(a|b)(a|b)*).(a(a|b)*|b(a|b)*)|(εε||(a|b)(a|b)*)_(a(a|b)*|b(a|b)*)→.(a(a|b)*|b(a|b)*)||(a|b)(a|b)*.(a(a|b)*|b(a|b)*)|_(a(a|b)*|b(a|b)*)||(a|b)(a|b)*_(a(a|b)*|b(a|b)*)→.B|_B|aC|bCB→(a|b)(a|b)*→aA|bA得到正规文法G[S]:S→aA|aCA→aA|bA|εC→aC|bC|.B|_BB→aA|bA例5给定如下正规式0(0|1)*1(1)写出相应的正规文法。(2)画出相应的状态转移图。【解】（1）引入非终结符S,A，S→0(0|1)*1→0AA→(0|1)*1→(εε||(0|1)+)1→1|(0|1)+得到正规文法G[S]:S→0AA→0A|1A|11→1|(0|1)(0|1)*1→1|0