哈工大編譯原理第2章.ppt

1、第二章 高級語言 及其語法描述,計(jì)算機(jī)學(xué)院 辛明影,2,內(nèi)容簡介：,本章概述程序設(shè)計(jì)語言的結(jié)構(gòu),2.1 程序語言的定義,任何語言實(shí)現(xiàn)的基礎(chǔ)是語言定義。,語言的定義決定了該語言,具有什么樣的語言功能、,什么樣的數(shù)據(jù)結(jié)構(gòu)、,什么樣的程序結(jié)構(gòu)、,以及具體的使用形式等細(xì)節(jié)問題。,和主要的共同特征，,并介紹程序設(shè)計(jì)語言主要語句的文法描述與形式定義。,計(jì)算機(jī)學(xué)院 辛明影,3,對于編譯程序設(shè)計(jì)者來說：語言定義就是具體實(shí)現(xiàn)的理論依據(jù)。,對于語言用戶來說：語言定義就是一本用戶手冊。,2.1.1語法,語言的語法是指這樣一組規(guī)則，用它可產(chǎn)生一個(gè)程序。,規(guī)則： 詞法規(guī)則 語法規(guī)則,計(jì)算機(jī)學(xué)院 辛明影,4,詞法規(guī)則是指

2、單詞符號的形成規(guī)則,字母表就是一個(gè)有窮字符集。,C語言的字母表為： =a-z 、 AZ 、 09 、(、) 、 、 、 、.、! 、 、+ 、- 、* 、 / 、 ,C語言的標(biāo)識符的構(gòu)成規(guī)則：,字母、下劃線打頭的字母、數(shù)字和下劃線構(gòu)成的符號串。如：a1、ave 、_day,一 .詞法規(guī)則,計(jì)算機(jī)學(xué)院 辛明影,5,上述的定義是用文字來描述的，當(dāng)設(shè)計(jì)編譯程序時(shí)，就要把它用形式的方式描述出來，就要用到形式語言。,各類型的常數(shù)、,標(biāo)識符、,基本字、,算符和界符等,正規(guī)式和有窮自動機(jī)是描述詞法結(jié)構(gòu)和進(jìn)行詞法分析的有效工具,在現(xiàn)今多數(shù)程序設(shè)計(jì)語言中，單詞符號一般包括：,計(jì)算機(jī)學(xué)院 辛明影,6,C語言的標(biāo)識

3、符的文法和自動機(jī)描述：,例：C語言標(biāo)識符的文法描述 L（G）=w/w為字母或-打頭的字母數(shù)字串,解：P:I aB I -B I a B aB B dB Ba B d,識別L（G）的自動機(jī),I,B,T,a,-,a,d,其它,計(jì)算機(jī)學(xué)院 辛明影,7,S,A,C,D,F,E,B,7,d,d,d,d,d,d,d,e,e,+,T,*,例：C語言實(shí)常數(shù)的文法描述,文法：S dA A dA A eD A .B B dC C dC C eD D -E D +E D dF E dF F dF F d,其它,其它,其它,1000,3.14,10e+3 3.14e-5,12e5,計(jì)算機(jī)學(xué)院 辛明影,8,二.語法規(guī)則

