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