编译原理第六周

13331130 李有才
编译原理

一、 给出生成下述语言的上下文无关文法:
1. $\{a^nb^na^mb^m | n, m >= 0\}$.

$S \rightarrow AA$
$A \rightarrow aAb | ε$

1. $\{1^n0^m1^m0^n | n, m >= 0\}$.

   $S \rightarrow 1S0 | A$
   $A \rightarrow 0A1 | ε$

2. $\{WaW^r | W 属于\{0|a\}^* ,W^r 表示 W 的逆\}$.

   $S \rightarrow 0Sa | aS0 | a$

二、 考虑以下文法:
$S \rightarrow aB|bA$
$A \rightarrow aS|bAA|a$
$B \rightarrow bS|aBB|b$
给出串 aaabbabbba 的最左推导,最右推导以及推导树

最左推导
$S \Rightarrow aB$
     $\Rightarrow aaBB$
     $\Rightarrow aaaBBB$
     $\Rightarrow aaabSBB$
     $\Rightarrow aaabbABB$
     $\Rightarrow aaabbaBB$
     $\Rightarrow aaabbabB$
     $\Rightarrow aaabbabbS$
     $\Rightarrow aaabbabbbA$
     $\Rightarrow aaabbabbba$
最右推导
$S \Rightarrow aB$
     $\Rightarrow aaBB$
     $\Rightarrow aaBbS$
     $\Rightarrow aaBbbA$
     $\Rightarrow aaBbba$
     $\Rightarrow aaaBBbba$
     $\Rightarrow aaaBbbba$
     $\Rightarrow aaabSbbba$
     $\Rightarrow aaabbAbbba$
     $\Rightarrow aaabbabbba$
推导树

三、 考虑以下文法:
$N \rightarrow SE|E$
$S \rightarrow SD|D$
$E \rightarrow 0|2|4|6|8|10$
$D \rightarrow 0|1|2|3|4|5|6|7|8|9$
1. 证明此文法有二义性。

对字符串10推导
推导1：
$N \Rightarrow SE$
     $\Rightarrow DE$
     $\Rightarrow 1E$
     $\Rightarrow 10$
推导2：
$N \Rightarrow E$
     $\Rightarrow 10$
对同一字符串存在两个最左推导，所以此文法有二义性

1. 此文法描述的语言是什么(用自然语言表述)。

   非负偶数

2. 写出一个新的文法,要求新文法无二义且和上述文法产生相同的语言。

   $N \rightarrow SE|E$
   $S \rightarrow SD|D$
   $E \rightarrow 0|2|4|6|8$
   $D \rightarrow 0|1|2|3|4|5|6|7|8|9$

四、 考虑以下文法:
$S \rightarrow aTUV | bV$
$T \rightarrow U | UU$
$U \rightarrow ε | bV$
$V \rightarrow ε | cV$
写出每个非终端符号的 FIRST 集和 FOLLOW 集。

$first(S)=\{a, b \}$
$first(T)=\{ε, b \}$
$first(U)=\{ε,b \}$
$first(V)=\{ε, c \}$
$follow(S)=\{ \$ \}$
$follow(T)=\{b, c, \$ \}$
$follow(U)=\{b, c, \$ \}$
$follow(V)=\{b, c, \$ \}$