4、,語法規(guī)則規(guī)定了如何從單詞符號形成更大的結(jié)構(gòu)（即語法單位），換言之，語法規(guī)則是語法單位的形成規(guī)則,一般的程序設(shè)計(jì)語言的語法單位有：,表達(dá)式 、,語句 、,分程序 、,函數(shù) 、,過程和程序等,下推自動機(jī)理論和上下文無關(guān)文法是我們討論語法分析的理論基礎(chǔ),計(jì)算機(jī)學(xué)院 辛明影,9,表達(dá)式： EE+T EE-T ET TT*F TT/F TF F(E) F id,主要語句的形式描述：,計(jì)算機(jī)學(xué)院 辛明影,10,布爾表達(dá)式： B B or B B B and B B not B B(E） B id relop id B true B false,計(jì)算機(jī)學(xué)院 辛明影,11,賦值、分支、循環(huán)語句： S id=

5、E S if B then S S if B then S else S S while B do S S L L L ;S L S,計(jì)算機(jī)學(xué)院 辛明影,12,調(diào)用語句： Scall id(Elist) Elist Elist,E Elist E|,計(jì)算機(jī)學(xué)院 辛明影,13,類型說明和過程說明語句： P D D D;D D id:T Did（Elist） D ; S T int T float,計(jì)算機(jī)學(xué)院 辛明影,14,數(shù)組說明語句： L idElist Elist Elist,E Elist E,計(jì)算機(jī)學(xué)院 辛明影,15,2.1.2 語義,例：a=b+c*d,例do 999 I=1,10,對

6、于一個(gè)語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義，這就是語義問題,對于編譯程序來說，只有了解程序的語義，才知道應(yīng)把它翻譯成什么樣的目標(biāo)指令代碼,計(jì)算機(jī)學(xué)院 辛明影,16,2.2 構(gòu)造基礎(chǔ),2.2.1 程序結(jié)構(gòu)簡介,一個(gè)高級語言程序通常由若干子程序段（過程、函數(shù)等）組成，,許多語言還引入了類、程序包等更高級的結(jié)構(gòu),計(jì)算機(jī)學(xué)院 辛明影,17,FORTRAN,一個(gè)FORTRAN 程序由一個(gè)主程序和若干個(gè)輔助程序段組成,PROGRAM MAIN . END SUBROUTINE SUB1 . .END FUNCTION FUN1 . END,它的定義是并列的,計(jì)算機(jī)

7、學(xué)院 辛明影,18,FORTRAN 的構(gòu)成特點(diǎn)：,同一名字在不同的程序段中一般都代表不同的對象，也就是說代表不同的存貯單元,PROGRAM MAIN .integer x END SUBROUTINE SUB1 Integer x .END,Integer x,X,X=9999,100,Integer x,9999,X=100,X,PROGRAM MAIN . END SUBROUTINE SUB1 .END,一個(gè)名字對應(yīng)多個(gè)對象,計(jì)算機(jī)學(xué)院 辛明影,19,但是不同程序段里的同名公用塊卻代表同一個(gè)存貯區(qū)域,PROGRAM MAIN . Common a,b END SUBROUTINE SUB

8、1 common x,y .END,PROGRAM MAIN . END SUBROUTINE SUB1 . END,Common a,b,a,b,A=100 B=50,100,50,Common x,y,x,y,Y=x+100,200,共享存貯單元,多個(gè)名字對應(yīng)一個(gè)對象,計(jì)算機(jī)學(xué)院 辛明影,20,二。Pascal,Pascal 允許子程序嵌套定義,Program main 說明部分 Begin 可執(zhí)行部分 end,Pascal的 程序結(jié)構(gòu),Program main Begin end,Procedure P1 Begin end,Procedure P11 Begin end,Procedu

9、re P2 Begin end,也允許并列定義,計(jì)算機(jī)學(xué)院 辛明影,21,關(guān)于名字的作用域的規(guī)定：,標(biāo)識符X的任意一次出現(xiàn)（除去說明語句中）都意味著對某個(gè)說明語句中說明的這個(gè)變量X的引用,此時(shí)，說明語句同標(biāo)識符X應(yīng)共處一個(gè)最小程序中，即：,P1中說明的X只在P1中有效,P11是P1的內(nèi)層子程序，P11中沒有再對X作新的說明，則在P11中對X的引用，實(shí)際上引用的就是P1中說明的X，,即內(nèi)部過程可以引用外部過程中定義的量,計(jì)算機(jī)學(xué)院 辛明影,22,三.java,Java語言是一種面向?qū)ο蟮母呒壵Z言，它很重要的方面是類和繼承的概念，同時(shí)支持多態(tài)性和動態(tài)綁定等特性,Class car Int colo

10、r_num; Int door_num; Int speed; . Void push_break() Void add_oil() ,Class benz extends car Double price; Void ABS( ) ,計(jì)算機(jī)學(xué)院 辛明影,23,一個(gè)類把有關(guān)的數(shù)據(jù)及其操作封裝在一起構(gòu)成一個(gè)抽象數(shù)據(jù)類型,一個(gè)子類繼承其父類的所有數(shù)據(jù)和方法，并且可以加入自己新的定義,在java中，變量和方法的定義之前可以加上public、private、pretected等修飾詞，,以限制其它類的對象對于這些變量和方法的使用,計(jì)算機(jī)學(xué)院 辛明影,24,2.2.2 構(gòu)造基礎(chǔ),程序設(shè)計(jì)語言的數(shù)據(jù)對象：

11、,數(shù)據(jù)、,函數(shù)、,過程,常用能反映其本質(zhì)的、有助于記憶的名字來表示,一.名字,特性：,一個(gè)名字對應(yīng)一個(gè)對象,，普通變量,多個(gè)名字對應(yīng)一個(gè)對象,一個(gè)名字對應(yīng)多個(gè)對象,，common, 數(shù)組、重載、 局部變量、 重寫、,計(jì)算機(jī)學(xué)院 辛明影,25,每個(gè)對象可以看做是一個(gè)存貯單元，,可能是一個(gè)字，也可能是多個(gè)字,名字具有屬性，,通常由說明語句給出,一個(gè)名字的屬性，包括：類型和作用域,類型決定了它有什么樣的值，,作用域規(guī)定了值的存在范圍,值在計(jì)算機(jī)內(nèi)的表示，,以及對它能施加什么樣的運(yùn)算,計(jì)算機(jī)學(xué)院 辛明影,26,二.數(shù)據(jù)類型,1.初等數(shù)據(jù)類型,數(shù)值數(shù)據(jù)：整形、實(shí)型、雙精度等，可施行算術(shù)運(yùn)算,邏輯數(shù)據(jù)：可

