(完整版)编译原理课后习题答案

第二章 词法分析2.1 完成下列选择题： (1) 词法分析器的输出结果是 。

a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (2) 正规式M1和M2等价是指 。

a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向边条数相等 (3) DFA M(见图2-1)接受的字集为 。

a. 以0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 【解答】 (1) c (2) c (3) d图2-1 习题的DFA M2.2 什么是扫描器？扫描器的功能是什么？ 【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。

每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。

2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下： f(x,a)={x,y} f {x,b}={y} f(y,a)=Φ f{y,b}={x,y} 试构造相应的确定有限自动机M ′。

【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。

先画出NFA M 相应的状态图，如图2-2所示。

图2-2 习题的NFA M用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。

编译原理及实现课后习题解答2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5 以及A+和A*.x0=(aaa)0=ε| x0|=0xx=aaaaaa |xx|=6x5=aaaaaaaaaaaaaaa | x5|=15A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…}A* = A0 ∪A1 ∪A2 ∪…. ∪A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…}2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3xy=abcb |xy|=4xyz=abcbaab |xyz|=7(xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=122.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。

S => SS* => Sa* => SS+a* => Sa+a* => aa+a*SS S *S S + aa a2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。

Z=>U0=>Z10=>U010=>1010Z=>U0=>Z10=>V110=>0110Z=>V1=>Z01=>U001=>1001Z=>V1=>Z01=>V101=>01012.5已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。

A∷=aA︱ε描述的语言: {a n|n>=0}B∷=bBc︱bc 描述的语言：{b n c n|n>=1}L(G[S])={a n b m c m|n>=0,m>=1}2.6已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。

第7 题证明下述文法G[〈表达式〉]是二义的。

〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/答案：可为句子a+a*a 构造两个不同的最右推导:最右推导1 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉a=>〈表达式〉* a=>〈表达式〉〈运算符〉〈表达式〉* a=>〈表达式〉〈运算符〉a * a=>〈表达式〉+ a * a=>a + a * a最右推导2 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉a=>〈表达式〉〈运算符〉〈表达式〉* a=>〈表达式〉〈运算符〉a * a=>〈表达式〉+ a * a=>a + a * a第8 题文法G[S]为：S→Ac|aB A→ab B→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc (2)S=>aB=>abc即存在两不同的最右推导。

所以，该文法是二义的。

或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。

第9 题考虑下面上下文无关文法：S→SS*|SS+|a(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。

(2)G[S]的语言是什么？答案：(1)此文法生成串aa+a*的最右推导如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。

第10 题文法S→S(S)S|ε(1) 生成的语言是什么？(2) 该文法是二义的吗？说明理由。

答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。

第11 题令文法G[E]为：E→T|E+T|E-T T→F|T*F|T/F F→(E)|i证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

第二章 词法分析2.1 完成下列选择题：(1) 词法分析器的输出结果是 。

a. 单词的种别编码b. 单词在符号表中的位置c. 单词的种别编码和自身值d. 单词自身值(2) 正规式M1和M2等价是指 。

a. M1和M2的状态数相等b. M1和M2的有向边条数相等c. M1和M2所识别的语言集相等d. M1和M2状态数和有向边条数相等(3) DFA M(见图2-1)接受的字集为 。

a. 以0开头的二进制数组成的集合b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合d. 含偶数个0的二进制数组成的集合【解答】(1) c (2) c (3) d图2-1 习题2.1的DFA M2.2 什么是扫描器？扫描器的功能是什么？【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。

每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。

2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下：f(x,a)={x,y} f {x,b}={y}f(y,a)=Φ f{y,b}={x,y}试构造相应的确定有限自动机M ′。

【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。

先画出NFA M 相应的状态图，如图2-2所示。

图2-2 习题2.3的NFA M 用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。

表2-2 状态转换矩阵将图2-3所示的DFA M ′最小化。

第二章 高级语言及其语法描述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=46．令文法G6为 N →D|NDD →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 ＝＞34N ＝＞ ND ＝＞ NDD ＝＞ DDD ＝＞ 5DD ＝＞ 56D ＝＞ 568 N ＝＞ ND ＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：A →SN, S →+|-|∑, N →D|MDD →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. 文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiEEFT+T F FTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S → iSeS|iS|I解：因为iiiiei 有两种最左推导，所以此文法是二义的。

编译原理(龙书)课后习题解答(详细)编译原理(龙书)课后题解答第一章1.1.1 ：翻译和编译的区别？答：翻译通常指自然语言的翻译，将一种自然语言的表述翻译成另一种自然语言的表述，而编译指的是将一种高级语言翻译为机器语言（或汇编语言）的过程。

1.1.2 ：简述编译器的工作过程？答：编译器的工作过程包括以下三个阶段：(1) 词法分析：将输入的字符流分解成一个个的单词符号，构成一个单词符号序列；(2) 语法分析：根据语法规则分析单词符号序列中各个单词之间的关系，确定它们的语法结构，并生成抽象语法树；(3) 代码生成：根据抽象语法树生成目标程序（机器语言或汇编语言），并输出执行文件。

1.2.1 ：解释器和编译器的区别？答：解释器和编译器的主要区别在于执行方式。

编译器将源程序编译成机器语言或汇编语言等，在运行时无需重新编译，程序会一次性运行完毕；而解释器则是边翻译边执行，每次执行都需要进行一次翻译，一次只执行一部分。

1.2.2 ：Java语言采用的是解释执行还是编译执行？答：Java一般是编译成字节码的形式，然后由Java虚拟机（JVM）进行解释执行。

但是，Java也有JIT（即时编译器）的存在，当某一段代码被多次执行时，JIT会将其编译成机器语言，提升代码的执行效率。

第二章2.1.1 ：使用BNF范式定义简单的加法表达式和乘法表达式答：<加法表达式> ::= <加法表达式> "+" <乘法表达式> | <乘法表达式><乘法表达式> ::= <乘法表达式> "*" <单项式> | <单项式><单项式> ::= <数字> | "(" <加法表达式> ")"2.2.3 ：什么是自下而上分析？答：自下而上分析是指从输入字符串出发，自底向上构造推导过程，直到推导出起始符号。

编译原理课后习题答案编译原理习题答案习题11.1翻译程序：把⽤某种程序设计语⾔（源语⾔）编写的程序（源程序）翻译成与之等价的另⼀种语⾔（⽬标语⾔）的程序（⽬标程序）。

编译程序：⼀种翻译程序，将⾼级语⾔编写的源程序翻译成等价的机器语⾔或汇编语⾔的⽬标程序。

1.2词法分析、语法分析、语义分析和中间代码⽣成、代码优化、⽬标代码⽣成1.3词法分析：根据语⾔的词法规则对构成源程序的符号进⾏扫描和分解，识别出⼀个个的单词。

语法分析：根据语⾔的语法规则，把单词符号串分解成各类语法单位。

语义分析及中间代码⽣成：对语法分析识别出的语法单位分析其含义，并进⾏初步翻译。

代码优化：对中间代码进⾏加⼯变换，以产⽣更⾼效的⽬标代码。

⽬标代码⽣成：将中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或会变指令代码。

以上5个阶段依次执⾏。

习题22.1 （1）有穷⾮空的符号集合（2）利⽤产⽣是规则A->v将A替换为v时与A的上下⽂⽆关。

（3）略（4）推导是把句型中的⾮终结符⽤⼀个产⽣是规则的右部开替代的过程；直接推导是将⾮终结符的替代结果只⽤了⼀次产⽣式规则。

（5）略（6）⼀个句型的最左直接短语（7）如果⼀个⽂法存在某个句⼦对应两棵不同的语法树或有两个不同的最左（右）推导，则称这个⽂法是⼆义的。

2.2（1）VN =｛Z,A,B｝ VT ={a,b,c,d,e}（2）abbcde,abbbcde是，acde不是。

2.3 （1）L[G]={d|n≥1,m≥0}（2）2.4 （1） A=>B=>c=>fAg=>fBg=>fCg=>feg（2）A=>AaB=>AaC=>Aae=>Bae=>BcCae=>Bceae=>Cceae=>eceae（3）A=>B=>BcC=>BcfAg=>BcfAaBg=>BcfAaCg=>BcfAaeg=>BcfBaeg =>BcfCaeg=>Bcfeaeg=>Ccfeaeg=>ecfeaeg（3）中题⽬有错应为C fCg|e2.5L[G]=｛a?b?c?|aab,n≥2｝2.6 (1)Z→AB A→Aa|ε B→Bb|ε(2)Z→aZb|ab(3)Z→aAb A→aAb|b(4)Z→AB A→aAb|ab B→cB|ε(5)Z→aaAb|ab Z→aaBb|bb A→aaAb|ab B→aaBb|bb2.7 ⼀位数：Z→2|4|6|8两位数：Z→AB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8三位以上：Z→ACB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8 C→CDD→0|1|2|3|4|5|6|7|8|92.8证明：E=>E+T=>E+T*F短语：T*F E+T*F 直接短语：T*F 句柄：T*F2.9 语法树： E 短语：E*T , (E*T) , F↑(E*T) ，F ,E* F↑(E*T)E *F 直接短语：E*T , FT ↑ F 句柄：FF ( E )E * T2.10（1）语法树（2）直接短语：a , ZZ 句柄：Z( L )L , ZZ ( L )Za2.11最左推导：Z=>ZaB=>BaB=>B+AaB=>A+AaB=>(+)Z*aB=>(+)ZaB*aB =>(+)+aB*aB=>(+)+aA*aB=>(+)+a(*aB=>(+)+a(*aA=>(+)+a(*a(直接短语：（，+句柄：(2.12(1) S=>iSeS=>iiSeS=>iiIeS=>iiIeIS=>iS=>iiSeS=>iiIeS=>iiIeI(2) S=>SaS=>cSaS=>cfaS=>cfafS=>cS=>cSaS=>cfaS=>cfaf(3) E=>EOE=>EOEOE=>iOEOE=>i+EOE=>i+iOE=>i+i-E=>i+i-iE=>EOE=>iOE=>i+E=>i+EOE=>i+iOE=>i+i-E=>i+i-i2.13 Z→aABZ|cCACdA→bAB|aZA|cCCB→bAB|CzbC→cZ|c习题33.1(1)确定的有限⾃动机(2)不确定的有限⾃动机(3)正规集是⼀类特殊的单词集合，正规式是正规集的描述⼯具 3.2 (1) (1|2|3|4|5|6|7|8|9|0)*(1|3|5|7|9) (2) 11(0|1)*00 3.3 证明：b *(a|b)+=｛a,b,ab,ba,aa,bb …｝ (a|b)+=｛a,b,ab,ba,aa,bb …｝ 3.4 (1)(2)DDDD3.5(1) (2)(3)3.6(1) (01|10) *(01|10)(2) (0(1|00)*)|003.7(1) Z →1AB (2)Z →ABA →(0|1)A A →0A|εA →0|1B →(0|1)B|ε B →0B B →ε3.8 r=a(a|b )*bb3.9 Z →1BB →0Z|0 Z →0Z|ε3.10 3.11DDD习题44.1 (1)若⽂法G[Z]满⾜①⽂法不含左递归②③(2)4.2(1) First(S)={a,d} First(B)={a,d,c,ε}First(A)={a,d,e,c} First(D)={a,d,ε}Follow(S)={#,a,b,d,e} Follow(B)={a,d}Follow(A)={b} Follow(D)={e,a,d,b}(2) 不是4.3 (1) 证明： First(Z)={a,b,c} Follow(S)={#,a,b,c,d} First(A)={a,b,c,d} Follow(A)={ #,a,b,c,d }First(B)={a,d,c} Follow(B)={ a,b,c,d } 是LL(1)⽂法。

编译原理课后答案（第三版蒋立源康慕宁编）第一章习题解答1解：源程序是指以某种程序设计语言所编写的程序。

目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。

翻译程序是将某种语言翻译成另一种语言的程序的统称。

编译程序与解释程序均为翻译程序，但二者工作方法不同。

解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。

即边解释边执行，翻译所得的指令序列并不保存。

编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。

即先翻译、后执行。

2解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。

3解：C语言的关键字有：auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。

上述关键字在C语言中均为保留字。

4解：C语言中括号有三种：{}，[]，（）。

其中，{}用于语句括号；[]用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。

C语言中无END关键字。

逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。

5略第二章习题解答1.（1）答：26*26=676（2）答：26*10=260（3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658个2.构造产生下列语言的文法（1）{anbn|n≥0}解：对应文法为G(S) = ({S},{a,b},{ S→ε| aSb },S)（2）{anbmcp|n,m,p≥0}解：对应文法为G(S) = ({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)（3）{an # bn|n≥0}∪{cn # dn|n≥0}解：对应文法为G(S) = ({S,X,Y},{a,b,c,d,#}, {S→X, S→Y,X→aXb|#,Y→cYd|# },S)（4）{w#wr# | w?{0,1}*,wr是w的逆序排列}解：G(S) = ({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S)（5）任何不是以0打头的所有奇整数所组成的集合解：G(S) = ({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e, I→J|2|4|6|8, Jà1|3|5|7|9}, S)（6）所有偶数个0和偶数个1所组成的符号串集合解：对应文法为S→0A|1B|e，A→0S|1C B→0C|1S C→1A|0B3.描述语言特点（1）S→10S0S→aAA→bAA→a解：本文法构成的语言集为：L(G)={(10)nabma0n|n, m≥0}。

编译原理课后习题答案第三章N=>D=> {0,1,2,3,4,5,6,7,8,9}N=>ND=>NDDL={a |a(0|1|3..|9)n且 n>=1}(0|1|3..|9)n且 n>=1{ab,}a nb n n>=1第6题.(1) <表达式> => <项> => <因子> => i(2) <表达式> => <项> => <因子> => (<表达式>) => (<项>)=> (<因子>)=>(i)(3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i(4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项>=> <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>)=> i+(<因子>+<因子>)=> i+(i+i)(6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i第7题第9题语法树ss s* s s+aa a推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F语法树:E*短语: T*F E+T*F直接短语: T*F句柄: T*F12．短语：直接短语：句柄：13.(1)最左推导：S => ABS => aBS =>aSBBS => aBBS => abBS => abbS => abbAa => abbaa最右推导：S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) 文法：S ABSS Aa S ε A aB b(3) 短语：a1 , b1 , b2, a2 , , bb , aa , abbaa,直接短语： a1 , b1 , b2, a2 , , 句柄：a114 (1)S ABA aAb | εB aBb | ε (2)S 1S0 S AA 0A1 |ε第四章1. 1. 构造下列正规式相应的DFA (1) 1(0|1)*101NFA123114(2) 1(1010*|1(010)*1)*0 NFA(3)NFA(4)NFA2.解：构造DFA 矩阵表示b其中0 表示初态，*表示终态用0，1，2，3，4，5分别代替{X} {Z} {X,Z} {Y} {X,Y} {X,Y,Z}得DFA状态图为：3．解：构造DFA矩阵表示构造DFA的矩阵表示其中表示初态，*表示终态替换后的矩阵4．（1）解构造状态转换矩阵：{2，3} {0，1}{2，3}a={0,3} {2},{3},{0,1}{0,1}a={1,1} {0,1}b={2,2}（2）解：首先把M 的状态分为两组：终态组{0}，和非终态组{1，2，3，4,5} 此时G=( {0},{1,2,3,4,5} ) {1,2,3,4,5}a ={1,3,0,5} {1,2,3,4,5}b ={4,3,2,5}由于{4}a ={0} {1,2,3,5}a ={1,3,5}因此应将{1,2,3,4,5}划分为{4},{1,2,3,5} G=({0}{4}{1,2,3,5}) {1,2,3,5}a ={1,3,5} {1,2,3,5}b ={4,3,2}因为{1,5}b ={4} {23}b ={2,3}所以应将{1,2,3,5}划分为{1,5}{2,3} G=({0}{1,5}{2,3}{4}){1,5}a ={1,5} {1,5}b ={4} 所以{1,5} 不用再划分{2,3}a ={1,3} {2,3}b ={3,2}因为 {2}a ={1} {3}a ={3} 所以{2,3}应划分为{2}{3} 所以化简后为G ＝（ {0},{2},{3},{4},{1,5}）7.去除多余产生式后，构造NFA 如下确定化，构造DFA 矩阵G={(0,1,3,4,6),(2,5)} {0,1,3,4,6}a={1,3}{0,1,3,4,6}b={2,3,4,5,6}所以将{0,1,3,4,6}划分为 {0,4,6}{1,3} G={(0,4,6),(1,3),(2,5)}{0,4,6}b={3,6,4} 所以划分为{0},{4,6} G={(0),(4,6),(1,3),(2,5)}不能再划分，分别用0，4，1，2代表各状态，构造DFA 状态转换图如下；b8．代入得S = 0(1S|1)| 1(0S|0) = 01(S|ε) | 10(S|ε) = (01|10)(S|ε) = (01|10)S | (01|10)= (01|10)*(01|10)构造NFA由NFA可得正规式为(01|10)*(01|10)=(01|10)+9.状态转换函数不是全函数,增加死状态8,G={(1,2,3,4,5,8),(6,7)}(1,2,3,4,5,8)a=(3,4,8) (3,4)应分出(1,2,3,4,5,8)b=(2,6,7,8)(1,2,3,4,5,8)c=(3,8)(1,2,3,4,5,8)d=(3,8)所以应将(1,2,3,4,5,8)分为(1,2,5,8), (3,4)G={(1,2,5,8),(3,4),(6,7)}(1,2,5,8)a=(3,4,8) 8应分出(1,2,5,8)b=(2,8)(1,2,5,8)c=(8)(1,2,5,8)d=(8)G={(1,2,5),(8),(3,4),(6,7)}(1,2,5)a=(3,4,8) 5应分出G={(1,2), (3,4),5, (6,7) ,(8) }去掉死状态8,最终结果为 (1,2) (3,4) 5,(6,7) 以1,3,5,6代替,最简DFA为b正规式:b*a(da|c)*bb*第五章1.S->a | ^ |( T )T -> T , S | S(a,(a,a))S => ( T ) => ( T , S ) => ( S , S ) => ( a , S) => ( a, ( T )) =>(a , ( T , S ) ) => (a , ( S , S )) => (a , ( a , a ) )S=>(T) => (T,S) => (S,S) => ( ( T ) , S ) => ( ( T , S ) , S ) => ( ( T , S , S ) , S ) => ( ( S , S , S ) , S )=> ( ( ( T ) , S , S ) , S ) => ( ( ( T , S ) , S , S ) , S ) =>( ( ( S , S ) ,S , S ) , S ) => ( ( ( a , S ) , S , S ) , S )=> ( ( ( a , a ) , S , S ) , S ) => ( ( ( a , a ) , ^ , S ) , S ) => ( ( ( a , a ) , ^ , ( T ) ) , S )=> ( ( ( a , a ) , ^ , ( S ) ) , S ) => ( ( ( a , a ) , ^ , ( a ) ) , S ) => ( ( ( a , a ) , ^ , ( a ) ) , a )S->a | ^ |( T )T -> T , ST -> S消除直接左递归：S->a | ^ |( T )T -> S T’T’ -> , S T’ | ξSELECT ( S->a) = {a}SELECT ( S->^) = {^}SELECT ( S->( T ) ) = { ( }SELECT ( T -> S T’) = { a , ^ , ( }SELECT ( T’ -> , S T’ ) = { , }SELECT ( T’ ->ξ) = FOLLOW ( T’ ) = FOLLOW ( T ) = { ） } 构造预测分析表分析符号串（ a , a ）#分析栈剩余输入串所用产生式#S ( a , a) # S -> ( T )# ) T ( ( a , a) # ( 匹配# ) T a , a ) # T -> S T’# ) T’ S a , a ) # S -> a# ) T’ a a , a ) # a 匹配# ) T’，a) # T’ -> , S T’# ) T’ S , , a ) # , 匹配# ) T’ S a ) # S->a# ) T’ a a ) # a匹配# ) T’) # T’ ->ξ# ) ) # )匹配# # 接受2.E->TE’ E’->+E E’->ξ T->FT’ T’->T T’->ξ F->PF’ F’->*F’ F’->ξP->(E) P->a P->b P->∧SELECT（E’－>+E）={+}SELECT（E’－>ε）=FOLLOW(E’)= {#，)}SELECT（T－>FT’）=FIRST（F）= {（，a，b，^}SELECT（T’ —>T）=FIRST（T）= {（，a，b，^）SELECT(T’－>ε)=FOLLOW(T’)= {＋，#，)}SELECT(F －>P F’)=FIRST(F)= {（，a，b，^}SELECT(F’－>*F’)={*}SELECT(F’－>ε)=FOLLOW(F’)= {（，a，b，^，＋，#，）}3. S->MH S->a H->Lso H->ξ K->dML K->ξ L->eHf M->K M->bLMFIRST ( S ) =FIRST(MH)= FIRST ( M ) ∪ FIRST ( H ) ∪ {ξ} ∪ {a}= {a, d , b , e ,ξ}FIRST( H ) = FIRST ( L ) ∪ {ξ}= { e , ξ}FIRST( K ) = { d , ξ}FIRST( M ) = FIRST ( K ) ∪ { b } = { d , b ,ξ}FOLLOW ( S ) = { # , o }FOLLOW ( H ) = FOLLOW ( S ) ∪ { f } = { f , # , o }FOLLOW ( K ) = FOLLOW ( M ) = { e , # , o }FOLLOW ( L ) ={ FIRST ( S ) –{ξ} } ∪{o} ∪ FOLLOW ( K )∪ { FIRST ( M ) –{ξ} } ∪ FOLLOW ( M )= {a, d , b , e , # , o }FOLLOW ( M ) ={ FIRST ( H ) –{ξ} } ∪ FOLLOW ( S )∪{ FIRST ( L ) –{ξ} } = { e , # , o }SELECT ( S-> M H) = ( FIRST ( M H) –{ξ} ) ∪ FOLLOW ( S )= ( FIRST( M ) ∪ FIRST ( H ) –{ξ} ) ∪ FOLLOW ( S )= { d , b , e , # , o }SELECT ( S-> a ) = { a }SELECT ( H->L S o ) = FIRST(L S o) = { e }SELECT ( H ->ξ ) = FOLLOW ( H ) = { f , # , o }SELECT ( K-> d M L ) = { d }SELECT ( K->ξ ) = FOLLOW ( K ) = { e , # , o }SELECT ( L-> e H f ) = { e }SELECT ( M->K ) = ( FIRST( K ) –{ξ} ) ∪ FOLLOW ( M ) = {d，e , # , o }SELECT ( M -> b L M )= { b }构造LL( 1 ) 分析表4 . 文法含有左公因式，变为S->C $ { b, a }C-> b A { b }C-> a B { a }A -> b A A { b }A-> a A’ { a }A’-> ξ { $ , a, b }A’-> C { a , b }B->a B B { a }B -> b B’ { b }B’->ξ { $ , a , b }B’-> C { a, b }5. <程序> --- S <语句表>――A <语句>――B <无条件语句>――C <条件语句>――D <如果语句>――E<如果子句> --FS->begin A end S->begin A end { begin }A-> B A-> B A’ { a , if }A-> A ; B A’-> ; B A’ { ; }A’->ξ { end }B-> C B-> C { a }B-> D B-> D { if }C-> a C-> a { a }D-> E D-> E D’ { if }D-> E else B D’-> else B { else }D’->ξ {; , end }E-> FC E-> FC { if }F-> if b then F-> if b then { if }非终结符是否为空S－否 A－否A’－是 B－否 C－否 D－否D’－是 E－否 F－否FIRST(S) = { begin }FIRST(A) = FIRST(B) ∪ FIRST(A’) ∪ {ξ} = {a , if , ; , ξ}FIRST(A’) ={ ; , ξ}FIRST(B) = FIRST(C) ∪ FIRST(D) ={ a , if }FIRST(C) = {a}FIRST(D) = FIRST（E）= { if }FIRSR(D’) = {else , ξ}FIRST(E) = FIRST(F) = { if }FIRST(F) = { if }FOLLOW(S) = {# }FOLLOW(A) = {end}FOLLOW(A’) = { end }FOLLOW(B) = {; , end }FOLLOW (C) = {; , end , else }FOLLOW(D) = {; , end }FOLLOW( D’ ) = { ; , end }FOLLOW(E) = { else , ; end }FOLLOW(F) = { a }S A A’ B C D D’ E F if then else begin end a b ;6. 1.(1) S -> A | B(2) A -> aA|a(3)B -> bB |b提取（2），（3）左公因子(1) S -> A | B(2) A -> aA’(3) A’-> A|ξ(4) B -> bB’2.(1) S->AB(2) A->Ba|ξ(3) B->Db|D(4) D-> d|ξ提取（3）左公因子(1) S->AB(2) A->Ba|ξ(3) B->DB’(4) B’->b|ξ(5) D-> d|ξ3.(1) S->aAaB | bAbB(2) A-> S| db(3) B->bB|a4(1)S->i|(E)(2)E->E+S|E-S|S提取（2）左公因子(1)S->i|(E)(2)E->SE’(3)E’->+SE’|-SE’ |ξ5(1)S->SaA | bB(2)A->aB|c(3)B->Bb|d消除（1）(3)直接左递归(1)S->bBS’(2)S’->aAS’|ξ(4) B -> dB’(5)B’->bB’|ξ6.(1) M->MaH | H(2) H->b(M) | (M) |b消除（1）直接左递归，提取（2）左公因子(1)M-> HM’(2)M’-> aHM’ |ξ(3)H->bH’ | ( M )(4)H’->(M) |ξ7. (1)1)A->baB2)A->ξ3)B->Abb4)B->a将1）、2)式代入3）式1)A->baB2)A->ξ3)B->baBbb4)B->bb5)B->a提取3）、4）式左公因子1)A->baB2)A->ξ3)B->bB’4)B’->aBbb | b5)B->a(3)1)S->Aa3)A->SB4)B->ab将3）式代入1）式1)S->SBa2)S->b3)A->SB4)B->ab消除1）式直接左递归1)S->bS’2)S’->BaS’ |ξ3)S->b4)A->SB5)B->ab删除多余产生式4）1)S->bS’2)S’->BaS’ |ξ3)S->b4)B->ab（5）1)S->Ab2)S->Ba3)A->aA4)A->a5)B->a提取3） 4）左公因子1)S->Ab2)S->Ba3)A->aA’4)A’-> A |ξ将3）代入1） 5）代入21)S->aA’b2)S->aa3)A->aA’4)A’-> A |ξ5)B->a提取1） 2）左公因子1)S-> aS’2)S’->A’b | a3)A->aA’4)A’-> A |ξ5)B->a删除多余产生式5）1)S-> aS’2)S’->A’b | a3)A->aA’4)A’-> A |ξA A’ S’ S将3）代入4）1)S-> aS’2)S’->A’b | a3)A->aA ’4)A’-> aA’ |ξ将4）代入2）1)S-> aS’2)S’->aA’b3)S’->a4)S’->b5)A->aA ’6)A’-> aA’ |ξ对2）3)提取左公因子1)S->aS’2)S’->aS’’3)S’’->A’b|ξ4)S’->b5)A->aA ’6)A’-> aA’ |ξ删除多余产生式5）1)S->aS’2)S’->aS’’3)S’’->A’b|ξ4)S’->b5)A’-> aA’ |ξ第六章1S a | ∧ | ( T )T T , S | S解：(1) 增加辅助产生式S’＃S＃求 FIRSTVT集FIRSTVT（S’）＝ {#}FIRSTVT（S）＝{a ∧ ( }＝{ a ∧ ( } FIRSTVT (T) ＝{,} ∪ FIRSTVT( S ) = { , a ∧ ( }求 LASTVT集LASTVT（S’）＝ { # }LASTVT（S）＝{ a ∧ )}LASTVT (T) ＝{ , a ∧ )}(2)算符优先关系表a∧(),# a·>·>·>∧·>·>·> (<·<·<·=·<·)·>·>·>,<·<·<··>·>#<·<·<·=·因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法(3)a ∧( ) , #F 1 1 1 1 1 1g 1 1 1 1 1 1f 2 2 1 3 2 1g 2 2 2 1 2 1f 3 3 1 3 3 1g 4 4 4 1 2 1f 3 3 1 3 3 1g 4 4 4 1 2 1(4)栈优先关系当前符号剩余输入串移进或规约＃<· ( a,a)# 移进＃( <· a ,a)# 移进# (a ·> , a)# 规约＃(T <· , a)# 移进＃(T，<· a )# 移进＃(T,a ·> ) # 规约＃(T,T ·> ) # 规约＃(T =· ) # 移进＃(T) ·> ＃规约＃T =·＃接受4.扩展后的文法S’#S# S S;G S G G G(T) G H H a H(S)T T+S T S（1）FIRSTVT(S)={;}∪FIRST VT(G) = {; , a , ( }FIRSTVT(G)={ ( }∪FIRSTVT(H) = {a , ( }FIRSTCT(H)={a , ( }FIRSTVT(T) = {+} ∪FIRSTVT(S) = {+ , ; , a , ( }LASTVT(S) = {;} ∪LASTVT(G) = { ; , a , )}LASTVT(G) = { )} ∪ LASTVT(H) = { a , )}LASTVT(H) = {a, )}LASTVT(T) = {+ } ∪LASTVT(S) = {+ , ; , a , ) };()a+#；·><··><··>·> (<·<·＝·<·<·)·>·>·>·>·> a·>·>·>·>·> +<·<··><··>#<·<·<·＝·因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法（2）句型a(T+S);H;(S)的短语有：a(T+S);H;(S) a(T+S);H a(T+S) a T+S (S) H直接短语有: a T+S H (S)句柄： a素短语：a T+S (S)最左素短语：a(3)分析a；（a＋a）（4）不能用最右推导推导出上面的两个句子。

编译原理教程课后习题答案【篇一：编译原理教程课后习题答案——第一章】完成下列选择题：(1) 构造编译程序应掌握a. 源程序b. 目标语言c. 编译方法d. 以上三项都是(2) 编译程序绝大多数时间花在上。

a. 出错处理b. 词法分析c. 目标代码生成d. 表格管理(3) 编译程序是对。

a. 汇编程序的翻译b. 高级语言程序的解释执行c. 机器语言的执行d. 高级语言的翻译【解答】(1) d (2) d(3) d1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。

在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。

这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。

在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。

因此，编译对源程序的处理是先翻译，后执行。

从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。

这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。

1.3 请画出编译程序的总框图。

如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】编译程序总框图如图1-1所示。

作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。

第二章 高级语言及其语法描述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=46．令文法G6为 N →D|NDD →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 ＝＞34N ＝＞ ND ＝＞ NDD ＝＞ DDD ＝＞ 5DD ＝＞ 56D ＝＞ 568 N ＝＞ ND ＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：A →SN, S →+|-|∑, N →D|MDD →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. 文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiE EFT+T F FTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S → iSeS|iS|I解：因为iiiiei 有两种最左推导，所以此文法是二义的。

编译原理教程课后习题答案【篇一：编译原理教程课后习题答案——第一章】完成下列选择题：(1) 构造编译程序应掌握a. 源程序b. 目标语言c. 编译方法d. 以上三项都是(2) 编译程序绝大多数时间花在上。

a. 出错处理b. 词法分析c. 目标代码生成d. 表格管理(3) 编译程序是对。

a. 汇编程序的翻译b. 高级语言程序的解释执行c. 机器语言的执行d. 高级语言的翻译【解答】(1) d (2) d(3) d1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。

在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。

这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。

在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。

因此，编译对源程序的处理是先翻译，后执行。

从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。

这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。

1.3 请画出编译程序的总框图。

如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】编译程序总框图如图1-1所示。

作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。

（完整版）编译原理课后习题答案第一章1．典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。

2. 实现编译程序的主要方法有哪些？答：主要有：转换法、移植法、自展法、自动生成法。

3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？答：编译法、解释法。

4. 编译方式和解释方式的根本区别是什么？答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。

第二章1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关系如何？答：1）0型文法、1型文法、2型文法、3型文法。

2）2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。

答：Z→SME | BS→1|2|3|4|5|6|7|8|9M→ε | D | MDD→0|SB→2|4|6|8E→0|B3. 设文法G为：N→ D|NDD→ 0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。

答：N?ND?N3?ND3?N23?D23?123N?ND?NDD?DDD?1DD?12D?123N?ND?N1?ND1?N01?D01?301N?ND?NDD?DDD?3DD?30D?301N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?7 5431N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754 DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。

答：对于句型iiSeS存在两个不同的最左推导：S?iSeS?iiSesS?iS?iiSeS所以该文法是二义性文法。

作业参考答案第二章 高级语言及其语法描述6、（1）L （G 6）={0,1,2,......,9}+（2）最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568 最右推导：N=>ND =>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>568 7、Ｇ：S →ABC | AC | CA →1|2|3|4|5|6|7|8|9B →BB|0|1|2|3|4|5|6|7|8|9C →1|3|5|7|98、（1）最左推导：E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iE=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=>i*(i+i) 最右推导：E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*iE=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>T*(i+i)=>F*(i+i)=>i*(i+i) (2)9、证明：该文法存在一个句子iiiei 有两棵不同语法分析树，如下所示，因此该文法是二义的。