編譯原理及實(shí)現(xiàn)技術(shù)課件：第三章 語法分析

1、第三章 語法分析語法分析概述語法分析的對(duì)象文法1 語法分析概述語法分析的功能語法錯(cuò)誤的分類語法錯(cuò)誤處理語法分析方法概述21.1 語法分析的功能Token List語法分析器語法樹 / 語法錯(cuò)誤信息31.2 語法錯(cuò)誤類別程序的開始符，語句（表達(dá)式）的開始符（后繼符）錯(cuò)標(biāo)識(shí)符（常量）錯(cuò)：該出現(xiàn)時(shí)未出現(xiàn)括號(hào)類錯(cuò)誤：不匹配分隔符錯(cuò)：assignment41.3 語法錯(cuò)誤處理要求：報(bào)告錯(cuò)誤出現(xiàn)的位置修復(fù)錯(cuò)誤并繼續(xù)檢查后續(xù)部分執(zhí)行開銷不應(yīng)太大處理策略：緊急方式恢復(fù)；短語級(jí)恢復(fù)；出錯(cuò)產(chǎn)生式；全局糾正。52.4 語法分析方法概述自頂向下LL（1）遞歸下降自底向上簡(jiǎn)單優(yōu)先方法LR族方法62 語法分析的對(duì)象文法文

2、法概述文法相關(guān)的概念文法等價(jià)變換72.1 文法概述文法能清晰地描述程序設(shè)計(jì)語言的語法構(gòu)成，易于理解。文法能構(gòu)造有效的語法分析器，檢查源程序是否符合語言規(guī)定的語法形式。文法定義可以了解程序設(shè)計(jì)語言的結(jié)構(gòu)，有利于將源程序轉(zhuǎn)化為目標(biāo)代碼及檢查出語法錯(cuò)誤。基于文法實(shí)現(xiàn)的語言易于擴(kuò)展82.1.1 文法的形式化定義文法G定義為四元組(VT,VN,S,P) VT是有限的終極符集合 VN是有限的非終極符集合 S是開始符，S VN P是產(chǎn)生式的集合，且具有下面的形式：，其中，(VTVN)*92.1.2 文法分類O型文法：也稱為短語文法，其產(chǎn)生式具有形式: ，其中,(VTVN)*，并且至少含一個(gè)非終極符 。1型文

3、法：也稱為上下文相關(guān)文法。它是0型文法的特例，要求| | (S例外，但S不得出現(xiàn)于產(chǎn)生式右部)。2型文法：也稱為上下文無關(guān)文法。它是1型文法的特例，即要求產(chǎn)生式左部是一個(gè)非終極符: A 。3型文法：也稱為正則文法。它是2型文法的特例，即產(chǎn)生式的右部至多有兩個(gè)符號(hào)，而且具有下面形式之一: A a ，A a B其中A,BVN ，aVT 。 102.1.3 上下文無關(guān)文法定義為四元組(VT,VN,S,P) VT是有限的終極符集合 VN是有限的非終極符集合 S是開始符，S VN P是產(chǎn)生式的集合，且具有下面的形式：AX1X2Xn 其中AVN，Xi(VTVN) ，右部可空。112.2 文法相關(guān)概念推導(dǎo)（

