【正文】 按其定義，可用下面兩條規(guī)則來構(gòu)造集合 FIRSTVT(P)： ① 若有產(chǎn)生式 P→a… 或 P→Qa… ， 則 a?FIRSTVT(P)； ② 若 a?FIRSTVT(Q)，且有產(chǎn)生式 P→Q… ， 則 a?FIRSTVT(P)。 (4)同理構(gòu)造構(gòu)造集合 LASTVT(P)的算法 按其定義，可用下面兩條規(guī)則來構(gòu)造集合 LASTVT(P)： ① 若有產(chǎn)生式 P→… a 或 P→… aQ ， 則 a? LASTVT(P)； ② 若 a? LASTVT(Q)，且有產(chǎn)生式 P→… Q ， 則 a? LASTVT(P)。 (5)有了這兩個(gè)集合之后，就可以通過檢查每個(gè)產(chǎn)生式的候選式確定滿足關(guān)系 .和 .的所有終結(jié)符對。 (1)假定有個(gè)產(chǎn)生式的一個(gè)候選形為 …aP… 那么，對任何 b?FIRSTVT(P)，有 a . b。 (2)假定有個(gè)產(chǎn)生式的一個(gè)候選形為 …Pb… 那么，對任何 a?LASTVT(P)，有 a . b。 F I R S T V T P a P a P Qa a V Q VT N( ) { | , , }? ? ? ? ?? ?? ?或 而},|{)( NT VQVaaQPaPaPLA S TV T ????? ?? 而或 ??例 1:考慮下面的文法 G： S → X | SaX X → Y | X%Y Y → | X！ 構(gòu)造該文法 G的每個(gè)非終結(jié)符的 FIRSTVT和 LASTVT集合 解 : (1)構(gòu)造 FIRSTVT集合 FIRSTVT(Y)={ } FIRSTVT(X)={ } FIRSTVT(S)={ } ① 若有產(chǎn)生式 P→a… 或 P→Qa… ，則 a?FIRSTVT(P)； ② 若 a?FIRSTVT(Q)，且有產(chǎn)生式P→Q… ，則 a?FIRSTVT(P)。 , %, , a, %, , 例 1:考慮下面的文法 G： S → X | SaX X → Y | X%Y Y → | X！ 構(gòu)造該文法 G的每個(gè)非終結(jié)符的 FIRSTVT和 LASTVT集合 解 : (1)構(gòu)造 LASTVT集合 LASTVT(Y)={ } LASTVT(X)={ } LASTVT(S)={ } !, %, ! , a, %, !, ① 若有產(chǎn)生式 P→… a 或 P→… aQ ，則 a? LASTVT(P)； ② 若 a? LASTVT(P)，且有產(chǎn)生式P→… Q ，則 a? LASTVT(P)。 例 2:G: S → X | SaX X → Y | X%Y Y → | X！ 求出該文法每個(gè)終結(jié)符號的優(yōu)先關(guān)系，并構(gòu)造優(yōu)先分析表 (1)S→SaX ，且 %, , ? FIRSTVT(X) aP 所以 a 小于 %, , (2) S→SaX ，且 a, %, !, ? LASTVT(S) Pb 所以 a, %, !, 大于 a 以下略。 FIRSTVT(S)={a, %, , } FIRSTVT(X)={ %, , } FIRSTVT(Y)={ , } LASTVT(S)={a, %, !, } LASTVT(X)={ %, !, } LASTVT(Y)={ !, } (1)假定有個(gè)產(chǎn)生式的一個(gè)候選形為 …aP… 那么，對任何 b?FIRSTVT(P)，有 a . b。 (2)假定有個(gè)產(chǎn)生式的一個(gè)候選形為 …Pb… 那么，對任何 a?LASTVT(P)，有 a . b。 a % ! a . . . . % . . . . . . . . . . . =. ! . . . 構(gòu)造分析表如下： 其中，空白為錯(cuò)誤 如果優(yōu)先函數(shù)存在，則可以通過以下三個(gè)步驟從優(yōu)先表構(gòu)造優(yōu)先函數(shù) : (1)對于每個(gè)終結(jié)符 a，令其對應(yīng)兩個(gè)符號 fa和 ga，畫一張以所有符號 fa和 ga為結(jié)點(diǎn)的方向圖。 如果 a.=.b，則從 fa畫一條弧至 gb 如果 a.=.b，則從 gb畫一條弧至 fa 。 (2)對每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn) (包括出發(fā)點(diǎn)自身 )。 賦給 fa的數(shù)作為 f(a) 賦給 ga的數(shù)作為 g(a)。 (3)檢查所構(gòu)造出來的函數(shù) f和 g是否與原來的關(guān)系矛盾。若沒有矛盾，則 f和 g就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。 i + * i ?? ?? ?? + ? ?? ? ?? * ? ?? ?? ?? ? ? ? gi fi f* g* g+ f+ f g 例 :取前面文法 G(E) (1) E→E+T | T (2) T→T*F | F (3) F→ (E) | i 的終結(jié)符 +， *， i， i + * f g 7 4 6 6 2 1 5 1 (1) U | V = V | U 或的交換律 證明：因?yàn)椋?L(U|V) = L(U)∪ L(V) 又因?yàn)椋?L(V|U) = L(V)∪ L(U) = L(U)∪ L(V) 因?yàn)椋? L(U|V) = L(V|U) 所以， U | V = V | U (2) U | ( V|W ) = ( U|V ) | W 或的結(jié)合律 證明： 因?yàn)椋?L(U|(V|W))=L(U)∪ L(V|W) =L(U)∪ L(V)∪ L(W) 又因?yàn)椋?L(( U|V ) | W) = L(U|V)∪ L(W) = L(U)∪ L(V)∪ L(W) 因此， L(U|(V|W)) = L(( U|V ) | W) 所以， U | ( V|W ) = ( U|V ) | W ? (3)證明 U(VW)=(UV)W 因?yàn)? L(U(VW)) =L(U)L(VW) = L(U)(L(V)L(W)) =(L(U)L(V))L(W) = L(UV)L(W) = L((UV)W) ? (4)證明 U ( V | W ) = ( UV ) | ( UW ) 因?yàn)? L(U)(L(V) ∪ L(W)) =(L(U)L(V)) ∪ (L(U)L(W)) ? (5) εU=Uε=U 證： L(εU)=L(ε)L(U)=L(U)0 L(U)=L(U) ?8. 給出下面的正規(guī)表達(dá)式。 (1) 以 01結(jié)尾的二進(jìn)制數(shù)串 。 正規(guī)式 (0|1)*01 (2) 能被 5整除的十進(jìn)制整數(shù) 。 正規(guī)式 ： (0|1|2|3|4|5|6|7|8|9)*(0|5) (3) 英文字母組成的所有符號串 , 要求符號串中的字母依照字典序排列 。 正規(guī)式 (a|A)*(b|B)*(c|C)*(d|D)*…(z|Z)* (4)給出描述包含奇數(shù)個(gè) 1或奇數(shù)個(gè) 0個(gè)二進(jìn)制數(shù)串的正規(guī)表達(dá)式： 解題思路： 本題求二進(jìn)制串，并且要求包含奇數(shù)個(gè) 0或奇數(shù)個(gè) 1，由于0和 1都可以在二進(jìn)制串中任何地方出現(xiàn)，所以本題只需要考慮一種情況，另外一種情況也可以類似求得?？紤]包含奇數(shù)個(gè) 0的字符串：由于只關(guān)心 0的個(gè)數(shù)的奇偶數(shù)，我們可以把二進(jìn)制串分成多段來考慮，第 1段為二進(jìn)制串的開始到第 1個(gè) 0為止，這一段包含 1個(gè) 0，并且 0的前面有 0個(gè)或多個(gè) 1，對于剩下的二進(jìn)制串按照每段包含兩個(gè) 0的方式去劃分，即以 0開始，以 0結(jié)尾，中間可以有 0個(gè)或多個(gè) 1，如果一個(gè)二進(jìn)制串被這樣劃分完后，剩下的部分如果全部是全 1串（這些全 1串在前面劃分的串之間或最后），則該二進(jìn)制串就具有奇數(shù)個(gè) 0，所以該二進(jìn)制可以這樣描述：以第 1段（ 1*））開始，后面由全 1串（ 1*）以及包含兩個(gè) 0的串（ 01*0）組成，所以包含奇數(shù)個(gè) 0的正規(guī)表達(dá)式為：1*0（ 1｜ 01*0） *，本題的解答則是： 1*0（ 1｜ 01*0） *｜ 0*1（ 0｜ 10*1） * (5)沒有重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號串全體 . (6) 最多有一個(gè)重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號串全體 令 ri = i | ?, i=0,1,2,...,9 R0|R1|R2|...|R9記為 ? Ri i?(0,1,2...,9) P(0,1,2...,9)表示 0,1,2...,9的全排列 ? ri0ri1...ri9 i0i1... i9?P(0,1,2...,9) ? i ? ri0ri1...ri9 i?(0,1,2...,9) i0i1... i9?P(0,1,2...,9) (7) 不包含子串 abb的由 a和 b組成的符號串全體 . b*( a* | (ba)* )*