12、施行邏輯運(yùn)算,字符數(shù)據(jù)：,指針類型：,計(jì)算機(jī)學(xué)院 辛明影,27,三。數(shù)據(jù)結(jié)構(gòu),1。數(shù)組,從邏輯上講，一個(gè)數(shù)組是由同類型數(shù)據(jù)所組成的n 維矩形結(jié)構(gòu),一個(gè)數(shù)組所需的存貯空間大小在編譯時(shí)就已知道的，則稱此數(shù)組是一個(gè)確定的數(shù)組；否則稱為可變數(shù)組,設(shè)int Al1u1,l2u2 lnun 為n維數(shù)組 各維的長度：di=ui-li+1 (1in),計(jì)算機(jī)學(xué)院 辛明影,28,任一數(shù)組元素Ai1,i2, in的地址為： D=a+(i1-l1) d2d3 dn +(i2-l2) d2 d2 dn + (in-1-ln-1) dn + (in-ln),整理后C= ( (l1 d2 +l2) d3+ l3) d4+

13、 + ln-1) dn+ ln,C是數(shù)組計(jì)算中不變的部分,計(jì)算機(jī)學(xué)院 辛明影,29,變量部分：v= ( (i1 d2 +i2) d3+ i3) d4+ + in-1) dn+ in,任一數(shù)組元素Ai1,i2, in的地址: addr=a-c+v,計(jì)算機(jī)學(xué)院 辛明影,30,在編譯時(shí)，當(dāng)遇到說明時(shí)，必須把數(shù)組的有關(guān)信息記錄在一個(gè)“內(nèi)情向量”之中，用于數(shù)組元素的地址計(jì)算。,數(shù)組的內(nèi)情向量包括：,維數(shù)，各維的上、下限，首地址及數(shù)組的類型,ln,un,dn,l2,l1,un,un,d1,d2,N維數(shù),C常數(shù),T類型,A首地址,計(jì)算機(jī)學(xué)院 辛明影,31,對于確定數(shù)組來說，內(nèi)情向量可登記在符號表中；,對于可

14、變數(shù)組，內(nèi)情向量的信息在編譯時(shí)無法全部知道，只有到運(yùn)行階段才能全部確定下來，存貯分配也要等到運(yùn)行時(shí)方能進(jìn)行,計(jì)算機(jī)學(xué)院 辛明影,32,2.記錄（結(jié)構(gòu)）,從邏輯上講，記錄是由已知的數(shù)據(jù)組合起來的一種結(jié)構(gòu),Struct student char name20; boolean partmember; int age; stu;,計(jì)算機(jī)學(xué)院 辛明影,33,記錄結(jié)構(gòu)最簡單的存貯方式是連續(xù)存放,上述的變量stu共占7個(gè)字，共28個(gè)字節(jié),S Stu.partmember Stu.age,3.字符串、表格和隊(duì)列,k K+1 . K+20 . K+24 .,. .,計(jì)算機(jī)學(xué)院 辛明影,34,四.

15、抽象數(shù)據(jù)類型,一個(gè)抽象數(shù)據(jù)類型包括：,這種類型對象的封裝,作用于這些數(shù)據(jù)對象的抽象運(yùn)算的集合,數(shù)據(jù)對象的一個(gè)集合,C+、Java語言通過類對抽象類型提供支持,計(jì)算機(jī)學(xué)院 辛明影,35,五.語句與控制結(jié)構(gòu),1.表達(dá)式,要解決的問題：,優(yōu)先級,結(jié)合率,2.語句,語句可分為：,說明語句：,可執(zhí)行語句：,定義各種不同數(shù)據(jù)類型的變量和運(yùn)算,描述語句的動作,執(zhí)行語句分為：賦值、控制和I/O語句,計(jì)算機(jī)學(xué)院 辛明影,36,賦值句,A=B,左值,右值,名字的左值指它所代表的存貯單元地址,名字的右值指該 單元的內(nèi)容,計(jì)算機(jī)學(xué)院 辛明影,37,控制語句,無條件轉(zhuǎn)移語句：Goto lable,條件語句：If B t

