編譯原理ppt課件(編輯修改稿)
2025-05-30 01:55 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 語(yǔ)法分析器的功能 ? 自上而下分析面臨的問題 ? LL(1)分析法 ? 遞歸下降分析程序構(gòu)造 ?遞歸下降分析器 ?擴(kuò)充的巴科斯范式 ?語(yǔ)法圖 ? 預(yù)測(cè)分析程序 ? LL(1)分析中的錯(cuò)誤處理 遞歸下降分析器 ? 遞歸下降分析器 ?當(dāng)文法滿足 LL(1)條件時(shí)，構(gòu)造不帶回溯的自上而下分析程序 ?該分析程序由一組遞歸過程組成，每個(gè)過程對(duì)應(yīng)文法的一個(gè)非終結(jié)符 擴(kuò)充的巴科斯范式 ? 巴科斯范式 ?元語(yǔ)言符號(hào)“ → ”和“ |” ? 擴(kuò)充的巴科斯范式（ 擴(kuò)充幾個(gè)元語(yǔ)言符號(hào) ） ?用花括號(hào) {?}表示閉包運(yùn)算 ?* ? 用表示 {?}0n可任意重復(fù) 0次至 n次 ? 用方括號(hào) [?]表示 {?}01 ??的出現(xiàn)可有可無(wú) ?等價(jià)于 ?|? 擴(kuò)充的巴科斯范式舉例 ? 例如，通常的“實(shí)數(shù)”可定義為： decimal→[sign]integer.{digit}[exponent] exponent→E[sign]integer integer→digit{digit} sign→ + | ? 用擴(kuò)充的巴科斯范式來(lái)描述語(yǔ)法 ? 直觀易懂 ? 便于表示左遞歸消去和因子提取 語(yǔ)法圖 ? 例 文法 E→T | E+T T→F | T*F F→i | (E) 可表示成 E→T{+T} T→F{*F} F→i | (E) T T + E F F * T i ( E F ) 預(yù)測(cè)分析程序 ? 語(yǔ)法分析器的功能 ? 自上而下分析面臨的問題 ? LL(1)分析法 ? 遞歸下降分析程序構(gòu)造 ? 預(yù)測(cè)分析程序 ?預(yù)測(cè)分析程序的工作過程 ?預(yù)測(cè)分析表及其構(gòu)造方法 ? LL(1)分析中的錯(cuò)誤處理 預(yù)測(cè)分析程序 ? 實(shí)現(xiàn) LL(1)分析的有效方法 ?遞歸下降分析器 ?要求編譯器支持遞歸 ?預(yù)測(cè)分析程序 ?非遞歸的 ?數(shù)學(xué)模型是下推自動(dòng)機(jī) ?使用 分析表 和 棧 聯(lián)合控制 預(yù)測(cè)分析程序工作過程 ? 預(yù)測(cè)分析程序或 LL(1)分析法 工作原理 ： ?總控程序 ?分析表 M[A， a]矩陣， A ? VN ， a ? VT 是終結(jié)符或‘＃’ ?分析棧 STACK 用于存放文法符號(hào) 預(yù)測(cè)分析器模型 總控程序 預(yù)測(cè)分析表 X ? 輸入串 分析棧 STACK a1a2...ai… 輸出 ? 分析表： M[A， a]矩陣 ? A ? VN ， a ? VT ，＃是輸入串結(jié)束符，不是終結(jié)符 ? 分析棧： 用于存放文法符號(hào) 預(yù)測(cè)分析表 例： 對(duì)于文法 G(E) E→TE ? E?→+TE ? | ? T→FT ? T?→*FT ? | ? F→(E) | i ? 對(duì)應(yīng)的 LL(1)分析表（預(yù)測(cè)分析表） 如下 i + * ( ) E E → TE ? E → TE ? E ? E ?→ +TE ? E ?→ ? E ?→ ? T T → FT ? T → FT ? T ? T ?→ ? T ?→ *FT ? T ?→ ? T ?→ ? F F → i F → (E) 輸入串為 i*i+i，利用分析表進(jìn)行預(yù)測(cè)分析 步驟 符號(hào)棧 輸入串 所用產(chǎn)生式0 E i*i+i1 E39。T i*i+i E→TE 39。2 E39。T39。F i*i+i T→FT 39。3 E39。T39。i i*i+i F→i4 E39。T39。 *i+i5 E39。T39。F* *i+i T39?！? FT39。6 E39。T39。F i+i7 E39。T39。i i+i F→i8 E39。T39。 +i9 E39。 +i T39?！?ε10 E39。T+ +i E39?！? TE39。11 E39。T i12 E39。T39。F i T→FT 39。13 E39。T39。i i F→i14 E39。T39。 15 E39。 T39?！?ε16 E→ ε分析過程如下： i + * ( ) E E → TE ? E → TE ? E ? E ? → +T E ? E ? → ? E ? → ? T T → FT ? T → FT ? T ? T ? → ? T ? → * F T ? T ? → ? T ? → ? F F → i F → (E) 總控程序 ? 總控程序根據(jù) STACK棧頂符號(hào) X和當(dāng)前輸入符號(hào) a，執(zhí)行下列三種動(dòng)作之一 ? 若 X＝ a＝‘?！?則宣布分析 成功 ，停止分析 ? 若 X＝ a ?‘?！?， 則把 X從 STACK棧頂逐出，讓 a指向下一個(gè)輸入符號(hào) ? 若 X是一個(gè)非終結(jié)符，則查看分析表 M ? 若 M[X， a]中存放著關(guān)于 X的一個(gè)產(chǎn)生式，把 X逐出 STACK棧頂，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn) STACK棧 (若右部符號(hào)為 ?，則意味不推什么東西進(jìn)棧 )。在把產(chǎn)生式的右部符號(hào)推進(jìn)棧的同時(shí)應(yīng)做這個(gè)產(chǎn)生式相應(yīng)的語(yǔ)義動(dòng)作（目前暫且不管） ? 若 M[X， a]中存放著 “ 出錯(cuò)標(biāo)志 ” ，則調(diào)用出錯(cuò)診察程序 ERROR 預(yù)測(cè)分析算法 ? 預(yù)測(cè)分析算法： BEGIN 首先把 ’ ‘入棧；然后把文法開始符號(hào)推入棧； 把第一個(gè)輸入符號(hào)讀進(jìn) a； FLAG： =TRUE； WHILE FLAG DO BEGIN 把棧頂符號(hào)上托出去并放在Ｘ 中； IF X ? Vt THEN IF X=a THEN 把下一 個(gè)輸入符號(hào)讀進(jìn) a ELSE ERROR ELSE IF X=‘’ THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF ?[X,a]={X → X1X2..XK} THEN 把 XK， XK1,..,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1