编译第3章习题(文法和语言)_09级

《编译原理》课后习题答案第三章第3 章文法和语言第1 题文法G＝({A,B,S},{a,b,c},P,S)其中P 为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

答案：L(G[S])={abc}第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 开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如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])的全部元素。

盛威网（）专业的计算机学习网站 1《编译原理》课后习题答案第三章答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={anbn|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第6 题已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。

（５）i+(i+i)（６）i+i*i盛威网（）专业的计算机学习网站 2 《编译原理》课后习题答案第三章答案：<表达式><表达式> + <项><因子><表达式><表达式> + <项><因子>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盛威网（）专业的计算机学习网站 3《编译原理》课后习题答案第三章第7 题证明下述文法G[〈表达式〉]是二义的。

第3章文法和语言习题参考答案1. L(G)={abc}2. L(G[N])是无符号整数。

3.G3: E→D+E | D-E | DD→0|1|2|3|4|5|6|7|8|94. L(G[Z])={a n b n | n>0}5.(1) G5: N→DN | EE→0|2|4|6|8D→E|1|3|5|7|9(2) G5: N→AB|EB→DB|EA→1|2|3|4|5|6|7|8|9E→0|2|4|6|8D→A|06.(1) E⇒T E (5) E⇒ E+T E (6) E⇒ E+T E⇒F T ⇒⇒⇒i F ⇒ F+T T F ⇒ F+T T T * Fi ⇒ i+T F ( E ) ⇒ i+T F F i⇒ i+F i E + T ⇒ i+T*F i i⇒ i+(E) T F ⇒ i+F*F⇒ i+(E+T) F i ⇒ i+i*F⇒ i+(T+T) i ⇒ i+i*i⇒ i+(F+T)⇒ i+(i+T)⇒ i+(i+F)⇒ i+(i+i)7. E E i+i*i的两棵语法树不同，E O E E O E 故文法是二义的。

i + E O E E O E * ii * i i + i8. S S abc的两棵语法树不同，A c aB 故文法是二义的。

a b b c9. (1) S (2) 该文法生成的语言是后缀表达式，S S * 或称为逆波兰式。

S aa a10. （1）该文法生成的语言是“可并列或嵌套的配对的括号串”。

（2）文法是二义的，因为句子“()()”有两棵不同的语法树。

S SS ( S ) S S ( S ) SS ( S ) S εεεε S ( S ) Sεεεεεε11. 可构造E+T*F的语法树如右所示： E 短语：E+T*F T*F故为文法的句型。

+ T 其中，T*F是直接短语和句柄T * F13. （1）最左推导最右推导(2) 文法规则可有：(3) 短语直接短语句柄S⇒ABS S⇒ABS S→ABS | Aa |εabbaa⇒aBS ⇒ABAa A→a a a a⇒aSBBS ⇒ABaa B→SBB | b εε⇒aBBS ⇒ASBBaa b b⇒abBS ⇒ASBbaa b b⇒abbS ⇒ASbbaa bb⇒abbAa ⇒Abbaa a a⇒abbaa ⇒abbaa aa14. (1) G1: S→CD (2) G2: S→1S0|AC→aCb|ε A→0A1|εD→aDb|ε(3) G3: S→0S0|aSa|a15．{WaW}上下文无关，W对应编程语言中的各种括号；{a n b m c n d m}上下文有关。

第三章习题参考解答3.1 构造自动机A，使得①②③当从左至右读入二进制数时，它能识别出读入的奇数；④它识别字母表{a, b}上的符号串，但符号串不能含两个相邻的a，也不含两个相邻的b；⑤它能接受字母表{0, 1}上的符号串，这些符号串由任意的1、0和随后的任意的11、00对组成。

⑥它能识别形式如±dd*⋅ d*E ±dd的实数，其中，d∈{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。

3.2 构造下列正规表达式的DFSA：① xy*∣yx*y∣xyx；② 00∣(01)*∣11；③ 01((10∣01)*(11∣00))*01；④ a(ab*∣ba*)*b。

3.3 消除图3.24所示自动机的空移。

bεq1q2q3aba,bqaq6q4q5abεεε图3.24 含空移的自动机3.4 将图3.25所示NDFSA确定化和最小化。

xyqq1q2q4q3xyxyx,yx图3.25 待确定化的NDFSA3.5 设e、e1、e2是字母表∑上的正规表达式，试证明① e∣e=e；② {{e}}={e}；③ {e}=ε∣e{e}；④ {e1 e2} e1= e1{e2 e1};⑤ {e1∣e2}={{e1}{e2}}={{e1}∣{e2}}。

3.6 构造下面文法G[Z]的自动机，指明该自动机是不是确定的，并写出它相应的语言： G[Z]:Z→A0A→A0∣Z1∣03.7 设NDFSA M=({x, y},{a, b},f, x, {y}), 其中，f(x, a)={x, y}, f(x, b)={y}, f(y, a)=∅, f(y, b)={x, y}。

试对此NDFSA确定化。

3.8 设文法G[〈单词〉]：〈单词〉→〈标识符〉∣〈无符号整数〉〈标识符〉→〈字母〉∣〈标识符〉〈字母〉∣〈标识符〉〈数字〉〈无符号整数〉→〈数字〉∣〈无符号整数〉〈数字〉〈字母〉→a∣b〈数字〉→1∣2试写出相应的有限自动机和状态图。

编译原理第三章练习题答案编译原理第三章练习题答案编译原理是计算机科学中的重要学科，它研究的是如何将高级语言代码转化为机器语言的过程。

在编译原理的学习过程中，练习题是不可或缺的一部分，通过完成练习题可以更好地理解和掌握编译原理的知识。

本文将为大家提供编译原理第三章练习题的答案，希望对大家的学习有所帮助。

1. 什么是语法分析？语法分析是编译器中的一个重要模块，它的主要任务是根据给定的语法规则，对输入的源代码进行分析和解释。

语法分析器会根据语法规则构建一个语法树，用于表示源代码的结构和含义。

常用的语法分析方法有递归下降法、LL(1)分析法和LR分析法等。

2. 什么是LL(1)文法？LL(1)文法是一种特殊的上下文无关文法，它具有以下两个特点：(1) 对于任何一个句子，最左推导和最右推导是唯一的。

(2) 在预测分析过程中，只需要向前看一个输入符号就可以确定所采用的产生式。

LL(1)文法是一种常用的文法形式，它适用于递归下降法和LL(1)分析法。

3. 什么是FIRST集合和FOLLOW集合？FIRST集合是指对于一个文法符号，它能够推导出的终结符号的集合。

FOLLOW 集合是指在一个句型中，某个非终结符号的后继终结符号的集合。

计算FIRST集合和FOLLOW集合可以帮助我们进行语法分析，特别是LL(1)分析。

4. 什么是递归下降语法分析法？递归下降语法分析法是一种基于产生式的自顶向下的语法分析方法。

它的基本思想是从文法的开始符号开始，递归地根据产生式进行分析，直到推导出输入符号串或发现错误。

递归下降语法分析法的实现比较简单，但对于某些文法可能会出现回溯现象，影响分析效率。

5. 什么是LR分析法？LR分析法是一种自底向上的语法分析方法，它的基本思想是从输入符号串开始，逐步构建语法树，直到推导出文法的开始符号。

LR分析法具有较好的分析效率和广泛的适用性，常用的LR分析方法有LR(0)、SLR(1)、LR(1)和LALR(1)等。

习题第3章文法和语言参考答案1．写一文法，使其语言是偶整数集合。

解：允许以0打头G：N→+A|-A|AA→DA|ED→0|1|2|3|4|5|6|7|8|9E→0|2|4|6|82．写一文法，使其语言是偶整数集合，但不允许由0打头。

解：0除外G：N→+A|-A|AA→CB|EB→DB|EC→1|2|3|4|5|6|7|8|9D→0|1|2|3|4|5|6|7|8|9E→0|2|4|6|83．写一文法G，使得L(G) = { a m b n| m≥0, n≥1 }解：G1:S→aS|T或 G2:S→aS|bT 或 G3:S→aS|Sb|bT→bT|b T→bT|ε4．写一文法G，使得L(G) = { a m b n c p| m≥0, n≥0, p≥0 }解：G1:S→ABC 或G2:S→Sc|T 或 G3:A→aA|bB|cC|εA→aA|ε T→Tb|R B→bB|cC|εB→bB|ε R→Ra|ε C→cC|εC→cC|ε5．设有文法G1：S → AaBS → aA → ABA → bA →εB → bBB →ε写一文法G2，使得L(G1) = L(G2)，并且G2不含空规则。

解：G2:S→BaB|Ba|aB|a 或G2:S→bB|Sb|aB→bB|b6．写一文法，使其语言是十位数不是0的整数集合。

解：G：N→SAS→+|-|εA→D|CD|BCDB→B D|CC→1|2|3|4|5|6|7|8|9D→0|1|2|3|4|5|6|7|8|97．写出以下文法G所定义的语言L(G)。

G：S → SaSS → bS → d解：L(G)={(xa)n x|n≥0, x∈{b,d}}={((b|d)a)n(b|d)|n≥0}={(b|d)(a(b|d))n|n≥0}8．设有文法G1：S → Sab | c | d将其改写成以下形式的文法G2，每条规则形如：V → xW或V → y其中V和W为非终结符，x和y为终结符串。

第三章习题1．给出与下图中的DFA 等价的正规文法G 。

解：G(A)：A → aD | bB B → aCC → bA | aD | ε D → aB | bD| ε2．构造与下列正规式等价的DFA (1) (a|b)* | ab*c + (2) b | a(aa*b)*b（1）答：①与之等价的εNFA 为-② 消除ε边后的NFA 为-③确定化过程如下：b--（2）答：本题可以直接得到DFA 如下（如果带有ε边，取消ε边，合并等价状态后同样可以该结果）：+3． 将下列DFA 最小化+(b)-aa解答：{0,1},{2,3,4,5} {0,1},{2,4},{3,5}4. 将下面两个NFA确定化和最小化（如果具有ε边，先删除ε边）. （1）答：标识隐含的开始状态和结束状态，并消除ε边后得到如下NFA：（2）现将该DFA 进行最小化：(ⅰ)按照结束或非结束状态，初始划分成两个子集，即{1,2}, {3,4}(ⅱ)为得到下一分划，考察子集{1,2}。

因为δ(1,a)= 3 , δ(2,a)= 1故1和2可拆分，于是便得到当前划分{1}, {2}, {3,4}(ⅲ)再考虑{3,4}，因为δ(3,a)= 1 , δ(4,a)= 1，δ(3,b)= 4 ,δ(4,b)= 4所以3和4不可区分，故子集{3,4}已不能再分裂。

子集分裂的过程宣告结束。

(ⅳ) 现选择状态3作为{3,4}的代表，将状态4从状态转换图中删去，并将原来指向4的箭头都指向3，这样，我们就得到了最小化后的DFA 如下所示：-5． 对于以下DFA ，根据课件中给出的控制器，按照下列表格给出符号串abcbb#的识别过程。

+。

第3章文法和语言第1题文法G＝({A,B,S},{a,b,c},P,S)其中P为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

答案：L(G[S])={abc}第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开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。

答案：G[S]: S->S+D|S-D|D D->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...bbbL(G[Z])={a n b n|n>=1}第5题写一文法，使其语言是偶正整数的集合。

要求：(1) 允许0打头；(2)不允许0打头。

答案：(1)允许0开头的偶正整数集合的文法E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8(2)不允许0开头的偶正整数集合的文法E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0第6题已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。

（５）i+(i+i)（６）i+i*i第8题文法G[S]为：S→Ac|aBA→abB→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc (2)S=>aB=>abc即存在两不同的最右推导。

第三章语法分析3.1 完成下列选择题：(1) 文法G：S→xSx|y所识别的语言是。

a. xyxb. (xyx)*c. xnyxn(n≥0)d. x*yx*(2) 如果文法G是无二义的，则它的任何句子α。

　a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同(3) 采用自上而下分析，必须。

a. 消除左递 a. 必有ac归b. 消除右递归c. 消除回溯d. 提取公共左因子(4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则。

b. 必有cac. 必有bad. a～c都不一定成立(5) 在规范归约中，用来刻画可归约串。

a. 直接短语b. 句柄c. 最左素短语d. 素短语(6) 若a为终结符，则A→α·aβ为项目。

a. 归约b. 移进c. 接受d. 待约(7) 若项目集Ik含有A→α· ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α· ”动作的一定是。

a. LALR文法b. LR(0)文法c. LR(1)文法d. SLR(1)文法(8) 同心集合并有可能产生新的冲突。

a. 归约b. “移进”/“移进”c.“移进”/“归约”d. “归约”/“归约”【解答】(1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法G[N]为G[N]: N→D|NDD→0|1|2|3|4|5|6|7|8|9(1) G[N]的语言L(G[N])是什么?(2) 给出句子0127、34和568的最左推导和最右推导。

【解答】(1) G[N]的语言L(G[N])是非负整数。

(2) 最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D685683.3 已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。

第3章习题解答1.构造正规式‎1(0|1)*101相应‎的D FA.[答案]先构造NF‎A确定化============================================================== 2.将下图确定‎化：[答案]E‎、Z为F。

转化为DF‎A：================================================================ 3.把下图最小‎化：[答案]（1）初始分划得‎Π0：终态组{0}，非终态组{1,2,3,4,5}对非终态组‎进行审查：{1,2,3,4,5}a {0,1,3,5}而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5} ∵{4} a {0}，所以得新分‎划 （2）Π1：{0}，{4}，{1,2,3,5} 对{1,2,3,5}进行审查： ∵{1,5} b {4}{2,3} b {1,2,3,5}，故得新分划‎ （3）Π2：{0}，{4}，{1, 5}，{2,3} {1, 5} a {1, 5}{2,3} a {1,3}，故状态2和‎状态3不等‎价，得新分划 （3）Π3：{0}，{2}，{3}，{4}，{1, 5} 这是最后分‎划了 （4）最小DFA ‎：======================================= 4.构造一个D ‎F A ，它接收Σ={0,1}上所有满足‎如下条件的‎字符串：每个1都有‎0直接跟在‎右边。

并给出该语‎言的正规式‎和正规文法‎。

[答案]按题意相应‎的正规表达‎式是0*(100*)*0* 构造相应的‎D F A ，首先构造N ‎F A 为用子集法确‎定化可最小化，终态组为G ‎1={C, D}，非终态组为‎G 2={S, A, B} 对于G2分‎析：f(S,0)=A, f(A,0)=A, 后继状态均‎属于G2 而f(B,0)=C, 后继状态属‎于G 1 将G2分割‎成G 21={S ，A}， G22={B}经检查DF‎A最小状态‎集有三个，可用S、B、D表示。

《编译原理》课后习题答案第一章第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第2题一个典型的编译程序通常由哪些部分组成各部分的主要功能是什么并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。

第三章语法分析3.1 完成下列选择题：(1) 文法G：S→xSx|y所识别的语言是。

a. xyxb. (xyx)*c. xnyxn(n≥0)d. x*yx*(2) 如果文法G是无二义的，则它的任何句子α。

　a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同(3) 采用自上而下分析，必须。

a. 消除左递 a. 必有ac归b. 消除右递归c. 消除回溯d. 提取公共左因子(4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则。

b. 必有cac. 必有bad. a～c都不一定成立(5) 在规范归约中，用来刻画可归约串。

a. 直接短语b. 句柄c. 最左素短语d. 素短语(6) 若a为终结符，则A→α·aβ为项目。

a. 归约b. 移进c. 接受d. 待约(7) 若项目集Ik含有A→α· ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α· ”动作的一定是。

a. LALR文法b. LR(0)文法c. LR(1)文法d. SLR(1)文法(8) 同心集合并有可能产生新的冲突。

a. 归约b. “移进”/“移进”c.“移进”/“归约”d. “归约”/“归约”【解答】(1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法G[N]为G[N]: N→D|NDD→0|1|2|3|4|5|6|7|8|9(1) G[N]的语言L(G[N])是什么?(2) 给出句子0127、34和568的最左推导和最右推导。

【解答】(1) G[N]的语言L(G[N])是非负整数。

(2) 最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D685683.3 已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。

第三章文法和语言课后习题参考答案1. L(G)={abc}2. L(G[N])是无符号整数。

3.G3: E→D+E | D-E | DD→0|1|2|3|4|5|6|7|8|94. L(G[Z])={a n b n | n>0}5. 写一文法，使其语言是偶正整数的集合要求：(1)允许0打头(2)不允许0打头解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P:S→PD|DP->NP|ND→0|2|4|6|8N->0|1|2|3|4|5|6|7|8|9(2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S)P:S→PD|P0|DP->NR|NR->QR|QD→2|4|6|8N->1|2|3|4|5|6|7|8|9Q->0|1|2|3|4|5|6|7|8|96. 已知文法G：<表达式>::=<项>|<表达式>+<项>|<表达式>-<项><项>::=<因子>|<项>*<因子>|<项>/<因子><因子>::=(<表达式>)|i。

试给出下述表达式的推导及语法树。

(1)i; (2)(i) (3)i*i;(4)i*i+i; (5)i+(i+i);(6)i+i*i。

解：(1)<表达式>=><项>=><因子>=>i(2)<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)(3)<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i(4)<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>=><因子>*<因子>+<因子>=>i*i+i=w(5)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)=> i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i)(6)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>=>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i语法树见下图:7. 为句子i+i*i 构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。

第三章复习重点：1.文法与语言的对应关系思路要点：注意结构拆分技巧：如何将表示语言的通用字符串形式作适当的“切割”？例：已知语言：L1 = {a x b2x c y | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。

提示：该题实际上要求为相应语言设计上下文无关文法。

一个文法设计好后，严格来说应当证明此文法是否对应于该语言。

解：G[S]：S →AB A →ε | aAbb B →ε | cB推导过程：S ⇒ AB +⇒ a x Ab2x B /*使用A →aAbb x次*/⇒ a x b2x B /*使用A →ε一次*/⇒ a x b2x c x B /*使用B →cB x次*/⇒ a x b2x c x/*使用B →ε一次*/举一反三：已知语言L2 = {a x b2y c y | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。

解：G[S]：S →AB A →ε | aA B →ε | bBcc练习：14：写出下列语言对应的文法(1).{a n b n a m b m|n,m≥0}2. {1n 0m 0m 0n |n,m ≥0}3. {1n 0m 0m 0n |n ≥0,m>0}4. { a n b m c k |n,m,k ≥0}G1: S —>AA G2: S —>ABA —>aAb|ε A —>aAb|εB —>aBb|ε G: S —>1S0 S —>A A —>0A1 A —>εG: S →1S0|A S →1S0|0A1 A →0A1|01 A →0A1|ε2. 给出文法，证明文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、直接短语、句柄。

1. 令文法G ［E ］为：Z →bMb M →a|(L L →Ma ）① 符号串b(Ma)b 是否为该文法的一个句型，并证明。