《编译原理阶段练习二》由会员分享，可在线阅读，更多相关《编译原理阶段练习二（6页珍藏版）》请在金锄头文库上搜索。
1、编译原理练习二一、填空题1、假设 G 是一个文法，S 是文法的开始符号，如果 S*x 则称 x 是句型。2、文法 G 产生的 句子 的全体是该文法描述的语言。3、文法 GS：SAB AaA| BbBc|bc 描述的语言 L（GS）=anbmcm | n0,m1 。4、已知文法 GE：ET|E+T|E-TTF|T*F|T/FF（E）|i该文法的开始符号是 E ，终级符号集合 VT 是 + ,- ,* ,/ ,( ,) ,i ，非终级符号集合 VN 是E, T, F，句型 T+T*F+i 的短语有 T+T*F+i, 第一个 T，T*F 和 i。改写该文法以消除直接左递归，改写后的文法为：ET(+|
2、-)T, TF(*|/)F , F (E)|i 。5、乔姆斯基定义的四种形式语言文法分别为： 0 型文法（又称 短语文法） 、1型文法（又称 上下文有关 文法） 、 2 型 文法（又称上下文无关 文法） 、3 型文法（又称 正规 文法） 。6、自顶向下语法分析方法的基本思想是：从 识别符号 出发，不断建立 直接推导 ，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串 。7、递归下降法的主要原理是，对每个非终极符按其产生式结构产生相应语法分析子程序，其中的终极符产生 匹配命令 ，而非终极符则产生 调用命令 ，由于文法递归相应子程序也递归，所以称这种方法为递归子程序方法或递归下降法。8
3、、LL（K）分析法中， “K”的含义是 向输入串中查看 k 个输入符号 。9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行 直接归约 ，试图 归约 到文法的 开始符号 。10、LR（0）分析法的名字中， “L”的含义是 从左到右进行分析 ， “R”的含义是 采用最右推导的逆过程最左归约 ， “0”的含义是 向貌似句柄的符号串后查看 0 个输入符号 。二、选择题（单项或多项）1、文法 G 所描述的语言是 d 的集合。a. 文法 G 的字汇表 V 中所有符号组成的符号串b. 文法 G 的字汇表 V 的闭包 V*中的所有符号串c. 由文法的开始符号推出的所有符号
4、串d. 由文法的开始符号推出的所有终极符号串2、巴科斯-诺尔范式（即 BNF）是一种广泛采用的 c 的工具。a.描述规则 b.描述语言 c.描述文法 d.描述句子3、描述语言 L=ambn|nm1的文法为 d 。a. Z Abb b. ZABbAaA|a AAa|aBbB|b BaBb|bc. ZAb d. ZaAbAaAb|a AAb|aAb|4、II1|I0|Ia|Ic|a|b|c下列符号串中是该文法的句子的有 b c d .a. ab0 b. a0c01 c. aaa d. bc105、 若一个文法是递归的，则它所产生语言的句子个数 a 。a.必定是无穷的 b.是有限个的 c.根据具体情
5、况而定6、一个句型中的最左 b 称为给句型的句柄。a. 短语 b. 简单短语 c. 素短语 d. 终极符号7、一个上下文无关文法 G 包括四个组成部分依次为：一组 g ，一组 h ，一个 e ，以及一组 c 。a. 字符串 b. 字母数字串 c. 产生式 d. 结束符号e. 开始符号 f. 文法 g. 非终极符号 h. 终极符号8、下列文法 a 二义文法EEiT|TTT+F|iF|FFE*|（a. 是 b. 不是 c. 无法判定9、编译过程中，语法分析器的任务是 b c d 。a. 分析单词是怎样构成的b. 分析单词串是如何构成语句和说明的c. 分析语句和说明是如何构成程序的d. 分析程序的结
6、构10、语法分析的常用方法是 a b 。a. 自顶向下 b. 自底向上 c. 自左向右 d. 自右向左11、编译程序中的语法分析器接受以 c 为单位的输入，并产生有关信息供以后各阶段使用。a. 表达式 b. 产生式 c. 单词 d. 语句12、高级语言编译程序常用的语法分析方法中，递归下降分析方法属于 a 分析方法。a. 自顶向下 b. 自底向上 c. 自左向右 d. 自右向左13、LL（1）文法的条件是 c 。a. 对形如 Ux1| x1| | xn 的规则，要求 FIRST（ xi） FIRST （x j）= , (ij)b. 对形如 Ux1| x1| | xn 的规则，若 xi * ，要
7、求 FIRST（x j） FOLLOW（U ）= c. (a)和（b）d. 都不是14、已知文法 GE：ETEE+TE|TFTT *FT|F(E)|idFOLLOW（F）= *,+,#,，FIRST（T）= *, 。a. *，+ b. *， c. +，#，d. *，+，#， e. #， f. *，+，#， ，id15、LR 语法分析栈中存放的状态是识别 b 的 DFA 状态。a. 前缀 b. 可归前缀 c. 项目 d. 句柄三、设有文法 GS：SAAB|IF A THEN A ELSE ABC|B+C|+CCD|C*D|*DDx|（A ）|-D(1) 试问其中哪些是终极符号，哪些是非终极符号(
8、2) 对于下列符号串：（ x*-x）IF x+x THEN x*x ELSE -xIF -x THEN x ELSE IF x THEN x+x ELSE x试分别构造其推导的语法分析树，并指出句柄。解答：（1）非终极符号集S，A，B，C，D 终极符号集IF，THEN，ELSE，+，-，*， （， ） ，x（2）句型推导的语法树如下图句型（x*-x）的句柄为 第一个 x句型 IF x+x THEN x*x ELSE -x 的句柄为 第一个 x句型 IF -x THEN x ELSE IF x THEN x+x ELSE x 的句柄为-x四、设有文法 GS：SABCD（ ）ABCC D*BxD
9、D-xSIF A THEN ELSE AABB + CCDxDxBC*C DDxxBCDD-xIF A THEN ELSE AASIF A THEN ELSE AABCDD-xBCDxBCDxB + CCDxDxB BCDxSa|（T）TT,S|S请给出句子（a,(a,a)）的最左、最右推导。解答：最左推导为：S(T)(T,S)(S,S) (a,S) (A,(T) (a,(T,S) (a,(S,S) (a,(a,S) (a,(a,a)最右推导为：S(T) (T,S) (T,(T) (T,(T,S) (T,(T,a) (T,(S,a) (T,(a,a) (S,(a,a) (a,(a,a)五、试消
10、除下列文法的直接左递归G1S： SSa|Ab|b|cABc|aBSb|b解答： S(bcb|ab|b|c)SS(a|bcb)S|ABc|aBSb|bG2S： Sa|（T）TT.S|S解答： Sa|（T）TSTT.ST|六、试构造生成语言 L=anbnci|n1,i0的文法。解答：SaAbBAaAb|BcB|七、有文法 GN：NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|9证明此文法有二义性；此文法所描述的语言是什么？证明：对于文法的句子 110，存在两棵不同的语法树或两种不同的最左（最右）推导，所以文法具有二义性。NSEDE1E110NSESDEDDE1DE11E110此文法描述的语言是偶数集合八、知文法 GS：SeT|RTTDR|RdR|Da|bd(1) FIRST(S)= a,b,d,e, ,FIRST(T)= a,b, ,FIRST(R)= d, ,FIRST(D)= a,b .(2) FOLLOW(S)= # ,FOLLOW(T)= # ,FOLLOW(R)= a,b,# ,FOLLOW(D)= d,# .(3) 该文法的 LL（1）分析表为：a b d e #S RT RT RT eT RTT DR DR R DR D a bd
