關注編譯原理的等價性

　　摘要：本文對編譯原理的等價性進行了分析和研究，提出一種有效的組織等價知識的方法，并在此基礎上提出應用等價關系提高教學效果的一種方法論。結合編譯原理教學實踐說明了該方法的可用性和有效性。
　　關鍵詞：知識等價性；教學方法論；教學效果；編譯原理
　　
　　1背景
　　在教學中，我們常常會使用斷言：“甲與乙是一樣的”，“甲乙二者是等價的”等等。從教和學的角度，這樣的斷言有如下作用：
　　1) 建立知識之間的聯系，有助于對知識進行組織，構建知識框架；
　　2) 減輕記憶的負擔，即本來對“甲”和“乙”的細節需要分別地記憶，現在二者被等價關聯起來，有大量細節不必重復記憶了；
　　3) 便于知識的靈活運用。例如原來使用“甲”知識解決的問題換做用“乙”知識去求解或許是一條更加簡潔有效的途徑；另外，求解某問題時，可用的知識從原來的一種增加到兩種，理論上增加了求解成功的可能性；
　　4) 便于突出重點，對于等價的知識，可以從其他的適合性角度做出選擇，不使總的知識量過于膨脹。
　　從以上可以看出，這種教學現象反映了教學過程中對知識等價性的關注。顯然，關注知識等價性的教學過程對于提高教學效果必定產生積極作用。
　　等效思維、等價轉化、等值變換等一些思維方法在教學和研究中被經常使用，從一定程度上說明關注知識等價性的教學過程已經廣為人們所接受。然而，不幸的是，這些思維方法僅停留在概念層面，屬于哲學上的思考，有模糊性，尚沒有形成系統的方法論(methodology)。事實上，由于這一原因，在課程教學中，有效地運用這種關注知識等價性的教學方法面臨著實質性的困難。
　　編譯原理是一門傳授對計算機程序進行分析、變換和優化的課程，是計算機專業核心課程，課程的知識分布在理論、技術和實現等多個層面，多年來的教學實踐反映出該課程是本專業學生最難學的課程之一，因而，結合該門課程的教學，系統地研究關注知識等價性的教學方法有典型性，同時從提高本門課程教學效果上也方便驗證該方法的有效性。
　　本文提出了一種關注知識的等價性的教學方法論，并應用于編譯原理課程教學中，給出了組織等價知識dmSgchPyxl255aXZWDvYntgzgKNX0fMSiOpUxxnFDUY=的方法，以及提高教學效果的形式規則，并基于編譯原理教學實踐闡明了該方法的有效性。本文后面部分：第二節分析等價性的利用對于提高教學效果的積極作用；第三節提出一種關注知識等價性的方法論；第四節結合編譯原理課程分析了該方法論的可用性和有效性；最后是本文總結。
　　2等價性的利用對提高教學效果的意義
　　一般來說，恰當地使用知識之間的等價關系，對于提高教學效果產生積極作用。等效思維、等價轉化以及等值變換等這些思維方法，是以知識的等價性為基礎所建立起來的，在教學過程中有意識或無意識地得到了廣泛使用。本節在介紹這些思維方法的基礎上，結合編譯原理中活動記錄(棧幀)知識對這些方法進行了具體解釋，并基于此進行了初步分析。
　　2.1基于等效思維舉一反三
　　所謂等效思維，就是在效果相同的前提下，把實際的、難于理解的問題變成理想的、易于思考的問題。它是數學上“等價轉化思想”在科學學科的問題求解中的應用，是一種常用的有效的科學思維方法。它常常是通過變換思維角度，對題目作適當假設，或者代換。
　　活動記錄是一種數據結構，用于運行時棧空間的管理，目的是支持函數調用的語義。活動記錄的結構有多種，常見的是fp-sp[1]365和sp-top[2]259兩種結構。這兩種結構中的內容是完全一樣的，也就是效果相同，但也存在著差異。fp-sp結構的特點是，幀指針fp把活動記錄分為兩個部分，前一部分的內容由調用者中的代碼來建立，而后一部分的內容由被調用者中的代碼建立。sp-top結構中幀指針sp指向活動記錄的開始位置，這樣幀與幀之間的邊界清楚。但是訪問sp-top結構的單元所使用的偏移量的絕對值要大?；诘刃季S，拋開了這些差異，從fp-sp結構容易得出sp-top結構，反之亦然。進一步地，容易設計出不同的活動記錄結構，以及相應的調用序列(calling sequence)和返回序列代碼，取得舉一反三的效果。
　　然而，在這一思維方法中，對于“實際的、難于理解的”知識和“理想的、易于思考的”知識，缺乏方法論層面上的定義和解釋，而“效果相同”也是泛化和不明確的陳述，因而，可以看出這一思維方法仍然停留在概念層面上，缺乏形式化描述，這成為有效應用這一方法的瓶頸。
　　2.2基于等價轉化化難為易
　　在數學研究中，使一種研究對象在一定條件下轉化為另一種研究對象的數學思想稱為等價轉化思想，是一種思維策略的體現，即我們常說的換個角度想問題，它是解決數學問題的重要思想，它要求我們能把握住問題的本質，能辨正地看待事物，能運用所學的知識把復雜的問題轉換為較簡單的問題解決，把隱含的條件轉化為明顯的條件，把生疏的問題轉化為較熟知的問題去解決。
　　運行時系統常常基于棧幀結構來支持嵌套過程的調用和返回。采用D表(Display表)的棧幀結構提高了時間效率，但理解起來略顯繁瑣。與它等效的采用靜態鏈的棧幀結構理解起來更簡潔一些。除此以外，二者沒有區別。因此，基于對靜態鏈棧幀結構理解的基礎上，通過將靜態鏈等價轉化為D表，使得后者化難為易了。
　　然而，在這一思維方法中，對于“一定條件”和“研究對象”缺乏形式化描述也成為有效使用該方法的障礙。
　　2.3基于等值變換法進行創新思維
　　等值變換法是從已有的事物中，通過模擬、借鑒、產生聯想來改變原來的對象而進行創造的方法，是依照蠶變成飛蛾、桑繭變成蠶絲的自然現象而總結出來的一種創造技法。自然界的各種等值變換形式歸結為三種類型：1)自我成長型等值變換，即類似于蠶從幼蟲變化為成蟲的變換過程；2)被加工型等值變換，即類似于從桑葉到蠶絲這一變換過程；3)綜合型等值變換，即前兩種的綜合。
　　仍然以棧幀知識為例，我們能注意到，嵌套過程的語義是一種知識，而棧幀結構及其調用序列和返回序列構成了另一種知識，在一定的抽象層次上看，這兩種知識之間存在著等價性。基于等值變換這種思維方法，后一種知識是前一種知識經第二類等值變換得到。進一步地，我們可以給棧幀結構中增加表示超長、變長形參單元，可以支持過程閉包和變長參數語義等等，依次可以看出是對棧幀知識的第一類等值變換。等值變換使得編譯原理的理論知識轉變為方法層面的知識，并最終轉變為程序代碼，就是組成編譯系統的代碼。
　　等值變換法的核心是保持等值，從已有到未知。目前仍然沒有形式化描述，沒有適用于計算系統的方法論。
　　綜上所述，基于知識的等價性，將等效思維、等價轉化以及等值變換等思維方法應用在編譯原理教學中，必定取得舉一反三、化難為易和創新思維的教學效果。但是，教授和學習每一種涉及到等價性的知識的過程中，準確描述等價關系是決定能夠利用等價性提高教學效果的前提，這將在下一節具體闡述。除此以外，基于等價性剪裁教學內容的意義在于：將適應不同的學分要求、適應不同的學生基礎這件事，轉變成為在多種等價知識中進行選擇的問題，顯然都變得易于實施。
　　3關注知識等價性的教學方法論
　　本節采用一種層次結構組織知識，并定義知識間的等價關系，在此基礎上引入知識等價性的層次視覺和抽象視覺，給出等效思維、等價轉化和等值變換等思維方法的一種形式化描述，形成一種關注知識等價性的教學方法論。
　　3.1知識單元及其層次結構組織
　　
　　知識是哲學層面的概念，為了應用于計算系統中并得到方便處理，采用知識單元的概念。
　　定義1 知識單元通常是指在一個問題域中用于闡述或解決某個問題的概念、算法、定理等，它在內容上是相對獨立和完整的。依據是將知識作為某個對象看待，作為結構化的知識要素，作為知識內容的不可再分的打包形式。知識單元有時采用集合形式表示，其元素是知識個體或稱為知識實例。
　　將編譯原理的內容作為一個問題領域，記為?，
　　那么?是編譯原理的知識單元的全集。知識單元不是
　　孤立的，它們之間存在著大量的聯系，我們把它表示成知識單元之間的關系。知識抽象是知識單元之間的
　　一種常見的關系，知識抽象關系的全集記為?。那
　　么有：
　　(1)T"(a:CaC)&Icir