1、第八章第八章 順序控制順序控制2n順序控制提供了操作和數據被組合成程順序控制提供了操作和數據被組合成程序和程序集合的框架。序和程序集合的框架。n涉及兩個方面的問題：涉及兩個方面的問題：n操作執行順序的控制（順序控制）操作執行順序的控制（順序控制）n數據在子程序間的傳遞（數據控制）數據在子程序間的傳遞（數據控制）3執行順序控制執行順序控制n控制的層次和形式控制的層次和形式n語句內（即表達式）的順序控制語句內（即表達式）的順序控制n算術表達的順序控制算術表達的順序控制n非算術表達式的順序控制非算術表達式的順序控制n語句間的順序控制語句間的順序控制48.1 隱式和顯式順序控制隱式和顯式順序控制n順序

2、控制結構可分為四組：順序控制結構可分為四組：1、用于表達式中的結構（也針對語句，表達式是語句的基本建、用于表達式中的結構（也針對語句，表達式是語句的基本建筑塊）。如：優先級規則和括號。筑塊）。如：優先級規則和括號。2、用于語句或語句組間的結構。如：條件和迭代。、用于語句或語句組間的結構。如：條件和迭代。3、用于申明式程序設計語言的程序結構。如邏輯程序設計語言、用于申明式程序設計語言的程序結構。如邏輯程序設計語言4、用于子程序間的結構，如：子程序調用和協同例程。、用于子程序間的結構，如：子程序調用和協同例程。n這種分法并不是精確的，如這種分法并不是精確的，如LISP和和APL中只有表達式中只有表

