中国石油大学-编译原理第03章、习题

1.设计一个文法定义一个已知的语言(1)文法是一个四元组G=(VN,VT,P,S)，文法四大要素中，关键是一组规则,它定义（或描述）了一个语言的结构。从文法定义可知,文法对于程序设计者来说，文法给出了语言的精确定义和描述。(2)分析已知语言句子的结构特征,设计出相应的一组规则，但不唯一。(4)若语言是无穷集合,设计该语言的文法一定是递归的。(3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。分析根据语言句子的结构特征，设计出相应规则例1.给出语言L2={anbm|m≥n≥1}的文法P2:S→ABL2={ab,abb,abbb,…aabb,aabbb,aabbbb,…aaabbb,aabbbb，…}A→aAb|abB→bB|ε分析根据语言句子的结构特征，设计出相应规则例2.给出语言L1={a2n+1|n≥0}的文法P1':A→aB|aP1：A→aAa|a或L1={a,aaa,aaaaa,aaaaaaa,aaaaaaaaa，…}B→aa|aBa分析根据语言句子的结构特征，设计出相应规则例3.给出语言L3={anbmck|n,m,k≥0}的文法P3:A→aA|bB|cC|εL3={ε,a,aa,aaa…,b,bb,bbb…,c,cc,ccc,…,ab,abb,…,bc,bcc，…}C→cC|εB→bB|cC|εL4={2,4,6,8,10,12,14,16,18,20,22,24,26,…}例4.写一个文法,使其语言是正偶数的集合,每个偶数不以0开头。P4:N→E′|AE分析不以0开头的偶数集合中串的结构特征:A→D|AD′E→0|2|4|6|8D→1|2|3|…|9D'→0|1|2|3|…|9E'→2|4|6|8A→0A1|εP:S→1S0|0A1|ε例5.给出语言L={1n0m1m0n|n,m≥0}的文法。分析根据语言句子的结构特征,设计出相应规则L={ε,01,0011,…,10,1100,…,1010,100110,110100,11001100…}P:S→a|0S0|1S1例6.给出语言L={WaWt|W∈{0|1}*}，其中Wt表示W的逆的文法。分析根据语言句子的结构特征，设计出相应规则L={a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,…}W={ε,0,1,01,10,00,11,101,110,100,111,…}2.已知一个文法，确定该文法所定义的语言。(2)给定一个文法，可根据语言和推导定义推导出文法的句子，从而确定出该文法所定义的语言。(1)文法所定义的语言L(G[S])={x|Sx且x∈VT*}*①自然语言描述。例如,L={x|x∈{a,b}+且x中a,b个数相同}②式子描述。例如L={a2nbb|n≥0}。③正规式描述。(3)语言可用例1文法G[A]=({A},{a,b},{A→bA|a},A)所生成的语言是什么？分析∵AbAbbAbbbA…bnAbna∴L(G[A])={bna|n≥0}例2文法G[N]为:N→ND|DD→0|1|2|3|4|5|6|7|8|9(1)G[N]所生成的语言是什么？(2)给出句子0127的最左、最右推导。L(G[N])={α|α∈{0,1,2,…9}+}={α|α为可带前导0的正整数}={α|α为数字串}最左推导:NNDN7ND7N27ND27N127D1270127最右推导:NNDNDDNDDDDDDD0DDD01DD012D0127N→ND|DD→0|1|2|3|4|5|6|7|8|9例3.已知文法G[S]=({A,B},{a,b,c,d},P,S),其中P为:分析∵SABaAbBa2Ab2B…an-1Abn-1BanbnBanbncBdanbnc2Bd2…anbncm-1Bdn-1anbncmdm∴L(G[S])={anbncmdm|n,m≥1}该文法所生成的语言是什么？A→aAb|abB→cBd|cdS→AB3.求句型的短语、直接短语和句柄(1)短语、直接短语和句柄是对某句型而言的。(2)短语总是句型的某个子串，它对应子树未端结点形成的符号串。(3)直接短语是某条规则右部，它对应简单子树未端结点形成的符号串。(4)最左边的直接短语是句柄。例1已知文法G[E]：证明E+T*F是它的一个句型,指出这个句型的短语﹑直接短语和句柄。∵EE+TE+T*F短语:E+T*F、T*F∴E+T*F是它的一个句型。画出该句型的语法树:句柄:T*F直接短语:T*FETFT+E*E→E+T|E-T|TT→T*F|T/F|FF→(E)|i例2已知文法G[S]：试找出符号串(a)和(A((SaA)(b)))的短语﹑直接短语和句柄(如果有的话)。S→(AS)|(b)A→(SaA)|(a)∴符号串(a))不是文法的句型，因此它没有短语﹑直接短语和句柄。分析∵S(AS)((a)S)(a)/∵S(AS)(A(AS))(A(A(b)))(A((SaA)(b)))∴符号串(A((SaA)(b)))是文法的句型，画出该句型的语法树如下图：S→(AS)|(b)A→(SaA)|(a)从句型的语法树求短语:(A((SaA)(b)))((SaA)(b))(SaA)(b)直接短语：(SaA)、(b)句柄：(SaA)S(SaA))b(S→(AS)|(b)A→(SaA)|(a)对于句型(A((SaA)(b)))4．文法二义性的判断一个文法存在某个句子对应两棵不同的语法树或对应两个不同的最左（最右）推导，则该文法是二义性的。例1设有文法G[S]:S→iSeS|iS|i试证明文法G[S]有二义性。分析因为对文法的句子iiiei有如下两棵不同的语法树与之对应，所以该文法是二义的S→iSeS|iS|i句子iiiei对应下面两颗语法树：SSN→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|91.试证明文法G[N]有二义性。2.此文法所描述的语言是什么？3.试写出另一文法G'使L(G')=L(G)且G'是无二义性的。例2设有文法G[N]:分析因为对文法的句子10有两棵不同的语法树与之对应，所以该文法是二义的NES0D1NE01N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|9该文法所描述的语言是所有无符号偶数的集合(可以0开头)。改写后的文法G‘[S]为:N→SE|ES→SD|DE→0|2|4|6|8D→0|1|2|3|4|5|6|7|8|9N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|9