編譯原理實踐與指導課程

1. 編譯原理及實踐的介紹

本書結合對現代編譯器設計理論的詳細研究，完整描述了一個可運行的小規模語方編譯器（包括源代碼）。本書反映了作者的這樣一些觀點：不掌握理論就不會理解實際的編譯器設計；而對大學生來說，看不到理論在實際中的應用就不會真正地理解理論。

2. 編譯原理與實踐中正規表達式的問題

(aa|b)*
由連續兩個a或一個b的任意序列組成的語言，比如aab,baaaabbbb.
(a|bb)*
連續兩個b或一個a的任意序列。

正則語言里，｜表示任選，有時也用+號。*號表示閉包－－就是說任意組合。

3. 為什麼要學習編譯原理(轉）

大學課程為什麼要開設編譯原理呢？這門課程關注的是編譯器方面的產生原理和技術問題，似乎和計算機的基礎領域不沾邊，可是編譯原理卻一直作為大學本科的必修課程，同時也成為了研究生入學考試的必考內容。編譯原理及技術從本質上來講就是一個演算法問題而已，當然由於這個問題十分復雜，其解決演算法也相對復雜。我們學的數據結構與演算法分析也是講演算法的，不過講的基礎演算法，換句話說講的是演算法導論，而編譯原理這門課程講的就是比較專註解決一種的演算法了。在20世紀50年代，編譯器的編寫一直被認為是十分困難的事情，第一Fortran的編譯器據說花了18年的時間才完成。在人們嘗試編寫編譯器的同時，誕生了許多跟編譯相關的理論和技術，而這些理論和技術比一個實際的編譯器本身價值更大。就猶如數學家們在解決著名的哥德巴赫猜想一樣，雖然沒有最終解決問題，但是其間誕生不少名著的相關數論。 推薦參考書 雖然編譯理論發展到今天，已經有了比較成熟的部分，但是作為一個大學生來說，要自己寫出一個像TurbocC,Java那樣的編譯器來說還是太難了。不僅寫編譯器困難，學習悶數編譯原理這門課程也比較困難。 第一本書的原名叫《CompilersPrinciples,Techniques,andTools》,另外一個響亮的名字就是龍書。原因是這本書的封面上有條紅色的龍，也因為獗臼樵詒嘁朐?砘?嘴域確實?忻?所以很多國外的學者都直接取名為龍書。最近機械工業出版社已經出版了此書的中文版，名字就叫《編譯原理》。該書出的比較早，大概是在85或86年編寫完成的，作者之一還是著名的貝爾實驗室的科學家。裡面講解的核心編譯原理至今都沒有變過，所以一直到今天，它的價值都非凡。這本書最大的特點就是一開始就通過一個實際的小例子，把編譯原理的大致內容羅列出來，讓很多編譯螞罩首原理的初學者很快心裡有了個底,也知道為什麼會有這些理論，怎麼運用這些理論。而這一點是我感覺國內的教材缺乏的東西，所以國內的教材都不是寫給願意自學的讀者，總之讓人看了半天，卻不知道裡面的東西有什麼用。 第二本書的原名叫《ModernCompilerDesign》,中文名字叫做《現代編譯程序設計》。該書由人民郵電出版社所出。此書比較關注的是編譯原理的實踐，書中給出了不少的實際程序代碼，還有很多實際的編譯技術問題等等。此書另外一個特點就是其現代而字。在傳統的編譯原理教材中，你是不可能看到如同Java中的垃圾回收等演算法的。因為Java這樣的解釋執行語言是在近幾年才流行起來的東西。如果你想深入學習編譯原理的理論知識，那麼你肯定得看前面那本龍書，如果你想自己動手做一個先進的編譯器，那麼你得看這本《現代編譯程序設計》。 第三本書就是很多國內的編譯原理學者都推薦的那本《編譯原理及實踐》。或許是這本書引入國內比較早吧，我記得我是在高中就買了這本書，不過也是在前段時間才把整本書看完。此書作為入門教程也的確是個不錯的選擇。書中給出的編譯原理講解也相當細致，雖然不如前面的龍書那麼深入，但是很多地方都是點到為止，作為大學本科教學已經是十分深入了。該書的特點就是注重實踐，不過感覺還不如前面那本《現代編譯程序設計》的實踐味道更重。此書的重點還是在原理上的實踐，而非前面那本那樣的技術實踐。《編譯原理及實踐》在講解編譯原理的各個部分的同時，也在逐步實踐一個現代的編譯器TinyC.等你把整本書看完，差不多自己也可以寫一個TinyC了。作者還對Lex和Yacc這兩個常用的編譯相關的工具進行了很詳細的說明，這一點也是很難在國內的教材中看到的。 推薦了這三本教材，都有英文版和中文版的。很多英文好的同學只喜歡看原版的書，不我的感覺是這三本書的翻譯都很不錯，沒有必要特別去買英文版的。理解理論的實質比理解表面的文字更為重要。 編譯原理的實質 幾乎每本編譯原理的教材都是分成詞法分析，語法分析（LL演算法，遞歸下降演算法，LR演算法），語義分析，運行時環境，中間悶悉代碼，代碼生成，代碼優化這些部分。其實現在很多編譯原理的教材都是按照85,86出版的那本龍書來安排教學內容的，所以那本龍書的內容格式幾乎成了現在編譯原理教材的定式，包括國內的教材也是如此。一般來說，大學裡面的本科教學是不可能把上面的所有部分都認真講完的，而是比較偏重於前面幾個部分。像代碼優化那部分東西，就像個無底洞一樣，如果要認真講，就是單獨開一個學期的課也不可能講得清楚。所以，一般對於本科生，對詞法分析和語法分析掌握要求就相對要高一點了。 詞法分析相對來說比較簡單。可能是詞法分析程序本身實現起來很簡單吧，很多沒有學過編譯原理的人也同樣可以寫出各種各樣的詞法分析程序。不過編譯原理在講解詞法分析的時候，重點把正則表達式和自動機原理加了進來，然後以一種十分標準的方式來講解詞法分析程序的產生。這樣的做法道理很明顯，就是要讓詞法分析從程序上升到理論的地步。 語法分析部分就比較麻煩一點了。現在一般有兩種語法分析演算法，LL自頂向下演算法和LR自底向上演算法。LL演算法還好說，到了LR演算法的時候，困難就來了。很多自學編譯原理的都是遇到LR演算法的理解成問題後就放棄了自學。其實這些東西都是只要大家理解就可以了，又不是像詞法分析那樣非得自己寫出來才算真正的會。像LR演算法的語法分析器，一般都是用工具Yacc來生成，實踐中完全沒有比較自己來實現。對於LL演算法中特殊的遞歸下降演算法，因為其實踐十分簡單，那麼就應該要求每個學生都能自己寫。當然，現在也有不少好的LL演算法的語法分析器，不過要是換在非C平台，比如Java,Delphi,你不能運用YACC工具了，那麼你就只有自己來寫語法分析器。 等學到詞法分析和語法分析時候，你可能會出現這樣的疑問：詞法分析和語法分析到底有什麼？就從編譯器的角度來講，編譯器需要把程序員寫的源程序轉換成一種方便處理的數據結構（抽象語法樹或語法樹）,那麼這個轉換的過程就是通過詞法分析和語法分析的。其實詞法分析並非一開始就被列入編譯器的必備部分，只是我們為了簡化語法分析的過程，就把詞法分析這種繁瑣的工作單獨提取出來，就成了現在的詞法分析部分。除了編譯器部分，在其它地方，詞法分析和語法分析也是有用的。比如我們在DOS,Unix,Linux下輸入命令的時候，程序如何分析你輸入的命令形式，這也是簡單的應用。總之，這兩部分的工作就是把不規則的文本信息轉換成一種比較好分析好處理的數據結構。那麼為什麼編譯原理的教程都最終把要分析的源分析轉換成樹這種數據結構呢？數據結構中有Stack,Line,List這么多數據結構，各自都有各自的特點。但是Tree這種結構有很強的遞歸性，也就是說我們可以把Tree的任何結點Node提取出來後，它依舊是一顆完整的Tree。這一點符合我們現在編譯原理分析的形式語言，比如我們在函數裡面使用函樹，循環中使用循環，條件中使用條件等等，那麼就可以很直觀地表示在Tree這種數據結構上。同樣，我們在執行形式語言的程序的時候也是如此的遞歸性。在編譯原理後面的代碼生成的部分，就會介紹一種堆棧式的中間代碼，我們可以根據分析出來的抽象語法樹，很容易，很機械地運用遞歸遍歷抽象語法樹就可以生成這種指令代碼。而這種代碼其實也被廣泛運用在其它的解釋型語言中。像現在流行的Java,.NET，其底層的位元組碼bytecode,可以說就是這中基於堆棧的指令代碼的。 關於語義分析，語法制導翻譯，類型檢查等等部分，其實都是一種完善前面得到的抽象語法樹的過程。比如說，我們寫C語言程序的時候，都知道，如果把一個浮點數直接賦值給一個整數，就會出現類型不匹配，那麼C語言的編譯器是怎麼知道的呢？就是通過這一步的類型檢查。像C++語言這中支持多態函數的語言，這部分要處理的問題就更多更復雜了。大部編譯原理的教材在這部分都是講解一些比較好的處理策略而已。因為新的問題總是在發生，舊的辦法不見得足夠解決。 本來說，作為一個編譯器，起作用的部分就是用戶輸入的源程序到最終的代碼生成。但是在講解最終代碼生成的時候，又不得不講解機器運行環境等內容。因為如果你不知道機器是怎麼執行最終代碼的，那麼你當然無法知道如何生成合適的最終代碼。這部分內容我自我感覺其意義甚至超過了編譯原理本身。因為它會把一個計算機的程序的運行過程都通通排在你面前，你將來可能不會從事編譯器的開發工作，但是只要是和計算機軟體開發相關的領域,都會涉及到程序的執行過程。運行時環境的講解會讓你更清楚一個計算機程序是怎麼存儲，怎麼裝載，怎麼執行的。關於部分的內容，我強烈建議大家看看龍書上的講解，作者從最基本的存儲組織，存儲分配策略，非局部名字的訪問，參數傳遞，符號表到動態存儲分配(malloc,new)都作了十分詳細的說明。這些東西都是我們編寫平常程序的時候經常要做的事情，但是我們卻少去探求其內部是如何完成。 關於中間代碼生成，代碼生成,代碼優化部分的內容就實在不好說了。國內很多教材到了這部分都會很簡單地走馬觀花講過去，學生聽了也只是作為了解，不知道如何運用。不過這部分內容的東西如果要認真講，單獨開一學期的課程都講不完。在《編譯原理及實踐》的書上，對於這部分的講解就恰到好處。作者主要講解的還是一種以堆棧為基礎的指令代碼，十分通俗易懂，讓人看了後，很容易模仿，自己下來後就可以寫自己的代碼生成。當然，對於其它代碼生成技術，代碼優化技術的講解就十分簡單了。如果要仔細研究代碼生成技術，其實另外還有本叫做《》,那本書現在由機械工業出版社引進的，十分厚重，而且是英文原版。不過這本書我沒有把它列為推薦書給大家，畢竟能把龍書的內容搞清楚，在中國已經就算很不錯的高手了，到那個時候再看這本《》也不遲。代碼優化部分在大學本科教學中還是一個不太重要的部分，就是算是實踐過程中，相信大家也不太運用得到。畢竟，自己做的編譯器能正確生成執行代碼已經很不錯了，還談什麼優化呢？ 編譯原理的課程畢竟還只是講解原理的課程，不是專門的編譯技術課程。這兩門課程是有很大的區別的。編譯技術更關注實際的編寫編譯器過程中運用到的技術，而原理的課

4. 計算機專業不需要開設編譯原理課程嗎

隨著信息技術的迅猛發展及其應用領域的不斷深化，幾乎所有專業的研究與應用都離不開信息技術。信息化浪潮對高等教育也帶來非常直接的變化，各專業課程設置無不將計算機知識教育作為其課程設置的組成部分。幾乎所有專業的大學畢業生，都要求掌握基本的計算機操作技能，非計算機專業學生需要通過計算機等級考試，而一些和信息技術密切相關的專業，如電子信息、信息管理、電子商務等，課程設置上與計算機專業更是大量重疊，計算機知識教育在各專業中的滲透程度日漸加劇。1 計算機專業面臨的新挑戰 在計算機知識正在成為各專業基本教育內容的背景下，計算機專業學生的專業優勢受到很大的挑戰，以往在軟硬體知識和應用能力上的獨特優勢似乎在逐漸弱化，與具有特定專業背景的學生相比就業壓力越來越大，由此也引發計算機專業到底學什麼、專什麼的現實思考，我們必須面臨的問題是：計算機專業的學生專業優勢體現在哪裡？ 計算機學科是一門技術性、工程性和應用性很強的學科，並有其基礎理論支撐的科學體系。計算機也是一種使用工具，但那種把工具使用等同於計算機專業的狹隘認識，其思維實際上和十多年前認為「會用計算機打字就是會用計算機」如出一轍。計算機專業學生的優勢應該在於：通過系統的專業原理性知識的學習與訓練，熟練掌握基本的應用技能，並能夠「知其然，且知其所以然」，為此專業基礎課程的熏陶必不可少。而編譯原理就是一門介紹這種原理性知識的綜合性專業基礎課程。 2 編譯原理是計算機專業必不可少的基礎知識 計算機專業的理論基礎對培養學生的計算機專業素養具有非常重要的作用。 在眾多的原理性學習課程中，編譯原理主要承擔了語言實現原理、方法和技術的介紹。人們藉助計算機減輕自己的勞動強度，提高生產率，完成一些人類無法進行的危險、高難度工作。然而所有這些工作都必須藉助程序設計語言書寫的程序來指揮計算機。非機器語言程序功能的實現必須由翻譯程序來完成。正是有了編譯程序、解釋程序、匯編程序等翻譯程序，人們才可以使用自己習慣的語言將需要計算機做的事情描述成程序，並通過這些翻譯程序的工作讓計算機理解並執行。可以說，沒有翻譯程序，計算機不可能象今天這樣得到如此廣泛的普及，網路也不會有今天這樣大的吸引力，我們的生活、學習和工作將會是另一個樣子。 包括編譯程序在內的翻譯程序承擔了實現語言的功能，它所涉及的知識包括形式語言、自動機理論等語言定義、翻譯與實現的基礎知識，這些知識可以讓學生領悟到計算機理論的精髓，可以讓學生從實現的角度重新審視軟體的開發，有助於學生對軟體的真正認識，對於今後從事應用軟體、語言開發平台、編譯系統甚至操作系統開發等都是非常有好處的。同時，編譯原理是許多課程的一個綜合性的實踐，它進一步加深了學生對程序設計語言課程中語言基本單位的定義和作用的理解。例如，編譯程序使用的一些數據結構和演算法是「離散數學」、「數據結構」以及「演算法設計與分析」等課程相關知識的典型應用；編譯程序對目標代碼的存儲組織與分配功能的實現原理又與「操作系統」的相關內容相互滲透；編譯程序對中間代碼的優化功能的實現則是數學、邏輯學、結構程序設計和優化理論的綜合應用和專門化。因此，編譯的原理性研究、學習和實踐，可以多角度提高學生的邏輯思維能力、實踐動手能力、編程調試及綜合應用能力，有助於切實有效地提高學生的專業素質。另外，編譯課程中介紹的知識也是後續許多課程的基礎。所以，編譯原理是計算機專業學生必須掌握的基本原理，編譯原理課程是計算機專業非常重要的專業課程。 盡管經過計算機專業人員的大量努力，大量的工具軟體為我們提供了極大的便利，以至於人們只需要通過若干次點擊滑鼠左鍵就可以方便地完成很多工作，但這並不是說所有問題都已經解決，還有很多深層次的工作需要計算機專業人員去完成。如果我們的計算機專業畢業生也只會「點擊左鍵」，很難想像他們會開發出更好的工具，或對計算機技術的發展作出應有的貢獻。 專業理論基礎的學習，可以培養學生的思維方式和洞察力。計算機技術的更新是非常快的，系統的理論基礎可以讓學生在將來更好地適應新技術，可以讓他們在理論框架的指導下尋找解決問題的方法，朝不同的方向發展！因此，「編譯原理」課程應該是計算機專業必須的重要基礎課。3 編譯技術的應用及需求 編譯原理課程的重要性，不僅僅是因為它所介紹的知識是計算機專業理論知識的重要組成，也在於編譯程序所使用的一些原理、方法和技術在非編譯系統的實際應用中也發揮了很大作用。 例如我們常用的文本編輯工具的實現，涉及到的字詞、語法正確性等內容就是編譯里介紹的詞法分析、語法分析技術的具體應用；又如現在大家上網必不可少的搜索引擎，在處理用戶輸入的查詢要求、對文檔資源的特徵分析、提取與描述等工作中都用到編譯的相關知識；一些特定的應用也可以用到編譯中的方法來解決問題，比如用正規表達式描述網路上某種信息的特徵等。 隨著消費類電子產品的大量開發，嵌入式系統的應用需求也不斷增加。在這種情況下，搭建適合的交叉編譯環境的工作日益重要，急需掌握編譯器構造相關原理、方法和技術的從業人員。這不僅說明了編譯知識的生命力，同時也給高等學校計算機專業的編譯課程設置帶來了新的要求。 現實告訴我們，目前的問題不是計算機專業要不要開設編譯原理課程，而是該如何改進編譯原理的內容與教學方式，以更好地適應社會的需求。4 國內外編譯相關課程的設置情況 我們查閱了國外一些著名的大學計算機專業的課程設置情況，研究了其中與編譯相關的課程安排，發現他們對與編譯相關知識的介紹是非常重視的。 美國麻省理工學院的計算機專業課程設置中，與編譯相關的課程就有Structure and Interpretation of Computer Programs, Computer Language Engineering (包括基本概念、編譯器的功能和結構、基本程序優化技術、理論和實踐的交互作用以及使用工具編制軟體)，Multithreaded Parallelism: Languages and Compilers；加州大學伯克利分校工學院的計算機課程設置中，涉及編譯的課程有Implementation of Programming Languages, Programming Languages and Compilers, Structure and Interpretation of Computer Programs等；英國劍橋大學的計算機科學課程與編譯相關的有Compiler construction 和Advanced compiler design等。 在國內，多年來編譯原理一直是各校特別是教育部所屬高校計算機專業的必修課，曾經也是計算機專業碩士入學考試的必考科目，現在某些學校的計算機專業碩士生入學面試和博士入學考試還必考編譯原理。編譯原理課程在我國計算機專業人材培養中起了很重要的作用，新形勢下開發具有自主知識產權的計算機系統軟、硬體，更需要編譯原理課程繼續發揮作用。5 關於我國計算機專業編譯原理課程設置的建議 一般認為，編譯原理課程是計算機專業最難的課程之一，它是數據結構、語言、演算法和軟體設計等知識的綜合體現，學生對這門課程的理解確實會有一定難度，但這正是教師工作需要解決的問題。實踐證明，如果讓學生認識到了課程內容的重要性，並輔之以合適的教學方法和教學手段，取得良好的教學效果是不難的。 為此，我們思考了新形勢下編譯原理課程所涉及內容的教學及課程設置的改革問題，如果必須改變現有的課程設置模式，我們建議在編譯原理課程的設置上，可以考慮採取以下兩種模式：(1) 課程分解式 將編譯原理課程根據內容分成兩門課：一門為必修，可命名為「編譯技術」，主要介紹一些為滿足基本應用而需要學生掌握的基礎知識、方法、技術，以達到語言實現理論基礎介紹的目的；另一門為選修，可命名為「編譯理論」，主要介紹偏重原理性的、更深層次的內容，方便有進一步深造需要的學生學習。 (2) 內容分解式 可以不單獨設置一門編譯課程，可將課程的內容根據其深淺，涉及到的具體問題，及與其他課程內容的相關性等分解到不同的課程中去，使學生在不同課程的學習中逐步掌握相關知識。 比較兩種模式，後者在目前階段來說還存在一定的難度：一是編譯課程內容的分解不是孤立的，需要與其他課程的內容進行重新整合，因而涉及面太大，短時期內難以做到科學分解與組織；二是增加了其他課程授課教師的工作量與難度，因為他們需要重新考慮、設計新增加的編譯部分內容的教學方法、教學形式等問題，有可能需要在教學實踐中磨合一段時間才能取得好的教學效果。 因此，在現有形勢下，比較可行的還是第一種模式。當然，在經過學科知識點合理的分解與組織之後，可以逐步過渡到第二種模式。

5. 編譯原理課程主講老師是誰

編譯原理主講老師在華東師范大學計算機系任教，講師。 在華東師范大學講授的主要課程包括本科生的《計算機編程實踐》，研究生的《高級演算法》，夜大學和網路學院的《編譯原理》等。個人主要研究興趣方向是不確定推理，智能計算，分布式環境下的計算等。