程序設計語言常用語法與翻譯

程序設計語言常用語法與翻譯第一頁，共四十四頁，編輯于2023年，星期一第四章程序設計語言常用的

語法與翻譯方法信息學院軟件工程教研室第二頁，共四十四頁，編輯于2023年，星期一4.1逆波蘭表示法

逆波蘭表示表達式高級語言表示表達式

ab* a*b

ab*c+ a*b+c

abcd/+* a*(b+c/d)

ab*cd*+ a*b+c*d信息學院軟件工程教研室第三頁，共四十四頁，編輯于2023年，星期一高級語言表達式E的逆波蘭表示法可這樣定義：（1）若E是高級語言中的一個變量或常數(shù)，則E的逆波蘭表示式仍是E。（2）若高級語言中的表達式為E1opE2，其中，op是一個二元算符，E1、E2也是表達式，則逆波蘭式表示為E1'E2'op，其中，E1'是E1的逆波蘭式，E2'是E2的逆波蘭式。（3）若高級語言中的表達式為（E），則逆波蘭表示式為去掉括號的E'，E'為E的逆波蘭表示式。信息學院軟件工程教研室第四頁，共四十四頁，編輯于2023年，星期一三地址代碼是由下面一般形式的語句構成的序列。x:=yopz其中x、y、z是變量名或編譯時產(chǎn)生的臨時變量名；y、z還可以是常數(shù)；op代表某種操作符。這種中間語言的特點有兩個。（1）非常接近匯編語言形式，包括匯編語言中最基本的操作。（2）每個語句中賦值號的右邊只有一個操作符，使得句子意義最小且不可分。例如，源語言表達式x+y*z可被翻譯成如下的句子序列：T1:=y*zT2:=x+T14.2三地址代碼信息學院軟件工程教研室第五頁，共四十四頁，編輯于2023年，星期一三地址代碼的語句形式可分為兩類：一類是帶有各種運算操作的賦值語句第二類是轉移語句三地址碼語句可看成是一種中間代碼的抽象形成，在編譯程序中，三地址代碼的具體實現(xiàn)常以記錄的形式表示，通常有3種表示方法：四元式、三元式、間接三元式信息學院軟件工程教研室第六頁，共四十四頁，編輯于2023年，星期一4.3程序設計語言常用語法4.3.1表達式語法（算術）4.3.2賦值語句4.3.3if語句4.3.4循環(huán)語句4.3.5說明語句4.3.6函數(shù)的定義與調(diào)用4.3.7程序語句序列文法信息學院軟件工程教研室第七頁，共四十四頁，編輯于2023年，星期一4.3.1表達式語法（算術）根據(jù)算術表達式的定義，一般算術表達式記為E，其文法被定義為：E→EopE （op為雙目操作符）E→opE （op為單目操作符）E→D|id （D為數(shù)字，id為標識符號）這是一個無法直接使用的二義性文法，必須使用前述兩種消除二義性文法的策略將文法中的二義性表達加以限制或改寫。信息學院軟件工程教研室第八頁，共四十四頁，編輯于2023年，星期一對這種表達式保留文法的二義性也有好處。不過在作語法分析時要規(guī)定算符間的優(yōu)先關系和結合順序，這樣才能確定語句的最終意義。這就是常用于表達式語法分析的算符優(yōu)先分析法。信息學院軟件工程教研室第九頁，共四十四頁，編輯于2023年，星期一無二義的表達式文法一般定義為：

無論采用哪一種文法形式，只要最終語句的意義是確定、不含糊的，并且是統(tǒng)一的，那么同一個語句所對應的抽象語法樹就是相同的。信息學院軟件工程教研室第十頁，共四十四頁，編輯于2023年，星期一4.3.2賦值語句賦值語句的文法最簡單，定義為：

