11. 将上下文无关文法 G[S]改写为等价的正则文法。 G[S]： SabcA AbcB Ba
12. 已知文法 G[S]： SaB|bA Aa|aS|bAA Bb|bS|aBB 证明该文法是二义的。
13. 有人认为“无符号偶数”构造文法的思路如下：无符号偶数是无符号整数的 2 倍，所以构造的文法 G[<偶数>]如下， G[<偶数>]： <偶数><整>*2 <整><整><整>|<数> <数>0|1|2|3|4|5|6|7|8|9 这种想法对吗？为什么？
7. 有关表达式的文法 G[E]： EE+T|T TT*F|F Fi|(E) 求句型 F*F*(T+T*i)的短语、简单短语和句柄。
8. 若Σ={0, 1}，则Σ2=？ 9. 给出描述语言 L(G)={anbn|n1}的文法。
10. 文法 G1[A]和 G2[A]是否等价？为什么？ G1[A]：AbA|a G2[A]：ABa|a BBb|b
班级：
姓名：
第二章练习题 学号：
一、填空题 1. 任一文法终结符集合和非终结符集合的交集是 。 2. 文法 G 产生的 的全体称为该文法描述的语言。 3. 已知文法 G[S]: SaSb|ab|，该文法描述的语言 L(G)= 。 4. 已知文法 G[S]: SAB, AAa|, BbBc|bc，该文法描述的语言 L(G)= 。 5. 文法 G[S]: SAB, AaAb|, BbBc|所描述的语言 L(G)= 。 6. 设字母表 A1={a,b,c,…,z}，A2={0,1,2,…,9}，则 A1 A2 中含有 个元素。 7. 设是文法 G 的句型， A 是非终结符， 若 则称是句 型相对于非终结符 A 的短语，若 则称是句 型相对于非终结符 A 的直接短语，若 则称是 句型的句柄。 二、判断题 1. 0 型文法中每条规则左部至少包含一非终结符。 2. 文法中的大写字母一定是非终结符。 3. 文法规则左边出现的符号一定是非终结符。 4. 3 型文法一定是 2 型、1 型和 0 型文法。 5. 文法的任一句型对应唯一的一棵语法树。 6. 文法的任一句型对应唯一的一个最左（右）推导。 7. 文法规则右部的符号一定是终结符号。 8. 一个语言的文法是唯一的。 9. 每个非终结符号产生的终结符号串集合都是该语言的子集。 10. 一个语言（如 PASCAL）的句子是无穷的。 11. 语法树描述的是一个文法。 12. 若 G 是正则文法，则 G 一定是上下文无关文法。
A. 语法分析 B. 语义分析 C. 词法分析 D. 目标代码生成 6. 正则式（ ）与(a*|b)*(c|d)等价。 A. a*(c|d)|b(c|d) B. B. a*(c|d)*|b(c|d)* C. a*(c|d)|b*(c|d) D. (a|b)*c|(a|b)*d 7. 同正则式 a*b*等价的文法是（ ） 。 A. G1：SaS|bS| B. G2：SaSb| C. G3：SaS|Sb| D. G4：SabS| 8. 给定语言 L(G)={anbbn|n1}，则文法（ ）可产生语言 L(G)。 A. ZaZb|aAb|b, AaAb|b B. AAbB, AaA|a, BbB|b C. AaAb|b D. ZaAb, AaAb|b 9. 由文法识别符号通过若干步（包括 0 步）推导得到的符号串是（ ） 。 A. 语言 B. 句型 C. 句子 D. 句柄 10. 句型最左简单子树的叶节点，自左向右排列组成句型的（ ） 。 11. 设文法 G=({S}, {0, 1}, P, S)，其中 P={SSS|0S1|1S0|}，该文法所描述的语言为 （ ） 。 A. {0n1n|n0} B. {w|w{0|1}*}且 w 中 0 和 1 的个数相等 C. {0m1k|m, k0}{1m0k|m, k0} D. {0n1n|n0}{1n0n|n0} 四、问答题 1. 设有文法 G[S]： SAa ABb|CD Ce 求 VN、VT 和该文法所描述的语言 L(G)。
2. 设有文法 G[A]： ABa BbB|a 求该文法所描述的语言 L(G)。
3. 设有文法 G[S]： S A AB|IF A THEN A ELSE A BC|B+C|+C CD|C*D|*D Dx|(A)|- D 求文法的非终结符集合和终结符集合
4. 消除文法 G[Z]中的多余规则。 G[Z]: ZBe AAe|e BCe|Af CCf D f

14. 给出描述语言 L(G)={a2nbn|n1}的 2 型文法。
15. 试给出描述语言 L(G)={a2m+1bm+1|m0} {a2mbm+2|m0}的文法。
16. 构造一文法，使其描述的语言是不能被 5 整除的且不以 0 开头的偶整数的集 合。
（ ） （ ） （ ） （ ） （ ） （ ） （ ） （ ） （ ） （ ） （ ） （ ）
三、选择题 1. 由“非终结符符号串”形式的规则构成的文法是（ ） 。 A. 0 型文法 B. 1 型文法 C. 2 型文法 D. 3 型文法 2. 文法 G[S]和语言 L(G[S])之间的关系是（ ） 。 A. 一一对应 B. 一个语言对应唯一的文法，反之则不然 C. 一个文法对应唯一的语言，反之则不然 D. 非二义性文法时，C 正确；二义性文法时，则一个文法可对应多个语言。 3. 关于短语和句柄，正确的叙述为（ ） 。 A. 短语就是句柄 B. 直接短语才可能是句柄 B. 最左短语一定是句柄 D. 最右短语一定是句柄 4. BNF 是一种广泛采用的（ ）的工具。 A. 描述规则 B. 描述语言 C. 描述文法 D. 描述句子 5. 在编译中产生语法树是为了（ ） 。
5. 设有文法 G[S]： SaAb ABcA|B Bidt| 请问下列符号串是否为文法的句子或句型。 ①aidtcBcAb ②aidtccb ③ab ④abidt ⑤aidtcidtcidtb ⑥aidtBb 6. 已知文法 G[E]： ET|E+T|E- T TF|T*F|T/F F(E)|i ①该文法的识别符号？ ②给出 VN 和 VT ③给出句型 T+T*F+i 的所有短语、直接短语和句柄。