第八章順序控制_第1頁(yè)
第八章順序控制_第2頁(yè)
第八章順序控制_第3頁(yè)
第八章順序控制_第4頁(yè)
已閱讀5頁(yè),還剩58頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、第八章第八章 順序控制順序控制2n順序控制提供了操作和數(shù)據(jù)被組合成程順序控制提供了操作和數(shù)據(jù)被組合成程序和程序集合的框架。序和程序集合的框架。n涉及兩個(gè)方面的問(wèn)題:涉及兩個(gè)方面的問(wèn)題:n操作執(zhí)行順序的控制(順序控制)操作執(zhí)行順序的控制(順序控制)n數(shù)據(jù)在子程序間的傳遞(數(shù)據(jù)控制)數(shù)據(jù)在子程序間的傳遞(數(shù)據(jù)控制)3執(zhí)行順序控制執(zhí)行順序控制n控制的層次和形式控制的層次和形式n語(yǔ)句內(nèi)(即表達(dá)式)的順序控制語(yǔ)句內(nèi)(即表達(dá)式)的順序控制n算術(shù)表達(dá)的順序控制算術(shù)表達(dá)的順序控制n非算術(shù)表達(dá)式的順序控制非算術(shù)表達(dá)式的順序控制n語(yǔ)句間的順序控制語(yǔ)句間的順序控制48.1 隱式和顯式順序控制隱式和顯式順序控制n順序

2、控制結(jié)構(gòu)可分為四組:順序控制結(jié)構(gòu)可分為四組:1、用于表達(dá)式中的結(jié)構(gòu)(也針對(duì)語(yǔ)句,表達(dá)式是語(yǔ)句的基本建、用于表達(dá)式中的結(jié)構(gòu)(也針對(duì)語(yǔ)句,表達(dá)式是語(yǔ)句的基本建筑塊)。如:優(yōu)先級(jí)規(guī)則和括號(hào)。筑塊)。如:優(yōu)先級(jí)規(guī)則和括號(hào)。2、用于語(yǔ)句或語(yǔ)句組間的結(jié)構(gòu)。如:條件和迭代。、用于語(yǔ)句或語(yǔ)句組間的結(jié)構(gòu)。如:條件和迭代。3、用于申明式程序設(shè)計(jì)語(yǔ)言的程序結(jié)構(gòu)。如邏輯程序設(shè)計(jì)語(yǔ)言、用于申明式程序設(shè)計(jì)語(yǔ)言的程序結(jié)構(gòu)。如邏輯程序設(shè)計(jì)語(yǔ)言4、用于子程序間的結(jié)構(gòu),如:子程序調(diào)用和協(xié)同例程。、用于子程序間的結(jié)構(gòu),如:子程序調(diào)用和協(xié)同例程。n這種分法并不是精確的,如這種分法并不是精確的,如LISP和和APL中只有表達(dá)式中只有表

