程序設(shè)計(jì)語言的語法描述.ppt

2019/12/16,第3章程序設(shè)計(jì)語言的語法描述,3.1文法的引入3.2上下文無關(guān)文法3.3文法舉例（略）,使用文法對程序設(shè)計(jì)語言的結(jié)構(gòu)進(jìn)行定義和描述。,2019/12/16,3.1文法的引入,先討論自然語言的文法。例：thebigelephentateabanana語法樹根據(jù)英語的語法，上述句子的語法結(jié)構(gòu)可用圖（語法樹）表示如下：,非葉結(jié)點(diǎn)稱為語法單位，在形式語言中稱為非終結(jié)符。處于根結(jié)點(diǎn)位置的結(jié)點(diǎn)又稱為開始符號(hào)。葉結(jié)點(diǎn)稱為單詞符號(hào)，在形式語言中稱為終結(jié)符。,2019/12/16,規(guī)則可以通過建立一組規(guī)則，來描述上述句子的語法結(jié)構(gòu)，規(guī)則在形式語言中稱為產(chǎn)生式。,the|abigelephant|bananaate,由規(guī)則推導(dǎo)句子可用規(guī)則來推導(dǎo)出句子。從開始符號(hào)出發(fā)，若能從規(guī)則推導(dǎo)出某符號(hào)串，則該符號(hào)串就是該文法的合法的句子，反之語法錯(cuò)誤。,上述英文句子可用下述規(guī)則來描述：,2019/12/16,thethebigthebigelephantthebigelephantthebigelephantatethebigelephantatethebigelephantateathebigelephantateabanana上述推導(dǎo)可簡單表示為：thebigelephantateabanana。值得注意的是用上述規(guī)則可推導(dǎo)出多個(gè)句子，因存在推導(dǎo)abigbananaatetheelephant所以，abigbananaatetheelephant也是文法的一個(gè)合法的句子。但意義是荒謬的，也就是說句子的語義是錯(cuò)誤的。一個(gè)語法正確的句子不能保證其語義是正確的，故一個(gè)句子是否正確，需要進(jìn)行語法和語義兩方面檢查。綜上所述，語言結(jié)構(gòu)通常是用文法來定義和描述，文法是由終結(jié)符、非終結(jié)符、開始符號(hào)（特殊非終結(jié)符）及產(chǎn)生式四個(gè)要素構(gòu)成。從開始符號(hào)出發(fā)，根據(jù)產(chǎn)生式能推導(dǎo)出的句子全體稱為文法所規(guī)定的語言,2019/12/16,遞歸規(guī)則和遞歸文法遞歸是編譯技術(shù)中的一個(gè)重要概念。遞歸定義：定義某事物，又用到該事物本身。遞歸規(guī)則（直接遞歸）：在規(guī)則的左部和右部有相同的非終結(jié)符。例：UxUy，通常用大寫字母表示非終結(jié)符，用小寫字母表示終結(jié)符。左遞歸規(guī)則：x=，UUy（表示空串）右遞歸規(guī)則：y=，UxU間接遞歸：由規(guī)則推導(dǎo)產(chǎn)生。例：VUy|Z，UxV因存在推導(dǎo)VUyxVy，故存在間接遞歸。間接左遞歸：若x=，則VVy。間接右遞歸：若y=，則VxU。遞歸文法：含有遞歸規(guī)則和間接遞歸的文法，稱為遞歸文法。利用遞歸文法，可以用有窮的規(guī)則來描述無窮的語言，這不但解決了語言的定義問題，而且使得對語言的語法檢查成為可能。,2019/12/16,3.2上下文無關(guān)文法,形式語言的奠基人喬姆斯基（Chomsky）將文法分為4種類型，它們是：短語文法（0型文法）上下文有關(guān)文法（1型文法）上下文無關(guān)文法（2型文法）正規(guī)文法（3型文法）這四種文法在形式語言中都有嚴(yán)格的定義。但對于程序設(shè)計(jì)語言來說，上下文無關(guān)文法已經(jīng)夠用了，上下文無關(guān)文法有足夠的能力描述大多數(shù)現(xiàn)今使用的程序設(shè)計(jì)語言的語法結(jié)構(gòu)。以后，“文法”一詞若無特別說明，則指“上下文無關(guān)文法”。,2019/12/16,文法和語言一個(gè)文法G是一個(gè)四元式(VT,VN,S,P)，其中VT是一個(gè)終結(jié)符的非空有限集，終結(jié)符通常用小寫字母表示。VN是一個(gè)非終結(jié)符的非空有限集，非終結(jié)符通常用大寫字母表示。S是一個(gè)特殊的非終結(jié)符（SVN），稱為開始符號(hào)。P是一個(gè)產(chǎn)生式（規(guī)則）的有限集合，每個(gè)產(chǎn)生式的形式是A，其中AVN，(VTVN)*。,終結(jié)符是語言的基本符號(hào)，即程序設(shè)計(jì)語言的單詞。語法分析時(shí)，終結(jié)符用單詞的種別表示。根據(jù)前面約定：標(biāo)識(shí)符（簡單變量）：i無符號(hào)整常數(shù)：x無符號(hào)實(shí)常數(shù)：y單字符單詞：用單詞本身表示（例單詞“+”的種別用+表示）多字符單詞：需特別指定（例“+”用$表示）,2019/12/16,非終結(jié)符表示抽象的語法單位.例“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“賦值語句”、“說明語句”和“程序”等。非終結(jié)符通常用大寫字母表示，也可以用帶尖括號(hào)的漢字表示。開始符號(hào)是一個(gè)特殊的非終結(jié)符，它代表我們最感興趣的語法單位。例如討論算術(shù)表達(dá)式，那么描述算術(shù)表達(dá)式文法的開始符號(hào)就是。在程序設(shè)計(jì)語言中，我們最感興趣的語法單位是“程序”。產(chǎn)生式是定義語法單位的一種書寫規(guī)則。上下文無關(guān)文法產(chǎn)生式的左部必定是一個(gè)非終結(jié)符，該非終結(jié)符稱為左部符號(hào)。產(chǎn)生式的右部是終結(jié)符和非終結(jié)符經(jīng)有限次連接構(gòu)成的文法符號(hào)串，可以是空字。四種文法的區(qū)別主要是對產(chǎn)生式的左部和右部的限制不同。若干個(gè)左部符號(hào)相同的產(chǎn)生式，可合并為一個(gè)，例：A1|2|n，其中i稱為A的候選式(1in)。,2019/12/16,例1：描述算術(shù)表達(dá)式文法G=(VT,VN,S,P)，其中VT=+,-,*,/,i,x,y,(,)VN=,S=P=+-*/()i/標(biāo)識(shí)符x/無符號(hào)整常數(shù)y/無符號(hào)實(shí)常數(shù)根據(jù)上述文法，可推導(dǎo)出任何僅包含加減乘除的算術(shù)表達(dá)式。,2019/12/16,因已約定非終結(jié)符和終結(jié)符的書寫方式，非終結(jié)符和終結(jié)符在產(chǎn)生式中一目了然，故終結(jié)符集VT和非終結(jié)符集VN無需再顯式列出。若規(guī)定左部符號(hào)為開始符號(hào)的產(chǎn)生式寫在所定義文法的第一行，上述文法G又可簡單表示為如下形式：+-*/()ixy若用E表示、T表示、F表示，借助符號(hào)|，算術(shù)表達(dá)式文法G可表示成如下最簡形式：EE+TETTTT*FT/FFF(E)ixy,2019/12/16,例2：描述算術(shù)表達(dá)式文法G=(VT,VN,S,P)，其中VT=+,-,*,/,i,x,y,(,)VN=P=+-*/()i/標(biāo)識(shí)符x/無符號(hào)整常數(shù)y/無符號(hào)實(shí)常數(shù)根據(jù)上述文法，同樣可推導(dǎo)出任何僅包含加減乘除的算術(shù)表達(dá)式。用E表示，上述文法可簡記為：EE+E|E-E|E*E|E/E|(E)|i|x|y,2019/12/16,基本術(shù)語以文法G：EE+E|E*E|(E)|i為例，進(jìn)行下述討論。直接推出和直接歸約推導(dǎo)和歸約若12n，則稱該直接推出序列是從1到n的一個(gè)推導(dǎo)，記作1n或n。1n：從1始，經(jīng)一步或一步以上可推導(dǎo)出n。1n：從1始，經(jīng)步或步以上可推導(dǎo)出n，即1n或1=n。也可稱直接歸約序列n,n-1,1為n到1的一個(gè)歸約。句型若存在推導(dǎo)S（S為文法的開始符號(hào)），則稱是文法的一個(gè)句型。句子僅包含終結(jié)符的句型稱為句子。,2019/12/16,語言文法所能推導(dǎo)出的句子全體稱為該文法的語言，記為：L(G)=|(S)(VT*)等價(jià)文法1和2是二個(gè)不同的文法，若L(G1)=L(G2)，則稱G1和G2是等價(jià)文法。等價(jià)文法的存在，使我們能夠在不改變文法所規(guī)定的語言的前提下，為了某種目的改造文法。最左推導(dǎo)和最右推導(dǎo)在各種推導(dǎo)中，考慮今后語法分析的需要，我們僅對兩種推導(dǎo)感興趣。1）最左推導(dǎo)在推導(dǎo)過程中始終對最左面的非終結(jié)符進(jìn)行替換，記為。2）最右推導(dǎo)在推導(dǎo)過程中始終對最右面的非終結(jié)符進(jìn)行替換，記為。,2019/12/16,文法的二義性語法樹我們可以用一個(gè)有向圖表示一個(gè)句型的推導(dǎo)，這種表示稱為語法樹。語法樹有助于理解一個(gè)句子語法結(jié)構(gòu)的層次。在一般情況下，某一句型不論其推導(dǎo)過程如何，其最終形成的語法樹是相同的，故語法樹是不同推導(dǎo)過程的共性抽象。若僅進(jìn)行最左（右）推導(dǎo)，則語法樹和最左（右）推導(dǎo)等價(jià)。二義文法若一個(gè)文法所產(chǎn)生的語言中，只要存在一個(gè)句子，它有二個(gè)最左推導(dǎo)，或有二個(gè)最右推導(dǎo)，或句子的推導(dǎo)對應(yīng)兩棵語法樹，則稱該文法為二義文法。二義文法的利用和處理1)根據(jù)條件修改文法，語言不變。算符優(yōu)先性：規(guī)定*優(yōu)先于+，i+i*i等價(jià)于i+(i*i)。算符結(jié)合性：規(guī)定同級運(yùn)算服從左結(jié)合，i+i+i等價(jià)于(i+i)+i。2)根據(jù)條件修改編譯程序的語法分析表，文法保持不變（詳見第四、五章）。,2019/12/16,1）根據(jù)條件修改文法，語言不變。算符優(yōu)先性：規(guī)定*優(yōu)先于+，i+i*i等價(jià)于i+(i*i)。算符結(jié)合性：規(guī)定同級運(yùn)算服從左結(jié)合，i+i+i等價(jià)于(i+i)+i。例文法GG：EE+E|E*E|(E)|i是一個(gè)二義文法。根據(jù)上述條件將文法G修改成G，如下所示G：EE+T|TTT*F|FF(E)|i顯然G不是二義文法，但L(G)=L(G)，故G和G等價(jià)。例句子i+i*i的最右推導(dǎo)：EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iETT*F?+?*?先形成+，才有可能形成*。若先形成*，只有帶括號(hào)才可能形成+。,2019/12/16,2）根據(jù)條件修改編譯程序的語法分析表，文法保持不變。例文法G：if標(biāo)識(shí)符thenelseSfitSeSif標(biāo)識(shí)符thenSfitS標(biāo)識(shí)符=Si=E無符號(hào)整常數(shù)Ex程序段a=2ifxthenifythena=4elsea=6相應(yīng)的語法結(jié)構(gòu)表示為i=xfitfiti=xei=x句子fitfiti=xei=x的最左推導(dǎo)序列有二個(gè)，如下所示：SfitSeSfitfitSeSfitfiti=EeSfitfiti=xeSfitfiti=xei=Efitfiti=xei=xSfitSfitfitSeSfitfiti=EeSfitfiti=xeSfitfiti=xei=Efifii=xei=x因句子fitfiti=xei=x存在二個(gè)最左推導(dǎo)，故文法G為二義文法。,2019/12/16,這樣對于該程序段有二個(gè)解釋：假設(shè)else和最近的if結(jié)合，即a=2ifxthenbeginifythena=4elsea=6end,當(dāng)x和y為下列值時(shí)，相應(yīng)a的值為：,假設(shè)else和最遠(yuǎn)的if結(jié)合，即a=2ifxthenbeginifythena=4endelsea=6,實(shí)際的編譯程序不可能、也不允許有兩種解釋，通常按第一種方式進(jìn)行翻譯執(zhí)行，即“else和最近的if結(jié)合”。,2019/12/16,結(jié)束,