编译原理课后习题答案ch3.pdf 16页

'《编译原理》课后习题答案第三章第3章文法和语言第1题文法G＝({A,B,S},{a,b,c},P,S)其中P为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。答案：L(G[S])={abc}例题：文法G[S]：(5分)S→aSa|AA→bA|BB→Bc|ε所描述的语言是什么？nmln答案：L（G[S]）={abca，n,m,l≥0}第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开头的非负整数？盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第三章第３题为只包含数字、加号和减号的表达式，例如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...bbbnnL(G[Z])={ab|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盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第三章第6题已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。（５）i+(i+i)（６）i+i*i答案：<表达式>(5)<表达式>=><表达式>＋<项>=><表达式>＋<因子><表达式>+<项>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）<项><因子>=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）<因子>（<表达式>)=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）i=><项>＋（i＋i）<表达式>+<项>=><因子>＋（i＋i）=>i＋（i＋i）<项><因子><因子>ii<表达式>(6)<表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子><表达式>+<项>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i<项>=><项>＋i*i<项>*<因子>=><因子>＋i*i<因子>=>i＋i*i<因子>iii盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第三章第7题证明下述文法G[〈表达式〉]是二义的。〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/答案：可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉a〈表达式〉*a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第三章第8题文法G[S]为：S→Ac|aBA→abB→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc(2)S=>aB=>abc即存在两不同的最右推导。所以，该文法是二义的。或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。SSaBAcbcab第9题考虑下面上下文无关文法：SS→SS*|SS+|a(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。(2)G[S]的语言是什么？SS*答案：SS+a(1)此文法生成串aa+a*的最右推导如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*aa(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。盛威网（www.snwei.com）专业的计算机学习网站5 《编译原理》课后习题答案第三章第10题文法S→S(S)S|ε(1)生成的语言是什么？(2)该文法是二义的吗？说明理由。答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。第11题令文法G[E]为：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案：此句型对应语法树如下图，故为此文法一个句型。或者，因为存在推导序列：E=>E+T=>E+T*F，所以E+T*F句型此句型相对于E的短语有：E+T*F；相对于T的短语有T*F直接短语为：T*F句柄为：T*F盛威网（www.snwei.com）专业的计算机学习网站6 《编译原理》课后习题答案第三章第13题一个上下文无关文法生成句子abbaa的推导树如下：(1)给出串abbaa最左推导、最右推导。(2)该文法的产生式集合P可能有哪些元素？S(3)找出该句子的所有短语、直接短语、句柄。ABSSBBAaaεbba答案：(1)串abbaa最左推导:S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa(2)产生式有：S→ABS|Aa|εA→aB→SBB|b可能元素有：ε，aa，ab，abbaa，aaabbaa，……(3)该句子的短语有：a是相对A的短语ε是相对S的短语b是相对B的短语εbb是相对B的短语（注意：回答bb可能会更好一些）aa是相对S的短语aεbbaa是相对S的短语（注意：回答abbaa可能会更好一些）直接短语有：a，ε，b句柄是：a盛威网（www.snwei.com）专业的计算机学习网站7 《编译原理》课后习题答案第三章第14题给出生成下述语言的上下文无关文法：nnmm（1）{abab|n，m>=0}nmmn（2）{1010|n，m>=0}（3）{WaWr|W属于{0|a}*，Wr表示W的逆}答案：（１）S→AAA→aAb|ε（２）S→1S0|AA→0A1|ε（３）S→0S0|aSa|a第16题给出生成下述语言的三型文法：(1){an|n>=0}nm(2){ab|n,m>=1}nmk(3){abc|n,m,k>=0}答案：(1)S→aS|ε(2)S→aAA→aA|BB→bB|b(3)A→aA|BB→bB|CC→cC|ε盛威网（www.snwei.com）专业的计算机学习网站8 《编译原理》课后习题答案第三章第17题习题７和习题11中的文法等价吗？答案：等价。第18题解释下列术语和概念：（１）字母表（２）串、字和句子（３）语言、语法和语义答案：（１）字母表：是一个非空有穷集合。（２）串：符号的有穷序列。字：字母表中的元素。+句子：如果Zx,x∈V*T则称x是文法G的一个句子。（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。盛威网（www.snwei.com）专业的计算机学习网站9 《编译原理》课后习题答案第三章附加题问题1：给出下述文法所对应的正规式：S→0A|1BA→1S|1B→0S|0答案：*R=(01|10)(01|10)问题2：已知文法G[A]，写出它定义的语言描述G[A]:A→0B|1CB→1|1A|0BBC→0|0A|1CC答案:G[A]定义的语言由0、1符号串组成，串中0和1的个数相同.问题3：给出语言描述，构造文法.构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案一：G[E]E→E+T|T*T→TF|FF→(E)|a答案二：*G[E]E→E+E|EE|(E)|a问题4：已知文法G[S]:S→dAB盛威网（www.snwei.com）专业的计算机学习网站10 《编译原理》课后习题答案第三章A→aA|aB→ε|bB相应的正规式是什么？G[S]能否改写成为等价的正规文法？答案：正规式是daa*b*；相应的正规文法为(由自动机化简来)：G[S]:S→dAA→a|aBB→aB|a|b|bCC→bC|b也可为(观察得来):G[S]:S→dAA→a|aA|aBB→bB|ε问题5：已知文法G：E→E+T|E-T|TT→T*F|T/F|FF→(E)|i试给出下述表达式的推导及语法树(1)i;(2)i*i+i(3)i+i*i(4)i+(i+i)答案：(1)E=>T=>F=>i(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)=>i+(i+T)=>i+(i+F)=>i+(i+i)EEETE+TE+TE+TTFFTTFT*F(E)iiFFFFii(1)E+Tiiii(2)TF(3)Fi(4)i盛威网（www.snwei.com）专业的计算机学习网站11 《编译原理》课后习题答案第三章问题6：已知文法G[E]:E→ET+|TT→TF*|FF→F^|a试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.答案：该句型对应的语法树如下：该句型相对于E的短语有FF^^*相对于T的短语有FF^^*,F相对于F的短语有F^;F^^简单短语有F;F^句柄为F.问题7：适当变换文法，找到下列文法所定义语言的一个无二义的文法：S→SaS⏐SbS⏐ScS⏐d答案：该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做进一步变换，即可消除二义性。设a、b和c的优先级别依次增高，根据优先级联规则将文法变换为：S→SaS⏐AA→AbA⏐CC→CcC⏐d规定结合性为左结合，进一步将文法变换为：S→SaA⏐AA→AbC⏐CC→CcF⏐FF→d该文法为非二义的。盛威网（www.snwei.com）专业的计算机学习网站12 《编译原理》课后习题答案第三章问题8：构造产生如下语言的上下文无关文法：n2nm（1）{abc|n，m≥0}nm2m（2）{abc|n，m≥0}mn（3）{ab⏐m≥n}mnpq（4）{abcd⏐m+n=p+q}（5）{uawb⏐u,w∈{a,b}*∧|u|=|w|}答案：n2nmn2n（1）根据上下文无关文法的特点，要产生形如abc的串，可以分别产生形如ab和m形如c的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是特别指明，通常可以忽略这一点。对于该语言，存在一个由以下产生式定义的上下文无关文法G[S]：S→ABA→ε⏐aAbbB→ε⏐cBnm2mnm2m（2）同样，要产生形如abc的串，可以分别产生形如a和形如bc的串。对于该语言，存在一个由以下产生式定义的上下文无关文法G[S]：S→ABA→ε⏐aAB→ε⏐bBcc（3）考虑在先产生同样数目的a,b，然后再生成多余的a。以下G[S]是一种解法：S→aSb⏐aS⏐ε（4）以下G[S]是一种解法：S→aSd⏐A⏐DA→bAd⏐BD→aDc⏐BB→bBc⏐ε注：a不多于d时，b不少于c；反之，a不少于d时，b不多于c。前一种情形通过对应A，后一种情形对应D。（5）以下G[S]是一种解法：S→AbA→BAB⏐a盛威网（www.snwei.com）专业的计算机学习网站13 《编译原理》课后习题答案第三章B→a⏐b问题9：下面的文法G(S)描述由命题变量p、q，联结词∧（合取）、∨（析取）、¬（否定）构成的命题公式集合：S→S∨T⏐TT→T∧F⏐FF→¬F⏐p⏐q试指出句型¬F∨¬q∧p的直接短语（全部）以及句柄。答案：直接短语：p，q，¬F句柄：¬F问题10：设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+.答案：000x=(aaa)=ε|x|=0xx=aaaaaa|xx|=655x=aaaaaaaaaaaaaaa|x|=15+12nA=A∪A∪∪….A…∪={a,aa,aaa,aaaa,aaaaa…}012nA*=A∪A∪A∪….∪A∪…={ε,a,aa,aaa,aaaa,aaaaa…}问题11：令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3答案：xy=abcb|xy|=4xyz=abcbaab|xyz|=7333(xy)=(abcb)=abcbabcbabcb|(xy)|=12问题12：已知文法G[Z]：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写出全部由此文法描述的只含有四个符号的句子。盛威网（www.snwei.com）专业的计算机学习网站14 《编译原理》课后习题答案第三章答案：Z=>U0=>Z10=>U010=>1010Z=>U0=>Z10=>V110=>0110Z=>V1=>Z00=>U000=>1000Z=>V1=>Z00=>V100=>0100问题13：已知文法G[S]：S∷=ABA∷=aA︱εB∷=bBc︱bc,写出该文法描述的语言。答案：nA∷=aA︱ε描述的语言:{a|n>=0}nnB∷=bBc︱bc描述的语言:{,bc|n>=1}nmmL(G[S])={abc|n>=0,m>=1}问题14：已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。答案：开始符号：EVT={+,-,*,/,（,）,i}VN={E,F,T}问题15：设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？答案：根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。盛威网（www.snwei.com）专业的计算机学习网站15 《编译原理》课后习题答案第三章SSS*SS+SS+SaaS*Saaaa问题16：写一文法，使其语言是奇正整数集合。答案：A::=1|3|5|7|9|NAN::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9|N::=0|1|2|3|4|5|6|7|8|9盛威网（www.snwei.com）专业的计算机学习网站16'