3、達式而無語句。而無語句。n順序控制結構可以是隱含的（缺省的）（由語言定義，順序控制結構可以是隱含的（缺省的）（由語言定義，除非程序員顯式修改）或顯式的（程序員可用來修改除非程序員顯式修改）或顯式的（程序員可用來修改隱含順序）。隱含順序）。 5ACABBroot2428.2 算術表達的順序控制算術表達的順序控制n考慮方程求根：考慮方程求根：n該公式至少涉及該公式至少涉及15個分開的操作，用匯編或機器語個分開的操作，用匯編或機器語言至少需要言至少需要15條指令甚至更多。而寫成條指令甚至更多。而寫成Fortran程程序則為：序則為：nROOT=(-B+SQRT(B*2-4*A*C)/(2*A)n這是

4、自然的表達方法，由翻譯器而不是程序員來考這是自然的表達方法，由翻譯器而不是程序員來考慮各種優化問題。慮各種優化問題。n然而，翻譯器如何控制正確的操作順序？然而，翻譯器如何控制正確的操作順序？ 6算術表達的順序控制算術表達的順序控制n算術表達式的表示算術表達式的表示n語法：語法：直觀表示直觀表示和和形式化表示形式化表示n語義語義：決定計值方式和過程：決定計值方式和過程n運算符的優先級運算符的優先級n算術表達式算術表達式在執行時的表示在執行時的表示7樹結構表示樹結構表示n目前，我們將表達式考慮為單個實體，目前，我們將表達式考慮為單個實體，忽略了其計值必需的實際語法和語義。忽略了其計值必需的實際語法

5、和語義。n表達式中的基本順序控制機制是表達式中的基本順序控制機制是“函數函數復合復合”：刻劃操作及其操作數。：刻劃操作及其操作數。n函數復合使表達式呈樹結構特征，根為函數復合使表達式呈樹結構特征，根為主操作，中間節點為中間層次操作，葉主操作，中間節點為中間層次操作，葉為操作數。為操作數。8樹結構表示樹結構表示n求方程根的表達式的樹。求方程根的表達式的樹。n樹表示闡明了表達式的控制結構，樹表示闡明了表達式的控制結構，低層的數據引用和操作作為高層低層的數據引用和操作作為高層操作的操作數，必須先計值，但操作的操作數，必須先計值，但樹表示也留下一些計值順序沒有樹表示也留下一些計值順序沒有指定。指定。n

6、如：如：B和和B*2誰先計值？誰先計值？B是否是否可組合為同一引用？可組合為同一引用？n通常語言定義只在樹表示級定義通常語言定義只在樹表示級定義表達式計值順序，允許實現者決表達式計值順序，允許實現者決定計值細節。定計值細節。返回9表達式的語法表達式的語法n表達式表達式(a+b)(ca)的樹結構的樹結構10表達式的語法表達式的語法n表達式可表示為樹結構，但為了在程序中表示，表達式可表示為樹結構，但為了在程序中表示，線性化是需要的。線性化是需要的。n前綴（波蘭前綴）記法。前綴（波蘭前綴）記法。n這是波蘭數學家發明的無括號記號法。如：這是波蘭數學家發明的無括號記號法。如：f(x,y,z)，+ab-c

7、anLISP使用了該記號法的變種，稱為劍橋波蘭，用括號將使用了該記號法的變種，稱為劍橋波蘭，用括號將操作符及其操作數括起來，如：操作符及其操作數括起來，如：(X(+ab)(-ca)。n后綴（逆波蘭）記號法后綴（逆波蘭）記號法n類似于前綴，但操作符數在后面，如：類似于前綴，但操作符數在后面，如：ab+ca-n中綴記號法中綴記號法n最適合二元操作，也是我們最常用的方式。最適合二元操作，也是我們最常用的方式。返回11表達式的語義表達式的語義 （1/3）n上三種記號法對語言的設計都有一些有用的屬上三種記號法對語言的設計都有一些有用的屬性，在如何計算表達式值方面也有不同。性，在如何計算表達式值方面也有不

8、同。n前綴計值前綴計值n可以通過一遍掃描計值每個表達式，然而需要知道可以通過一遍掃描計值每個表達式，然而需要知道每個操作的操作數量。除了可省去括號外，前綴表每個操作的操作數量。除了可省去括號外，前綴表達式在語言設計中有如下價值：達式在語言設計中有如下價值：1、一般的函數調用均采用前綴方式。、一般的函數調用均采用前綴方式。2、可表示有任意數量操作數的操作，寫表達式只需一個語、可表示有任意數量操作數的操作，寫表達式只需一個語法規則。法規則。3、解碼可以機械地很容易地進行，將其翻譯成簡單代碼序、解碼可以機械地很容易地進行，將其翻譯成簡單代碼序是容易的。是容易的。12表達式的語義表達式的語義 （1/3

9、）n前綴計值前綴計值n下面算法用一個執行棧計值表達式：對表達下面算法用一個執行棧計值表達式：對表達式式P，1、如、如P中下一項是操作子，壓入棧項，設置所需中下一項是操作子，壓入棧項，設置所需參數數目。參數數目。2、如、如P中下一項是操作數，壓入棧項。中下一項是操作數，壓入棧項。3、如棧項、如棧項n項是操作數（對棧中第一個項是操作數（對棧中第一個n元操元操作），則可以進行計值，用計值結果替代該操作作），則可以進行計值，用計值結果替代該操作符和操作數。符和操作數。13表達式的語義表達式的語義 （2/3）n后綴計值后綴計值n后綴計值時，操作符緊跟其操作數后而且操后綴計值時，操作符緊跟其操作數后而且操

10、作數已被計值。作數已被計值。n1、如、如P中下一項是操作數，壓入棧頂中下一項是操作數，壓入棧頂n2、如、如P中下一項是中下一項是n元操作符，元操作符，n個參數必須是個參數必須是棧頂部的棧頂部的n個元素，計算結果并替換這個元素，計算結果并替換這n個元素。個元素。n這種計值策略直接、簡單，是很多翻譯器中生成這種計值策略直接、簡單，是很多翻譯器中生成表達式代碼的基礎。表達式代碼的基礎。14表達式的語義表達式的語義 （3/3）n中綴計值中綴計值n中綴是常見的，但用于程序語言中會導致一中綴是常見的，但用于程序語言中會導致一些問題：些問題：n1、只適合于二元操作。語言單用中綴是不夠的，、只適合于二元操作。

11、語言單用中綴是不夠的，還需使用前綴，這二者的混合使翻譯更為復雜。還需使用前綴，這二者的混合使翻譯更為復雜。n2、表達式中涉及多個中綴操作時，如不使用括、表達式中涉及多個中綴操作時，如不使用括號，則存在固有二義性。為解決這個問題，通常號，則存在固有二義性。為解決這個問題，通常引入隱含的規則。引入隱含的規則。返回15操作子計值順序操作子計值順序16操作的層次操作的層次n即操作的優先規則即操作的優先規則返回返回n同一層次操作的計算順序的隱含規則同一層次操作的計算順序的隱含規則n優先級對算術表達式是適用的，因為表優先級對算術表達式是適用的，因為表達式語義的數學模型已對大多數程序員達式語義的數學模型已對

12、大多數程序員熟知的。熟知的。結合律結合律17結合律結合律n然而，當語言引入新的，不是源自傳統數學的操作符然而，當語言引入新的，不是源自傳統數學的操作符時，優先規則可能不再有用，因此，需要有不同方法時，優先規則可能不再有用，因此，需要有不同方法來處理擴展的操作集。來處理擴展的操作集。nC語言：使用擴展的優先規則集合，大多數使用從左到右的結語言：使用擴展的優先規則集合，大多數使用從左到右的結合律。大多數合律。大多數C規則是合理的。規則是合理的。nAPL：操作數為數組和矢量，語言沒有優先規則。所有表達：操作數為數組和矢量，語言沒有優先規則。所有表達式計值從右到左。這規則對大多數表達式也是合理的，除了

13、式計值從右到左。這規則對大多數表達式也是合理的，除了一些典型的表達式，如一些典型的表達式，如a-b-c-意為意為a-(b-c)。nSmalltalk：模型類似：模型類似APL，沒有優先規則，表達式計值從左，沒有優先規則，表達式計值從左到右。到右。nForth：用于實時過程控制。其運行時結構為棧，語言是純后：用于實時過程控制。其運行時結構為棧，語言是純后綴的，沒有優先規則。綴的，沒有優先規則。返回返回18執行時表示執行時表示n對中綴形式的表達式的解碼是困難的，需要翻對中綴形式的表達式的解碼是困難的，需要翻譯為易于解碼的可執行形式。通常的選擇有：譯為易于解碼的可執行形式。通常的選擇有：1、機器代碼

14、序列、機器代碼序列n表達式被直接翻譯成實際的機器代碼，而不是先翻譯為中表達式被直接翻譯成實際的機器代碼，而不是先翻譯為中間形式。指令順序反映了初始表達式的順序控制結構。間形式。指令順序反映了初始表達式的順序控制結構。n機器代碼序列必須使用顯式的臨時存儲位置來保持中間結機器代碼序列必須使用顯式的臨時存儲位置來保持中間結果，允許使用硬件解釋器，因此，執行速度快。果，允許使用硬件解釋器，因此，執行速度快。2、樹結構、樹結構n表達式可以表達式可以以其自然的樹結構直接執行以其自然的樹結構直接執行（使用軟件解釋（使用軟件解釋器）。執行通過簡單的樹遍歷來完成。器）。執行通過簡單的樹遍歷來完成。n這是這是LI

15、SP中使用的典型技術，整個程序被表示為樹結構。中使用的典型技術，整個程序被表示為樹結構。19執行時表示執行時表示3、前綴或后綴形式、前綴或后綴形式n這兩種形式可用前面給出的解釋算法來執行。這兩種形式可用前面給出的解釋算法來執行。n在某些基于堆棧組織的實際計算機中，實際的機在某些基于堆棧組織的實際計算機中，實際的機器代碼表示為后綴形式。器代碼表示為后綴形式。n前綴表示是前綴表示是SNOBOL4程序的執行形式，執行從程序的執行形式，執行從左到右進行。左到右進行。n每個操作遞歸地調用解釋器來計值其操作數。每個操作遞歸地調用解釋器來計值其操作數。20表達式的樹表示的計值表達式的樹表示的計值n表達式翻成

16、樹結構雖有困難，但總體上是直接表達式翻成樹結構雖有困難，但總體上是直接的。的。n而樹到可執行原語序列的翻譯，則涉及計值順而樹到可執行原語序列的翻譯，則涉及計值順序的一些微妙問題。在代碼生成中出現的計值序的一些微妙問題。在代碼生成中出現的計值順序問題有：順序問題有：n問題一：統一的計值規則問題一：統一的計值規則n問題二：副作用，問題二：副作用，Side effect。n問題三：出錯條件問題三：出錯條件n問題四：短路布爾表達式問題四：短路布爾表達式21表達式的計值表達式的計值(1)：統一的計值規則：統一的計值規則n對表達式樹中的每個操作結點，首先計值其操作數對表達式樹中的每個操作結點，首先計值其操

17、作數（或生成相應代碼），然而應用操作到計算出的操作（或生成相應代碼），然而應用操作到計算出的操作數上（或生成相應代碼）數上（或生成相應代碼）積極計值規則（積極計值規則（eager）。）。n對有些表達式來說，計值發生的順序并不重要，可以對有些表達式來說，計值發生的順序并不重要，可以選擇以優化存儲和其他機器特性。選擇以優化存儲和其他機器特性。n例，對例，對(a+b)(c-a)，下列順序均可接受。，下列順序均可接受。順序一：取順序一：取a的右值的右值順序二：取順序二：取c的右值的右值 取取b的右值的右值 取取b的右值的右值 a+bd 取取a的右值的右值 取取c右值右值 c-ae c-ae a+bd

18、def表達式的右值表達式的右值 def22ZY0XXYIF/表達式的計值表達式的計值(1)：統一的計值規則：統一的計值規則n但是，并不是在任何情況下都可以使用這種統但是，并不是在任何情況下都可以使用這種統一的計值規則。一的計值規則。n例如，包含條件的表達式：例如，包含條件的表達式：nZ+(Y=0？X：X/Y)，當，當Y0時，計算時，計算X/Y23表達式的計值表達式的計值(1)：統一的計值規則：統一的計值規則n采用統一規則，對采用統一規則，對IF操作，需先計算操作數，即使操作，需先計算操作數，即使Y=0。n顯然，此時我們不希望所有操作數被計值。顯然，此時我們不希望所有操作數被計值。n從而，我們有

19、另一個規則：永不在應用操作之前計值從而，我們有另一個規則：永不在應用操作之前計值操作數。操作數。n即，總是不計值地傳遞操作數，由作用操作決定什么時候計即，總是不計值地傳遞操作數，由作用操作決定什么時候計值操作數值操作數Lazy計值。計值。n然而，對此規則，在很多情況下是不實際的。比如：如何仿然而，對此規則，在很多情況下是不實際的。比如：如何仿真未計值操作數到操作的傳遞？這需要軟件仿真。真未計值操作數到操作的傳遞？這需要軟件仿真。n這兩種計值規則：積極和隋性（這兩種計值規則：積極和隋性（lazy），對應子程序），對應子程序參數傳遞的按值和按名。參數傳遞的按值和按名。n對表達式而言，沒有簡單的統一

20、規則是完全令人滿意的，通對表達式而言，沒有簡單的統一規則是完全令人滿意的，通常規則是混合的。常規則是混合的。24表達式的計值表達式的計值(2)：副作用：副作用n表達式中使用有副作用的操作，一直是語言設計中的表達式中使用有副作用的操作，一直是語言設計中的爭論點。爭論點。n考慮：考慮：afun(x)+an對乘法：需先取對乘法：需先取a的右值并計值的右值并計值fun(x)n對加法：需取對加法：需取a的右值，并計算乘法。的右值，并計算乘法。n顯然，我們希望只取顯然，我們希望只取a一次并應用到兩個地方，而且一次并應用到兩個地方，而且fun(x)的的計值在取計值在取a的前或后并無區別。的前或后并無區別。n

21、但如但如fun有副作用，改變了有副作用，改變了a的值，則計值序成為關鍵。的值，則計值序成為關鍵。n如如a值本為值本為1，但，但fun執行后值為執行后值為3，并改，并改a為為2。則表達式可能值。則表達式可能值為：為：1、順序計值：、順序計值：13+2=52、取、取a一次：一次：13+1=43、在取、在取a前調用前調用fun：23+2=8n執行序不同導致不同結果。執行序不同導致不同結果。25表達式的計值表達式的計值(2)：副作用：副作用n對表達式中副作用的使用有兩種選擇：對表達式中副作用的使用有兩種選擇：1、不允許副作用、不允許副作用n不允許有副作用的函數或對副作用可能影響的表不允許有副作用的函數

22、或對副作用可能影響的表達式的值改為未定義。達式的值改為未定義。2、允許副作用、允許副作用n但語言定義應精確地給出計值順序，這將使很多但語言定義應精確地給出計值順序，這將使很多優化不可能。優化不可能。n通常，語句允許有副作用，如：賦值必通常，語句允許有副作用，如：賦值必須產生副作用。須產生副作用。26表達式的計值表達式的計值(3)：出錯條件：出錯條件n對可能失敗和產生出錯條件的操作，涉及一種對可能失敗和產生出錯條件的操作，涉及一種特殊的副作用。一般的副作用只涉及到程序員特殊的副作用。一般的副作用只涉及到程序員定義的函數，而出錯條件可能在很多原操作中定義的函數，而出錯條件可能在很多原操作中出現（溢

23、出、被零除等）。出現（溢出、被零除等）。n這類副作用是不希望被排除的，而出錯條件的這類副作用是不希望被排除的，而出錯條件的意義在于其出現甚至會受到表達式的計值順序意義在于其出現甚至會受到表達式的計值順序的影響。這樣，程序員需要精確的計值順序控的影響。這樣，程序員需要精確的計值順序控制。制。27表達式的計值表達式的計值(4)：短路布爾表達式：短路布爾表達式n考慮例子：考慮例子：nif (A=0)|(B/AC)nWhile(IC)n兩個例子中，第二個條件可能產生出錯條件。第一兩個例子中，第二個條件可能產生出錯條件。第一個操作數用于防止錯誤產生。個操作數用于防止錯誤產生。n在很多語言中，求布爾操作需

24、先計值操作數，在很多語言中，求布爾操作需先計值操作數，這將產生不期望的錯誤，因為人們期望左操作這將產生不期望的錯誤，因為人們期望左操作數短路右操作數。數短路右操作數。nAda中提供了兩個特殊的布爾操作來解決這個問題。中提供了兩個特殊的布爾操作來解決這個問題。nand then 和和 or else。顯式地提供短路機制。顯式地提供短路機制。n例：例：if (A=0) or else (B/AC) thenn這將不會失敗，因這將不會失敗，因A=0將導致整個表達式計值結束。將導致整個表達式計值結束。返回288.3 語句間的順序控制語句間的順序控制n基本語句基本語句n語句級順序控制的語句級順序控制的形

25、式形式n語句級順序控制的語句級順序控制的語句語句n結構化順序控制結構化順序控制n結構的程序設計簡介結構的程序設計簡介n結構順序控制語句結構順序控制語句n結構順序控制中的問題結構順序控制中的問題n順序控制的結構化：順序控制的結構化：素程序素程序29基本語句基本語句n任何程序的結果由其基本語句確定。這任何程序的結果由其基本語句確定。這里我們不再考慮語句中表達式，而是將里我們不再考慮語句中表達式，而是將語句作為考慮的單元來代表一單步計算。語句作為考慮的單元來代表一單步計算。n數據對象的賦值數據對象的賦值n通過向數據對象賦值而改變計算狀態是影響通過向數據對象賦值而改變計算狀態是影響計算狀態的主要機制。

26、計算狀態的主要機制。30基本語句基本語句n數據對象的賦值數據對象的賦值n賦值語句賦值語句n主要目的是將某表達式的右值賦給某數據對象的左值。主要目的是將某表達式的右值賦給某數據對象的左值。n賦值為每個基本數據類型定義的中心操作。賦值為每個基本數據類型定義的中心操作。n輸入語句輸入語句n大多數語言有一種語句形式，從終端用戶、文件或通大多數語言有一種語句形式，從終端用戶、文件或通訊線讀數據。這樣的語句也通過賦值改變變量的值。訊線讀數據。這樣的語句也通過賦值改變變量的值。n其他賦值操作其他賦值操作n參數傳遞：給形參賦值參數傳遞：給形參賦值n隱含賦值：如隱含賦值：如SNOBOL4中的引用，中的引用，Pr

27、olog目標匹配，目標匹配，聲明時初始值等。聲明時初始值等。返回31語句級順序控制的形式語句級順序控制的形式n三種主要的語句級順序控制：三種主要的語句級順序控制：n復合：語句順序放置，順序執行。復合：語句順序放置，順序執行。n選擇：兩個語句序列可形成選擇，使得一個選擇：兩個語句序列可形成選擇，使得一個或另一個序列被執行，但不能同時執行。或另一個序列被執行，但不能同時執行。n迭代：一個語句序列被重復執行零次或多次。迭代：一個語句序列被重復執行零次或多次。n這是三種常見結構，語句被組成這三種這是三種常見結構，語句被組成這三種結構而形成程序。結構而形成程序。返回32顯式順序控制顯式順序控制ngoto

28、語句，兩種形式語句，兩種形式n無條件無條件goto和條件和條件gotonGoto語句導致無結構的設計。語言的很多形式模語句導致無結構的設計。語言的很多形式模型均不允許型均不允許goto存在。存在。n此外，此外，goto也是多余的，沒有也是多余的，沒有goto也可以寫出同也可以寫出同樣能力的程序。樣能力的程序。nBreak語句語句n通常使控制被前移到一個顯式點（在給定控制結構通常使控制被前移到一個顯式點（在給定控制結構的結束處）。的結束處）。n如如C中中Break語句使得立即退出語句使得立即退出while、for、switch語句。語句。nC中還有中還有Continue語句，只結束本次循環。語句

29、，只結束本次循環。33結構化結構化break語句語句返回34結構的程序設計結構的程序設計n70年代，年代，goto語句受到很大攻擊，以至語句受到很大攻擊，以至有的語言完全刪去了有的語言完全刪去了goto。goto 語句語句有一些優點：有一些優點：如果標號只是局部語法標記，則對高效執如果標號只是局部語法標記，則對高效執行有直接的硬件支持。行有直接的硬件支持。在小程序中使用簡單、容易。在小程序中使用簡單、容易。為匯編語言和老語言用戶熟悉。為匯編語言和老語言用戶熟悉。可作為通用建筑塊來表示（仿真）其他控可作為通用建筑塊來表示（仿真）其他控制形式。制形式。35結構的程序設計結構的程序設計n它也有嚴重的

30、缺點：它也有嚴重的缺點：1、缺乏層次的程序結構、缺乏層次的程序結構n程序的正確性和開發效率已遠比效率更為重要，語言也應程序的正確性和開發效率已遠比效率更為重要，語言也應反映此需求。單進單出的控制結構概念，已成為更易理解反映此需求。單進單出的控制結構概念，已成為更易理解的設計。層次化提供了一種抽象，符合的設計。層次化提供了一種抽象，符合“分而治之分而治之”的思的思想。而想。而goto將打破這種層次性。將打破這種層次性。2、程序文本中語句順序不一定對應執行的順序。、程序文本中語句順序不一定對應執行的順序。n要理解程序，必須理解語句的執行順序。要理解程序，必須理解語句的執行順序。n靜態順序和動態順序

31、有關聯將使程序更易于理解。靜態順序和動態順序有關聯將使程序更易于理解。3、語句組可能有多個用途。、語句組可能有多個用途。n如果每個組只含單個用途。則程序更易理解。如果每個組只含單個用途。則程序更易理解。n人為地通過人為地通過goto使某組有多用途將打亂執行順序，使程使某組有多用途將打亂執行順序，使程序難于修改。序難于修改。36結構的程序設計結構的程序設計n結構化程序設計強調：結構化程序設計強調：、程序結構的層次設計，只用三種控制結、程序結構的層次設計，只用三種控制結構。構。、層次設計的表示應直接體現在程序文本、層次設計的表示應直接體現在程序文本中（只使用結構化控制語句）。中（只使用結構化控制語

32、句）。、語句的文本序列對應執行序列：、語句的文本序列對應執行序列：、使用單一用途的語句組。、使用單一用途的語句組。返回37結構順序控制結構順序控制n大多數語言提供了控制語句集合來表示三種基本的控大多數語言提供了控制語句集合來表示三種基本的控制形式，這些語句均應該是單入單出的。它們所構成制形式，這些語句均應該是單入單出的。它們所構成的程序，其執行和語句序基本對應。的程序，其執行和語句序基本對應。n復合語句復合語句n一個語句序列，可按單個語句處理來構造更大的語句。一個語句序列，可按單個語句處理來構造更大的語句。n用用beginend 和和 等來構造等來構造n其實現是將其存放在一個連續存儲區域中。其

33、實現是將其存放在一個連續存儲區域中。n條件語句條件語句n用來表示兩個或更多語句的選擇執行，或單個語句的可選執用來表示兩個或更多語句的選擇執行，或單個語句的可選執行。行。nif 語句語句n單分枝：單分枝：if 條件條件 then 語句語句語句的可選執行語句的可選執行n兩分枝：兩分枝：if 條件條件 thenelsen還可表示多分枝。還可表示多分枝。 38結構順序控制結構順序控制n條件語句條件語句ncase語句，重復測試某變量的值。語句，重復測試某變量的值。case Tag is When 0 When 1 endcasen實現實現nif語句常用硬件支持的分枝和跳轉指令實現。語句常用硬件支持的分枝

34、和跳轉指令實現。ncase語句常用跳轉表來避免同一變量值的重復測試。語句常用跳轉表來避免同一變量值的重復測試。n跳轉表是一個向量，順序存放在內存中，其部件是無條件跳跳轉表是一個向量，順序存放在內存中，其部件是無條件跳轉指令。轉指令。39case語語句句的的跳跳轉轉表表實實現現40結構順序控制結構順序控制n迭代語句迭代語句n提供重復計算的機制。通常分為頭和體兩部分。體提供語句提供重復計算的機制。通常分為頭和體兩部分。體提供語句的動作。頭控制重復執行體的次數。的動作。頭控制重復執行體的次數。n簡單重復簡單重復n直接給出執行的次數。直接給出執行的次數。n例：例：COBOL中，中，perform bo

35、dy k timesn當條件成立時重復當條件成立時重復nwhile test do bodyn計數器增量的重復計數器增量的重復nfor I:=1 step 2 until 30 do bodyn無限重復無限重復nLoopexit when condition沒有顯式的終止測試。沒有顯式的終止測試。endloopn循環的實現循環的實現n直接使用硬件提供的分支直接使用硬件提供的分支/跳轉指令。跳轉指令。返回41結構順序控制中的問題結構順序控制中的問題n多出口循環多出口循環n有些情況下，可能在幾種條件下都需要循環終止。有些情況下，可能在幾種條件下都需要循環終止。n如：搜索循環是一個例子：如：搜索循環

36、是一個例子：從從K元素矢量中搜索第一個滿足某條件的元素。元素矢量中搜索第一個滿足某條件的元素。For I:=1 to k do if VECT(I)=0 the goto for I in 1k loop exit when VECT (I)=0;endloop42結構順序控制中的問題結構順序控制中的問題ndo-while-don經常最自然的測試是否退出循環的地方是在中間部經常最自然的測試是否退出循環的地方是在中間部位，即已完成某些處理之后。稱為位，即已完成某些處理之后。稱為do while do，因為中間點因為中間點while是需要的是需要的do while doread (x)while

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

38、程圖由這三類結構成。功能結點決策結點匯合結點素程序（素程序（Prime Program）44合式程序（合式程序（ proper program ）n控制結構的形式模式是如下的流程圖：控制結構的形式模式是如下的流程圖：n1、有單個進入線、有單個進入線n2、有單個退出線、有單個退出線n3、有從入口到每個結點和從每個結點到出口的路徑。、有從入口到每個結點和從每個結點到出口的路徑。n我們的目標是區分我們的目標是區分“結構的結構的”“”“合式程序合式程序”和和“非結非結構的構的”合式程序。下圖均為合式程序，差別在于結構合式程序。下圖均為合式程序，差別在于結構性。性。45素程序素程序n是合式程序，但不能被

39、分為更小的合式程序，是合式程序，但不能被分為更小的合式程序，（功能結點的長序列被視為基本的）。否則成（功能結點的長序列被視為基本的）。否則成為復合程序。為復合程序。n所有素程序可以枚舉出來。注意：它們中大多所有素程序可以枚舉出來。注意：它們中大多數或是無效的，或是常見的控制結構。數或是無效的，或是常見的控制結構。n所用的控制結構均是具有少量結點的素程序。所用的控制結構均是具有少量結點的素程序。n通過枚舉，我們看出，通過枚舉，我們看出，do-while-do是自然的是自然的控制結構。但很少有語言提供這種機制。控制結構。但很少有語言提供這種機制。46素程序的枚舉素程序的枚舉n至多至多4節點的素程序

40、，其中節點的素程序，其中na、b、e、i是功能結點序列。是功能結點序列。nf是是if-then、 g是是 do while、h 是是 repeat-until、nj是是 if-then-else、k是是 do-while-donc、d、l和和q只含決策結點和只含決策結點和匯合結點，沒有功能結點，匯合結點，沒有功能結點，故不會改變抽象機的狀態空故不會改變抽象機的狀態空間，因此，等價于恒等函數。間，因此，等價于恒等函數。而其中而其中c、l總退出，而總退出，而d、q是循環（一旦循環，將不會是循環（一旦循環，將不會終止）。終止）。47結構定理結構定理nBohm & Jacobini任何素程序可

41、被轉換為任何素程序可被轉換為只使用只使用while和和if的素程序。的素程序。n該構造過程的概述：該構造過程的概述：1、給定任意流程圖，標記每個結點，出口標記為、給定任意流程圖，標記每個結點，出口標記為O2、定義、定義I為新的程序變量為新的程序變量3、對流程圖中每個結點，應用轉換規則。、對流程圖中每個結點，應用轉換規則。4、重建程序。、重建程序。n這里這里I類似虛擬機指令計數器，指出下一條執行語類似虛擬機指令計數器，指出下一條執行語句。句。n整個程序簡單地是一系列嵌套的整個程序簡單地是一系列嵌套的if語句（在單個語句（在單個while循環中），這樣，任何程序可用此法轉換為循環中），這樣，任何程

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

43、為直接仿真這個操作而設計的語言。其實現獨立是為直接仿真這個操作而設計的語言。其實現獨立于任何實際的機器體系結構，面向串處理虛擬機而設計。為于任何實際的機器體系結構，面向串處理虛擬機而設計。為了執行了執行SNOROL4，需將串處理機的操作實現為現有機器上，需將串處理機的操作實現為現有機器上的宏。的宏。n因此，因此，SNOBOL4是第一個幾乎可運行于所有機器的語言。在是第一個幾乎可運行于所有機器的語言。在其每個實現中有精確相同的語義。其每個實現中有精確相同的語義。nSNOBOL4使用串替代來實現匹配操作。使用串替代來實現匹配操作。模式匹配模式匹配51模式匹配模式匹配nProlog使用使用“關系作為

44、關系作為n元組集合元組集合”的概念作為匹的概念作為匹配機制。配機制。n通過刻劃這些關系的已知實例，其他實例可被導出。通過刻劃這些關系的已知實例，其他實例可被導出。n例：有事實例：有事實nParentof(John,Mary)nParentof(Susan,Mary)nParentof(Bill,John)nParentof(Ann,John)n要想知道要想知道Mary的父輩，我們寫的父輩，我們寫Parentof(X,Mary)，推導，推導結果結果X可以是可以是John或或Susan。n如需知道如需知道Mary的兩個父輩，式子為：的兩個父輩，式子為：nParentof(X,Mary), Pare

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

46、un fact (1)=1 | fact (N:int)=N*fact(N-1)返回53合一合一nProlog數據庫包含事實和規則。包含一個或多個變量數據庫包含事實和規則。包含一個或多個變量的表達式稱為查詢，用來表示一個未知關系。的表達式稱為查詢，用來表示一個未知關系。nProlog的主要特性是使用模式匹配來發現是否查詢可的主要特性是使用模式匹配來發現是否查詢可解。解。n合一是進行模式匹配的方法，用于確定對查詢的合法合一是進行模式匹配的方法，用于確定對查詢的合法一致的替代。一致的替代。n例：對查詢例：對查詢nParentof(X, Mary)=Parentof(John, Y)n顯然，解答為顯

47、然，解答為Parentof(John,Mary)n我們稱，該實例使用替代我們稱，該實例使用替代John/X, Mary/Y,合一了合一了Parentof(X, Mary)和和Parentof(John, Y)n合一可視為對替代的公共性質的擴展。合一可視為對替代的公共性質的擴展。54合一：替代與一般合一合一：替代與一般合一n替代替代n這是在編程中學到的第一條原則，涉及參數傳遞和這是在編程中學到的第一條原則，涉及參數傳遞和宏擴展。在宏擴展中，是用任意表達式替代一個變宏擴展。在宏擴展中，是用任意表達式替代一個變量。量。n一般合一：一般合一：n要合一兩個表達式要合一兩個表達式U和和V，需找到對，需找到

48、對U、V中出現的中出現的變量的替代，該替代使兩個表達式相同。變量的替代，該替代使兩個表達式相同。n例，例，f(X,John), f(g(John),Z)n綁定綁定X到到g(John), Z到到John可完成合一。可完成合一。n結果為結果為f(g(John),John), 我們將替代稱為我們將替代稱為 （sigma），），寫成寫成U =V 55替代和合一的不同替代和合一的不同56替代和合一的不同替代和合一的不同n對替代，有模式定義（表示子程序基調對替代，有模式定義（表示子程序基調或宏定義），以及模式的實例（表示子或宏定義），以及模式的實例（表示子程序調用或宏擴展）。程序調用或宏擴展）。n替代需用

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