3、達(dá)式而無(wú)語(yǔ)句。而無(wú)語(yǔ)句。n順序控制結(jié)構(gòu)可以是隱含的(缺省的)(由語(yǔ)言定義,順序控制結(jié)構(gòu)可以是隱含的(缺省的)(由語(yǔ)言定義,除非程序員顯式修改)或顯式的(程序員可用來(lái)修改除非程序員顯式修改)或顯式的(程序員可用來(lái)修改隱含順序)。隱含順序)。 5ACABBroot2428.2 算術(shù)表達(dá)的順序控制算術(shù)表達(dá)的順序控制n考慮方程求根:考慮方程求根:n該公式至少涉及該公式至少涉及15個(gè)分開(kāi)的操作,用匯編或機(jī)器語(yǔ)個(gè)分開(kāi)的操作,用匯編或機(jī)器語(yǔ)言至少需要言至少需要15條指令甚至更多。而寫(xiě)成條指令甚至更多。而寫(xiě)成Fortran程程序則為:序則為:nROOT=(-B+SQRT(B*2-4*A*C)/(2*A)n這是

4、自然的表達(dá)方法,由翻譯器而不是程序員來(lái)考這是自然的表達(dá)方法,由翻譯器而不是程序員來(lái)考慮各種優(yōu)化問(wèn)題。慮各種優(yōu)化問(wèn)題。n然而,翻譯器如何控制正確的操作順序?然而,翻譯器如何控制正確的操作順序? 6算術(shù)表達(dá)的順序控制算術(shù)表達(dá)的順序控制n算術(shù)表達(dá)式的表示算術(shù)表達(dá)式的表示n語(yǔ)法:語(yǔ)法:直觀表示直觀表示和和形式化表示形式化表示n語(yǔ)義語(yǔ)義:決定計(jì)值方式和過(guò)程:決定計(jì)值方式和過(guò)程n運(yùn)算符的優(yōu)先級(jí)運(yùn)算符的優(yōu)先級(jí)n算術(shù)表達(dá)式算術(shù)表達(dá)式在執(zhí)行時(shí)的表示在執(zhí)行時(shí)的表示7樹(shù)結(jié)構(gòu)表示樹(shù)結(jié)構(gòu)表示n目前,我們將表達(dá)式考慮為單個(gè)實(shí)體,目前,我們將表達(dá)式考慮為單個(gè)實(shí)體,忽略了其計(jì)值必需的實(shí)際語(yǔ)法和語(yǔ)義。忽略了其計(jì)值必需的實(shí)際語(yǔ)法

5、和語(yǔ)義。n表達(dá)式中的基本順序控制機(jī)制是表達(dá)式中的基本順序控制機(jī)制是“函數(shù)函數(shù)復(fù)合復(fù)合”:刻劃操作及其操作數(shù)。:刻劃操作及其操作數(shù)。n函數(shù)復(fù)合使表達(dá)式呈樹(shù)結(jié)構(gòu)特征,根為函數(shù)復(fù)合使表達(dá)式呈樹(shù)結(jié)構(gòu)特征,根為主操作,中間節(jié)點(diǎn)為中間層次操作,葉主操作,中間節(jié)點(diǎn)為中間層次操作,葉為操作數(shù)。為操作數(shù)。8樹(shù)結(jié)構(gòu)表示樹(shù)結(jié)構(gòu)表示n求方程根的表達(dá)式的樹(shù)。求方程根的表達(dá)式的樹(shù)。n樹(shù)表示闡明了表達(dá)式的控制結(jié)構(gòu),樹(shù)表示闡明了表達(dá)式的控制結(jié)構(gòu),低層的數(shù)據(jù)引用和操作作為高層低層的數(shù)據(jù)引用和操作作為高層操作的操作數(shù),必須先計(jì)值,但操作的操作數(shù),必須先計(jì)值,但樹(shù)表示也留下一些計(jì)值順序沒(méi)有樹(shù)表示也留下一些計(jì)值順序沒(méi)有指定。指定。n

6、如:如:B和和B*2誰(shuí)先計(jì)值?誰(shuí)先計(jì)值?B是否是否可組合為同一引用?可組合為同一引用?n通常語(yǔ)言定義只在樹(shù)表示級(jí)定義通常語(yǔ)言定義只在樹(shù)表示級(jí)定義表達(dá)式計(jì)值順序,允許實(shí)現(xiàn)者決表達(dá)式計(jì)值順序,允許實(shí)現(xiàn)者決定計(jì)值細(xì)節(jié)。定計(jì)值細(xì)節(jié)。返回9表達(dá)式的語(yǔ)法表達(dá)式的語(yǔ)法n表達(dá)式表達(dá)式(a+b)(ca)的樹(shù)結(jié)構(gòu)的樹(shù)結(jié)構(gòu)10表達(dá)式的語(yǔ)法表達(dá)式的語(yǔ)法n表達(dá)式可表示為樹(shù)結(jié)構(gòu),但為了在程序中表示,表達(dá)式可表示為樹(shù)結(jié)構(gòu),但為了在程序中表示,線(xiàn)性化是需要的。線(xiàn)性化是需要的。n前綴(波蘭前綴)記法。前綴(波蘭前綴)記法。n這是波蘭數(shù)學(xué)家發(fā)明的無(wú)括號(hào)記號(hào)法。如:這是波蘭數(shù)學(xué)家發(fā)明的無(wú)括號(hào)記號(hào)法。如:f(x,y,z),+ab-c

7、anLISP使用了該記號(hào)法的變種,稱(chēng)為劍橋波蘭,用括號(hào)將使用了該記號(hào)法的變種,稱(chēng)為劍橋波蘭,用括號(hào)將操作符及其操作數(shù)括起來(lái),如:操作符及其操作數(shù)括起來(lái),如:(X(+ab)(-ca)。n后綴(逆波蘭)記號(hào)法后綴(逆波蘭)記號(hào)法n類(lèi)似于前綴,但操作符數(shù)在后面,如:類(lèi)似于前綴,但操作符數(shù)在后面,如:ab+ca-n中綴記號(hào)法中綴記號(hào)法n最適合二元操作,也是我們最常用的方式。最適合二元操作,也是我們最常用的方式。返回11表達(dá)式的語(yǔ)義表達(dá)式的語(yǔ)義 (1/3)n上三種記號(hào)法對(duì)語(yǔ)言的設(shè)計(jì)都有一些有用的屬上三種記號(hào)法對(duì)語(yǔ)言的設(shè)計(jì)都有一些有用的屬性,在如何計(jì)算表達(dá)式值方面也有不同。性,在如何計(jì)算表達(dá)式值方面也有不

8、同。n前綴計(jì)值前綴計(jì)值n可以通過(guò)一遍掃描計(jì)值每個(gè)表達(dá)式,然而需要知道可以通過(guò)一遍掃描計(jì)值每個(gè)表達(dá)式,然而需要知道每個(gè)操作的操作數(shù)量。除了可省去括號(hào)外,前綴表每個(gè)操作的操作數(shù)量。除了可省去括號(hào)外,前綴表達(dá)式在語(yǔ)言設(shè)計(jì)中有如下價(jià)值:達(dá)式在語(yǔ)言設(shè)計(jì)中有如下價(jià)值:1、一般的函數(shù)調(diào)用均采用前綴方式。、一般的函數(shù)調(diào)用均采用前綴方式。2、可表示有任意數(shù)量操作數(shù)的操作,寫(xiě)表達(dá)式只需一個(gè)語(yǔ)、可表示有任意數(shù)量操作數(shù)的操作,寫(xiě)表達(dá)式只需一個(gè)語(yǔ)法規(guī)則。法規(guī)則。3、解碼可以機(jī)械地很容易地進(jìn)行,將其翻譯成簡(jiǎn)單代碼序、解碼可以機(jī)械地很容易地進(jìn)行,將其翻譯成簡(jiǎn)單代碼序是容易的。是容易的。12表達(dá)式的語(yǔ)義表達(dá)式的語(yǔ)義 (1/3

9、)n前綴計(jì)值前綴計(jì)值n下面算法用一個(gè)執(zhí)行棧計(jì)值表達(dá)式:對(duì)表達(dá)下面算法用一個(gè)執(zhí)行棧計(jì)值表達(dá)式:對(duì)表達(dá)式式P,1、如、如P中下一項(xiàng)是操作子,壓入棧項(xiàng),設(shè)置所需中下一項(xiàng)是操作子,壓入棧項(xiàng),設(shè)置所需參數(shù)數(shù)目。參數(shù)數(shù)目。2、如、如P中下一項(xiàng)是操作數(shù),壓入棧項(xiàng)。中下一項(xiàng)是操作數(shù),壓入棧項(xiàng)。3、如棧項(xiàng)、如棧項(xiàng)n項(xiàng)是操作數(shù)(對(duì)棧中第一個(gè)項(xiàng)是操作數(shù)(對(duì)棧中第一個(gè)n元操元操作),則可以進(jìn)行計(jì)值,用計(jì)值結(jié)果替代該操作作),則可以進(jìn)行計(jì)值,用計(jì)值結(jié)果替代該操作符和操作數(shù)。符和操作數(shù)。13表達(dá)式的語(yǔ)義表達(dá)式的語(yǔ)義 (2/3)n后綴計(jì)值后綴計(jì)值n后綴計(jì)值時(shí),操作符緊跟其操作數(shù)后而且操后綴計(jì)值時(shí),操作符緊跟其操作數(shù)后而且操

10、作數(shù)已被計(jì)值。作數(shù)已被計(jì)值。n1、如、如P中下一項(xiàng)是操作數(shù),壓入棧頂中下一項(xiàng)是操作數(shù),壓入棧頂n2、如、如P中下一項(xiàng)是中下一項(xiàng)是n元操作符,元操作符,n個(gè)參數(shù)必須是個(gè)參數(shù)必須是棧頂部的棧頂部的n個(gè)元素,計(jì)算結(jié)果并替換這個(gè)元素,計(jì)算結(jié)果并替換這n個(gè)元素。個(gè)元素。n這種計(jì)值策略直接、簡(jiǎn)單,是很多翻譯器中生成這種計(jì)值策略直接、簡(jiǎn)單,是很多翻譯器中生成表達(dá)式代碼的基礎(chǔ)。表達(dá)式代碼的基礎(chǔ)。14表達(dá)式的語(yǔ)義表達(dá)式的語(yǔ)義 (3/3)n中綴計(jì)值中綴計(jì)值n中綴是常見(jiàn)的,但用于程序語(yǔ)言中會(huì)導(dǎo)致一中綴是常見(jiàn)的,但用于程序語(yǔ)言中會(huì)導(dǎo)致一些問(wèn)題:些問(wèn)題:n1、只適合于二元操作。語(yǔ)言單用中綴是不夠的,、只適合于二元操作。

11、語(yǔ)言單用中綴是不夠的,還需使用前綴,這二者的混合使翻譯更為復(fù)雜。還需使用前綴,這二者的混合使翻譯更為復(fù)雜。n2、表達(dá)式中涉及多個(gè)中綴操作時(shí),如不使用括、表達(dá)式中涉及多個(gè)中綴操作時(shí),如不使用括號(hào),則存在固有二義性。為解決這個(gè)問(wèn)題,通常號(hào),則存在固有二義性。為解決這個(gè)問(wèn)題,通常引入隱含的規(guī)則。引入隱含的規(guī)則。返回15操作子計(jì)值順序操作子計(jì)值順序16操作的層次操作的層次n即操作的優(yōu)先規(guī)則即操作的優(yōu)先規(guī)則返回返回n同一層次操作的計(jì)算順序的隱含規(guī)則同一層次操作的計(jì)算順序的隱含規(guī)則n優(yōu)先級(jí)對(duì)算術(shù)表達(dá)式是適用的,因?yàn)楸韮?yōu)先級(jí)對(duì)算術(shù)表達(dá)式是適用的,因?yàn)楸磉_(dá)式語(yǔ)義的數(shù)學(xué)模型已對(duì)大多數(shù)程序員達(dá)式語(yǔ)義的數(shù)學(xué)模型已對(duì)

12、大多數(shù)程序員熟知的。熟知的。結(jié)合律結(jié)合律17結(jié)合律結(jié)合律n然而,當(dāng)語(yǔ)言引入新的,不是源自傳統(tǒng)數(shù)學(xué)的操作符然而,當(dāng)語(yǔ)言引入新的,不是源自傳統(tǒng)數(shù)學(xué)的操作符時(shí),優(yōu)先規(guī)則可能不再有用,因此,需要有不同方法時(shí),優(yōu)先規(guī)則可能不再有用,因此,需要有不同方法來(lái)處理擴(kuò)展的操作集。來(lái)處理擴(kuò)展的操作集。nC語(yǔ)言:使用擴(kuò)展的優(yōu)先規(guī)則集合,大多數(shù)使用從左到右的結(jié)語(yǔ)言:使用擴(kuò)展的優(yōu)先規(guī)則集合,大多數(shù)使用從左到右的結(jié)合律。大多數(shù)合律。大多數(shù)C規(guī)則是合理的。規(guī)則是合理的。nAPL:操作數(shù)為數(shù)組和矢量,語(yǔ)言沒(méi)有優(yōu)先規(guī)則。所有表達(dá):操作數(shù)為數(shù)組和矢量,語(yǔ)言沒(méi)有優(yōu)先規(guī)則。所有表達(dá)式計(jì)值從右到左。這規(guī)則對(duì)大多數(shù)表達(dá)式也是合理的,除了

