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

《編譯原理第三章語法分析.ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯原理第三章語法分析.ppt（63頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

第三章語法分析 語法分析器的作用 上下文無關(guān)文法 CFG 定義 上下文無關(guān)文法是一個(gè)四元組G N T P S N是非終結(jié)符的有限集合 T是終結(jié)符的有限集合 且N T P是產(chǎn)生式的有限集合 S是非終結(jié)符 是文法的開始符號 例 定義上下文無關(guān)文法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 的每個(gè)產(chǎn)生式 中 均有 N T N N T 且至少含有一個(gè)非終結(jié)符 N T 則稱G為0型文法 短語文法 1型文法 上下文有關(guān)文法 G的任何產(chǎn)生式 S 除外 均滿足 x 表示x中文法符號的個(gè)數(shù) 2型文法 上下文無關(guān)文法 G的任何產(chǎn)生式形如A 其中A N N T 3型文法 正規(guī)文法 線性文法 G的任何產(chǎn)生式形如A a或者A aB 或者A Ba 其中A B N a T 正規(guī)式與上下文無關(guān)文法 正規(guī)式所描述的語言結(jié)構(gòu)均可以用CFG描述 反之不一定 例 正規(guī)式r a b abb的CFG描述如下A HTH aH bHT abb往往采用正規(guī)式而不是CFG描述詞法 正規(guī)式適合描述線性結(jié)構(gòu) CFG適合描述具有嵌套 層次 性質(zhì)的非線性結(jié)構(gòu) CFG產(chǎn)生語言的基本方法 推導(dǎo) 定義 將產(chǎn)生式A 的右部代替文法符號序列 A 中的A得到 的過程 稱為 A 直接推導(dǎo)出 記作 A 1 n為零步或多步推導(dǎo) 1 n為零步推導(dǎo) 任何文法符號序列可以推導(dǎo)出它自身 推導(dǎo)具有傳遞性 則 定義 由CFGG所產(chǎn)生的語言L G S and T 稱為上下文無關(guān)語言 稱為句子 若S N T 則稱 為G的一個(gè)句型 只含終結(jié)符的句型是句子 定義 在推導(dǎo)中 若每次直接推導(dǎo)均替換句型中最左邊的非終結(jié)符 則稱為最左推導(dǎo) 產(chǎn)生的句型稱為左句型 最右推導(dǎo)也稱為規(guī)范推導(dǎo) 例 已知G E E E E E E E E idid id id 的推導(dǎo)過程 最左推導(dǎo) E E E id E id E id E E id id E id id id 最右推導(dǎo) E E E E E E E E E E id E id id id id id 定義 設(shè) 是上下文無關(guān)文法G的一個(gè)句型 如果有S A 并且A 則稱 是句型 關(guān)于非終結(jié)符A的一個(gè)短語 或稱 是句型 的一個(gè)短語 直接短語 簡單短語 A 句柄 一個(gè)句型的最左直接短語 素短語 含有終結(jié)符的短語 但不存在也具有相同性質(zhì)的真子串短語 以非終結(jié)符為根的子樹中所有從左到右排列的葉子 直接短語 只有父子關(guān)系的樹中所有從左到右排列的葉子 樹高為2 句柄 最左邊父子關(guān)系樹中所有從左到右排列的葉子 句柄是唯一的 素短語 子樹末端結(jié)點(diǎn)組成的符號串含終結(jié)符 且在該子樹中不再有包含含有終結(jié)符的更小子樹 短語與語法樹 例 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 分析樹 根由開始符號標(biāo)記 每個(gè)葉子由一個(gè)終結(jié)符 非終結(jié)符或 標(biāo)記 每個(gè)內(nèi)部結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記 若A X1X2 Xn是一個(gè)產(chǎn)生式 則標(biāo)記為A的內(nèi)部結(jié)點(diǎn)從左到右有子結(jié)點(diǎn)X1 X2 Xn 若A 則 必是葉結(jié)點(diǎn) 且它是A的唯一子結(jié)點(diǎn) 例 E 語法樹 根與內(nèi)部結(jié)點(diǎn)由表達(dá)式中的操作符標(biāo)記 葉子由表達(dá)式中的操作數(shù)標(biāo)記 用于改變運(yùn)算優(yōu)先級和結(jié)合性的括弧 被隱含在語法樹的結(jié)構(gòu)中 例 語法樹只反映句型的結(jié)構(gòu) 忽略了推導(dǎo)句型的過程 二義性與二義性的消除 定義 若文法G對同一個(gè)句子產(chǎn)生不止一棵分析樹 則稱G是二義的 例 id id id原因是文法中缺少對文法符號優(yōu)先級和結(jié)合性的規(guī)定 E id E E E idid E E E E Eid idid 自上而下語法分析 自上而下語法分析法 從文法開始符號出發(fā) 找最左推導(dǎo) 或從根開始 構(gòu)造推導(dǎo)樹 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當(dāng)一個(gè)文法中既有左遞歸又含左因子時(shí) 先消除左遞歸 文法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 匹配 匹配 匹配 預(yù)測分析器 LL 1 分析法 構(gòu)成 下推棧 預(yù)測分析表 控制程序 輸入串分析方法 初始時(shí) 和開始符入棧 輸入指針指向第一個(gè)符號 然后根據(jù)下推棧棧頂符x和當(dāng)前輸入符a進(jìn)行工作 x a 成功 x a 匹配 x N 查預(yù)測分析表 構(gòu)造預(yù)測分析表 1 FIRST集 1 定義 文法符號序列A的FIRST集合FIRST A a A a a T 若A 則 FIRST A 若x是終結(jié)符 則FIRST x x 若A是非終結(jié)符且A 則加入 到FIRST A 若A是非終結(jié)符且A Y1Y2 Yk 并且Y1 Yj 1都能推導(dǎo)出 則對所有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非終結(jié)符的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 定義 非終結(jié)符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非終結(jié)符的FOLLOW集FOLLOW L FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F mod 構(gòu)造算法 對每個(gè)產(chǎn)生式A 對FIRST A 的每個(gè)終結(jié)符a 加入 到M A a 若 FIRST A 則對FOLLOW A 的每個(gè)終結(jié)符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è)文法G是LL 1 文法 當(dāng)且僅當(dāng)G的任何兩個(gè)產(chǎn)生式A 滿足下列條件 對任何終結(jié)符a 和 不能同時(shí)推導(dǎo)出以a開始的串 和 最多有一個(gè)可以推導(dǎo)出 若 則 不能推導(dǎo)出以FOLLOW A 中的終結(jié)符開始的任何串 自下而上語法分析法 從輸入串開始 歸約 直至文法開始符 定義 若 是文法G的一個(gè)句子 序列 n n 1 0滿足下述條件時(shí)稱為最左規(guī)約 規(guī)范歸約 n 0為文法的開始符 即 0 S 對任何i 0 i n i 1是從 i經(jīng)把句柄替換為相應(yīng)產(chǎn)生式的左部非終結(jié)符而得到的 自下而上語法分析 例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)先分析法 適合于分析程序語言中的各類表達(dá)式 所謂算符優(yōu)先分析 就是依照算術(shù)表達(dá)式的四則運(yùn)算過程來進(jìn)行語法分析 預(yù)先規(guī)定終結(jié)符之間的優(yōu)先關(guān)系和結(jié)合性質(zhì) 以確定句型的 可規(guī)約串 來進(jìn)行規(guī)約 它不是一種規(guī)范規(guī)約 在整個(gè)過程中起決定作用的是相繼兩個(gè)終結(jié)符的優(yōu)先關(guān)系 1 算符文法上下文無關(guān)文法G 沒有形如P 或P QR 的產(chǎn)生式 則稱G為算符文法2 終結(jié)符之間的優(yōu)先關(guān)系對算符文法G a b T定義 1 a b G中有P ab 或P aQb 的產(chǎn)生式 2 ab G中有P Rb 且R a或R aQ3 算符優(yōu)先文法若算符文法G的任何終結(jié)符a b之間的優(yōu)先關(guān)系至多有 中的一個(gè) 則G為一算符優(yōu)先文法 構(gòu)造優(yōu)先關(guān)系表 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 是推導(dǎo)出的第一個(gè)終結(jié)符集 FIRSTVT A 是所有推導(dǎo)中首先遇到的終結(jié)符集 FOLLOW A 是緊跟非終結(jié)符A后的終結(jié)符集 LASTVT A 是所有推導(dǎo)中最后遇到的終結(jié)符集 例 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)先關(guān)系表 從上表可知 1 相同終結(jié)符之間的優(yōu)先關(guān)系未必是 2 有aa 3 a b之間未必一定有優(yōu)先關(guān)系故 不同于關(guān)系運(yùn)算符 等于 小于 大于 算符優(yōu)先分析方法設(shè)a為棧頂終結(jié)符 i i i的算符優(yōu)先分析過程 LR分析法 LR K 分析法 自下而上的LR分析法是指從左向右掃描輸入串 每次分析由分析棧中符號及向前搜索K個(gè)輸入符號 以確定作為產(chǎn)生式右部的短語 句柄 是否已在分析棧的棧頂形成 從而決定應(yīng)采取的動作 這種分析方法稱為LR K 分析法 一般只考慮K 1的情況 識別活前綴 活前綴 規(guī)范句型的不含句柄之后任何符號的一個(gè)前綴 亦即 若A 是文法的一個(gè)產(chǎn)生式 且有S A 則 的任何前綴都是規(guī)范句型 的活前綴 項(xiàng)目 在產(chǎn)生式右部添加一個(gè)圓點(diǎn) 如A A A 歸約項(xiàng)目 形如A 移進(jìn)項(xiàng)目 形如A a a T待約項(xiàng)目 形如A B B N接受項(xiàng)目 形如S S為開始符拓廣文法 增加產(chǎn)生式S S 從而S S 成為唯一的接受項(xiàng)目 識別活前綴的DFA 項(xiàng)目集I的閉包c(diǎn)losure I 對i I 都有i closure I 若A B closure I B為非終結(jié)符 且B 為文法G的一個(gè)產(chǎn)生式 則B closure I 重復(fù) 直至closure不再增大 定義 對所有屬于項(xiàng)目集I 且形如 A X 的項(xiàng)目 令X N T 則goto I X 是所有形如 A X 的項(xiàng)目 LR分析器組成 分析棧 控制程序 分析表 輸入串 輸入串 分析棧 驅(qū)動程序 輸出 action goto 分析表 s0 sm 1 sm a1 ai 分析棧 存放狀態(tài) 初始時(shí) 置初始狀態(tài)s0 棧里的每一狀態(tài)概括了從分析開始到某一時(shí)刻已進(jìn)行的分析工作 分析表 由action s a 和goto s A 兩個(gè)子表組成 action s a 定義了在狀態(tài)s下 當(dāng)前輸入符號為a時(shí)應(yīng)采取的分析動作 移進(jìn) 歸約 接受 出錯 goto表是一個(gè)狀態(tài)及非終結(jié)符的二維矩陣 goto s A 定義了在狀態(tài)s下 面對文法符號A時(shí)的狀態(tài)轉(zhuǎn)換 C I0 I1 In Ii對應(yīng)狀態(tài)i I0 closure S S 為唯一初態(tài) 對每個(gè)Ii 若A a Ii 且go Ii a Ij 則action i a sj 若A Ii A 為第j個(gè)產(chǎn)生式 則action i a rj 若S S Ii 則action i acc 若go Ii A Ij 則goto i A j 凡不能用規(guī)則 登記的表項(xiàng)均為 錯誤 LR 0 分析表的構(gòu)造 假定LR 0 文法規(guī)范族的每個(gè)項(xiàng)目集不含沖突項(xiàng)目 按下述方法構(gòu)造的分析表是一張LR 0 表 使用LR 0 表的分析器叫做LR 0 分析器 例 試構(gòu)造該文法的LR 0 分析表G S S BBB aB b拓廣為 G S 0 S S 1 S BB 2 B aB 3 B b構(gòu)造G S 的LR 0 項(xiàng)目集規(guī)范族 計(jì)算初態(tài) I0 closure S S I0 S SS BBB aBB b 計(jì)算初態(tài)下的每個(gè)可能狀態(tài)轉(zhuǎn)移closure goto I0 x I1 S S I2 S B BI3 B a BI4 B b B aBB aBB bB b 計(jì)算下一狀態(tài)的每個(gè)可能狀態(tài)轉(zhuǎn)移closure goto Ii x I5 S BB I6 B aB 構(gòu)造DFA LR 0 分析表 例 為文法構(gòu)造識別活前綴的DFA 0 E E 1 E E T 2 E T 3 T T F 4 T F 5 F F 6 F id 計(jì)算DFA初態(tài) I0 closure E E I0 E EE E TE TT T FT FF FF id SLR分析表的構(gòu)造 計(jì)算初態(tài)下的每個(gè)可能狀態(tài)轉(zhuǎn)移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 計(jì)算下一狀態(tài)的每個(gè)可能狀態(tài)轉(zhuǎn)移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方法 當(dāng)某個(gè)項(xiàng)目集形如I X b A B 時(shí) 出現(xiàn)了移進(jìn) 歸約沖突和歸約 歸約沖突 可用如下方法解決 該方法稱為SLR方法 C I0 I1 In Ii對應(yīng)狀態(tài)i I0 closure S S 為唯一初態(tài) 對每個(gè)Ii 若A a Ii 且go Ii a Ij 則action i a sj 若A Ii A 為第j個(gè)產(chǎn)生式 則任何b FOLLOW A action i b rj 若S S Ii 則action i acc 若go Ii A Ij 則goto i A j 凡不能用規(guī)則 登記的表項(xiàng)均為 錯誤 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 項(xiàng)目集規(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 存在移進(jìn) 歸約沖突 2 SLR能否解決I2中的沖突 FOLLOW R 與 交不為空仍然無法解決沖突 故不是SLR 1 文法