其中，是一個名字,它表示各種類型的變量，包括下標變量（數(shù)組）?！?”是賦值號，E是表達式，賦值語句的語義是把賦值號右邊表達式的值放到賦值號左邊名字所指的地址中去。信息學院軟件工程教研室第十一頁，共四十四頁，編輯于2023年，星期一對賦值語句文法定義的句子而言，相應的抽象語法樹如圖所示。信息學院軟件工程教研室第十二頁，共四十四頁，編輯于2023年，星期一4.3.3if語句if語句是控制語句的一種，它的文法被定義為：這個語法有兩個候選式，這兩個候選式的前半部分是一樣的，即：。也就是說，在一個符號串之后可能緊跟一個或跟其他的符號串。由于可選的影響，這個文法有二義性的，即所謂“懸掛問題”。信息學院軟件工程教研室第十三頁，共四十四頁，編輯于2023年，星期一考慮以下符號串:其中，符號E1、E2、S1、S2都是由終結符組成的符號串。這個串有兩個分析樹該語法樹把看作與其最近的同屬一層該語法樹把看作與整句之首的同屬一層信息學院軟件工程教研室第十四頁，共四十四頁，編輯于2023年，星期一改寫的文法如下：這個文法用非終結符M單獨定義可嵌套的if…else語句。它是無二義的，只是有些累贅，也不太容易理解。實際上，并不是所有的語句文法一定會存在懸掛，有些語言的設計就避免了這個問題。如果所有的語句都有結尾，或其他類似符號結尾，就不存在這個問題了。

信息學院軟件工程教研室第十五頁，共四十四頁，編輯于2023年，星期一語句又稱分支語句。在C中，它的語義是根據(jù)表達式的值決定是否執(zhí)行語句S或執(zhí)行兩個語句S中的某一個。仔細分析一下語句的符號串，真正有可執(zhí)行意義的符號只有E和S兩個非終結符，其他終結符只是標記符號串的結構形式。因此，在建立抽象語法樹的時候，我們可以擺脫那些沒有意義的符號。信息學院軟件工程教研室第十六頁，共四十四頁，編輯于2023年，星期一上圖所示是語句抽象語法樹的結構。這是一棵有三棵子樹的抽象語法樹，最左邊的子樹是表達式，這里一般都是關系表達式和邏輯表達式，但是有些Ｃ語言里也用算術表達式。最右邊的子樹是可選句子，所以用虛線連接。信息學院軟件工程教研室第十七頁，共四十四頁，編輯于2023年，星期一4.3.4循環(huán)語句循環(huán)語句也有各種不同的情況，但實質(zhì)是一樣的，其一般的語法形式也很簡單，如下：對應的抽象語法樹如圖所示。信息學院軟件工程教研室第十八頁，共四十四頁，編輯于2023年，星期一說明語句用以定義各種名字的數(shù)據(jù)類型。與表達式和控制語句不同的是，說明語句不會被翻譯成可執(zhí)行代碼，因此也不會被翻譯成中間代碼。說明語句實質(zhì)是為名字確定存儲空間或過程、函數(shù)的起始地址。說明語句也可以生成語法樹，通過語法樹來確定各個名字的類型。由于說明語句沒有嵌套，所以沒有層次。因此它的抽象語法樹蛻化成一個鏈表。所謂類型，其實質(zhì)就是存儲控制。信息學院軟件工程教研室第十九頁，共四十四頁，編輯于2023年，星期一4.1.5說明語句名字本身則與存儲地址或過程函數(shù)入口地址關聯(lián)，說明語句的語法為：這里，D可理解為說明語句。T是類型標識集合，L是變量表，是變量名。說明語句常與符號表配合使用，所謂符號表就是名字登記表，那里保存著與名字相關的信息。信息學院軟件工程教研室第二十頁，共四十四頁，編輯于2023年，星期一4.3.7程序語句序列文法程序是由語句序列組成的，語句序列的文法可表示為：這是用分號分隔開的語句序列。由于語句間的并列意義，故仍以鏈表表示為最好，對應的結構如下圖所示。信息學院軟件工程教研室第二十一頁，共四十四頁，編輯于2023年，星期一其中，三角形表示潛在的子樹。由前文可知，各種各樣的語句經(jīng)語法分析后都有與之對應的語法樹。實際上，每個程序在語法分析之前可看成一個長長的詞串，而在語法分析之后就變成一棵整體的語法樹。下面通過一個例子來說明。P45-列4.1信息學院軟件工程教研室第二十二頁，共四十四頁，編輯于2023年，星期一4.4中間代碼的翻譯4.4.1表達式中間代碼4.4.2if語句中間代碼生成4.4.3布爾表達式代碼生成4.4.4循環(huán)語句中間代碼4.4.5綜合實例信息學院軟件工程教研室第二十三頁，共四十四頁，編輯于2023年，星期一1．逆波蘭式的生成4.4.1表達式中間代碼信息學院軟件工程教研室第二十四頁，共四十四頁，編輯于2023年，星期一2．四元式的生成表達式的四元式變換如下所示：是編譯過程中的臨時變量，用以存儲中間結果。