4、直接推導(dǎo)）：如果A是一個(gè)產(chǎn)生式，則有A ,其中表示一步推導(dǎo)。這時(shí)稱是由A直接推導(dǎo)的。 /*的含義是，使用一條規(guī)則，代替左邊的某個(gè)符號(hào)，產(chǎn)生右端的符號(hào)串。*/ + : 表示通過一步或多步可推導(dǎo)出 * : 表示通過0步或多步可推導(dǎo)出 12句型：如果有S* ，則稱符號(hào)串為CFG的句型 。我們用SF(G)表示文法G的所有句型的集合。句子：如果只包含終極符，則稱為CFG的句子。語言：L(G)= u| S + u ,u VT* 文法G所定義的語言是其開始符所能推導(dǎo)的所有終極符號(hào)串(句子)的集合。 13最左（右）推導(dǎo)：如果進(jìn)行推導(dǎo)時(shí)選擇的是句型中的最左(右）非終極符，則稱這種推導(dǎo)為最左(右)推導(dǎo)，并用符號(hào)l

5、m（rm）表示最左（右）推導(dǎo)。左（右）句型：用最左推導(dǎo)方式導(dǎo)出的句型，稱為左句型，而用最右推導(dǎo)方式導(dǎo)出的句型，稱為右句型(也稱為規(guī)范句型)。14短語：設(shè)S是文法的開始符，是句型(即有S *），如果滿足條件：S* AA+ VT+ 則稱是句型的一個(gè)短語。直接短語（簡(jiǎn)單短語）：如果滿足條件：S* AA VT+ 則稱是句型的一個(gè)簡(jiǎn)單短語。句柄：一個(gè)句型可能有多個(gè)簡(jiǎn)單短語，其中最左的簡(jiǎn)單短語稱之為句柄。 15語法分析樹(簡(jiǎn)稱分析樹)用來描述句型的結(jié)構(gòu)，是句型推導(dǎo)的一種樹型表示。給定文法 G=(VN,VT,S,P)，則稱滿足下面條件的樹為G的一棵語法分析樹：每個(gè)結(jié)點(diǎn)都有G的一個(gè)文法符號(hào)，并且根結(jié)點(diǎn)標(biāo)有初始

6、符S，非葉結(jié)點(diǎn)標(biāo)有非終極符，葉結(jié)點(diǎn)標(biāo)有終極符或非終極符或。如果一個(gè)非葉結(jié)點(diǎn)A有n個(gè)兒子結(jié)點(diǎn)(從左到右）為 X1,X2,.,Xn，則G一定有產(chǎn)生式 AX1X2 .Xn 。16線性推導(dǎo)：稱用符號(hào)進(jìn)行的推導(dǎo)為線性推導(dǎo) 。樹型推導(dǎo)與線性推導(dǎo)的不同：線性推導(dǎo)指明了推導(dǎo)的順序，而樹型推導(dǎo)則沒有指明推導(dǎo)的順序。因此，句型一般只有一棵分析樹(如果無二義性)，而線性推導(dǎo)則可以有很多棵分析樹。二義性文法：如果一個(gè)文法的某個(gè)句型有兩棵不同的語法分析樹，則稱該文法二義性為二義性文法。17思考給定分析樹的任一子樹的樹葉全體(具有共同祖先的葉節(jié)點(diǎn)符號(hào)串)皆為短語？任一簡(jiǎn)單子樹的樹葉全體(具有共同父親的葉節(jié)點(diǎn)符號(hào)串)皆為簡(jiǎn)

7、單短語？每個(gè)句子都有相應(yīng)的最右和最左推導(dǎo)嗎？每個(gè)句型呢？18二義性文法實(shí)例例：文法G=( +,*,i,(,), E, E, P),其中P為：E iE E + EE E * EE ( E )19句型i*i+i 可能的推導(dǎo):推導(dǎo)1: E E + E E * E + E i * E + E i * i + E i * i + i推導(dǎo)2: E E * E i * E i * E + E i * i + E i * i + i推導(dǎo)1的語法樹E+EEE*EiiiEE*EE+Eii推導(dǎo)2的語法樹i202.3 文法的等價(jià)變換增加拓廣產(chǎn)生式消除空產(chǎn)生式消除不可達(dá)產(chǎn)生式消除特型產(chǎn)生式消除公共前綴消除左遞歸消除二義

8、性21增加拓廣產(chǎn)生式定理：對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，且G2的開始符唯一且不出現(xiàn)于任何產(chǎn)生式的右部。證明：假設(shè)S是G1的開始符，則只要在G1中擴(kuò)充一條新產(chǎn)生式ZS即可，其中Z是新的開始符。另這樣擴(kuò)充后的文法為G2，則它顯然滿足定理的要求。22消除空產(chǎn)生式定理：對(duì)任一文法G1，可構(gòu)造文法G2，使得L(G1)=L(G2)，且G2中無空產(chǎn)生式。證明：根據(jù)G1，構(gòu)造G2的方法如下：令G2=G1；令=A | A，=A | A +, +；對(duì)于文法中任意產(chǎn)生式AX1X2Xi-1XiXi+1Xn,若Xi，補(bǔ)充規(guī)則A X1X2Xi-1Xi+1Xn；重復(fù)2，直到不補(bǔ)充新的產(chǎn)生式。

9、從G2.P中刪除所有形如A的產(chǎn)生式。從G2.VN刪除只能導(dǎo)出空串的非終極符。例： AaBcD Bb | DBB | d23消除不可達(dá)產(chǎn)生式定理：對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，且G2中的每個(gè)非終極符必出現(xiàn)在它的某個(gè)句型中。證明：根據(jù)G1，構(gòu)造文法G2的方法如下：令G2=G1。令=S | S是文法的開始符，遞歸擴(kuò)充 =B | AxByG1, BVN, A。若A，則刪除以A為左部的所有產(chǎn)生式。24消除特型產(chǎn)生式定理：對(duì)任一文法G1，可以構(gòu)造文法G2，使得L(G1)=L(G2)，且在G2中沒有特型產(chǎn)生式。證明：構(gòu)造無特型產(chǎn)生式的文法G2的方法如下：(1)對(duì)文法G1中任意

10、非終極符A，求集合 A=B | A+B, BVN。(2)若BA，且B是文法G中的一個(gè)非特型產(chǎn)生式，則補(bǔ)充如下規(guī)則A。(3)去掉文法G1中的所有的特型產(chǎn)生式。(4)去掉新的文法中的無用產(chǎn)生式。例：AB|D|aBBC|bCcDB|d25消除公共前綴某個(gè)非終極符A有如下的兩個(gè)產(chǎn)生式：A，A 稱這兩個(gè)產(chǎn)生式有公共前綴。方法：對(duì)于產(chǎn)生式：A1|2| |n| ，其中表示不以開頭的字符串，引進(jìn)非終極符A，使產(chǎn)生式替換為：A A | A 1|2 | n26消除左遞歸一個(gè)文法含有下列形式的產(chǎn)生式時(shí)（1） AAa |b其中AVN；a, (VNVT)*（2） AB|BA| 其中A,B VN； a, (VNVT)*（1）稱為直接左遞歸，（2）稱為間接左遞歸，即文法中只要有A+A，則稱文法為左遞歸的。對(duì)于不含回路或空產(chǎn)生式，消除做遞歸方法為27（1）對(duì)直接左遞歸形如：AA|消除左遞歸：AAAA|（2）間接左遞歸形如：AB|BA|消除左遞歸：轉(zhuǎn)為直接左遞歸形式：AA| 或者 BB|按照直接左遞歸方式消除。去掉多余的