编译原理第二章练习题.pdf

第二章练习题 班级： 姓名： 学号： 一、填空题 1. 任一文法终结符集合和非终结符集合的交集是 。 2. 文法G 产生的 的全体称为该文法描述的语言。 3. 已知文法G[S]: SaSb|ab|，该文法描述的语言L(G)= 。 4. 已知文法G[S]: SAB, AAa |, BbBc|bc，该文法描述的语言 L(G)= 。 5. 文法G[S]: SAB, AaAb|, BbBc|所描述的语言L(G)= 。 6. 设字母表A ={a,b,c,…,z}，A ={0,1,2,…,9} ，则A A 中含有 个元素。 1 2 1 2 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 一定是上下文无关文法。 （） 三、选择题 1. 由“非终结符符号串”形式的规则构成的文法是（ ）。 A. 0 型文法 B. 1 型文法 C. 2 型文法 D. 3 型文法 2. 文法G[S]和语言L(G[S])之间的关系是（ ）。 A. 一一对应 B. 一个语言对应唯一的文法，反之则不然 C. 一个文法对应唯一的语言，反之则不然 D. 非二义性文法时，C 正确；二义性文法时，则一个文法可对应多个语言。 3. 关于短语和句柄，正确的叙述为（ ）。 A. 短语就是句柄 B. 直接短语才可能是句柄 B. 最左短语一定是句柄