13、式計(jì)值從右到左。這規(guī)則對(duì)大多數(shù)表達(dá)式也是合理的,除了一些典型的表達(dá)式,如一些典型的表達(dá)式,如a-b-c-意為意為a-(b-c)。nSmalltalk:模型類(lèi)似:模型類(lèi)似APL,沒(méi)有優(yōu)先規(guī)則,表達(dá)式計(jì)值從左,沒(méi)有優(yōu)先規(guī)則,表達(dá)式計(jì)值從左到右。到右。nForth:用于實(shí)時(shí)過(guò)程控制。其運(yùn)行時(shí)結(jié)構(gòu)為棧,語(yǔ)言是純后:用于實(shí)時(shí)過(guò)程控制。其運(yùn)行時(shí)結(jié)構(gòu)為棧,語(yǔ)言是純后綴的,沒(méi)有優(yōu)先規(guī)則。綴的,沒(méi)有優(yōu)先規(guī)則。返回返回18執(zhí)行時(shí)表示執(zhí)行時(shí)表示n對(duì)中綴形式的表達(dá)式的解碼是困難的,需要翻對(duì)中綴形式的表達(dá)式的解碼是困難的,需要翻譯為易于解碼的可執(zhí)行形式。通常的選擇有:譯為易于解碼的可執(zhí)行形式。通常的選擇有:1、機(jī)器代碼

14、序列、機(jī)器代碼序列n表達(dá)式被直接翻譯成實(shí)際的機(jī)器代碼,而不是先翻譯為中表達(dá)式被直接翻譯成實(shí)際的機(jī)器代碼,而不是先翻譯為中間形式。指令順序反映了初始表達(dá)式的順序控制結(jié)構(gòu)。間形式。指令順序反映了初始表達(dá)式的順序控制結(jié)構(gòu)。n機(jī)器代碼序列必須使用顯式的臨時(shí)存儲(chǔ)位置來(lái)保持中間結(jié)機(jī)器代碼序列必須使用顯式的臨時(shí)存儲(chǔ)位置來(lái)保持中間結(jié)果,允許使用硬件解釋器,因此,執(zhí)行速度快。果,允許使用硬件解釋器,因此,執(zhí)行速度快。2、樹(shù)結(jié)構(gòu)、樹(shù)結(jié)構(gòu)n表達(dá)式可以表達(dá)式可以以其自然的樹(shù)結(jié)構(gòu)直接執(zhí)行以其自然的樹(shù)結(jié)構(gòu)直接執(zhí)行(使用軟件解釋?zhuān)ㄊ褂密浖忉屍鳎?zhí)行通過(guò)簡(jiǎn)單的樹(shù)遍歷來(lái)完成。器)。執(zhí)行通過(guò)簡(jiǎn)單的樹(shù)遍歷來(lái)完成。n這是這是LI

15、SP中使用的典型技術(shù),整個(gè)程序被表示為樹(shù)結(jié)構(gòu)。中使用的典型技術(shù),整個(gè)程序被表示為樹(shù)結(jié)構(gòu)。19執(zhí)行時(shí)表示執(zhí)行時(shí)表示3、前綴或后綴形式、前綴或后綴形式n這兩種形式可用前面給出的解釋算法來(lái)執(zhí)行。這兩種形式可用前面給出的解釋算法來(lái)執(zhí)行。n在某些基于堆棧組織的實(shí)際計(jì)算機(jī)中,實(shí)際的機(jī)在某些基于堆棧組織的實(shí)際計(jì)算機(jī)中,實(shí)際的機(jī)器代碼表示為后綴形式。器代碼表示為后綴形式。n前綴表示是前綴表示是SNOBOL4程序的執(zhí)行形式,執(zhí)行從程序的執(zhí)行形式,執(zhí)行從左到右進(jìn)行。左到右進(jìn)行。n每個(gè)操作遞歸地調(diào)用解釋器來(lái)計(jì)值其操作數(shù)。每個(gè)操作遞歸地調(diào)用解釋器來(lái)計(jì)值其操作數(shù)。20表達(dá)式的樹(shù)表示的計(jì)值表達(dá)式的樹(shù)表示的計(jì)值n表達(dá)式翻成

16、樹(shù)結(jié)構(gòu)雖有困難,但總體上是直接表達(dá)式翻成樹(shù)結(jié)構(gòu)雖有困難,但總體上是直接的。的。n而樹(shù)到可執(zhí)行原語(yǔ)序列的翻譯,則涉及計(jì)值順而樹(shù)到可執(zhí)行原語(yǔ)序列的翻譯,則涉及計(jì)值順序的一些微妙問(wèn)題。在代碼生成中出現(xiàn)的計(jì)值序的一些微妙問(wèn)題。在代碼生成中出現(xiàn)的計(jì)值順序問(wèn)題有:順序問(wèn)題有:n問(wèn)題一:統(tǒng)一的計(jì)值規(guī)則問(wèn)題一:統(tǒng)一的計(jì)值規(guī)則n問(wèn)題二:副作用,問(wèn)題二:副作用,Side effect。n問(wèn)題三:出錯(cuò)條件問(wèn)題三:出錯(cuò)條件n問(wèn)題四:短路布爾表達(dá)式問(wèn)題四:短路布爾表達(dá)式21表達(dá)式的計(jì)值表達(dá)式的計(jì)值(1):統(tǒng)一的計(jì)值規(guī)則:統(tǒng)一的計(jì)值規(guī)則n對(duì)表達(dá)式樹(shù)中的每個(gè)操作結(jié)點(diǎn),首先計(jì)值其操作數(shù)對(duì)表達(dá)式樹(shù)中的每個(gè)操作結(jié)點(diǎn),首先計(jì)值其操

17、作數(shù)(或生成相應(yīng)代碼),然而應(yīng)用操作到計(jì)算出的操作(或生成相應(yīng)代碼),然而應(yīng)用操作到計(jì)算出的操作數(shù)上(或生成相應(yīng)代碼)數(shù)上(或生成相應(yīng)代碼)積極計(jì)值規(guī)則(積極計(jì)值規(guī)則(eager)。)。n對(duì)有些表達(dá)式來(lái)說(shuō),計(jì)值發(fā)生的順序并不重要,可以對(duì)有些表達(dá)式來(lái)說(shuō),計(jì)值發(fā)生的順序并不重要,可以選擇以?xún)?yōu)化存儲(chǔ)和其他機(jī)器特性。選擇以?xún)?yōu)化存儲(chǔ)和其他機(jī)器特性。n例,對(duì)例,對(duì)(a+b)(c-a),下列順序均可接受。,下列順序均可接受。順序一:取順序一:取a的右值的右值順序二:取順序二:取c的右值的右值 取取b的右值的右值 取取b的右值的右值 a+bd 取取a的右值的右值 取取c右值右值 c-ae c-ae a+bd

