2/5/2023溫故知新翻譯程序：它是一個程序，能把一種語言程序轉換成另一種語言程序，且二者在邏輯上是等價的。這兩種語言分別稱為源語言和目標語言。編譯程序：一種翻譯程序，它的源語言是“高級語言”（C,Java,Pascal），目標語言是“低級語言”(匯編語言，機器語言)12/5/2023中國科大溫故知新編譯前端編譯后端編譯前端：與源語言有關，與目標機無關詞法分析器語法分析器語義分析與中間代碼生成器源程序優(yōu)化器目標代碼生成器目標代碼表格管理出錯處理單詞符號語法單位中間代碼中間代碼編譯后端：與源語言無關，與目標機有關2第二章高級語言及其語法描述本章內(nèi)容簡介本章描述程序設計語言的基本結構和主要共同特征并介紹程序設計語言主要語句的文法描述與形式定義。

與機器語言或匯編語言比較，高級語言的優(yōu)點：較接近于數(shù)學語言和工程語言，比較直觀、自然和易于理解;便于驗證其正確性，易于改錯;編寫效率高;易于移植.2.1程序語言的定義任何語言實現(xiàn)的基礎是語言定義語言的定義決定了該語言具有什么樣的語言功能、什么樣的程序結構、什么樣的數(shù)據(jù)結構以及具體的使用形式等細節(jié)問題。對于語言用戶來說：語言定義就是一本用戶手冊。對于編譯程序設計者來說：語言定義就是具體實現(xiàn)的理論依據(jù)。對程序設計語言的描述是從語法、語義和語用三個因素來考慮。語法是對語言結構的定義。語義是描述了語言的含義語用則是從使用的角度去描述語言。例如賦值語句s＝2*3.1416*r*(r+h)的非形式化的描述為：語法：賦值語句由一個變量，后隨一個賦值號“＝”，再在其后面跟一個表達式構成。語義：首先計算語句右部表達式的值，然后把所得結果送給左部變量中。語用：賦值語句可用來計算和保存表達式的值。2.1.1語法語言的語法是指這樣一組規(guī)則，用它可產(chǎn)生一個程序。規(guī)則：詞法規(guī)則語法規(guī)則詞法規(guī)則：單詞符號的形成規(guī)則。單詞符號是語言中具有獨立意義的最基本結構。一般包括：常數(shù)、標識符、基本字、算符、界符等。描述工具：有限自動機語法規(guī)則：語法單位的形成規(guī)則。語法單位通常包括：表達式、語句、分程序、過程、函數(shù)、程序等;描述工具：上下文無關文法2.1.2語義語義：一組規(guī)則，用它可以定義一個程序的意義。程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運算。所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處理過程。程序的層次結構程序|子程序或分程序、過程、函數(shù)|語句|表達式|數(shù)據(jù)引用算符函數(shù)調(diào)用程序語言每個組成成分的邏輯和實現(xiàn)意義

抽象的邏輯的意義數(shù)學意義計算機實現(xiàn)的意義具體實現(xiàn)2.2高級語言的一般特性

高級語言的分類

強制式語言(ImperativeLanguge)也稱過程式語言：命令驅(qū)動，面向語句FORTRAN、C、Pascal，Ada應用式語言（ApplicativeLanguage）：注重程序所表示的功能，而不是具體語句的執(zhí)行LISP、ML2.2高級語言的一般特性

2.2.1高級語言的分類

