《程序設(shè)計語言的語法描述.ppt》由會員分享，可在線閱讀，更多相關(guān)《程序設(shè)計語言的語法描述.ppt（18頁珍藏版）》請在裝配圖網(wǎng)上搜索。

2020 2 24 第3章程序設(shè)計語言的語法描述 3 1文法的引入3 2上下文無關(guān)文法3 3文法舉例 略 使用文法對程序設(shè)計語言的結(jié)構(gòu)進(jìn)行定義和描述 2020 2 24 3 1文法的引入 先討論自然語言的文法 例 thebigelephentateabanana 語法樹根據(jù)英語的語法 上述句子的語法結(jié)構(gòu)可用圖 語法樹 表示如下 非葉結(jié)點(diǎn)稱為語法單位 在形式語言中稱為非終結(jié)符 處于根結(jié)點(diǎn)位置的結(jié)點(diǎn)又稱為開始符號 葉結(jié)點(diǎn)稱為單詞符號 在形式語言中稱為終結(jié)符 2020 2 24 規(guī)則可以通過建立一組規(guī)則 來描述上述句子的語法結(jié)構(gòu) 規(guī)則在形式語言中稱為產(chǎn)生式 the a big elephant banana ate 由規(guī)則推導(dǎo)句子可用規(guī)則來推導(dǎo)出句子 從開始符號出發(fā) 若能從規(guī)則推導(dǎo)出某符號串 則該符號串就是該文法的合法的句子 反之語法錯誤 上述英文句子可用下述規(guī)則來描述 2020 2 24 the thebig thebigelephant thebigelephant thebigelephantate thebigelephantate thebigelephantatea thebigelephantateabanana上述推導(dǎo)可簡單表示為 thebigelephantateabanana 值得注意的是用上述規(guī)則可推導(dǎo)出多個句子 因存在推導(dǎo) abigbananaatetheelephant所以 abigbananaatetheelephant也是文法的一個合法的句子 但意義是荒謬的 也就是說句子的語義是錯誤的 一個語法正確的句子不能保證其語義是正確的 故一個句子是否正確 需要進(jìn)行語法和語義兩方面檢查 綜上所述 語言結(jié)構(gòu)通常是用文法來定義和描述 文法是由終結(jié)符 非終結(jié)符 開始符號 特殊非終結(jié)符 及產(chǎn)生式四個要素構(gòu)成 從開始符號出發(fā) 根據(jù)產(chǎn)生式能推導(dǎo)出的句子全體稱為文法所規(guī)定的語言 2020 2 24 遞歸規(guī)則和遞歸文法遞歸是編譯技術(shù)中的一個重要概念 遞歸定義 定義某事物 又用到該事物本身 遞歸規(guī)則 直接遞歸 在規(guī)則的左部和右部有相同的非終結(jié)符 例 U xUy 通常用大寫字母表示非終結(jié)符 用小寫字母表示終結(jié)符 左遞歸規(guī)則 x U Uy 表示空串 右遞歸規(guī)則 y U xU 間接遞歸 由規(guī)則推導(dǎo)產(chǎn)生 例 V Uy Z U xV因存在推導(dǎo)V Uy xVy 故存在間接遞歸 間接左遞歸 若x 則V Vy 間接右遞歸 若y 則V xU 遞歸文法 含有遞歸規(guī)則和間接遞歸的文法 稱為遞歸文法 利用遞歸文法 可以用有窮的規(guī)則來描述無窮的語言 這不但解決了語言的定義問題 而且使得對語言的語法檢查成為可能 2020 2 24 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)文法 2020 2 24 文法和語言一個文法G是一個四元式 VT VN S P 其中VT是一個終結(jié)符的非空有限集 終結(jié)符通常用小寫字母表示 VN是一個非終結(jié)符的非空有限集 非終結(jié)符通常用大寫字母表示 S是一個特殊的非終結(jié)符 S VN 稱為開始符號 P是一個產(chǎn)生式 規(guī)則 的有限集合 每個產(chǎn)生式的形式是A 其中A VN VT VN 終結(jié)符是語言的基本符號 即程序設(shè)計語言的單詞 語法分析時 終結(jié)符用單詞的種別表示 根據(jù)前面約定 標(biāo)識符 簡單變量 i無符號整常數(shù) x無符號實(shí)常數(shù) y單字符單詞 用單詞本身表示 例單詞 的種別用 表示 多字符單詞 需特別指定 例 用 表示 2020 2 24 非終結(jié)符表示抽象的語法單位 例 算術(shù)表達(dá)式 布爾表達(dá)式 賦值語句 說明語句 和 程序 等 非終結(jié)符通常用大寫字母表示 也可以用帶尖括號的漢字表示 開始符號是一個特殊的非終結(jié)符 它代表我們最感興趣的語法單位 例如討論算術(shù)表達(dá)式 那么描述算術(shù)表達(dá)式文法的開始符號就是 在程序設(shè)計語言中 我們最感興趣的語法單位是 程序 產(chǎn)生式是定義語法單位的一種書寫規(guī)則 上下文無關(guān)文法產(chǎn)生式的左部必定是一個非終結(jié)符 該非終結(jié)符稱為左部符號 產(chǎn)生式的右部是終結(jié)符和非終結(jié)符經(jīng)有限次連接構(gòu)成的文法符號串 可以是空字 四種文法的區(qū)別主要是對產(chǎn)生式的左部和右部的限制不同 若干個左部符號相同的產(chǎn)生式 可合并為一個 例 A 1 2 n 其中 i稱為A的候選式 1 i n 2020 2 24 例1 描述算術(shù)表達(dá)式文法G VT VN S P 其中VT i x y VN S P i 標(biāo)識符 x 無符號整常數(shù) y 無符號實(shí)常數(shù) 根據(jù)上述文法 可推導(dǎo)出任何僅包含加減乘除的算術(shù)表達(dá)式 2020 2 24 因已約定非終結(jié)符和終結(jié)符的書寫方式 非終結(jié)符和終結(jié)符在產(chǎn)生式中一目了然 故終結(jié)符集VT和非終結(jié)符集VN無需再顯式列出 若規(guī)定左部符號為開始符號的產(chǎn)生式寫在所定義文法的第一行 上述文法G又可簡單表示為如下形式 i x y若用E表示 T表示 F表示 借助符號 算術(shù)表達(dá)式文法G可表示成如下最簡形式 E E T E T TT T F T F FF E i x y 2020 2 24 例2 描述算術(shù)表達(dá)式文法G VT VN S P 其中VT i x y VN P i 標(biāo)識符 x 無符號整常數(shù) y 無符號實(shí)常數(shù) 根據(jù)上述文法 同樣可推導(dǎo)出任何僅包含加減乘除的算術(shù)表達(dá)式 用E表示 上述文法可簡記為 E E E E E E E E E E i x y 2020 2 24 基本術(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為文法的開始符號 則稱 是文法的一個句型 句子僅包含終結(jié)符的句型稱為句子 2020 2 24 語言文法 所能推導(dǎo)出的句子全體稱為該文法的語言 記為 L G S VT 等價文法 1和 2是二個不同的文法 若L G1 L G2 則稱G1和G2是等價文法 等價文法的存在 使我們能夠在不改變文法所規(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)行替換 記為 2020 2 24 文法的二義性 語法樹我們可以用一個有向圖表示一個句型的推導(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)先性 規(guī)定 優(yōu)先于 i i i等價于i i i 算符結(jié)合性 規(guī)定同級運(yùn)算服從左結(jié)合 i i i等價于 i i i 2 根據(jù)條件修改編譯程序的語法分析表 文法保持不變 詳見第四 五章 2020 2 24 1 根據(jù)條件修改文法 語言不變 算符優(yōu)先性 規(guī)定 優(yōu)先于 i i i等價于i i i 算符結(jié)合性 規(guī)定同級運(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) E E T E T F E T i E F i E i i T i i F i i i i iE T T F 先形成 才有可能形成 若先形成 只有帶括號才可能形成 2020 2 24 2 根據(jù)條件修改編譯程序的語法分析表 文法保持不變 例文法G if標(biāo)識符thenelseS fitSeS if標(biāo)識符thenS fitS 標(biāo)識符 S i E 無符號整常數(shù)E x程序段a 2ifxthenifythena 4elsea 6相應(yīng)的語法結(jié)構(gòu)表示為i xfitfiti xei x句子fitfiti xei x的最左推導(dǎo)序列有二個 如下所示 S fitSeS fitfitSeS fitfiti EeS fitfiti xeS fitfiti xei E fitfiti xei xS fitS fitfitSeS fitfiti EeS fitfiti xeS fitfiti xei E fifii xei x因句子fitfiti xei x存在二個最左推導(dǎo) 故文法G為二義文法 2020 2 24 這樣對于該程序段有二個解釋 假設(shè)else和最近的if結(jié)合 即a 2ifxthenbeginifythena 4elsea 6end 當(dāng)x和y為下列值時 相應(yīng)a的值為 假設(shè)else和最遠(yuǎn)的if結(jié)合 即a 2ifxthenbeginifythena 4endelsea 6 實(shí)際的編譯程序不可能 也不允許有兩種解釋 通常按第一種方式進(jìn)行翻譯執(zhí)行 即 else和最近的if結(jié)合 2020 2 24 結(jié)束