【文章內(nèi)容簡介】 i F T’ ε ?問題 : 是不是一旦非終結(jié)符 A面臨輸入符號 a, 且 a不屬于所有FIRST(αi), 但 ε屬于某個FIRST(αj), 就一定可以使 A自動匹配 ε呢 ? ?答案是 不一定 。在一定的條件下才可以。否則錯誤。 ?條件是 a 允許跟在 A的緊后面 ?例如上例中， +可跟在 T’后， 可跟在 T’、 E’后面。 ?下面定義 可跟在非終結(jié)符后的終結(jié)符號的集合 FOLLOW。 41 非終結(jié)符的后隨終結(jié)符集 FOLLOW ? 假定 S是文法 G的開始符號，對于任何非終結(jié)符 A， 定義： FOLLOW(A) = { a | S?* …Aa… 且 a?VT } ? 特別是 , 若 S?*…A , 則規(guī)定 ?FOLLOW(A) ( 是句末符號 ) ? 也就是說， FOLLOW(A)是所有句型中，出現(xiàn)在緊接 A之后的終結(jié)符或‘ ’。 ? 例： S→aA A→ε S→d A→bAS FOLLOW(S)={,a,d} FOLLOW(A) = {a,d,} ∵ S?aA?abAS?abbASS 2022/8/21 自上而下分析 42 計算 FOLLOW集合：例 ? 例： P69.()表達式文法 E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i FOLLOW(T’)={ , +, )} ∵ E?TE’ ? T ?FT’ ∴ 有 號 ∵ E ?TE’ ? T+TE’ ?FT’+TE’ ∴ 有 +號 ∵ E? TE’ ? T ?FT’ ?(E)T’ ?(TE’)T’ ?(T)T’ ?(FT’)T’ ∴ 有 ) 號 2022/8/21 自上而下分析 43 LL(1)分析條件： 3個 ? (1) 文法 不含左遞歸 。 ? (2) 對于文法中 每個非終結(jié)符 A的各個候選式的終結(jié)首符集兩兩不相交 。 即 ， 若 A ? ?1 | ?2 |… | ?n 則： FIRST(?i) ? FIRST(?j) =? ( i ?j ) ? (3) 對文法中每一個非終結(jié)符 A， 若它存在某個候選式的終結(jié)首符集包含 ?， 則 FIRST(A) ?FLLOW(A)= ? ? 特別注意 第 3個條件：當(dāng)空字 ε 屬于非終結(jié)符的某個候選式的終結(jié)首符集時的條件 !!! 44 LL(1)文法 ? 一個文法 G若滿足上述 LL(1)分析的三個條件 ， 則稱該文法 G為 LL(1)文法 。 ? LL(1)文法 : ? 第一個 L 表示從左到右掃描輸入串 ? 第二個 L 表示語法分析欲構(gòu)造輸入串的最左推導(dǎo) ? 括號里的 1 表示分析時 , 每步只需向前查看一個符號 ? LL(1)文法是無二義文法 , 上述三個條件是 LL(1)文法無二義的充分條件 。 ? 對 LL(1)文法 ， 可以對其輸入串進行有效的無回溯的自上而下分析 。 2022/8/21 自上而下分析 45 LL(1)文法：自上而下分析過程 ? 對 LL(1)文法 ， 假設(shè)要用非終結(jié)符 A進行匹配 ，面臨的輸入符號為 a， A的所有產(chǎn)生式為： A ? ?1 | ?2 |… | ?n ? (1) 若 a∈ FIRST(?i ), 則指派 ?i 執(zhí)行匹配任務(wù) 。 ? (2) 若 a不屬于任何一個候選式的終結(jié)首符集 , 則 : ? ① 若 ε屬于某個 FIRST(?j )且 a∈ FOLLOW(A), 則讓 A與 ε自動匹配 。 ? ② 否則 , a的出現(xiàn)是一種錯誤 。 ? 根據(jù) LL(1)文法的條件 , 每一步這樣的工作都是確信無疑的 。 46 LL(1)文法：例 ? 例 (P69.) 不是 LL(1)文法 , 有左遞歸 ? 例 P69.()是 LL(1)文法 ? 滿足 LL(1)分析的三個條件 ? 例 1 文法 G: S → iA A → :i=e|=e 是 LL(1)文法 ? 滿足 LL(1)分析的三個條件 : 1. 不含左遞歸 2. FIRST(:i=e)={ : }, FIRST(=e)={=}, 不交 3. 候選式的 FIRST集都不含 ε 2022/8/21 自上而下分析 47 LL(1)文法 : 例 2 ? 例 2 文法 G: S → LU L → i:|ε U → i=e ? 因為 : 1. 不含左遞歸 2. L的各個候選的 FIRST集合互不交 3. L有個候選式的 FIRST集合含 ε, 再求得 FIRST(L)={ i,ε}, FOLLOW(L)={ i }, 是相交的 ? 所以 G不是 LL(1)文法 。 2022/8/21 自上而下分析 48 遞歸下降分析程序構(gòu)造 ? 當(dāng)一個文法滿足 LL(1)條件時 ， 就可以為該文法構(gòu)造一個 不帶回溯的自上而下分析程序 ： ?這個分析程序由一組 遞歸過程 組成； ?每個遞歸過程對應(yīng)文法的一個非終結(jié)符號 ， 完成該非終結(jié)符號所對應(yīng)的語法成分的分析和識別任務(wù) 。 ? 這樣一個自上而下語法分析程序稱為 遞歸下降分析器 。 2022/8/21 自上而下分析 49 遞歸下降分析程序構(gòu)造： 過程和變量 ? 先設(shè)定一些過程和變量 ， 作為遞歸下降分析程序的基本成分 。 ? 過程 ADVANCE： 調(diào)整 ip指向下一個輸入符號 , 讀入 ip指向的輸入符號到 SYM中 。 ? 變量 SYM： 表示 ip當(dāng)前所指的那個輸入符號 。 ? 過程 ERROR： 出錯診察處理 。 50 遞歸下降分析程序構(gòu)造： 非終結(jié)符對應(yīng)的遞歸過程的結(jié)構(gòu) ? ① A??1| ?2|… | ?n ? ② ?=X1X2… Xm Xi∈ (VT∪ VN) ? ③ Xi∈ VT ? ④ Xi∈ VN ? ① IF… ELSE IF … ELSE… 結(jié)構(gòu) ? ② 順序結(jié)構(gòu) ? ③ IF SYM=Xi THEN ADVANCE ELSE ERROR ? ④ 調(diào)用 Xi對應(yīng)的遞歸過程 2022/8/21 自上而下分析 51 例 : 算術(shù)表達式的遞歸下降分析器 (1) ? Ｅ的子程序 E→TE ’ procedure E。 begin T。 Ｔ的過程調(diào)用 E’ E’的過程調(diào)用 end。 ? Ｅ ’ 的子程序 E’→+TE ’|ε procedure E’。 IF SYM=‘+’ THEN begin ADVANCE。 T。 T的過程調(diào)用 E’ E’的過程調(diào)用 end。 2022/8/21 自上而下分析 52 例 : 算術(shù)表達式的遞歸下降分析器 (2) ? T的子程序 T→FT ’ procedure T。 begin F。 F的過程調(diào)用 T’ T’的過程調(diào)用 end。 ? T’的子程序 T’→*FT ’|ε procedure E’。 IF SYM=‘*’ THEN begin ADVANCE。 F。 F的過程調(diào)用 T’ T’的過程調(diào)用 end。 2022/8/21 自上而下分析 53 例 : 算術(shù)表達式的遞歸下降分析器 (3) ? F的子程序 F→i|(E) procedure F。 IF SYM=‘i’ then ADVANCE ELSE IF SYM=‘(‘ then BEGIN ADVANCE。 E。 E的過程調(diào)用 IF SYM=‘)’ THEN ADVANCE ELSE ERROR END ELSE ERROR。 54 擴充巴科斯范式定義系統(tǒng) ? 對前面的產(chǎn)生式 (巴科斯范式 )進行擴充 ： ? (1) 用花括號 {?}表示閉包運算 ?*。 ? (2) 用 {?}0n表示 ?可以任意重復(fù) 0次至 n次 , {?}00= ? 0=?。 ? (3) 用方括號 [?]表示 {?}01， 即表示 ?的出現(xiàn)可有可無 , 等價于 ? |ε。 ? 這樣 , 使得產(chǎn)生式右部的形式像正規(guī)式一樣 , 這種定義形式稱 擴充 巴科斯范式定義系統(tǒng) 。 ? 例如 , P75. “實數(shù) ? 的擴充 巴科斯范式定義 ? Decimal→ [sign]integer.{digit}[exponent] 55 使用擴充 BNF定義系統(tǒng)的好處 (1) ? (1)直觀易懂 : 如表示不超過 10位的無符號整數(shù) 無符號數(shù) → 數(shù)字 {數(shù)字 }90 E ? T|E+T T ? F|T*F F ? (E)|i E ? T{+T} T ? F{*F} F ? (E)|i 例 , 提左因子 A ? BC|BCD |AXZ|AXY A ? BC(ε|D)|AX(Z|Y) 提左 A ? BC(ε|D){X(Z|Y)} 消左 ? (2)便于表示消除左遞歸和提取左因子消除回溯 例 , 消除左遞歸 ， 不用引入新的非終結(jié)符和 ε產(chǎn)生式 56 使用擴充 BNF定義系統(tǒng)的好處 (2) ? (3)便于構(gòu)造自上而下分析程序 , 過程是 : 關(guān)于 非終結(jié)符 A的產(chǎn)生式 ? 寫為擴充 BNF定義形式 ? 畫出其語法圖 ? 轉(zhuǎn)換為 A對應(yīng)的程序 ? 非終結(jié)符號的語法圖 類似于表示正規(guī)式的狀態(tài)轉(zhuǎn)換圖 ， 所以也稱為文法的狀態(tài)轉(zhuǎn)換圖 。 ? 結(jié)點 文法符號 ? 有向邊 文法符號的排列順序 |或 [] 分支 {} 回路 .連接 順序 57 用語法圖描述語言的文法 : 例 (P75.) T→ F|T*F T→ F{*F}的語法圖 ＊ Ｆ Ｔ + T E E→ T|E+T E→ T{+T}的語法圖 i Ｅ Ｆ （ ） F→ i|(E)的語法圖 58 例 : 簡單算術(shù)表達式的 遞歸下降分析器 (P76.)E ? E→T{+T} Ｅ的子程序 , 請與 procedure E。 begin T。 Ｔ的過程調(diào)用 while SYM=39。+39。 do 當(dāng)前符號等于＋時 begin ADVANCE。 處理終結(jié)符＋ T Ｔ的過程調(diào)用 end end。 SYM： 當(dāng)前符號 59 例 : 簡單算術(shù)表達式的 遞歸下降分析器 (P76.)T ? T→F{*F} Ｔ的子程序 , 請與 proced