【正文】 1X2 … X n 構(gòu)造 FIRST(α) (1)置 FIRST(α)= FIRST(X1)\{ε} (2)若對(duì)任何 1≤j≤i1， ε∈ FIRST(Xj)，則把 FIRST(Xj)\{ε}加至 FIRST(α)中 (3)特別的，若所有的 FIRST(Xj)均含有 ε， 1≤j≤n，則把 ε 也加至 FIRST(α)中 ， a, ∧ ,( a ( ∧ S → a | ∧ | (T) T→ST’ T’→,ST’|ε 解： FOLLOW(T)={ }。 FIRST( T’)={ }。 → εT 39。F輸 入 符 號(hào)i + * （ ） F → iE 39。編譯原理 —— 練習(xí) 1 王金偉 計(jì)算機(jī)與信息工程學(xué)院 天津師范大學(xué) 練習(xí) 基本概念 ? 編譯程序的結(jié)構(gòu) ? 上下文無(wú)關(guān)文法的一些概念 ? 詞法分析 ? 語(yǔ)法分析 ?自上而下 ?自下而上 源程序 目標(biāo)程序 ( 字符串 ) 詞法分析器 語(yǔ)法分析器 語(yǔ)義分析和中間代碼生成器 代碼優(yōu)化器 目標(biāo)代碼生成器 表 格 管 理 出 錯(cuò) 處 理 對(duì)于 ∑上的每一個(gè)正規(guī)式 V，存在一個(gè) ∑上的 DFA M，使得 L(M) = L(V) 問(wèn)題 ：如何由一個(gè)正規(guī)式 V，構(gòu)造一個(gè) DFA M 思路 ：分兩步走 V，構(gòu)造一個(gè) NFA M’，使得 L(M’) = L(V) M’確定化，變?yōu)?DFA M 第一步 ，在 ∑上構(gòu)造一個(gè) NFA M’ (1)構(gòu)造一個(gè)拓廣的轉(zhuǎn)換圖 YXV練習(xí) 詞法分析 (2)使用分裂規(guī)則對(duì) V進(jìn)行分裂，加進(jìn)新結(jié)點(diǎn)，直到把圖轉(zhuǎn)換成每條弧上標(biāo)識(shí)為 ∑上的一個(gè)字符或 ε 最后得到一個(gè) NFA M’ 且 L(M’) = L(V) i kV1V2iV1j kV2i jV1| V2iV1jV2i kV*i j kVε ε第二步 ，把 M’確定化 (1)兩個(gè)概念 定義 1：假定 I是 M’的狀態(tài)集的子集，定義 I的 ε閉包ε_(tái)CLOSURE(I)為： (a)若 q∈ I，則 q∈ ε_(tái)CLOSURE(I) (b)若 q∈ I，那么從 q出發(fā)經(jīng)任意條 ε弧而能到達(dá)的任何狀態(tài) q’都屬于 ε_(tái)CLOSURE(I) ； 定義 2：假定 I是 M’的狀態(tài)集的子集，定義 Ia =ε_(tái)CLOSURE(J) 其中， J是所有那些可從 I中的某一狀態(tài)結(jié)點(diǎn)出發(fā)經(jīng)過(guò)一條 a弧而到達(dá)的狀態(tài)結(jié)點(diǎn)的全體 例 ：有如下一個(gè)狀態(tài)轉(zhuǎn)換圖 假定 I={1, 2}，求 Ia = ？ 解： Ia =ε_(tái)CLOSURE(J) J = { } ε_(tái)CLOSURE(J) = { } Ia={5, 6, 2, 4, 7, 3, 8} 1 a 5 4 3 8 ε ε 2 6 7 ε ε ε a a 4, 5, 3 5, 6, 2, 4, 7, 3, 8 (2)用子集法把 M’確定化 設(shè) ∑ = {a， b} ① 構(gòu)造一張表 I Ia =ε_(tái)CLOSURE(J) Ib =ε_(tái)CLOSURE(J) 集合 1 集合 1 集合 1 集合 2 集合 2 集合 2 集合 3 集合 3 集合 3 集合 4 集合 4 集合 4 ε_(tái)CLOSURE(X) … … I Ia =ε_(tái)CLOSURE(J) Ib =ε_(tái)CLOSURE(J) ε_(tái)CLOSURE(X) 集合 1 集合 2 集合 3 集合 4 集合 1 集合 3 集合 4 集合 2 … 集合 2 集合 4 集合 3 集合 1 … S a b 0 1 2 3 4 1 3 4 2 … 2 4 3 1 … ② 把得到的每個(gè)集合看成一個(gè)狀態(tài)，得到一張狀態(tài)轉(zhuǎn)換表，該表的初態(tài)就是 ε_(tái)CLOSURE(X)，它的終態(tài)是那些含有終態(tài) Y的子集，這樣就得到一個(gè) DFA M 且 L(M) = L(M’) DFA。T → F T 39。F → ( E )E 39。 FIRST( T )={ }。 FIRST((T))={ }。 (1)假定有個(gè)產(chǎn)生式的一個(gè)候選形為 …aP… 那么，對(duì)任何 b?FIRSTVT(P)，有 a . b。 如果 a.=.b，則從 fa畫一條弧至 gb 如果 a.=.b，則從 gb畫一條弧至 fa 。 正規(guī)式 ： (0|1|2|3|4|5|6|7|8|9)*(0|5) (3) 英文字母組成的所有符號(hào)串 , 要求符號(hào)串中的字母依照字典序排列 。若沒(méi)有矛盾，則 f和 g就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。 例 2:G: S → X | SaX X → Y | X%Y Y → | X！ 求出該文法每個(gè)終結(jié)符號(hào)的優(yōu)先關(guān)系，并構(gòu)造優(yōu)先分析表 (1)S→SaX ，且 %, , ? FIRSTVT(X) aP 所以 a 小于 %, , (2) S→SaX ，且 a, %, !, ? LASTVT(S) Pb 所以 a, %, !, 大于 a 以下略。 (1)對(duì)于分發(fā)開始符號(hào) S，置 于FOLLOW(S)中； (2)若 A→αBβ 是一個(gè)產(chǎn)生式，則把FIRST(β)\{ε}加至 FOLLOW(B)中； (3)若 A→αB 是一個(gè)產(chǎn)生式，或A→αBβ 是一個(gè)產(chǎn)生式而 ε∈ FIRST(β)，F(xiàn)OLLOW(A)加至 FOLLOW(B)中。 a, ∧ , , , ε ∧ , ( a, ( S → a | ∧ | (T) T→ST’ T’→,ST’|ε 解： FIRST(ST’)={ }。 → εE R R O R 1. 定義 FIRST集 令文法 G是不含左遞歸的文法，對(duì) G的非終結(jié)符的候選 α ，定義它的開始符號(hào)（終結(jié)首符）集合： ? 特別地，如果 α ε，則 ε∈ FIRST(α ) ? 如果非終結(jié)符 A的任意兩個(gè)候選式 α i和 α j的開始符號(hào)集滿足 FIRST(α i)∩FIRST( α j)=Φ，則 A可以根據(jù)所面臨的第一個(gè)輸入符號(hào)，準(zhǔn)確地指派一個(gè)候選式 α 去執(zhí)行任務(wù)， α 是那個(gè) FIRST集含 a的候選式，即 a ∈ FIRST(α ) *? ? ?TF I R ST ( ) { a | a . . . , a V }αα*? X∈ VN∪ VT構(gòu)造其 FIRST(X) 連續(xù)使用以下規(guī)則，直至每個(gè)結(jié)合 FIRST不再增大為止 (1)若 X∈ VT，則 FIRST(X)={X}. (2)若 X∈ VN，且有產(chǎn)生式 X→a … ，則把 a加入到 FIRST(X)中；若 X→ ε 也是一條產(chǎn)生式，則把 ε 也加到 FIRST(X)中。 → ε T 39。 其中 Pj→ δ 1|δ 2|… |δ k是關(guān)于 Pj的所有產(chǎn)生式 Endfor 消除關(guān)于 Pi的直接左遞歸 Endfor (3)化簡(jiǎn)由 (2)得到的文法：除去從開始符號(hào)無(wú)法達(dá)到的非終結(jié)符的產(chǎn)生式 PP ??例子 ：考慮以下文法，消除其左遞歸性 S→Qc | c Q→Rb | b R→Sa | a 解 ： (1)把該文法的非終結(jié)符排列為 R、 Q、 S. (2)對(duì)于 R，不存在直接左遞歸，不用消除 對(duì)于 Q，把 R代入到 Q的有關(guān)候選式后，把 Q的產(chǎn)生式改寫為 Q→Sab| ab | b 現(xiàn)在 Q不存在直接左遞歸，不用消除 對(duì)于 S，把 Q代讀到 S的有關(guān)候選式后，把 S的產(chǎn)生式改寫為 S→Sabc | abc | bc | c S有直接左遞歸，消除 S的直接左遞歸為 S→abcS’ | bcS’ | cS’ S’→abcS’ | ε 得到消除左遞歸性的文法為 S→abcS’ | bcS’ | cS’ S’→abcS’ | ε Q→Sab| ab | b R→Sa | a (3)顯然， Q和 R的產(chǎn)生式已經(jīng)是多余的，將它們?nèi)サ? 化簡(jiǎn)后的文法是： S→abcS’ | bcS’ | cS’ S’→abcS’ | ε 注意 ：由于對(duì)非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣，但它們都是等價(jià)的 例如 ：考慮剛才的文法，消除其左遞歸性 S→Qc | c Q→Rb |