基于規(guī)則的語言（Rule-basedLanguage）：檢查一定的條件，當它滿足值，則執(zhí)行適當?shù)膭幼鱌rolog面向?qū)ο笳Z言（Object-OrientedLanguage）：封裝性、繼承性和多態(tài)性Smalltalk，C++，Java2.2.2程序結構FORTRAN一個程序由一個主程序段和若干輔程序段組成。輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊。每個程序段有一系列的說明語句和執(zhí)行語句組成。各段可以獨立編譯。模塊結構，沒有嵌套和遞歸各程序段中的名字相互獨立，同一個標識符在不同的程序段中代表不同的名字。主程序PROGRAM… …end輔程序1SUBROUTINE… …end輔程序2FUNCTION… …endPASCALPASCAL程序本身可以看成是一個操作系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。一個PASCAL過程：過程頭；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；end2/5/2023中國科大2.2高級語言的一般特性2.2.2程序結構–JavaclassCar{intcolor_number;intdoor_number;intspeed;Push_break(){…}Add_oil(){…}}classTrash_CarextendsCar{doubleamount;Fill_trash(){…}}封裝、繼承、多態(tài)(2)public、protected、private202.2.3數(shù)據(jù)類型與操作一個數(shù)據(jù)類型通常包括以下三種要素：用于區(qū)別這種類型數(shù)據(jù)對象的屬性這種類型的數(shù)據(jù)對象可以具有的值可以作用于這種類型的數(shù)據(jù)對象的操作2.2.3數(shù)據(jù)類型與操作一．初等數(shù)據(jù)類型數(shù)值類型：整型、實型、復數(shù)、雙精度，運算：+，-，*，/等邏輯類型：布爾運算：∨，∧，┑字符類型：符號處理指針類型：值指向另外一些數(shù)據(jù)標識符與名字標識符：以字母開頭的，由字母數(shù)字組成的字符串。標識符與名字兩者有本質(zhì)區(qū)別：標識符是語法概念名字有確切的意義和屬性標識符與名字名字：值：單元中的內(nèi)容屬性：類型和作用域名字的性質(zhì)的說明方式：由說明語句來明確規(guī)定的隱含說明：FORTRAN以I,J,K,…N為首的名字代表整型，否則為實型。動態(tài)確定：走到哪里，是什么，算什么2/5/2023中國科大2.2高級語言的一般特性1、數(shù)組數(shù)組：同一類型數(shù)據(jù)所組成的某種n維矩形結構下標：沿著某一維的距離數(shù)組元素：由數(shù)組名連同各維的下標值命名確定數(shù)組、可變數(shù)組intarray[3];

inta=array[2];intsize=3;//或用戶輸入的數(shù)int*array=newint[size];

inta=array[2];Delete[]array;確定數(shù)組可變數(shù)組252/5/2023中國科大2.2高級語言的一般特性1、數(shù)組數(shù)組存儲方式：按行存放、按列存放數(shù)組元素地址計算：數(shù)據(jù)結構1A[2][3]={{1,2,3},{4,5,6}}23456123456按行存放142536按列存放26內(nèi)情向量把數(shù)組的有關信息記錄在一個“內(nèi)情向量”中，每個數(shù)組的內(nèi)情向量必須包括：維數(shù)，各維的上、下限，首地址，以及數(shù)組（元素）的類型。對于確定數(shù)組來說，內(nèi)情向量可登記在符號表中；

對于可變數(shù)組，內(nèi)情向量的信息在編譯時無法全部知道，只有到運行階段才能全部確定下來，存貯分配也要等到運行時方能進行2記錄邏輯上說，記錄結構由已知類型的數(shù)據(jù)組合在一起的一種結構。 record{charNAME[20]; integerAGE; boolMARRIED; }CARD[1000]訪問：復合名CARD[k].NAME存儲：連續(xù)存放域的地址計算：相對于記錄結構起點的相對數(shù)OFFSET。3字符串、表格、棧字符串：符號處理、公式處理表格：本質(zhì)上是一種記錄結構線性表：一組順序化的記錄結構棧：一種線性表，后進先出，POP,PUSH三抽象數(shù)據(jù)類型一個抽象數(shù)據(jù)類型包括：數(shù)據(jù)對象的一個集合；作用于這些數(shù)據(jù)對象的抽象運算的集合；這種類型對象的封裝，即，除了使用類型中所定義的運算外，用戶不能對這些對象進行操作。程序設計語言對抽象數(shù)據(jù)類型的支持Ada語言通過程序包（package）提供了數(shù)據(jù)封裝的支持Smalltalk、C++和Java語言則通過類（Class）對抽象數(shù)據(jù)類型提供支持。2.2.4語句與控制結構一．表達式表達式由運算量（也稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符（操作符）組成。形式：中綴、前綴、后綴X*Y-AP↑表達式形成規(guī)則(1)變量（包括下標變量）、常數(shù)是表達式(2)若E1、E2為表達式，θ為二元運算符，則E1θE2是表達式(3)若E是表達式，θ為一元運算符，則θE或Eθ是表達式(4)若E是表達式，則（E）是表達式5、a、5+a、-a、(a+5)、2+(4+a)-(-5)都是表達式2/5/20232.2高級語言的一般特性表達式的結合性和優(yōu)先集與數(shù)學習慣類似不同的語言，這兩種性質(zhì)各有差異FORTRAN結合性優(yōu)先集X–Y-Z等于(X–Y)-Z左結合X–Y+Z等于(X-Y)+Z左結合X**Y**Z等于X**(Y**Z)右結合332/5/2023中國科大2.2高級語言的一般特性表達式的結合性和優(yōu)先集與數(shù)學習慣類似不同的語言，這兩種性質(zhì)各有差異FORTRAN結合性優(yōu)先集乘冪**或↑一元負-乘、除*，/，÷加、減+，-關系符<,=,>,<=,<>,>=非﹁，not或.NOT.與∧，&，and或.AND.或∨，|，or或.OR.隱含imp或等值≡，～或epui342/5/2023中國科大2.2高級語言的一般特性例：令+、*和↑代表加、乘和乘冪，按照如下的非標準優(yōu)先集和結合性的約定（1）優(yōu)先順序（從高至低）為+、*和↑（2）同級優(yōu)先采用左結合計算1+1*2↑2*1↑2的值