18、def表達(dá)式的右值表達(dá)式的右值 def22ZY0XXYIF/表達(dá)式的計(jì)值表達(dá)式的計(jì)值(1):統(tǒng)一的計(jì)值規(guī)則:統(tǒng)一的計(jì)值規(guī)則n但是,并不是在任何情況下都可以使用這種統(tǒng)但是,并不是在任何情況下都可以使用這種統(tǒng)一的計(jì)值規(guī)則。一的計(jì)值規(guī)則。n例如,包含條件的表達(dá)式:例如,包含條件的表達(dá)式:nZ+(Y=0?X:X/Y),當(dāng),當(dāng)Y0時(shí),計(jì)算時(shí),計(jì)算X/Y23表達(dá)式的計(jì)值表達(dá)式的計(jì)值(1):統(tǒng)一的計(jì)值規(guī)則:統(tǒng)一的計(jì)值規(guī)則n采用統(tǒng)一規(guī)則,對(duì)采用統(tǒng)一規(guī)則,對(duì)IF操作,需先計(jì)算操作數(shù),即使操作,需先計(jì)算操作數(shù),即使Y=0。n顯然,此時(shí)我們不希望所有操作數(shù)被計(jì)值。顯然,此時(shí)我們不希望所有操作數(shù)被計(jì)值。n從而,我們有

19、另一個(gè)規(guī)則:永不在應(yīng)用操作之前計(jì)值從而,我們有另一個(gè)規(guī)則:永不在應(yīng)用操作之前計(jì)值操作數(shù)。操作數(shù)。n即,總是不計(jì)值地傳遞操作數(shù),由作用操作決定什么時(shí)候計(jì)即,總是不計(jì)值地傳遞操作數(shù),由作用操作決定什么時(shí)候計(jì)值操作數(shù)值操作數(shù)Lazy計(jì)值。計(jì)值。n然而,對(duì)此規(guī)則,在很多情況下是不實(shí)際的。比如:如何仿然而,對(duì)此規(guī)則,在很多情況下是不實(shí)際的。比如:如何仿真未計(jì)值操作數(shù)到操作的傳遞?這需要軟件仿真。真未計(jì)值操作數(shù)到操作的傳遞?這需要軟件仿真。n這兩種計(jì)值規(guī)則:積極和隋性(這兩種計(jì)值規(guī)則:積極和隋性(lazy),對(duì)應(yīng)子程序),對(duì)應(yīng)子程序參數(shù)傳遞的按值和按名。參數(shù)傳遞的按值和按名。n對(duì)表達(dá)式而言,沒(méi)有簡(jiǎn)單的統(tǒng)一

20、規(guī)則是完全令人滿(mǎn)意的,通對(duì)表達(dá)式而言,沒(méi)有簡(jiǎn)單的統(tǒng)一規(guī)則是完全令人滿(mǎn)意的,通常規(guī)則是混合的。常規(guī)則是混合的。24表達(dá)式的計(jì)值表達(dá)式的計(jì)值(2):副作用:副作用n表達(dá)式中使用有副作用的操作,一直是語(yǔ)言設(shè)計(jì)中的表達(dá)式中使用有副作用的操作,一直是語(yǔ)言設(shè)計(jì)中的爭(zhēng)論點(diǎn)。爭(zhēng)論點(diǎn)。n考慮:考慮:afun(x)+an對(duì)乘法:需先取對(duì)乘法:需先取a的右值并計(jì)值的右值并計(jì)值fun(x)n對(duì)加法:需取對(duì)加法:需取a的右值,并計(jì)算乘法。的右值,并計(jì)算乘法。n顯然,我們希望只取顯然,我們希望只取a一次并應(yīng)用到兩個(gè)地方,而且一次并應(yīng)用到兩個(gè)地方,而且fun(x)的的計(jì)值在取計(jì)值在取a的前或后并無(wú)區(qū)別。的前或后并無(wú)區(qū)別。n

21、但如但如fun有副作用,改變了有副作用,改變了a的值,則計(jì)值序成為關(guān)鍵。的值,則計(jì)值序成為關(guān)鍵。n如如a值本為值本為1,但,但fun執(zhí)行后值為執(zhí)行后值為3,并改,并改a為為2。則表達(dá)式可能值。則表達(dá)式可能值為:為:1、順序計(jì)值:、順序計(jì)值:13+2=52、取、取a一次:一次:13+1=43、在取、在取a前調(diào)用前調(diào)用fun:23+2=8n執(zhí)行序不同導(dǎo)致不同結(jié)果。執(zhí)行序不同導(dǎo)致不同結(jié)果。25表達(dá)式的計(jì)值表達(dá)式的計(jì)值(2):副作用:副作用n對(duì)表達(dá)式中副作用的使用有兩種選擇:對(duì)表達(dá)式中副作用的使用有兩種選擇:1、不允許副作用、不允許副作用n不允許有副作用的函數(shù)或?qū)Ω弊饔每赡苡绊懙谋聿辉试S有副作用的函數(shù)

22、或?qū)Ω弊饔每赡苡绊懙谋磉_(dá)式的值改為未定義。達(dá)式的值改為未定義。2、允許副作用、允許副作用n但語(yǔ)言定義應(yīng)精確地給出計(jì)值順序,這將使很多但語(yǔ)言定義應(yīng)精確地給出計(jì)值順序,這將使很多優(yōu)化不可能。優(yōu)化不可能。n通常,語(yǔ)句允許有副作用,如:賦值必通常,語(yǔ)句允許有副作用,如:賦值必須產(chǎn)生副作用。須產(chǎn)生副作用。26表達(dá)式的計(jì)值表達(dá)式的計(jì)值(3):出錯(cuò)條件:出錯(cuò)條件n對(duì)可能失敗和產(chǎn)生出錯(cuò)條件的操作,涉及一種對(duì)可能失敗和產(chǎn)生出錯(cuò)條件的操作,涉及一種特殊的副作用。一般的副作用只涉及到程序員特殊的副作用。一般的副作用只涉及到程序員定義的函數(shù),而出錯(cuò)條件可能在很多原操作中定義的函數(shù),而出錯(cuò)條件可能在很多原操作中出現(xiàn)(溢

23、出、被零除等)。出現(xiàn)(溢出、被零除等)。n這類(lèi)副作用是不希望被排除的,而出錯(cuò)條件的這類(lèi)副作用是不希望被排除的,而出錯(cuò)條件的意義在于其出現(xiàn)甚至?xí)艿奖磉_(dá)式的計(jì)值順序意義在于其出現(xiàn)甚至?xí)艿奖磉_(dá)式的計(jì)值順序的影響。這樣,程序員需要精確的計(jì)值順序控的影響。這樣,程序員需要精確的計(jì)值順序控制。制。27表達(dá)式的計(jì)值表達(dá)式的計(jì)值(4):短路布爾表達(dá)式:短路布爾表達(dá)式n考慮例子:考慮例子:nif (A=0)|(B/AC)nWhile(IC)n兩個(gè)例子中,第二個(gè)條件可能產(chǎn)生出錯(cuò)條件。第一兩個(gè)例子中,第二個(gè)條件可能產(chǎn)生出錯(cuò)條件。第一個(gè)操作數(shù)用于防止錯(cuò)誤產(chǎn)生。個(gè)操作數(shù)用于防止錯(cuò)誤產(chǎn)生。n在很多語(yǔ)言中,求布爾操作需

24、先計(jì)值操作數(shù),在很多語(yǔ)言中,求布爾操作需先計(jì)值操作數(shù),這將產(chǎn)生不期望的錯(cuò)誤,因?yàn)槿藗兤谕蟛僮鬟@將產(chǎn)生不期望的錯(cuò)誤,因?yàn)槿藗兤谕蟛僮鲾?shù)短路右操作數(shù)。數(shù)短路右操作數(shù)。nAda中提供了兩個(gè)特殊的布爾操作來(lái)解決這個(gè)問(wèn)題。中提供了兩個(gè)特殊的布爾操作來(lái)解決這個(gè)問(wèn)題。nand then 和和 or else。顯式地提供短路機(jī)制。顯式地提供短路機(jī)制。n例:例:if (A=0) or else (B/AC) thenn這將不會(huì)失敗,因這將不會(huì)失敗,因A=0將導(dǎo)致整個(gè)表達(dá)式計(jì)值結(jié)束。將導(dǎo)致整個(gè)表達(dá)式計(jì)值結(jié)束。返回288.3 語(yǔ)句間的順序控制語(yǔ)句間的順序控制n基本語(yǔ)句基本語(yǔ)句n語(yǔ)句級(jí)順序控制的語(yǔ)句級(jí)順序控制的形