其中，信息學院軟件工程教研室第二十五頁，共四十四頁，編輯于2023年，星期一4.4.2if語句中間代碼生成if語句翻譯成中間代碼時，變成對布爾表達式的判斷與轉移組合。所生成的四元式中間代碼由兩條基本語句組成：信息學院軟件工程教研室第二十六頁，共四十四頁，編輯于2023年，星期一語句有兩種形式：形式1：(E)S信息學院軟件工程教研室第二十七頁，共四十四頁，編輯于2023年，星期一形式2：信息學院軟件工程教研室第二十八頁，共四十四頁，編輯于2023年，星期一根據(jù)這個語義的關系將其相應的抽象語法圖翻譯為固定的四元式格式。(E的四元式，值存入T)next：(后續(xù)程序四元式)信息學院軟件工程教研室第二十九頁，共四十四頁，編輯于2023年，星期一在語句中，表達式E的作用是提供選擇執(zhí)行語句S1還是S2的判斷。因此不必保留E的值，而是將計算結果表示為程序執(zhí)行流程的轉移。此時E的值只需有兩個即可。所以E被視為布爾表達式。E的真值被轉換為一個條件轉移，稱為“真出口”。E的假值被轉換為一個無條件轉移，稱為“假出口”。信息學院軟件工程教研室第三十頁，共四十四頁，編輯于2023年，星期一最簡單的情況E是一個布爾變量a，那么有：真出口假出口信息學院軟件工程教研室第三十一頁，共四十四頁，編輯于2023年，星期一另外，布爾量間的運算除了一般的布爾代數(shù)運算外，還有一種運算方法，稱為“短路布爾操作”。它的意義是：對于一個二元布爾操作，如果根據(jù)第1個布爾量的值就可以判斷這個布爾結果，那么就不必計算第2個布爾量了。就是說，在某種情況下第2個布爾量被短路了。信息學院軟件工程教研室第三十二頁，共四十四頁，編輯于2023年，星期一例如，對于二元操作aandb，如果a是假，不管b是什么，aandb的結果都是假。所以

b就不用計算了。再如，二元操作aorb，如果a是真，不管b是什么，aorb的結果都是真。所以b就可以被短路掉，這種短路的操作對代碼來說是很重要的。有些時候，沒被短路的操作會引起錯誤。例如：信息學院軟件工程教研室第三十三頁，共四十四頁，編輯于2023年，星期一這是C語言中常見的語句，但如果出現(xiàn)p==NULL時還要對求值將引起內(nèi)存錯誤。信息學院軟件工程教研室第三十四頁，共四十四頁，編輯于2023年，星期一短路的布爾操作類似于if語句，它們經(jīng)常用if表達式定義，例如：將E1的真出口轉移至E2的第1個四元式的假出口與全句假出口并聯(lián)（相同），E2的真出口就是全句的真出口，E2的假出口也是全句的假出口。將E1的真出口與全句的真出口并聯(lián)，E1的假出口轉移至E2的第1個四元式，E2的真出口是全句的真出口，E2的假出口是全句的假出口。信息學院軟件工程教研室第三十五頁，共四十四頁，編輯于2023年，星期一4.4.4循環(huán)語句中間代碼循環(huán)語句的一般語法為：信息學院軟件工程教研室第三十六頁，共四十四頁，編輯于2023年，星期一信息學院軟件工程教研室第三十七頁，共四十四頁，編輯于2023年，星期一循環(huán)語句生成的四元式序列的結構如下：next:(后續(xù)程序四元式)信息學院軟件工程教研室第三十八頁，共四十四頁，編輯于2023年，星期一4.4.5綜合實例【例】有語句如下：While(A>BorC>D)if(x==0)x=y*z;elsex=y+z;求四元式序列（翻譯）。信息學院軟件工程教研室第三十九頁，共四十四頁，編輯于2023年，星期一解：（1）求出該句的語法樹信息學院軟件