编译原理 龙书答案

（Aho）4.4考虑文法

R→R ‘|’ R | RR | R* | (R) | a | b c) 构造等价的非二义性文法 R→R ‘|’ A | A A→A B | B B→B* | C C→( R ) | a | b

（Aho）4.5下面if-then-else文法试图消除空悬else的二义性，证明它仍是二义性的 stmt→if expr then stmt | matched_stmt

matched_stmt→if expr then matched_stmt else stmt | other 解：

用S、M、E表示stmt、matched_stmt和expr，用i、t、e、o表示if、then、else和other 则句子i E t i E t o e i E t o e o对应两个最左推导：

i E t i E t o e i E t o e o

i E t i E t o e i E t o e o 因此文法是二义性文法

直接构造比较困难，可从SLR分析表的构造角度考虑，LR(0)项目集规范族中，项目 I8={M→i E t M e S, S→ M}，有移进/归约冲突，这就是是二义性所在。

显然，存在句型...i E t M e S...和...i E t S e S...，当M位于栈顶时，产生移进/归约冲突。 按此思路，构造形如... i E t S e S...的句型即可

（Aho）4.6 为下列语言设计上下文无关文法。哪些语言是正规式？ a) 满足这样条件的二进制串：每个0之后都紧跟着至少一个1 S→0 A | 1 S | A→1 S

正规式：(1 | 01)*

b) 0和1个数相等的二进制串 S→0 S 1 S | 1 S 0 S |

d) 不含011子串的二进制串 S→0 A | 1 S | A→0 A | 1 B | B→0 A |