25、式形式n語(yǔ)句級(jí)順序控制的語(yǔ)句級(jí)順序控制的語(yǔ)句語(yǔ)句n結(jié)構(gòu)化順序控制結(jié)構(gòu)化順序控制n結(jié)構(gòu)的程序設(shè)計(jì)簡(jiǎn)介結(jié)構(gòu)的程序設(shè)計(jì)簡(jiǎn)介n結(jié)構(gòu)順序控制語(yǔ)句結(jié)構(gòu)順序控制語(yǔ)句n結(jié)構(gòu)順序控制中的問(wèn)題結(jié)構(gòu)順序控制中的問(wèn)題n順序控制的結(jié)構(gòu)化:順序控制的結(jié)構(gòu)化:素程序素程序29基本語(yǔ)句基本語(yǔ)句n任何程序的結(jié)果由其基本語(yǔ)句確定。這任何程序的結(jié)果由其基本語(yǔ)句確定。這里我們不再考慮語(yǔ)句中表達(dá)式,而是將里我們不再考慮語(yǔ)句中表達(dá)式,而是將語(yǔ)句作為考慮的單元來(lái)代表一單步計(jì)算。語(yǔ)句作為考慮的單元來(lái)代表一單步計(jì)算。n數(shù)據(jù)對(duì)象的賦值數(shù)據(jù)對(duì)象的賦值n通過(guò)向數(shù)據(jù)對(duì)象賦值而改變計(jì)算狀態(tài)是影響通過(guò)向數(shù)據(jù)對(duì)象賦值而改變計(jì)算狀態(tài)是影響計(jì)算狀態(tài)的主要機(jī)制。

26、計(jì)算狀態(tài)的主要機(jī)制。30基本語(yǔ)句基本語(yǔ)句n數(shù)據(jù)對(duì)象的賦值數(shù)據(jù)對(duì)象的賦值n賦值語(yǔ)句賦值語(yǔ)句n主要目的是將某表達(dá)式的右值賦給某數(shù)據(jù)對(duì)象的左值。主要目的是將某表達(dá)式的右值賦給某數(shù)據(jù)對(duì)象的左值。n賦值為每個(gè)基本數(shù)據(jù)類(lèi)型定義的中心操作。賦值為每個(gè)基本數(shù)據(jù)類(lèi)型定義的中心操作。n輸入語(yǔ)句輸入語(yǔ)句n大多數(shù)語(yǔ)言有一種語(yǔ)句形式,從終端用戶(hù)、文件或通大多數(shù)語(yǔ)言有一種語(yǔ)句形式,從終端用戶(hù)、文件或通訊線(xiàn)讀數(shù)據(jù)。這樣的語(yǔ)句也通過(guò)賦值改變變量的值。訊線(xiàn)讀數(shù)據(jù)。這樣的語(yǔ)句也通過(guò)賦值改變變量的值。n其他賦值操作其他賦值操作n參數(shù)傳遞:給形參賦值參數(shù)傳遞:給形參賦值n隱含賦值:如隱含賦值:如SNOBOL4中的引用,中的引用,Pr

27、olog目標(biāo)匹配,目標(biāo)匹配,聲明時(shí)初始值等。聲明時(shí)初始值等。返回31語(yǔ)句級(jí)順序控制的形式語(yǔ)句級(jí)順序控制的形式n三種主要的語(yǔ)句級(jí)順序控制:三種主要的語(yǔ)句級(jí)順序控制:n復(fù)合:語(yǔ)句順序放置,順序執(zhí)行。復(fù)合:語(yǔ)句順序放置,順序執(zhí)行。n選擇:兩個(gè)語(yǔ)句序列可形成選擇,使得一個(gè)選擇:兩個(gè)語(yǔ)句序列可形成選擇,使得一個(gè)或另一個(gè)序列被執(zhí)行,但不能同時(shí)執(zhí)行。或另一個(gè)序列被執(zhí)行,但不能同時(shí)執(zhí)行。n迭代:一個(gè)語(yǔ)句序列被重復(fù)執(zhí)行零次或多次。迭代:一個(gè)語(yǔ)句序列被重復(fù)執(zhí)行零次或多次。n這是三種常見(jiàn)結(jié)構(gòu),語(yǔ)句被組成這三種這是三種常見(jiàn)結(jié)構(gòu),語(yǔ)句被組成這三種結(jié)構(gòu)而形成程序。結(jié)構(gòu)而形成程序。返回32顯式順序控制顯式順序控制ngoto

28、語(yǔ)句,兩種形式語(yǔ)句,兩種形式n無(wú)條件無(wú)條件goto和條件和條件gotonGoto語(yǔ)句導(dǎo)致無(wú)結(jié)構(gòu)的設(shè)計(jì)。語(yǔ)言的很多形式模語(yǔ)句導(dǎo)致無(wú)結(jié)構(gòu)的設(shè)計(jì)。語(yǔ)言的很多形式模型均不允許型均不允許goto存在。存在。n此外,此外,goto也是多余的,沒(méi)有也是多余的,沒(méi)有g(shù)oto也可以寫(xiě)出同也可以寫(xiě)出同樣能力的程序。樣能力的程序。nBreak語(yǔ)句語(yǔ)句n通常使控制被前移到一個(gè)顯式點(diǎn)(在給定控制結(jié)構(gòu)通常使控制被前移到一個(gè)顯式點(diǎn)(在給定控制結(jié)構(gòu)的結(jié)束處)。的結(jié)束處)。n如如C中中Break語(yǔ)句使得立即退出語(yǔ)句使得立即退出while、for、switch語(yǔ)句。語(yǔ)句。nC中還有中還有Continue語(yǔ)句,只結(jié)束本次循環(huán)。語(yǔ)句

29、,只結(jié)束本次循環(huán)。33結(jié)構(gòu)化結(jié)構(gòu)化break語(yǔ)句語(yǔ)句返回34結(jié)構(gòu)的程序設(shè)計(jì)結(jié)構(gòu)的程序設(shè)計(jì)n70年代,年代,goto語(yǔ)句受到很大攻擊,以至語(yǔ)句受到很大攻擊,以至有的語(yǔ)言完全刪去了有的語(yǔ)言完全刪去了goto。goto 語(yǔ)句語(yǔ)句有一些優(yōu)點(diǎn):有一些優(yōu)點(diǎn):如果標(biāo)號(hào)只是局部語(yǔ)法標(biāo)記,則對(duì)高效執(zhí)如果標(biāo)號(hào)只是局部語(yǔ)法標(biāo)記,則對(duì)高效執(zhí)行有直接的硬件支持。行有直接的硬件支持。在小程序中使用簡(jiǎn)單、容易。在小程序中使用簡(jiǎn)單、容易。為匯編語(yǔ)言和老語(yǔ)言用戶(hù)熟悉。為匯編語(yǔ)言和老語(yǔ)言用戶(hù)熟悉??勺鳛橥ㄓ媒ㄖK來(lái)表示(仿真)其他控可作為通用建筑塊來(lái)表示(仿真)其他控制形式。制形式。35結(jié)構(gòu)的程序設(shè)計(jì)結(jié)構(gòu)的程序設(shè)計(jì)n它也有嚴(yán)重的

30、缺點(diǎn):它也有嚴(yán)重的缺點(diǎn):1、缺乏層次的程序結(jié)構(gòu)、缺乏層次的程序結(jié)構(gòu)n程序的正確性和開(kāi)發(fā)效率已遠(yuǎn)比效率更為重要,語(yǔ)言也應(yīng)程序的正確性和開(kāi)發(fā)效率已遠(yuǎn)比效率更為重要,語(yǔ)言也應(yīng)反映此需求。單進(jìn)單出的控制結(jié)構(gòu)概念,已成為更易理解反映此需求。單進(jìn)單出的控制結(jié)構(gòu)概念,已成為更易理解的設(shè)計(jì)。層次化提供了一種抽象,符合的設(shè)計(jì)。層次化提供了一種抽象,符合“分而治之分而治之”的思的思想。而想。而goto將打破這種層次性。將打破這種層次性。2、程序文本中語(yǔ)句順序不一定對(duì)應(yīng)執(zhí)行的順序。、程序文本中語(yǔ)句順序不一定對(duì)應(yīng)執(zhí)行的順序。n要理解程序,必須理解語(yǔ)句的執(zhí)行順序。要理解程序,必須理解語(yǔ)句的執(zhí)行順序。n靜態(tài)順序和動(dòng)態(tài)順序

