編譯原理第三章語法分析.ppt

《編譯原理第三章語法分析.ppt》由會員分享，可在線閱讀，更多相關《編譯原理第三章語法分析.ppt（63頁珍藏版）》請在裝配圖網上搜索。

第三章語法分析 語法分析器的作用 上下文無關文法 CFG 定義 上下文無關文法是一個四元組G N T P S N是非終結符的有限集合 T是終結符的有限集合 且N T P是產生式的有限集合 S是非終結符 是文法的開始符號 例 定義上下文無關文法G N T P S 如下 N E T id S EP E E EE E EE E E EE id 縮寫為 E E E E E E E id 形式語言分類 定義 若文法G N T P S 的每個產生式 中 均有 N T N N T 且至少含有一個非終結符 N T 則稱G為0型文法 短語文法 1型文法 上下文有關文法 G的任何產生式 S 除外 均滿足 x 表示x中文法符號的個數(shù) 2型文法 上下文無關文法 G的任何產生式形如A 其中A N N T 3型文法 正規(guī)文法 線性文法 G的任何產生式形如A a或者A aB 或者A Ba 其中A B N a T 正規(guī)式與上下文無關文法 正規(guī)式所描述的語言結構均可以用CFG描述 反之不一定 例 正規(guī)式r a b abb的CFG描述如下A HTH aH bHT abb往往采用正規(guī)式而不是CFG描述詞法 正規(guī)式適合描述線性結構 CFG適合描述具有嵌套 層次 性質的非線性結構 CFG產生語言的基本方法 推導 定義 將產生式A 的右部代替文法符號序列 A 中的A得到 的過程 稱為 A 直接推導出 記作 A 1 n為零步或多步推導 1 n為零步推導 任何文法符號序列可以推導出它自身 推導具有傳遞性 則 定義 由CFGG所產生的語言L G S and T 稱為上下文無關語言 稱為句子 若S N T 則稱 為G的一個句型 只含終結符的句型是句子 定義 在推導中 若每次直接推導均替換句型中最左邊的非終結符 則稱為最左推導 產生的句型稱為左句型 最右推導也稱為規(guī)范推導 例 已知G E E E E E E E E idid id id 的推導過程 最左推導 E E E id E id E id E E id id E id id id 最右推導 E E E E E E E E E E id E id id id id id 定義 設 是上下文無關文法G的一個句型 如果有S A 并且A 則稱 是句型 關于非終結符A的一個短語 或稱 是句型 的一個短語 直接短語 簡單短語 A 句柄 一個句型的最左直接短語 素短語 含有終結符的短語 但不存在也具有相同性質的真子串短語 以非終結符為根的子樹中所有從左到右排列的葉子 直接短語 只有父子關系的樹中所有從左到右排列的葉子 樹高為2 句柄 最左邊父子關系樹中所有從左到右排列的葉子 句柄是唯一的 素短語 子樹末端結點組成的符號串含終結符 且在該子樹中不再有包含含有終結符的更小子樹 短語與語法樹 例 G E E E T TT T F FF E i句型 i i i的短語 直接短語 句柄和素短語短語 i1 i2 i3 i1 i2 i1 i2 i3直接短語 i1 i2 i3句柄 i1素短語 i1 i2 i3 分析樹 根由開始符號標記 每個葉子由一個終結符 非終結符或 標記 每個內部結點由一個非終結符標記 若A X1X2 Xn是一個產生式 則標記為A的內部結點從左到右有子結點X1 X2 Xn 若A 則 必是葉結點 且它是A的唯一子結點 例 E 語法樹 根與內部結點由表達式中的操作符標記 葉子由表達式中的操作數(shù)標記 用于改變運算優(yōu)先級和結合性的括弧 被隱含在語法樹的結構中 例 語法樹只反映句型的結構 忽略了推導句型的過程 二義性與二義性的消除 定義 若文法G對同一個句子產生不止一棵分析樹 則稱G是二義的 例 id id id原因是文法中缺少對文法符號優(yōu)先級和結合性的規(guī)定 E id E E E idid E E E E Eid idid 自上而下語法分析 自上而下語法分析法 從文法開始符號出發(fā) 找最左推導 或從根開始 構造推導樹 1 回溯分析法 不確定性 例 S xAyA ab a輸入串為xay 說明分析過程 2 存在的問題 1 回溯 公共左因子的存在A 1 2 2 左遞歸A A 或A A 提取左因子 以避免回溯 消除左遞歸 以避免陷入死循環(huán) 消除左遞歸 1 直接左遞歸的消除A A 改寫為 A A A A 一般地A A 1 A 2 A m 1 2 n i j不以A開頭 改寫為 A 1A 2A nA A 1A 2A mA 例 消除直接左遞歸E E T TT T F FF E F id消除后E TE E TE T FT T FT F E F id 2 間接左遞歸的消除例 S Qc cQ Rb bR Sa a按S Q R排列 或R Q S排列按S Q R排列 代入后按R Q S排列 代入后S Qc cR Sa aQ Rb bQ Sab ab bR Rbca bca ca aS Sabc abc bc c消除R中的直接左遞歸消除S中的直接左遞歸R bcaR caR aR S abcS bcS cS R bcaR S abcS 提取左因子 回溯 A 1 2 n 改寫為 A A A 1 2 n例 S iCtS iCtSeS aC b消除左因子 S iCtSS aS eS C b當一個文法中既有左遞歸又含左因子時 先消除左遞歸 文法3 2 E TE E TE T FT T FT F E i輸入串i i i 的語法分析 遞歸下降程序 voidmatch tokent if lookahead t lookahead nexttoken elseerror voidE T E voidE if lookahead match T E voidT F T voidT if lookahead match F T 遞歸下降程序 voidF if lookahead i match i elseif lookahead match E if lookahead match elseerror elseerror 匹配 匹配 匹配 預測分析器 LL 1 分析法 構成 下推棧 預測分析表 控制程序 輸入串分析方法 初始時 和開始符入棧 輸入指針指向第一個符號 然后根據下推棧棧頂符x和當前輸入符a進行工作 x a 成功 x a 匹配 x N 查預測分析表 構造預測分析表 1 FIRST集 1 定義 文法符號序列A的FIRST集合FIRST A a A a a T 若A 則 FIRST A 若x是終結符 則FIRST x x 若A是非終結符且A 則加入 到FIRST A 若A是非終結符且A Y1Y2 Yk 并且Y1 Yj 1都能推導出 則對所有j 1 j k 若a FIRST Yj 加入a到FIRST A 例 L E L E TE E TE TE T FT T FT FT modFT F E id num非終結符的FIRST集FIRST F id num FIRST T mod FIRST T FIRST F id num FIRST E FIRST E FIRST T id num FIRST L id num 1 FOLLOW集 1 定義 非終結符A的FOLLOW集合FOLLOW A a S Aa a T 若S A 則 FOLLOW A 其中S為開始符號 FOLLOW S A BC 將FIRST C 加入FOLLOW B A B或A BC且 FIRST C 則將FOLLOW A 加入FOLLOW B 例 L E L E TE E TE TE T FT T FT FT modFT F E id num非終結符的FOLLOW集FOLLOW L FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F mod 構造算法 對每個產生式A 對FIRST A 的每個終結符a 加入 到M A a 若 FIRST A 則對FOLLOW A 的每個終結符b 包括 加入 到M A b M中其他沒有定義的條目均為error 例 id id id 的分析過程 LL 1 文法 例 S iCtSS aS eS C bFIRST C b FIRST S e FIRST S i a FOLLOW S e FOLLOW S e FOLLOW C t 任何二義文法 含左遞歸和左因子的文法都不是LL 1 文法 一個文法G是LL 1 文法 當且僅當G的任何兩個產生式A 滿足下列條件 對任何終結符a 和 不能同時推導出以a開始的串 和 最多有一個可以推導出 若 則 不能推導出以FOLLOW A 中的終結符開始的任何串 自下而上語法分析法 從輸入串開始 歸約 直至文法開始符 定義 若 是文法G的一個句子 序列 n n 1 0滿足下述條件時稱為最左規(guī)約 規(guī)范歸約 n 0為文法的開始符 即 0 S 對任何i 0 i n i 1是從 i經把句柄替換為相應產生式的左部非終結符而得到的 自下而上語法分析 例1 G E E E T TT T F FF E ii i i的規(guī)范規(guī)約過程 i i iE i iE T iE T FE TE 例2 G S S aAcBeA Ab bB dabbcde的規(guī)范規(guī)約過程 abbcdeaAbcdeaAcdeaAcBeS 算符優(yōu)先分析法 適合于分析程序語言中的各類表達式 所謂算符優(yōu)先分析 就是依照算術表達式的四則運算過程來進行語法分析 預先規(guī)定終結符之間的優(yōu)先關系和結合性質 以確定句型的 可規(guī)約串 來進行規(guī)約 它不是一種規(guī)范規(guī)約 在整個過程中起決定作用的是相繼兩個終結符的優(yōu)先關系 1 算符文法上下文無關文法G 沒有形如P 或P QR 的產生式 則稱G為算符文法2 終結符之間的優(yōu)先關系對算符文法G a b T定義 1 a b G中有P ab 或P aQb 的產生式 2 ab G中有P Rb 且R a或R aQ3 算符優(yōu)先文法若算符文法G的任何終結符a b之間的優(yōu)先關系至多有 中的一個 則G為一算符優(yōu)先文法 構造優(yōu)先關系表 1 FIRSTVT集FIRSTVT P a P a 或P Qa a T Q N 若P a 或P Qa 則a FIRSTVT P 若P Q 則FIRSTVT Q FIRSTVT P 直至FIRSTVT P 不再增大 2 LASTVT集LASTVT P a P a 或P aQ a T Q N 若P a或P aQ 則a LASTVT P 若P Q 則LASTVT Q LASTVT P 直至LASTVT P 不再增大 FIRST A 是推導出的第一個終結符集 FIRSTVT A 是所有推導中首先遇到的終結符集 FOLLOW A 是緊跟非終結符A后的終結符集 LASTVT A 是所有推導中最后遇到的終結符集 例 G E E E T TT T F FF E i E T F FIRSTVT LASTVT i i i i i i 考察E E T中的E和 和T 和 和E E和 考察T T F中的T和 和F考察F E 中的 和E 和 E和 i i 算符優(yōu)先關系表 從上表可知 1 相同終結符之間的優(yōu)先關系未必是 2 有aa 3 a b之間未必一定有優(yōu)先關系故 不同于關系運算符 等于 小于 大于 算符優(yōu)先分析方法設a為棧頂終結符 i i i的算符優(yōu)先分析過程 LR分析法 LR K 分析法 自下而上的LR分析法是指從左向右掃描輸入串 每次分析由分析棧中符號及向前搜索K個輸入符號 以確定作為產生式右部的短語 句柄 是否已在分析棧的棧頂形成 從而決定應采取的動作 這種分析方法稱為LR K 分析法 一般只考慮K 1的情況 識別活前綴 活前綴 規(guī)范句型的不含句柄之后任何符號的一個前綴 亦即 若A 是文法的一個產生式 且有S A 則 的任何前綴都是規(guī)范句型 的活前綴 項目 在產生式右部添加一個圓點 如A A A 歸約項目 形如A 移進項目 形如A a a T待約項目 形如A B B N接受項目 形如S S為開始符拓廣文法 增加產生式S S 從而S S 成為唯一的接受項目 識別活前綴的DFA 項目集I的閉包closure I 對i I 都有i closure I 若A B closure I B為非終結符 且B 為文法G的一個產生式 則B closure I 重復 直至closure不再增大 定義 對所有屬于項目集I 且形如 A X 的項目 令X N T 則goto I X 是所有形如 A X 的項目 LR分析器組成 分析棧 控制程序 分析表 輸入串 輸入串 分析棧 驅動程序 輸出 action goto 分析表 s0 sm 1 sm a1 ai 分析棧 存放狀態(tài) 初始時 置初始狀態(tài)s0 棧里的每一狀態(tài)概括了從分析開始到某一時刻已進行的分析工作 分析表 由action s a 和goto s A 兩個子表組成 action s a 定義了在狀態(tài)s下 當前輸入符號為a時應采取的分析動作 移進 歸約 接受 出錯 goto表是一個狀態(tài)及非終結符的二維矩陣 goto s A 定義了在狀態(tài)s下 面對文法符號A時的狀態(tài)轉換 C I0 I1 In Ii對應狀態(tài)i I0 closure S S 為唯一初態(tài) 對每個Ii 若A a Ii 且go Ii a Ij 則action i a sj 若A Ii A 為第j個產生式 則action i a rj 若S S Ii 則action i acc 若go Ii A Ij 則goto i A j 凡不能用規(guī)則 登記的表項均為 錯誤 LR 0 分析表的構造 假定LR 0 文法規(guī)范族的每個項目集不含沖突項目 按下述方法構造的分析表是一張LR 0 表 使用LR 0 表的分析器叫做LR 0 分析器 例 試構造該文法的LR 0 分析表G S S BBB aB b拓廣為 G S 0 S S 1 S BB 2 B aB 3 B b構造G S 的LR 0 項目集規(guī)范族 計算初態(tài) I0 closure S S I0 S SS BBB aBB b 計算初態(tài)下的每個可能狀態(tài)轉移closure goto I0 x I1 S S I2 S B BI3 B a BI4 B b B aBB aBB bB b 計算下一狀態(tài)的每個可能狀態(tài)轉移closure goto Ii x I5 S BB I6 B aB 構造DFA LR 0 分析表 例 為文法構造識別活前綴的DFA 0 E E 1 E E T 2 E T 3 T T F 4 T F 5 F F 6 F id 計算DFA初態(tài) I0 closure E E I0 E EE E TE TT T FT FF FF id SLR分析表的構造 計算初態(tài)下的每個可能狀態(tài)轉移closure goto I0 x E EE E TE TT T FT FF FF id I0 E E E E T E I1 E T T T F T T F F F id I2 I3 I4 id F FF FF id I5 計算下一狀態(tài)的每個可能狀態(tài)轉移closure goto Ii x E EE E TE TT T FT FF FF id I0 E E E E T E I1 E T T T F T T F F F id I2 I3 I4 id F FF FF id I5 E E TT T FT FF FF id I6 T T FF FF id I7 F F I8 F E E T T T F T I9 F id T T F F id I10 id SLR方法 當某個項目集形如I X b A B 時 出現(xiàn)了移進 歸約沖突和歸約 歸約沖突 可用如下方法解決 該方法稱為SLR方法 C I0 I1 In Ii對應狀態(tài)i I0 closure S S 為唯一初態(tài) 對每個Ii 若A a Ii 且go Ii a Ij 則action i a sj 若A Ii A 為第j個產生式 則任何b FOLLOW A action i b rj 若S S Ii 則action i acc 若go Ii A Ij 則goto i A j 凡不能用規(guī)則 登記的表項均為 錯誤 FOLLOW E FOLLOW T FOLLOW F SLR 1 分析表 例 id id id的分析過程 二義文法不是SLR 1 文法例 G S 0 S S 1 S L R 2 S R 3 L R 4 L i 5 R L證明該文法既不是LR 0 文法 也不是SLR 1 文法 LR 0 項目集規(guī)范族 I0 S SS L RS RL RL iR L I1 S S I2 S L RR L I3 S R I4 L RR LL RL i I5 L i I6 S L RR LL RL i I7 L R I8 R L 1 不是LR 0 文法 I2中S L R R L 存在移進 歸約沖突 2 SLR能否解決I2中的沖突 FOLLOW R 與 交不為空仍然無法解決沖突 故不是SLR 1 文法