1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256352/5/2023中國科大2.2高級語言的一般特性2.2.4語句和控制結構二、語句從功能上說，語句大體可分執(zhí)行性語句和說明性語句。從形式上說，語句還可分為簡單句、復合句和分程序等。36二．語句賦值語句：A:=B名字左值：該名字代表的那個單元（地址）稱為該名字的左值。(所代表的存貯單元的地址)右值：一個名字的值稱為該名字的右值。(所代表的存貯單元的內(nèi)容)控制語句：無條件轉移語句

gotoL條件語句

ifBthenSifB

thenS1elseS2循環(huán)語句

whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS過程調(diào)用語句

callP(X1,X2,...,Xn)返回語句

return(E)說明語句：定義各種不同數(shù)據(jù)類型的變量或運算，定義名字的性質(zhì)。簡單句和復合句簡單句：不包含其他語句成分的基本句復合句：句中有句的語句復習：高級語言的一般特性

高級語言的分類

程序結構數(shù)據(jù)類型與操作初等數(shù)據(jù)類型數(shù)據(jù)結構抽象數(shù)據(jù)類型語句與控制結構2/5/2023中國科大作業(yè)P35頁，第3、4題422.3程序語言的語法描述為了精確定義和描述程序設計語言,需采用形式化的方法。所謂形式化的方法,是用一整套帶有嚴格規(guī)定的符號體系來描述問題的方法。形式語言理論是編譯的重要理論基礎。重點介紹如何采用形式化的方法描述程序設計語言。字母表字母表：元素的非空有窮集例如，∑={a,b,c}根據(jù)字母表的定義，Σ是字母表，它由a、b、c三個元素組成。注意：

(1)字母表中至少包含一個元素。

(2)字母表中的元素,可以是字母、數(shù)字或其他符號。例如，∑‘={0,1}是一個字母表，由0、1兩個元素組成。字母表中的元素稱為符號或稱為字符。例如，前述例子中2.符號（字符）a、b、c是字母表Σ中的符號；0、1是字母表Σ'中的符號。例如，設有字母表∑={a,b,c}符號的有窮序列稱為符號串。符號串總是建立在某個特定字母表上的且只由字母表上的有窮多個符號組成。則有符號串a(chǎn)，b，ab，ba，cba，

abc…

3.符號串（字）說明：符號串中符號的順序很重要ab和ba是字母表Σ上的兩個不同符號串。不包含任何符號的符號串被稱為是空符號串。用ε表示2/5/20232.3程序語言的語法描述符號串的長度串中符號的個數(shù)為符號串的長度。若x=ab是符號串，則|x|表示符號串的長度。|x|=2。注意：|ε|=049字符串的連接：設X是個字符串，Y是個字符串，則XY就是字符串的連接。例如設X＝ABC，Y＝10A則XY＝ABC10A，YX＝10AABC。對于任意一個字符串X，都有εx＝xε＝x。注意在U≠V下，UV≠VU，即不滿足交換率(UV)W=U(VW)，即滿足結合率2、集合乘積

設A和B是符號串的集合,則A和B的乘積定義為：

AB={xy|x∈A,y∈B}集合的乘積是滿足于x∈A,y∈B的所有符號串xy所構成的集合。例如：設A={a,b},B={c,d}則AB={ac,ad,bc,bd}由于對任意的符號串x，總有

x=x=x所以,對任意集合A,我們有:{}A=A{}=A特別指出的是，是符號串,不是集合，而{}表示由空符號串所組成的集合,但這樣的集合不是空集合Φ={}。3.符號串的冪運算設x是符號串,則x的冪運算定