31、有關(guān)聯(lián)將使程序更易于理解。靜態(tài)順序和動(dòng)態(tài)順序有關(guān)聯(lián)將使程序更易于理解。3、語(yǔ)句組可能有多個(gè)用途。、語(yǔ)句組可能有多個(gè)用途。n如果每個(gè)組只含單個(gè)用途。則程序更易理解。如果每個(gè)組只含單個(gè)用途。則程序更易理解。n人為地通過(guò)人為地通過(guò)goto使某組有多用途將打亂執(zhí)行順序,使程使某組有多用途將打亂執(zhí)行順序,使程序難于修改。序難于修改。36結(jié)構(gòu)的程序設(shè)計(jì)結(jié)構(gòu)的程序設(shè)計(jì)n結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào):結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào):、程序結(jié)構(gòu)的層次設(shè)計(jì),只用三種控制結(jié)、程序結(jié)構(gòu)的層次設(shè)計(jì),只用三種控制結(jié)構(gòu)。構(gòu)。、層次設(shè)計(jì)的表示應(yīng)直接體現(xiàn)在程序文本、層次設(shè)計(jì)的表示應(yīng)直接體現(xiàn)在程序文本中(只使用結(jié)構(gòu)化控制語(yǔ)句)。中(只使用結(jié)構(gòu)化控制語(yǔ)

32、句)。、語(yǔ)句的文本序列對(duì)應(yīng)執(zhí)行序列:、語(yǔ)句的文本序列對(duì)應(yīng)執(zhí)行序列:、使用單一用途的語(yǔ)句組。、使用單一用途的語(yǔ)句組。返回37結(jié)構(gòu)順序控制結(jié)構(gòu)順序控制n大多數(shù)語(yǔ)言提供了控制語(yǔ)句集合來(lái)表示三種基本的控大多數(shù)語(yǔ)言提供了控制語(yǔ)句集合來(lái)表示三種基本的控制形式,這些語(yǔ)句均應(yīng)該是單入單出的。它們所構(gòu)成制形式,這些語(yǔ)句均應(yīng)該是單入單出的。它們所構(gòu)成的程序,其執(zhí)行和語(yǔ)句序基本對(duì)應(yīng)。的程序,其執(zhí)行和語(yǔ)句序基本對(duì)應(yīng)。n復(fù)合語(yǔ)句復(fù)合語(yǔ)句n一個(gè)語(yǔ)句序列,可按單個(gè)語(yǔ)句處理來(lái)構(gòu)造更大的語(yǔ)句。一個(gè)語(yǔ)句序列,可按單個(gè)語(yǔ)句處理來(lái)構(gòu)造更大的語(yǔ)句。n用用beginend 和和 等來(lái)構(gòu)造等來(lái)構(gòu)造n其實(shí)現(xiàn)是將其存放在一個(gè)連續(xù)存儲(chǔ)區(qū)域中。其

33、實(shí)現(xiàn)是將其存放在一個(gè)連續(xù)存儲(chǔ)區(qū)域中。n條件語(yǔ)句條件語(yǔ)句n用來(lái)表示兩個(gè)或更多語(yǔ)句的選擇執(zhí)行,或單個(gè)語(yǔ)句的可選執(zhí)用來(lái)表示兩個(gè)或更多語(yǔ)句的選擇執(zhí)行,或單個(gè)語(yǔ)句的可選執(zhí)行。行。nif 語(yǔ)句語(yǔ)句n單分枝:?jiǎn)畏种Γ篿f 條件條件 then 語(yǔ)句語(yǔ)句語(yǔ)句的可選執(zhí)行語(yǔ)句的可選執(zhí)行n兩分枝:兩分枝:if 條件條件 thenelsen還可表示多分枝。還可表示多分枝。 38結(jié)構(gòu)順序控制結(jié)構(gòu)順序控制n條件語(yǔ)句條件語(yǔ)句ncase語(yǔ)句,重復(fù)測(cè)試某變量的值。語(yǔ)句,重復(fù)測(cè)試某變量的值。case Tag is When 0 When 1 endcasen實(shí)現(xiàn)實(shí)現(xiàn)nif語(yǔ)句常用硬件支持的分枝和跳轉(zhuǎn)指令實(shí)現(xiàn)。語(yǔ)句常用硬件支持的分枝

34、和跳轉(zhuǎn)指令實(shí)現(xiàn)。ncase語(yǔ)句常用跳轉(zhuǎn)表來(lái)避免同一變量值的重復(fù)測(cè)試。語(yǔ)句常用跳轉(zhuǎn)表來(lái)避免同一變量值的重復(fù)測(cè)試。n跳轉(zhuǎn)表是一個(gè)向量,順序存放在內(nèi)存中,其部件是無(wú)條件跳跳轉(zhuǎn)表是一個(gè)向量,順序存放在內(nèi)存中,其部件是無(wú)條件跳轉(zhuǎn)指令。轉(zhuǎn)指令。39case語(yǔ)語(yǔ)句句的的跳跳轉(zhuǎn)轉(zhuǎn)表表實(shí)實(shí)現(xiàn)現(xiàn)40結(jié)構(gòu)順序控制結(jié)構(gòu)順序控制n迭代語(yǔ)句迭代語(yǔ)句n提供重復(fù)計(jì)算的機(jī)制。通常分為頭和體兩部分。體提供語(yǔ)句提供重復(fù)計(jì)算的機(jī)制。通常分為頭和體兩部分。體提供語(yǔ)句的動(dòng)作。頭控制重復(fù)執(zhí)行體的次數(shù)。的動(dòng)作。頭控制重復(fù)執(zhí)行體的次數(shù)。n簡(jiǎn)單重復(fù)簡(jiǎn)單重復(fù)n直接給出執(zhí)行的次數(shù)。直接給出執(zhí)行的次數(shù)。n例:例:COBOL中,中,perform bo

35、dy k timesn當(dāng)條件成立時(shí)重復(fù)當(dāng)條件成立時(shí)重復(fù)nwhile test do bodyn計(jì)數(shù)器增量的重復(fù)計(jì)數(shù)器增量的重復(fù)nfor I:=1 step 2 until 30 do bodyn無(wú)限重復(fù)無(wú)限重復(fù)nLoopexit when condition沒(méi)有顯式的終止測(cè)試。沒(méi)有顯式的終止測(cè)試。endloopn循環(huán)的實(shí)現(xiàn)循環(huán)的實(shí)現(xiàn)n直接使用硬件提供的分支直接使用硬件提供的分支/跳轉(zhuǎn)指令。跳轉(zhuǎn)指令。返回41結(jié)構(gòu)順序控制中的問(wèn)題結(jié)構(gòu)順序控制中的問(wèn)題n多出口循環(huán)多出口循環(huán)n有些情況下,可能在幾種條件下都需要循環(huán)終止。有些情況下,可能在幾種條件下都需要循環(huán)終止。n如:搜索循環(huán)是一個(gè)例子:如:搜索循環(huán)

