《编译原理第一章练习和答案复习课程.docx》由会员分享，可在线阅读，更多相关《编译原理第一章练习和答案复习课程.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理第一章练习和答案复习课程例1设有文法GS:Sa|T|TT,S|S1试给出句子(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，Sa(3)(a,a,a)最右推导最左规约每一步的句柄S=(T)句柄为：(T)=(T,S)句柄为：T,S=(T,a)句柄为：a=(T,S,a)句柄为：T,S=(T,a,a)句柄为：第一个a=
2、(S,a,a)句柄为：S=(a,a,a)句柄为：第一个a例2已知文法GZ:Z0U|1VU1Z|1V0Z|01请写出此文法描绘的只含有个符号的全部句子。2GZ产生的语言是什么？3该文法在Chomsky文法分类中属于几型文法？【解】10101，0110，1010，10012分析GZ所推导出的句子的特点：由Z开场的推导不外乎图1所示的四种情形。图1文法GZ可能的几种推导Z1UZUZ1Z1VZ1V由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出一样的符号串：10或01。所以GZ产生的语言L(GZ)=x|x(10|01)+(3)该文法属于3型文法。例3已知文法G=(A,B,C，a,b,c，
3、P，A),P由下面产生式组成:AabcAaBbcBbbBBcCbccbCCbaCaaBaCaa此文法所表示的语言是什么？【解】分析文法的规则：每使用一次BcCbcc，b、c的个数各增加一个；每使用一次aCaaB或aCaa,a的个数就增加一个；产生式BbbB、bCCb起连接转换作用。由于A是开场符号，由产生式Aabc推导得到终结符号串abc；由产生式AaBbc推导得到B后，每当使用产生式BbbB、BcCbcc、bCCb、aCaaB就会递归调用B一次，所产生的a、b、c的个数分别增加一个，因而推导所得的终结符号串为abc、aabbcc、aaabbbccc、所以文法描绘的语言为anbncn|n0.例
4、4构造描绘语言L(GS)=nn|n0的文法。【解】(1)找出语言的一些典型句子:n=0n=1()n=2()所以,L(GS)=、()()、()、(2)分析句子的特点:只含有(和),(和)的个数一样且对称,句子中所含的符号数可无限,句子的个数可无限。(3)凑规则:由S|()得到|()，由A(S)得到()，()是在的两边再加上一对得到，()是在()的两边再加上一对得到，所以将上述产生式合并为S(S)|。(4)得到文法GS:S(S)|(5)检验:语言所有的句子均可由文法GS推导出来,文法GS推导出来的所有终结符号串均为语言的句子.例5构造描绘语言L(GS)=ambn|nm0的文法。【解】找出语言的一些
5、典型句子:abb、abbb、aabbb、aabbbb、,语言的句子的特点是仅含有a、b,a在b的左边，b的个数大于a的个数，a的个数至少是1。单独生成ck,k1可用产生式Cc|Cc句子中要求b的个数大于a的个数，所以得到文法：GS:SAb|SbAaAb|ab检验:语言所有的句子均可由文法GS推导出来,文法GS推导出来的所有终结符号串均为语言L(GS)的句子.例6设有文法GS:SS*S|S+S|(S)|i该文法能否为二义文法？【解】该文法是二义文法，由于该文法存在句子i*i+i,该句子有两棵不同的语法树如图2所示.。SS*SSS(1)+SS+SSS(2)*iii图2句子i*i+i的语法树例7写一
6、个文法，使其语言是奇数集，且每个奇数不以0开始。【解】解题思路首先分析题意，此题是希望构造一个文法，由它产生的句子是奇数，并且不以0开始，也就是讲它的每个句子都是以1、3、5、7、9中的某个数结尾。假如数字只要一位，则1、3、5、7、9就知足要求，假如有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字必须是数字则没什么要求，因而，我们能够把这个文法分3部分来完成。分别用3个非终结符来产生句子的第1位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开始，能够是19之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开始后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。解答：G(S)：SCDDCCBABA0A2468DD13579例8写一个上下文无关文法CFG，使其语言是能被5整除且不以0开始的无符号整数的集合。如5,10,15，.【解】解答：能被5整除的数从形式上看，是以0,5结尾的数字串。题目要求的不以0开始，并要注意0不是该语言的句子。所求文法为：G(S)：SMF5F50MMDNDN0