第二章 高级语言及其语法描述 4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算 1+1*2↑2*1↑2 的值： （1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。 （2） 优先顺序为↑，+，*，同级优先采用右结合。 解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16 （2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=4 6．令文法G6 为 N→D|ND D→0|1|2|3|4|5|6|7|8|9 （1） G6 的语言L（G6）是什么？ （2） 给出句子 0127、34 和568 的最左推导和最右推导。 解：（1）L（G6）=｛a|a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝ （2）N ＝＞ND＝＞ NDD＝＞ NDDD＝＞ DDDD＝＞ 0DDD＝＞ 01DD＝＞ 012D＝＞ 0127 N＝＞ ND＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127 N＝＞ ND＝＞ DD＝＞ 3D＝＞ 34 N＝＞ ND＝＞ N4＝＞ D4 ＝＞34 N＝＞ ND＝＞ NDD＝＞ DDD＝＞ 5DD＝＞ 56D＝＞ 568 N＝＞ ND＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 568 7．写一个文法，使其语言是奇数集，且每个奇数不以 0 开头。 解：A→SN, S→+|-|∑, N→D|MD D→1|3|5|7|9, M→MB|1|2|3|4|5|6|7|8|9 B→0|1|2|3|4|5|6|7|8|9 8. 文法： ET ET ETTF TF TFFE i||| *|/( )| 最左推导: EETTTFTi Ti TFi FFi i Fi i iETTFFFi FiEiETiTTiFTii Tii Fii i********()*()*()*()*()*()*() 最右推导: EETETFET iEF iEi iTi iFi ii i iETFTFFFEFETFEFFEiFTiFFiFi iii i**********()*()*()*()*()*()*()*() 语法树：/******************************** EEFTE+TFFT+iiiEEFTE-TFFT-iiiEEFT+TFFTiii*i+i+ii-i-ii+i*i *****************/ 9．证明下面的文法是二义的： S→ iSeS|iS|I 解：因为 iiiiei 有两种最左推导，所以此文法是二义的。 10．把下面文法改写为无二义的： S→SS|(S)|() 解：S→ ST|T, T→ (S)|() 11．给出下面语言的相应文法 L1=｛anbnci|n≥1,i≥0｝ L2=｛aibncn|n≥1,i≥0｝ L3=｛anbnambm|n,m≥0｝ L4=｛1n0m1m0n|n,m≥0｝ 解：（1）S→ AB|A A→ aAb|ab B→ c|cB (2) S→ AB|B A→ a|aA B→ bBc|bc (3) S→ AB|A|B|∑ A→ aAb|ab B...