36、是一個(gè)例子:從從K元素矢量中搜索第一個(gè)滿(mǎn)足某條件的元素。元素矢量中搜索第一個(gè)滿(mǎn)足某條件的元素。For I:=1 to k do if VECT(I)=0 the goto for I in 1k loop exit when VECT (I)=0;endloop42結(jié)構(gòu)順序控制中的問(wèn)題結(jié)構(gòu)順序控制中的問(wèn)題ndo-while-don經(jīng)常最自然的測(cè)試是否退出循環(huán)的地方是在中間部經(jīng)常最自然的測(cè)試是否退出循環(huán)的地方是在中間部位,即已完成某些處理之后。稱(chēng)為位,即已完成某些處理之后。稱(chēng)為do while do,因?yàn)橹虚g點(diǎn)因?yàn)橹虚g點(diǎn)while是需要的是需要的do while doread (x)while

37、(not end-of-file)process (x)endn例外條件例外條件n例外可表示各種錯(cuò)誤條件。例外可表示各種錯(cuò)誤條件。nRaise BAD-CHAR-VALVEloopread(x)if end-of-file then goto process (x)end loop返回43n素程序的理論可用于描述一致的控制結(jié)構(gòu)理論。素程序的理論可用于描述一致的控制結(jié)構(gòu)理論。n1975年由年由Maddux提出,作為結(jié)構(gòu)化程序設(shè)計(jì)的推廣,提出,作為結(jié)構(gòu)化程序設(shè)計(jì)的推廣,以定義唯一的流程圖分解。以定義唯一的流程圖分解。n假定程序圖有三類(lèi)結(jié)點(diǎn):假定程序圖有三類(lèi)結(jié)點(diǎn):nn每個(gè)流程圖由這三類(lèi)結(jié)構(gòu)成。每個(gè)流

