程序設(shè)計(jì)語言編譯原理第三版第4章-文庫吧資料
2025-01-12 18:29本頁面
【正文】 字符 a來 執(zhí)行控制功能 。 預(yù)測分析程序 —— M[A,a]形式的矩陣表示 矩陣元素 M[A,a]存放內(nèi)容： 一條 A的 產(chǎn)生式 或 出錯(cuò)標(biāo)志 ； 矩陣元素 — 實(shí)際是 相應(yīng)的分析動作 （即所選用的推導(dǎo)的產(chǎn)生式）。 (2)由于遞歸調(diào)用多 ,所以速度慢占用空間多 . 應(yīng)用舉例 : Pascal, C語言 預(yù)測分析器模型 167。 遞歸下降分析程序構(gòu)造 (1)Advance/Sym/IP (2)圖 (1){ } * (2){ }n0 可重復(fù) 0次或任意次 . (3)[ ] ∣ ????? ?167。 ② 否則 ,a的出現(xiàn)是一種語法錯(cuò)誤 . 一 .實(shí)現(xiàn)思想 對應(yīng)文法中每個(gè)非終結(jié)符編寫一個(gè)遞歸過程 ,每個(gè)過程 的 功能 是 識別由該非終結(jié)符推出的串 ,當(dāng)某非終結(jié)符的產(chǎn)生 式有多個(gè)侯選時(shí)能夠按 LL(1)形式可唯一地確定選擇某個(gè)侯 選進(jìn)行推導(dǎo) . 167。 LL(1)分析法 對非終結(jié)符 A進(jìn)行匹配 ,此時(shí)面臨的輸入符號為 a: (1)若 a∈first( α i ),則指派 α i去執(zhí)行匹配任務(wù) 。 LL(1)分析法 構(gòu)造不帶回溯的自上而下分析的文法的條件： （ 1）文法 不含左遞歸 。 當(dāng)Ａ面臨輸入符號ａ，且ａ ? first（ A），但 ?∈first （ A），只有當(dāng) a∈follow （ A）時(shí)，才可能允許 A自動匹配。 LL(1)分析法 Follow(A)={ a | A?… Aa… ,a∈ V T } 若 S?… A,則規(guī)定 ∈follow(A) * * 167。 LL(1)分析法 Ｆ Ｔ ’ + T Ｅ ’ i F Ｔ’ ｉ ? ? ? 經(jīng)消去直接左遞歸后變成 E?TE’ E’?+TE’|? T?FT’ T’?*FT’|? F?（ E） ｜ i ２ .由上分析是不是就意味著： 當(dāng)非終結(jié)符Ａ面臨輸入符號ａ，且ａ不屬于Ａ的任意候選首符集，但Ａ的某個(gè)候選首符集包含 ?時(shí)，就一定可以使Ａ自動匹配？ 分析： 只有當(dāng)ａ是在文法的某個(gè)句型中 允許 跟在Ａ后的終結(jié)符時(shí)，才可能允許Ａ自動匹配，否則，ａ在這里的出現(xiàn)是一種語法錯(cuò)誤。 LL(1)分析法 經(jīng)過反復(fù)提取左因子 ,就能把每個(gè)非終結(jié)符 (包括新引進(jìn)者 )的所有候選首符集變成兩兩不相交 . 三、分析條件 不含左遞歸 ,并且滿足 每個(gè)非終結(jié)符的所有候選首符集兩兩不相交 的條件 ,是不是就 一定能進(jìn)行有效的 自上而下分析了呢 ? 167。 例如： 語句 ?if 條件 then 語句 else 語句 if 條件 then 語句 提取公共左因子 167。 LL(1)分析法 此時(shí)，當(dāng)要求 A匹配輸入串時(shí)， A根據(jù)它所面臨的第一個(gè)輸入符號 a， 準(zhǔn)確地指派 某一個(gè)候選前去執(zhí)行任務(wù)；這個(gè)候選就是那個(gè) 終結(jié)首符集含 a的 α . 即 : first(α) 是 α 的所有可能推導(dǎo)的開頭終結(jié)符或可能的 ?。 LL(1)分析法 ２ .當(dāng)不得回溯時(shí)，對文法有什么要求？ ? 非終結(jié)符Ａ的各個(gè)候選的首符集的交集均為空。在這里Ａ已不再是讓某個(gè)候選去試探性地執(zhí)行任務(wù)，而是 根據(jù)所面臨的輸入符號ａ準(zhǔn)確地指派唯一的一個(gè)候選。 即： 若此候選獲得 成功匹配 ，那么，這種匹配決 不會 是 虛假 的； 若此候選 無法完成匹配任務(wù) ，則 任何其它候選 也 肯定無法完成 。 LL(1)分析法 二、消除回溯 ,提取公共左因子 167。 LL(1)分析法 例題 :（間接左遞歸） 已知文法 G: S?Qc|c Q?Rb|b R?Sa|a 試消除其左遞歸 ? 解答 （３）化簡由（２）所得的文法 ,即 去除 那些從開始符號 出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則 . 解答 : 令非終結(jié)符排序?yàn)? R、 Q、 S i=1， 無法執(zhí)行 for i=2， j=1 Q ? Rb|b R ? Sa|a Q ? Sab|ab|b 167。 LL(1)分析法 ２ . 消除間接左遞歸： （１）把文法Ｇ的所有 Ｖ Ｎ 按任一種順序排列成
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1