16、hen S If B then S else S,循環(huán)語句：While B do S Repeat S until B For I=e1 to e2 step e3,過程調(diào)用語句：Call P(x1, x2,.xn),返回語句：Return(E),計(jì)算機(jī)學(xué)院 辛明影,38,說明語句,說明語句用于定義名字的性質(zhì)。,編譯程序把這些性質(zhì)登記在符號表中，并檢查程序中名字的引用和說明是否一致。,許多說明語句不產(chǎn)生目標(biāo)代碼,但有的說明語句，如過程說明和可變數(shù)組說明，則要產(chǎn)生相應(yīng)的目標(biāo)代碼,計(jì)算機(jī)學(xué)院 辛明影,39,簡單句和復(fù)合句,簡單句是指不包含其它語句成分的基本句。賦值、goto語句等,復(fù)合句則指那些句

17、中有句的語句,If (x=0) then x=1 x=1;y=2;goto l1;,program reference（input，output）； var a，b ： integer； procedure swap（x，y： integer）； var temp： integer； begin temp :x； x ：y； y ：temp end; begin a：1; b：2; swap(a，b); writeln( a=，a， b= , b ） end.,2.2.3 參數(shù)傳遞,結(jié)果是什么？,1 傳值調(diào)用,實(shí)在參數(shù)和形式參數(shù)結(jié)合的方法： 傳值調(diào)用（call-by-value） 引用調(diào)用（c

18、all-by-reference） 復(fù)制恢復(fù)（copy-restore） 傳名調(diào)用（call-by-name）,計(jì)算機(jī)學(xué)院 辛明影,42,子程序?yàn)槊恳粋€(gè)形參開辟一個(gè)存貯單元，用于存放 相應(yīng)實(shí)參的值。,子程序執(zhí)行時(shí)，每當(dāng)訪問形參時(shí)，就直接訪問形參單元。,實(shí)參：,形參：,傳值調(diào)用可以實(shí)現(xiàn)如下：,主調(diào)過程計(jì)算實(shí)在參數(shù)，并把它們的右- 值放入到形式參數(shù)的存儲空間中。,計(jì)算機(jī)學(xué)院 辛明影,43,使用傳值的方法，調(diào)用swap（a,b）等價(jià)于下面幾步： x：= a y：= b temp：= x x：= y y：= temp,2 引用調(diào)用（傳地址） 把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù), 在目標(biāo)代碼中，在被調(diào)

19、用過程中對形式參數(shù)的一次引用就成為對傳遞給被調(diào)用過程的指針的一個(gè)間接引用。,Reference,a b x y,1 2,swap,a b,temp,計(jì)算機(jī)學(xué)院 辛明影,45,子程序?yàn)槊總€(gè)形參開辟一個(gè)單元，用于存放相應(yīng)實(shí)參的地址，,執(zhí)行時(shí)，子程序間址方式訪問這些形參單元,當(dāng)實(shí)參為表達(dá)式或常數(shù)時(shí)，則存放它們值的臨時(shí)單元。,實(shí)參：,地址,形參：,Temp:=x; x:=y; y:=temp;,temp:=a; a:= b; b:=temp;,3 復(fù)制恢復(fù)（傳值結(jié)果） 實(shí)現(xiàn)： 1. 當(dāng)控制流入到被調(diào)用過程之前，把實(shí)在參數(shù) 的右-值和左-值傳遞到被調(diào)用過程中； 2. 當(dāng)控制返回時(shí)，把形式參數(shù)的現(xiàn)行右-值

20、復(fù)制回到相應(yīng)的實(shí)在參數(shù)的左-值中。,計(jì)算機(jī)學(xué)院 辛明影,47,子程序?yàn)槊總€(gè)形參分配兩個(gè)存貯單元B1和B2，B1用于存放實(shí)參地址，B2用于存放實(shí)參值。,執(zhí)行時(shí)，對B2單元使用直接訪問形式；返回前，按B1中的地址把B2中的內(nèi)容存入主調(diào)程序的實(shí)參單元中。,實(shí)參：,地址,形參：,B1,B2,B1,計(jì)算機(jī)學(xué)院 辛明影,48,在主調(diào)程序中設(shè)置計(jì)算實(shí)參地址和右值的形實(shí)替換子程序THUNK,子程序中為相應(yīng)實(shí)參開辟一個(gè)形式單元，用于存放該實(shí)參的THUNK子程序的入口地址。,執(zhí)行時(shí)，每當(dāng)要對形參進(jìn)行訪問時(shí)，就調(diào)用THUNK子程序，以獲得相應(yīng)實(shí)參地址或值,4 傳名調(diào)用,對形參的訪問是發(fā)生在實(shí)參單元上的,計(jì)算機(jī)學(xué)院 辛明影,49,例：有程序段： procedure p(x,y,z) begin y=y+1; z=z+x; end,Begin a=2; b=3; c=4; P(a,b,c); print a,b,c; end,計(jì)算機(jī)學(xué)院 辛明