程序設(shè)計語言的語法描述市公開課金獎市賽課一等獎?wù)n件

第3章程序設(shè)計語言語法描述3.1文法引入3.2上下文無關(guān)文法3.3文法舉例（略）使用文法對程序設(shè)計語言結(jié)構(gòu)進(jìn)行定義和描述。10/10/第1頁3.1文法引入先討論自然語言文法。例：thebigelephentateabanana㈠語法樹依據(jù)英語語法，上述句子語法結(jié)構(gòu)可用圖（語法樹）表示以下：非葉結(jié)點稱為語法單位，在形式語言中稱為非終止符。處于根結(jié)點位置結(jié)點又稱為開始符號。葉結(jié)點稱為單詞符號，在形式語言中稱為終止符。10/10/第2頁㈡規(guī)則能夠經(jīng)過建立一組規(guī)則，來描述上述句子語法結(jié)構(gòu)，規(guī)則在形式語言中稱為產(chǎn)生式。<句子>→<主語><謂語> <主語>→<冠詞><形容詞><名詞><冠詞>→the|a<形容詞>→big<名詞>→elephant|banana<謂語>→<動詞><直接賓語><直接賓語>→<冠詞><名詞><動詞>→ate㈢由規(guī)則推導(dǎo)句子可用規(guī)則來推導(dǎo)出句子。從開始符號出發(fā)，若能從規(guī)則推導(dǎo)出某符號串，則該符號串就是該文法正當(dāng)句子，反之語法錯誤。上述英文句子可用下述規(guī)則來描述：10/10/第3頁 <句子><主語><謂語> <冠詞><形容詞><名詞><謂語> the<形容詞><名詞><謂語> thebig<名詞><謂語> thebigelephant<謂語> thebigelephant<動詞><直接賓語> thebigelephantate<直接賓語> thebigelephantate<冠詞><名詞> thebigelephantatea<名詞> thebigelephantateabanana上述推導(dǎo)可簡單表示為： <句子>thebigelephantateabanana。值得注意是用上述規(guī)則可推導(dǎo)出多個句子，因存在推導(dǎo) <句子>abigbananaatetheelephant所以，abigbananaatetheelephant也是文法一個正當(dāng)句子。但意義是荒謬，也就是說句子語義是錯誤。一個語法正確句子不能確保其語義是正確，故一個句子是否正確，需要進(jìn)行語法和語義兩方面檢驗?？偠灾Z言結(jié)構(gòu)通常是用文法來定義和描述，文法是由終止符、非終止符、開始符號（特殊非終止符）及產(chǎn)生式四個要素組成。從開始符號出發(fā)，依據(jù)產(chǎn)生式能推導(dǎo)出句子全體稱為文法所要求語言10/10/第4頁㈣遞歸規(guī)則和遞歸文法遞歸是編譯技術(shù)中一個主要概念。①遞歸定義：定義某事物，又用到該事物本身。②遞歸規(guī)則（直接遞歸）：在規(guī)則左部和右部有相同非終止符。例：U→xUy，通慣用大寫字母表示非終止符，用小寫字母表示終止符。 ⑴左遞歸規(guī)則：x=ε，U→Uy（ε表示空串） ⑵右遞歸規(guī)則：y=ε，U→xU③間接遞歸：由規(guī)則推導(dǎo)產(chǎn)生。例：V→Uy|Z，U→xV 因存在推導(dǎo)VUyxVy，故存在間接遞歸。 ⑴間接左遞歸：若x=ε，則VVy。 ⑵間接右遞歸：若y=ε，則VxU。④遞歸文法：含有遞歸規(guī)則和間接遞歸文法，稱為遞歸文法。利用遞歸文法，能夠用有窮規(guī)則來描述無窮語言，這不但處理了語言定義問題，而且使得對語言語法檢驗成為可能。10/10/第5頁3.2 上下文無關(guān)文法形式語言奠基人喬姆斯基（Chomsky）將文法分為4種類型，它們是：短語文法（0型文法）上下文相關(guān)文法（1型文法）上下文無關(guān)文法（2型文法）正規(guī)文法（3型文法）這四種文法在形式語言中都有嚴(yán)格定義。但對于程序設(shè)計語言來說，上下文無關(guān)文法已經(jīng)夠用了，上下文無關(guān)文法有足夠能力描述大多數(shù)現(xiàn)今使用程序設(shè)計語言語法結(jié)構(gòu)。以后，“文法”一詞若無尤其說明，則指“上下文無關(guān)文法”。10/10/第6頁㈠文法和語言一個文法G是一個四元式(VT,VN,S,P)，其中VT是一個終止符非空有限集，終止符通慣用小寫字母表示。VN是一個非終止符非空有限集，非終止符通慣用大寫字母表示。S是一個特殊非終止符（S∈VN），稱為開始符號。P是一個產(chǎn)生式（規(guī)則）有限集合，每個產(chǎn)生式形式是A→α，其中A∈VN，α∈(VT∪VN)*。①終止符是語言基本符號，即程序設(shè)計語言單詞。語法分析時，終止符用單詞種別表示。依據(jù)前面約定： 標(biāo)識符（簡單變量）： i 無符號整常數(shù)： x 無符號實常數(shù)： y 單字符單詞： 用單詞本身表示（例單詞“+” 種別用+表示） 多字符單詞： 需尤其指定（例“++”用$表示）10/10/第7頁②非終止符表示抽象語法單位.例“算術(shù)表示式”、“布爾表示式”、“賦值語句”、“說明語句”和“程序”等。非終止符通慣用大寫字母表示，也能夠用帶尖括號漢字表示。③開始符號是一個特殊非終止符，它代表我們最感興趣語法單位。比如討論算術(shù)表示式，那么描述算術(shù)表示式文法開始符號就是<算術(shù)表示式>。在程序設(shè)計語言中，我們最感興趣語法單位是“程序”。④產(chǎn)生式是定義語法單位一個書寫規(guī)則。上下文無關(guān)文法產(chǎn)生式左部必定是一個非終止符，該非終止符稱為左部符號。產(chǎn)生式右部是終止符和非終止符經(jīng)有限次連接組成文法符號串，能夠是空字ε。四種文法區(qū)分主要是對產(chǎn)生式左部和右部限制不一樣。若干個左部符號相同產(chǎn)生式，可合并為一個，例： A→α1|α2|……|αn，其中αi稱為A候選式(1≤i≤n)。10/10/第8頁例1：描述算術(shù)表示式文法G=(VT,VN,S,P)，其中 VT={+,-,*,/,i,x,y,(,)} VN={<算術(shù)表示式>,<項>,<因子>} S=<算術(shù)表示式> P={ <算術(shù)表示式>→<算術(shù)表示式>+<項> <算術(shù)表示式>→<算術(shù)表示式>-<項> <算術(shù)表示式>→<項> <項>→<項>*<因子> <項>→<項>/<因子> <項>→<因子> <因子>→(<算術(shù)表示式>) <因子>→i //標(biāo)識符 <因子>→x //無符號整常數(shù) <因子>→y //無符號實常數(shù) }依據(jù)上述文法，可推導(dǎo)出任何僅包含加減乘除算術(shù)表示式。10/10/第9頁

因已約定非終止符和終止符書寫方式，非終止符和終止符在產(chǎn)生式中一目了然，故終止符集VT和非終止符集VN無需再顯式列出。若要求左部符號為開始符號產(chǎn)生式寫在所定義文法第一行，上述文法G又可簡單表示為以下形式： <算術(shù)表示式>→<算術(shù)表示式>+<項> <算術(shù)表示式>→<算術(shù)表示式>-<項> <算術(shù)表示式>→<項> <項>→<項>*<因子> <項>→<項>/<因子> <項>→<因子> <因子>→(<算術(shù)表示式>) <因子>→i <因子>→x <因子>→y若用E表示<算術(shù)表示式>、T表示<項>、F表示<因子>，借助符號'|'，算術(shù)表示式文法G可表示成以下最簡形式：

E→E+T︱E–T︱T T→T*F︱T/F︱F F→(E)︱i︱x︱y10/10/第10頁例2：描述算術(shù)表示式文法G=(VT,VN,S,P)，其中 VT={+,-,*,/,i,x,y,(,)} VN={<算術(shù)表示式} S=<算術(shù)表示式> P={ <算術(shù)表示式>→<算術(shù)表示式>+<算術(shù)表示式> <算術(shù)表示式>→<算術(shù)表示式>-<算術(shù)表示式> <算術(shù)表示式>→<算術(shù)表示式>*<算術(shù)表示式> <算術(shù)表示式>→<算術(shù)表示式>/<算術(shù)表示式> <算術(shù)表示式>→(<算術(shù)表示式>) <算術(shù)表示式>→i //標(biāo)識符 <算術(shù)表示式>→x //無符號整常數(shù) <算術(shù)表示式>→y //無符號實常數(shù) }依據(jù)上述文法，一樣可推導(dǎo)出任何僅包含加減乘除算術(shù)表示式。用E表示<算術(shù)表示式>，上述文法可簡記為： E→E+E|E-E|E*E|E/E|(E)|i|x|y10/10/第11頁㈡基本術(shù)語以文法G： E→E+E|E*E|(E)|i為例，進(jìn)行下述討論。①直接推出和直接歸約②推導(dǎo)和歸約若α1α2…αn，則稱該直接推出序列是從α1到αn一個推導(dǎo)，記作α1αn或ααn。 α1αn：從α1始，經(jīng)一步或一步以上可推導(dǎo)出αn。 α1αn：從α1始，經(jīng)０步或０步以上可推導(dǎo)出αn，即 α1αn或α1=αn。也可稱直接歸約序列αn,αn-1,…,α1為αn到α1一個歸約。③句型若存在推導(dǎo)Sα（S為文法開始符號），則稱α是文法一個句型。④句子僅包含終止符句型稱為句子。10/10/第12頁⑤語言文法Ｇ所能推導(dǎo)出句子全體稱為該文法語言，記為： L(G)={α|(Sα)∧(α∈VT*)}⑥等價文法Ｇ1和Ｇ2是二個不一樣文法，若L(G1)=L(G2)，則稱G1和G2是等價文法。等價文法存在，使我們能夠在不改變文法所要求語言前提下，為了某種目標(biāo)改造文法。⑦最左推導(dǎo)和最右推導(dǎo)在各種推導(dǎo)中，考慮今后語法分析需要，我們僅對兩種推導(dǎo)感興趣。1）最左推導(dǎo)在推導(dǎo)過程中一直對最左面非終止符進(jìn)行替換，記為。2）最右推導(dǎo)在推導(dǎo)過程中一直對最右面非終止符進(jìn)行替換，記為。10/10/第13頁㈢文法二義性①語法樹我們能夠用一個有向圖表示一個句型推導(dǎo)，這種表示稱為語法樹。語法樹有利于了解一個句子語法結(jié)構(gòu)層次。在普通情況下，某一句型不論其推導(dǎo)過程怎樣，其最終形成語法樹是相同，故語法樹是不一樣推導(dǎo)過程共性抽象。若僅進(jìn)行最左（右）推導(dǎo)，則語法樹和最左（右）推導(dǎo)等價。②二義文法若一個文法所產(chǎn)生語言中，只要存在一個句子，它有二個最左推導(dǎo)，或有二個最右推導(dǎo)，或句子推導(dǎo)對應(yīng)兩棵語法樹，則稱該文法為二義文法。③二義文法利用和處理1)依據(jù)條件修改文法，語言不變。 算符優(yōu)先性：要求*優(yōu)先于+，i+i*i等價于i+(i*i)。 算符結(jié)合性：要求同級運(yùn)算服從左結(jié)合，i+i+i等價于 (i+i)+i。

2)依據(jù)條件修改編譯程序語法分析表，文法保持不變（詳見第四、五章）。10/10/第14頁1）依據(jù)條件修改文法，語言不變。算符優(yōu)先性：要求*優(yōu)先于+，i+i*i等價于i+(i*i)。算符結(jié)合性：要求同級運(yùn)算服從左結(jié)合，i+i+i等價于(i+i)+i。例文法GG：E→E+E|E*E|(E)|i是一個二義文法。依據(jù)上述條件將文法G修改成G’，以下所表示G'：E→E+T|TT→T*F|FF→(E)|i顯然G‘不是二義文法，但L(G)=L(G’)，故G和G‘等價。例句子i+i*i最右推導(dǎo)：EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iETT*F?+?*?…先形成+，才有可能形成*。若先形成*，只有帶括號才可能形成+。10/10/第15頁2）依據(jù)條件修改編譯程序語法分析表，文法保持不變。例文法G：<語句>→if

標(biāo)識符

then<語句>else<語句> S→fitSeS<語句>→if

標(biāo)識符

then<語句> S→fitS<語句>→標(biāo)識符=<算術(shù)表示式> S→i=E<算術(shù)表示式>→無符號整常數(shù) E→x程序段 a=2 ifxthenifythena=4elsea=6對應(yīng)語法結(jié)構(gòu)表示為 i=x fitfiti=xei=x句子fitfiti=xei=x最左推導(dǎo)序列有二個，以下所表示：SfitSeSfitfitSeSfitfiti=EeSfitfiti=xeSfitfiti=xei=Efitfiti=xei=xSfitSfitfitSeSfitfiti=EeSfitfiti=xeSfitfiti=xei=Efifii=xei=x因句子fitfiti=xei=x存在二個最左推導(dǎo)，故文法G為二義文法。10/10/第16頁這么對于該程序段有二個解釋：假設(shè)else和最近if結(jié)合，即a=2ifxthenbegin ifythena=4elsea=6end