38、程圖由這三類(lèi)結(jié)構(gòu)成。功能結(jié)點(diǎn)決策結(jié)點(diǎn)匯合結(jié)點(diǎn)素程序(素程序(Prime Program)44合式程序(合式程序( proper program )n控制結(jié)構(gòu)的形式模式是如下的流程圖:控制結(jié)構(gòu)的形式模式是如下的流程圖:n1、有單個(gè)進(jìn)入線(xiàn)、有單個(gè)進(jìn)入線(xiàn)n2、有單個(gè)退出線(xiàn)、有單個(gè)退出線(xiàn)n3、有從入口到每個(gè)結(jié)點(diǎn)和從每個(gè)結(jié)點(diǎn)到出口的路徑。、有從入口到每個(gè)結(jié)點(diǎn)和從每個(gè)結(jié)點(diǎn)到出口的路徑。n我們的目標(biāo)是區(qū)分我們的目標(biāo)是區(qū)分“結(jié)構(gòu)的結(jié)構(gòu)的”“”“合式程序合式程序”和和“非結(jié)非結(jié)構(gòu)的構(gòu)的”合式程序。下圖均為合式程序,差別在于結(jié)構(gòu)合式程序。下圖均為合式程序,差別在于結(jié)構(gòu)性。性。45素程序素程序n是合式程序,但不能被

39、分為更小的合式程序,是合式程序,但不能被分為更小的合式程序,(功能結(jié)點(diǎn)的長(zhǎng)序列被視為基本的)。否則成(功能結(jié)點(diǎn)的長(zhǎng)序列被視為基本的)。否則成為復(fù)合程序。為復(fù)合程序。n所有素程序可以枚舉出來(lái)。注意:它們中大多所有素程序可以枚舉出來(lái)。注意:它們中大多數(shù)或是無(wú)效的,或是常見(jiàn)的控制結(jié)構(gòu)。數(shù)或是無(wú)效的,或是常見(jiàn)的控制結(jié)構(gòu)。n所用的控制結(jié)構(gòu)均是具有少量結(jié)點(diǎn)的素程序。所用的控制結(jié)構(gòu)均是具有少量結(jié)點(diǎn)的素程序。n通過(guò)枚舉,我們看出,通過(guò)枚舉,我們看出,do-while-do是自然的是自然的控制結(jié)構(gòu)。但很少有語(yǔ)言提供這種機(jī)制??刂平Y(jié)構(gòu)。但很少有語(yǔ)言提供這種機(jī)制。46素程序的枚舉素程序的枚舉n至多至多4節(jié)點(diǎn)的素程序

40、,其中節(jié)點(diǎn)的素程序,其中na、b、e、i是功能結(jié)點(diǎn)序列。是功能結(jié)點(diǎn)序列。nf是是if-then、 g是是 do while、h 是是 repeat-until、nj是是 if-then-else、k是是 do-while-donc、d、l和和q只含決策結(jié)點(diǎn)和只含決策結(jié)點(diǎn)和匯合結(jié)點(diǎn),沒(méi)有功能結(jié)點(diǎn),匯合結(jié)點(diǎn),沒(méi)有功能結(jié)點(diǎn),故不會(huì)改變抽象機(jī)的狀態(tài)空故不會(huì)改變抽象機(jī)的狀態(tài)空間,因此,等價(jià)于恒等函數(shù)。間,因此,等價(jià)于恒等函數(shù)。而其中而其中c、l總退出,而總退出,而d、q是循環(huán)(一旦循環(huán),將不會(huì)是循環(huán)(一旦循環(huán),將不會(huì)終止)。終止)。47結(jié)構(gòu)定理結(jié)構(gòu)定理nBohm & Jacobini任何素程序可

41、被轉(zhuǎn)換為任何素程序可被轉(zhuǎn)換為只使用只使用while和和if的素程序。的素程序。n該構(gòu)造過(guò)程的概述:該構(gòu)造過(guò)程的概述:1、給定任意流程圖,標(biāo)記每個(gè)結(jié)點(diǎn),出口標(biāo)記為、給定任意流程圖,標(biāo)記每個(gè)結(jié)點(diǎn),出口標(biāo)記為O2、定義、定義I為新的程序變量為新的程序變量3、對(duì)流程圖中每個(gè)結(jié)點(diǎn),應(yīng)用轉(zhuǎn)換規(guī)則。、對(duì)流程圖中每個(gè)結(jié)點(diǎn),應(yīng)用轉(zhuǎn)換規(guī)則。4、重建程序。、重建程序。n這里這里I類(lèi)似虛擬機(jī)指令計(jì)數(shù)器,指出下一條執(zhí)行語(yǔ)類(lèi)似虛擬機(jī)指令計(jì)數(shù)器,指出下一條執(zhí)行語(yǔ)句。句。n整個(gè)程序簡(jiǎn)單地是一系列嵌套的整個(gè)程序簡(jiǎn)單地是一系列嵌套的if語(yǔ)句(在單個(gè)語(yǔ)句(在單個(gè)while循環(huán)中),這樣,任何程序可用此法轉(zhuǎn)換為循環(huán)中),這樣,任何程

42、序可用此法轉(zhuǎn)換為“良構(gòu)良構(gòu)”程序。程序。48結(jié)結(jié)構(gòu)構(gòu)定定理理返回498.4 非算術(shù)表達(dá)式的順序控制非算術(shù)表達(dá)式的順序控制n控制方式:控制方式:n模式匹配模式匹配n合一合一n回溯回溯50n這是這是SNOBOL4、Prolog、ML等語(yǔ)言中的重要操作。操作的等語(yǔ)言中的重要操作。操作的成功是:匹配并賦一變量集到預(yù)定義的模板。如成功是:匹配并賦一變量集到預(yù)定義的模板。如BNF文法中文法中分析樹(shù)的識(shí)別。分析樹(shù)的識(shí)別。n例:例:A0A0|1A0|01n合法有效串合法有效串00100的識(shí)別過(guò)程為:的識(shí)別過(guò)程為:nA1匹配中間匹配中間1nA2匹配匹配 0 A1 0nA3匹配匹配 0 A2 0nSNOBOL4是

43、為直接仿真這個(gè)操作而設(shè)計(jì)的語(yǔ)言。其實(shí)現(xiàn)獨(dú)立是為直接仿真這個(gè)操作而設(shè)計(jì)的語(yǔ)言。其實(shí)現(xiàn)獨(dú)立于任何實(shí)際的機(jī)器體系結(jié)構(gòu),面向串處理虛擬機(jī)而設(shè)計(jì)。為于任何實(shí)際的機(jī)器體系結(jié)構(gòu),面向串處理虛擬機(jī)而設(shè)計(jì)。為了執(zhí)行了執(zhí)行SNOROL4,需將串處理機(jī)的操作實(shí)現(xiàn)為現(xiàn)有機(jī)器上,需將串處理機(jī)的操作實(shí)現(xiàn)為現(xiàn)有機(jī)器上的宏。的宏。n因此,因此,SNOBOL4是第一個(gè)幾乎可運(yùn)行于所有機(jī)器的語(yǔ)言。在是第一個(gè)幾乎可運(yùn)行于所有機(jī)器的語(yǔ)言。在其每個(gè)實(shí)現(xiàn)中有精確相同的語(yǔ)義。其每個(gè)實(shí)現(xiàn)中有精確相同的語(yǔ)義。nSNOBOL4使用串替代來(lái)實(shí)現(xiàn)匹配操作。使用串替代來(lái)實(shí)現(xiàn)匹配操作。模式匹配模式匹配51模式匹配模式匹配nProlog使用使用“關(guān)系作為

44、關(guān)系作為n元組集合元組集合”的概念作為匹的概念作為匹配機(jī)制。配機(jī)制。n通過(guò)刻劃這些關(guān)系的已知實(shí)例,其他實(shí)例可被導(dǎo)出。通過(guò)刻劃這些關(guān)系的已知實(shí)例,其他實(shí)例可被導(dǎo)出。n例:有事實(shí)例:有事實(shí)nParentof(John,Mary)nParentof(Susan,Mary)nParentof(Bill,John)nParentof(Ann,John)n要想知道要想知道Mary的父輩,我們寫(xiě)的父輩,我們寫(xiě)Parentof(X,Mary),推導(dǎo),推導(dǎo)結(jié)果結(jié)果X可以是可以是John或或Susan。n如需知道如需知道Mary的兩個(gè)父輩,式子為:的兩個(gè)父輩,式子為:nParentof(X,Mary), Pare

45、ntof(Y,Mary), not(X=Y)n也可自己建立關(guān)系:也可自己建立關(guān)系:nGrandparentof(X,Y) :- Parentof(X,Z), Parentof(Z,Y)52模式匹配:模式匹配:項(xiàng)重寫(xiě)項(xiàng)重寫(xiě)n模式匹配的一種限制形式。模式匹配的一種限制形式。n給定串給定串a(chǎn)1a2an和重寫(xiě)規(guī)則和重寫(xiě)規(guī)則 ,if =ai,則,則a1a2ai-1an是是a1a2an的項(xiàng)重寫(xiě)。的項(xiàng)重寫(xiě)。n例:對(duì)文法例:對(duì)文法nA0B|1nB0An產(chǎn)生產(chǎn)生001串的重寫(xiě)過(guò)程為:串的重寫(xiě)過(guò)程為:nA0B00A001nML將項(xiàng)重寫(xiě)表示為一種函數(shù)定義形式。將項(xiàng)重寫(xiě)表示為一種函數(shù)定義形式。n例:求階乘例:求階乘f

46、un fact (1)=1 | fact (N:int)=N*fact(N-1)返回53合一合一nProlog數(shù)據(jù)庫(kù)包含事實(shí)和規(guī)則。包含一個(gè)或多個(gè)變量數(shù)據(jù)庫(kù)包含事實(shí)和規(guī)則。包含一個(gè)或多個(gè)變量的表達(dá)式稱(chēng)為查詢(xún),用來(lái)表示一個(gè)未知關(guān)系。的表達(dá)式稱(chēng)為查詢(xún),用來(lái)表示一個(gè)未知關(guān)系。nProlog的主要特性是使用模式匹配來(lái)發(fā)現(xiàn)是否查詢(xún)可的主要特性是使用模式匹配來(lái)發(fā)現(xiàn)是否查詢(xún)可解。解。n合一是進(jìn)行模式匹配的方法,用于確定對(duì)查詢(xún)的合法合一是進(jìn)行模式匹配的方法,用于確定對(duì)查詢(xún)的合法一致的替代。一致的替代。n例:對(duì)查詢(xún)例:對(duì)查詢(xún)nParentof(X, Mary)=Parentof(John, Y)n顯然,解答為顯

47、然,解答為Parentof(John,Mary)n我們稱(chēng),該實(shí)例使用替代我們稱(chēng),該實(shí)例使用替代John/X, Mary/Y,合一了合一了Parentof(X, Mary)和和Parentof(John, Y)n合一可視為對(duì)替代的公共性質(zhì)的擴(kuò)展。合一可視為對(duì)替代的公共性質(zhì)的擴(kuò)展。54合一:替代與一般合一合一:替代與一般合一n替代替代n這是在編程中學(xué)到的第一條原則,涉及參數(shù)傳遞和這是在編程中學(xué)到的第一條原則,涉及參數(shù)傳遞和宏擴(kuò)展。在宏擴(kuò)展中,是用任意表達(dá)式替代一個(gè)變宏擴(kuò)展。在宏擴(kuò)展中,是用任意表達(dá)式替代一個(gè)變量。量。n一般合一:一般合一:n要合一兩個(gè)表達(dá)式要合一兩個(gè)表達(dá)式U和和V,需找到對(duì),需找到

48、對(duì)U、V中出現(xiàn)的中出現(xiàn)的變量的替代,該替代使兩個(gè)表達(dá)式相同。變量的替代,該替代使兩個(gè)表達(dá)式相同。n例,例,f(X,John), f(g(John),Z)n綁定綁定X到到g(John), Z到到John可完成合一。可完成合一。n結(jié)果為結(jié)果為f(g(John),John), 我們將替代稱(chēng)為我們將替代稱(chēng)為 (sigma),),寫(xiě)成寫(xiě)成U =V 55替代和合一的不同替代和合一的不同56替代和合一的不同替代和合一的不同n對(duì)替代,有模式定義(表示子程序基調(diào)對(duì)替代,有模式定義(表示子程序基調(diào)或宏定義),以及模式的實(shí)例(表示子或宏定義),以及模式的實(shí)例(表示子程序調(diào)用或宏擴(kuò)展)。程序調(diào)用或宏擴(kuò)展)。n替代需用

49、實(shí)際的實(shí)例值來(lái)替代模式定義中的替代需用實(shí)際的實(shí)例值來(lái)替代模式定義中的參數(shù)。參數(shù)。n例:例:F(A, B)=G(A, B),實(shí)例為,實(shí)例為F(g(I),h(j)n用用g(i)替替A, h(j)替替B,得到,得到F(A,B)=G(g(i),h(j)57替代和合一的不同替代和合一的不同n對(duì)合一,有兩個(gè)模式定義,和一個(gè)模式的一個(gè)實(shí)例。對(duì)合一,有兩個(gè)模式定義,和一個(gè)模式的一個(gè)實(shí)例。n需要知道的是:是否有對(duì)參數(shù)的賦值使得模式的實(shí)例成為兩需要知道的是:是否有對(duì)參數(shù)的賦值使得模式的實(shí)例成為兩個(gè)模式定義的一個(gè)替代。個(gè)模式定義的一個(gè)替代。n為了應(yīng)用模式的定義,我們必須在兩個(gè)方向上替換。為了應(yīng)用模式的定義,我們必須在兩個(gè)方向上替換。n例:模式例:模式F(A, B)=G(A, B),M(C, D)=N(C, D)n實(shí)例為:實(shí)例為:F(John, M(h(v),7)n如果用如果用John替代替代A,7替代替代D,同時(shí),用,同時(shí),用M(h(v)替代替代B,h(v)替代替代C。n則我們的模式實(shí)例代表了一個(gè)有效的替代。則我們的模式實(shí)例代表了一個(gè)有效的替代。n從我們的初始表達(dá)式從我們的初始表達(dá)式F(John, M(h(v),7),我們可有兩個(gè)結(jié),我們可有兩個(gè)結(jié)果。果。n如先作用到如先作用到F:F(J

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論