12．对下面给出的DFA最小化。 a
a a A b a
b S a B D b
b C b
b a a a b b 1 2 a 3 4
b
13．有如下布尔表达式： a
假定整个表达式的真假出口分别为Ltrue和Lfalse，请翻译成三地址语句。 if a
L1:if c L2:if e 14．有如下语句： if a L1:if c 9 goto L5 L4:T2:=b+1 p:=T2 L5: goto Lnext L2:T3:=c+1 p:=T3 Lnext: ? 五、语法分析 1．设有文法G: S→a|b|(A) A→SdA|S ⑴ 完成下列算符优先关系表，并判断是否为算符优先文法（请说明理由）。 a b ( ) d # a ＜· ＜· ＜· b ＜· ＜· ＜· ( ＜· ＜· ＜· ) ·＞ ·＞ ＝ ·＞ ·＞ d ·＞ ·＞ ＜· ·＞ ＜· # ·＞ ·＞ ·＞ ·＞ ＝ 由于该文法的任何产生的右部都不含两个相继的非终结符，故属于算符文法。 从上表可以看出，任何两个终结符之间至多满足＝、＜· 、·＞三种关系之一，故G为算符优先文法。 ⑵ 给出句型(SdSdS)对应的语法树，指出该句型的短语、句柄 S ( A ) S d A S d A S 10 短语：(SdSdS) SdSdS SdS S 句柄: S 2．设有文法G: S→S*F|F F→F↑P|P P→(S)|i ⑴ 完成下列算符优先关系表，并判断是否为算符优先文法（请说明理由）。 * ↑ ( ) i # * ·＞ ·＞ ＜· ·＞ ·＞ ＜· ↑ ＜· ·＞ ＜· ·＞ ·＞ ＜· ( ＜· ＜· ＜· ＜· ) ·＞ ·＞ ＝ ·＞ ·＞ i ＜· ＜· ＜· ＜· # ·＞ ·＞ ·＞ ·＞ ＝ 由于该文法的任何产生的右部都不含两个相继的非终结符，故属于算符文法。 从上表可以看出，任何两个终结符之间至多满足＝、＜· 、·＞三种关系之一，故G为算符优先文法。 ⑵ 给出句型S*P↑(S)对应的语法树，指出该句型的短语、句柄 S S * F F ↑ P 11 P ( S ) 短语：S*P↑(S) P↑(S) P (S) 句柄: P 12