【正文】 第 5 章 語法分析 語法分析是編譯的第二階段；其任務(wù)是 識別 和處理 比單詞更大的語法單位 ，如： 程序設(shè)計語言中的 表達式 、 各種 說明 和 語句 乃至全部 源程序 ， 指出其中的語法錯誤；必要時，可生成內(nèi)部形式，便于下一階段處理。 內(nèi)容提要 : 語法分析的基本概念 遞歸子程序法 LL(1)分析法 LR()分析法 簡單優(yōu)先分析法 語法分析的 基本 概念 語法分析的定義與分類 【 定義 】 形式上說，語法分析是指對給定的符號串（ ?），判定其是否是某文法 G(Z)的句子。即 Z ? 成立嗎 ? = + ? Z 成立嗎 ? = . + 【 分類 】 語法分析方法通常分兩大類： 1. 自頂向下法 （ 推導(dǎo)法 ） 2. 自底向上法 （ 歸約法 ） 從開始符號出發(fā)，采用 推導(dǎo) 運算，試圖 自頂向下 構(gòu)造語法樹。 從給定的符號串出發(fā)，采用 歸約 運算，試圖自底向上 構(gòu)造語法樹。 或 ※ 通常采用 ? 最左推導(dǎo)法 ? 。 ※ 通常采用 ? 最左歸約法 ? 給定： ? = a*(b+c)， ?是否是表達式？ (接上頁 ) 算法設(shè)計分析 1 【 例 】 G(E)： E T | E+T | ET T F | T*F | T/F F i | (E) ※ 最左推導(dǎo) 分析過程： 【 結(jié)論 】 自頂向下分析的關(guān)鍵技術(shù)是如何確定具有相同左部的產(chǎn)生式之 侯選者 ！ 即 E a*(b+c) = + =T*F =F*F =a*F =a*(E) =a*(E+T) =a*(T+T) =a*(F+T) =a*(b+T) =a*(b+F) =a*(b+c) 自頂向下法 : E =T ※ 為了清楚每次 歸約 的是什麼？我們觀察語法樹的 ? = a*(b+c) 算法設(shè)計分析 2 E T | E+T | ET T F | T*F | T/F F i | (E) 自底向上法 a*(b+c) = . F*(b+c) = . T*(E+c) = . T*(b+c) = . T*(F+c) = . T*(T+c) = . T*(E+F) = . T*(E+T) = . T*(E) = . T*F = . E = . T = .+ E a*(b+c) 即 【 結(jié)論 】 自底向上分析的關(guān)鍵技術(shù)是 如何確定當前句型的句柄！ 最左歸約 分析過程 ： 構(gòu)造過程： 遞歸子程序法的設(shè)計 原理 ： 語法分析的核心技術(shù)是 ? 文法 ? 的 機內(nèi)表示問題；遞歸子程序法直接把 文法 變成 程序。 對每一個 非終結(jié)符 ，構(gòu)造一個子程序，用以識別該非終結(jié)符所定義的符號串。 每個子程序以產(chǎn)生式左部非終結(jié)符命名 ， 以產(chǎn)生式右部構(gòu)造子程序內(nèi)容。 例如：設(shè)有如下產(chǎn)生式： A aBeD | bAc | ? 則有：遞歸子程序 A: 遞歸子程序法屬于 自頂向下語法分析方法 。故又名遞歸下降法。 設(shè)計原理： y n 入口 出口 a? b? NEXT(w) y NEXT(w) NEXT(w) n c? y n err2 e? 遇ε時 B A D y err1 n NEXT(w) A aBeD | bAc | ? 判斷當前單詞是否是 c 即 w=c? 調(diào)用 子程序 A (接上頁 ) 讀單詞函數(shù) 遞歸子程序的構(gòu)造 算法 ? 擴展文法 ： ※ 增設(shè)一個產(chǎn)生式，作為主程序： Z`Z ， ? 入出口約定 ： ※ 子程序入口時，其 首符號 已經(jīng)讀來！ ※ 子程序出口時，其 后繼符 應(yīng)該讀來！ ? 子程序內(nèi)容設(shè)計 ： ※ 遇 終結(jié)符 ，判定之 ，確認后讀下一單詞； ※ 遇 非終結(jié)符 ,調(diào)用之 ,返回后不讀下一單詞； ※ 遇 空串 ( ? ) ，直接出口； 【 例 】 G(S): 令 Z S , 則 遞歸子程序 : 子程序 A 開始 結(jié)束 S NEXT(w) err0 y n 入口 出口 a b err1 NEXT(w) A b err2 NEXT(w) S NEXT(w) 子程序 S n n n y y y 入口 c NEXT(w) 出口 遇?時 n y d NEXT(w) err3 y n 主程序 S aAb |bS , A cd | ? 實際上，上述兩點可歸納為同一個條件，即： ※ 遞歸子程序要求文法應(yīng)是： 遞歸子程序法對文法的 要求 ： 遞歸子程序是根據(jù)文法各產(chǎn)生式的 首符號 與當前所讀 單詞 進行匹配，以決定 候選產(chǎn)生式 的；這就要求文法： ① 具有相同左部的各產(chǎn)生式，首符號不同； ② 文法不能有左遞歸！ 如： A a?|a? (首符號相同， )； A A?|? (直接左遞歸， )。 LL(1)文法 !（見 ）。 遞歸子程序的 構(gòu)造例 ： Ⅰ . 消除左遞歸后的文法 1: G`(E) : T F { ω 2 F } F i | ( E ) E T { ω 1T } 【 提示 】 根據(jù)文法變換： A A? |? ? A ?{ ? } 【 例 】 G(E)： E T | Eω 1T T F | Tω 2F F i | (E) 其中： ω 1(+,),ω 2(*,/),i(變量或常數(shù) ) 主程序 T F { ω 2 F } F i | ( E ) E T { ω 1 T } 子程序 E 令 Z E 開始 結(jié)束 E NEXT(w) err0 y n 入口 出口 NEXT(w) T ω 1 T y n 入口 出口 NEXT(w) F ω 2 F y n 子程序 T (接上頁 ) T F { ω 2 F } F i | ( E ) E T { ω 1 T } 入口 出口 i ( err1 NEXT(w) err2 NEXT(w) E ) y y y n n n 子程序 F (接上頁 ) Ⅱ. 消除左遞歸后的文法 2 : G``(E) : T F { ω 2 F } F i | ( E ) E T { ω 1 T } E T E` E` ω 1T E` | ? T F T` T` ω 2F T` | ? F i | ( E ) ※ 文法 G`(E)消除花括號后可得： 令 Z E ，則可構(gòu)造遞歸子程序如下： （主程序 省略） 入口 出口 T E` 子程序 E 入口 ω 1 NEXT(w) T 出口 遇?時 n y E` … 子程序 E` E T E` E` ω 1T E` | ? T F T` T` ω 2F T` | ? F i | ( E ) (接上頁 ) 1. 什麼是 LL(1)分析法？ LL(1)分析法基本概念 LL(1)分析法 ※ LL(1) 分析法的基本要點有三： ? 利用一個 分析表 ，登記如何 選擇產(chǎn)生式 的知識； ? 利用一個 分析棧 ，記錄分析過程； ? 此分析法要求文法必須是 LL(1)文法 。 LL(1)分析法是指從 左 到右掃描 、 最 左 推導(dǎo) (LL)和只查看 一 個當前符號（括號中的 1）之意； LL(1)分析法又稱預(yù)測分析法，與遞歸子程序法同屬于自頂向下確定性語法分析方法 。 2. LL(1)分析過程示例 G(Z)： ZdAZ① | bAc② AaA③ |ε ④ 棧 當前符號 剩余序列 棧操作 ? 選擇推導(dǎo)產(chǎn)生式后，為什麼要逆序壓棧 ? ? 當棧頂為 A,當前單詞為 c時，為什么 選擇 A?? ? 討論 逆序壓棧 c A c c A c c A b A a b a c 選擇 Z?bAc② b a c 匹配 b a c 選擇 A?aA③ a c 匹配 a c 選擇 A?? ④ c 匹配 c 正確結(jié)束 Z 查分析表 ※ 對符號串： ? = bac 的分析過程： ④ ① d ④ ④ ③ A ② Z c b a 分析表： ※ 設(shè)有文法 G(Z), 棧底標記 和 結(jié)束標記 。 棧 結(jié)束 ： ② 若 棧頂符 =a 且 當前符為 a； 則 pop,NEXT(w)。 Z ? 開始 ： 棧 。 NEXT(w) ； 當前符 w= ? ? 重復(fù)執(zhí)行 ①、②、③ ，直到棧中只剩 為止： 即：棧調(diào)整： … a … 即：棧調(diào)整： … A … ?a 3. LL(1)分析法算法概要 ① 若 棧頂符 =A 且 當前符 w=a 且 有 產(chǎn)生式 ： A?a?， 則 POP,PUSH(a?)R 。 逆序壓棧 ! ③ 否則， 錯誤處理 ！ LL(1)文法及其判定 集合、 后繼符 集合與 選擇符 集合 設(shè) G(Z)=(VN, VT, Z, P)， A? ∈P ，則 first(?) , ? ? first(?)∪follow(A), ? ? select(A?)= =* ≠ * 【 注 】? ? ?(?可空 ), ? ?(?不可空 )； ? 若 ?= ? 則 first(?)={ }； ? 設(shè) 為輸入串的結(jié)束符，則 ∈follow(Z)。 = * ≠ * first(?)={ t| ? t… ， t∈V T } = * follow(A)={ t| Z … At… ， t∈V T } = * 【 注 】 求 follow(A) 要點： ※ 查所有右部含有 A的產(chǎn)生式 : B … A? ① 若 ? 不空時 , 則 first(?)∈follow(A) ； ② 若 ? 取空時 , 則 follow(B)∈follow(A) ； ③ 若 ? = ? 時 , 則 follow(B)∈follow(A) 。 select(① )= first(dAZ)=nhcuj7d3 select(② )= first(bcA)= select(③ )= first(aA)={a} select(④ )= first(?)∪follow(A)= { b,d， } 即： B … A G(Z)： Z dAZ ① | bcA ② A aA ③ | ? ④ 【 例 】 求文法產(chǎn)生式的 選擇集合 : 則有： 產(chǎn)生式序號 【 定義 】 LL(1)文法是指文法中，具有相同左部的各產(chǎn)生式，其選擇集合不相交。