(完整word版)编译原理教程课后习题答案——第三章.docVIP

第三章 语法分析 3.1 完成下列选择题： (1) 文法 G：S→ xSx|y 所识别的语言是 。 a. xyx b. (xyx)* c. xnyxn(n ≥ 0) d. x*yx* (2) 如果文法 G 是无二义的，则它的任何句子α 。 最左推导和最右推导对应的语法树必定相同 最左推导和最右推导对应的语法树可能不同 最左推导和最右推导必定相同 可能存在两个不同的最左推导，但它们对应的语法树相同 (3) 采用自上而下分析，必须 。 a. 消除左递 a. 必有 ac 归 b. 消除右递归 c. 消除回溯 d. 提取公共左因子 (4) 设 a、b、 c 是文法的终结符，且满足优先关系 ab 和 bc，则 。 b. 必有 ca c. 必有 ba d. 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) d 3.2 令文法 G[N] 为 G[N]: N →D|ND D → 0|1|2|3|4|5|6|7|8|9 G[N] 的语言 L(G[N]) 是什么 ? 给出句子 0127、 34 和 568 的最左推导和最右推导。 【解答】 G[N] 的语言 L(G[N]) 是非负整数。 最左推导： NNDNDDNDDDDDDD0DDD01DD012D0127 NNDDD3D34 NNDNDDDDD5DD56D568 最右推导： NNDN7ND7N27ND27N127D1270127 NNDN4D434 NNDN8ND8N68D68568 3.3 已知文法 G[S] 为 S→ aSb|Sb|b，试证明文法 G[S] 为二义文法。 【解答】 由文法 G[S] ：S→ aSb|Sb|b，对句子 aabbbb 可对应如图 3-1 所示的两棵 语法树。 S S a S b S b a S b a S b S b a S b b b 图 3-1 句子 aabbbb 对应的两棵不同语法树 因此，文法 G[S] 为二义文法 (对句子 abbb 也可画出两棵不同语法树 )。 3.4 已知文法 G[S] 为 S→ SaS|ε，试证明文法 G[S] 为二义文法。 【解答】 由文法 G[S] ： S→ SaS|ε，句子 aa 的语法树如图 3-2 所示。 S S S a S S a S S a S S a S (a) (b) 图 3-2 句子 aa对应的两棵不同的语法树由图 3-2 可知，文法 G[S] 为二义文法。 3.5 按指定类型，给出语言的文法。 L={aibj|j ＞ i≥ 0} 的上下文无关文法； 字母表Σ ={a,b} 上的同时只有奇数个 a 和奇数个 b 的所有串的集合的正规文法； 由相同个数 a 和 b 组成句子的无二义文法。 【解答】 (1) 由 L={aibj|j ＞ i ≥ 0} 知，所求该语言对应的上下文无关文法首先应有 S→ aSb 型产生式， 以保证 b 的个数不少于 a 的个数； 其次，还需有 S→ Sb 或 S→ b 型的产生 式，用以保证 b 的个数多于 a 的个数。因此，所求上下文无关文法 G[S] 为 G[S] ： S→ aSb|Sb|b (2) 为了构造字母表Σ ={a,b} 上同时只有奇数个 a 和奇数个 b 的所有串集合的正规式，我们 画出如图 3-3 所示的 DFA ，即由开始符 S 出发，经过奇数个 a 到达状态 A ，或经过奇数个 b 到达状态 B ；而由状态 A 出发，经过奇数个 b 到达状态 C(终态 ) ；同样，由状态 B 出发经过 奇数个 a 到达终态 C。 由图 3-3 可直接得到正规文法 G[S] 如下： G[S] ： S→ aA|bB A A → aS|bC|b a b B→ bS|aC|a a b C→ bA|aB|ε S C b a 图 3-3 习题 3.5 b a 的 DFA B (3) 我们用一个非终结符 A 代表一个 a(即有 A → a)，用一个非终结符 B 代表