本書結合對現代編譯器設計理論的詳細研究，精心設計了若干個實驗，每個實驗都使用C語言編寫完成，并配有大量的練習，使讀者可以將注意力集中到編程上，真正做到以源代碼為核心。讀者可以親自動手完成這些實驗，在實踐的過程中循序漸進地學習編譯原理的理論知識，進而加深對編譯原理的理解，掌握理論知識在實際中的應用情況，從而將理論知識統一起來。本書還完整描述了一個可運行的小規模語言編譯器(包括源代碼)。
全書包含12個實驗，是一本真正能夠引導讀者動手實踐的書。本書可作為高等院校編譯原理課程的實踐教材，也可作為各類程序開發者、愛好者的閱讀參考書。
本書結合對現代編譯器設計理論的詳細研究，精心設計了若干個實驗，每個實驗都使用C語言編寫完成，并配有大量的練習，使讀者可以將注意力集中到編程上，真正做到以源代碼為核心。
紙上得來終覺淺，絕知此事要躬行。陸游
本書特點眾所周知，編譯原理是計算機知識領域中一個核心的組成部分，也是高校計算機科學專業學生的重要基礎課。同時，編譯原理也是一門實踐性很強的課程。本書通過引導讀者動手進行相應的實驗，進而達到使讀者深刻理解編譯原理的目的。本書非常適合于編譯原理的初學者使用，能夠幫助初學者進行高質量的編譯系統實驗。本書精心設計了若干個實驗題目，使讀者可以逐步地接觸到一個實際編譯系統的源代碼。本書還配置了一個集成度很高的實驗環境CP Lab，在這個集成實驗環境中，讀者可以非常輕松地編輯、編譯和調試源代碼，從而讀者可以將有限的精力放在學習編譯原理上，而不是如何構建實驗環境，或者使用各種工具上。本書會一步一步地帶動讀者通過動手實踐的方式來分析和編寫可以實際工作的源代碼，進而理解編譯原理。現代編譯系統已經變得越來越復雜，雖然本書中的編譯系統是專為教學而設計，相對于一些商用編譯系統已經非常簡化，但是相信本書的很多讀者都是第一次接觸到這樣規模的源代碼。本書在編寫時充分考慮到了這個問題，并做了一些有益的嘗試。為了方便讀者理解，編譯系統的源代碼進行了很多簡化，各個模塊間的耦合性被設計得盡量小，這樣讀者在學習某個模塊時就更容易集中精力。在本書的各個實驗之間也會存在一些交叉的或者重復的內容，有時還會提示讀者回到之前的實驗學習相關的內容，這種螺旋式的學習方法可以幫助讀者從整體上理解編譯原理。本書另外一個著重點就是要讓讀者真正動手實踐。只有通過親身實踐學習到的知識才能夠真正被掌握，而那些僅僅從書本上得到的知識更容易被忘記。本書為了讓讀者在動手實踐的過程中達到做中學的目的，精心設計了12個配套實驗，可以覆蓋編譯原理知識領域中所有重要的模塊和知識點。本書配套的實驗按照由易到難，循序漸進的原則進行設計。前面的若干個實驗以驗證型練習為主，后面的若干個實驗會添加適當的設計型和綜合型練習。在單個實驗內容的安排上，一般會首先帶領讀者閱讀并調試相關模塊的源代碼，并結合相應的編譯原理進行分析。待讀者對源代碼和系統原理熟悉后，再安排讀者對已有代碼進行適當改寫，或者編寫新的代碼。在每個實驗的最后還會提編譯原理實驗教程前言供一些思考與練習的題目，感興趣的讀者可以完成這些題目，從而進一步提高動手實踐能力和創新能力。此外，考慮到在實際工作中，如果一位剛參加工作的程序員參與到一個項目的開發中，項目負責人一定會讓他首先閱讀項目已有的代碼，并在已有代碼的基礎上進行一些小的修改，待他工作一段時間后，對項目有較深入的理解，才能在項目中添加一些復雜的、創新的功能。讀者按照本書提供的實驗進行實踐的過程，與上述過程是完全一致的，這也是本書實驗設計的目的之一。研究表明，圖示具有直觀、簡潔、易于說明事物的客觀現狀或事件的發展過程的特點。在對某一事物或事件進行描述時, 圖示往往比文字更容易被讀者理解和接受。所以，本書不遺余力地使用各種圖示或者表格，力求將枯燥、復雜的編譯原理，以更直觀的方式展現在讀者的面前。而且，本書在適當的地方會從源代碼中引用一些關鍵的代碼片段，并結合編譯原理對這些代碼片段進行詳細講解，讓讀者有一種身臨其境的真實感。閱讀源代碼的建議接下來為讀者閱讀源代碼提供一些有益的建議，希望能夠幫助讀者更順利地閱讀源代碼。首先，讀者應該明確閱讀源代碼的目的，或者說通過閱讀源代碼，讀者能夠學到哪些有用的知識，對讀者參加實際工作會有哪些幫助。最重要的目的當然是理解編譯系統的原理，源代碼能夠幫助讀者將書本上枯燥的理論實例化。雖然讀者親自動手開發一個商業編譯系統的可能性很小，但是編譯系統所使用的許多思想在計算機科學的各個領域有廣泛的適用性，學習系統的內部設計理念對于算法設計和實現、構建虛擬環境、網絡管理等其他多個領域也非常有用。而且，源代碼是精心編寫的高質量源代碼，無論是代碼的組織結構還是代碼的編寫風格，都是按照商業級的規格來完成的，這些在讀者的實際工作中都會有很大的借鑒意義。此外，本書由于篇幅的限制，不可能涉及系統的所有內容，幸好源代碼就是最完全、最準確的文檔，讀者通過學習源代碼，能夠獲得幾倍于本書內容的知識。其次，讀者在開始閱讀源代碼之前，還應該完成一些準備工作。源代碼主要使用C語言編寫，定義較多的數據結構，并盡量使用常用的、簡單的算法來操作這些數據結構，所以讀者需要有比較扎實的C語言程序設計、數據結構和算法的相關知識。在閱讀源代碼時應該使用一些正確的方法，從而達到事半功倍的效果。已經有專門的書籍詳細介紹閱讀源代碼的方法，本書由于篇幅的限制，在這里只能為讀者列舉一些快速而有效的方法。 應該首先搞清楚源代碼的組織方式，例如都包含哪些源代碼文件，這些源代碼文件是如何組織在不同的文件夾中的。這對于讀者快速地了解結構有很大幫助。 重視數據結構。要搞清楚數據結構中各個域的意義，以及使用這些數據結構定義了哪些重要的變量（特別是全局變量）。系統的大部分函數都是在操作由這些數據結構所定義的變量，要搞清楚函數對這些變量進行的操作會產生怎樣的結果。 分析函數的層次和調用關系。要特別注意哪些函數是全局函數，哪些函數是模塊內部使用的函數。 本書對于特別簡單或者特別復雜的函數會一語帶過，讀者也可以在搞清楚這些函數功能的基礎上暫時跳過它們，從而將有限的時間和精力用于學習本書詳細介紹的重要函數。 重視閱讀源代碼文件中的注釋，必要的情況下可以根據自己的理解添加一些注釋。 使用工具提高閱讀源代碼的效率。 每當閱讀完一部分源代碼后，應該認真思考一下，大膽地提出一些問題，例如為什么要這樣編寫？可以不可以用別的方法來編寫？也可以試著向別人介紹自己正在閱讀的源代碼，或者將自己的心得發布到互聯網上。以某種方式表達自己思想的過程，其實就是重新梳理自己知識的過程，這樣能夠讓讀者的知識更加系統化，并且有可能發現被忽略掉的細節。 讀者除了可以完成本書配套的實驗之外，還可以自己設計一些小實驗，例如進行一些修改或者添加一些功能來驗證讀者的想法。參與討論讀者可以使用下面的鏈接登錄本書配套的論壇。論壇中有和讀者一樣對編譯原理感興趣的網友，有本書的編者，還有CP Lab的開發者。讀者在這里提出的問題可以獲得及時準確的解答，提出的意見和建議也可以在本書的下一版中獲得虛心的接納。如果本書有勘誤信息或者更新的章節內容，也會在第一時間發布到論壇上。可以說，有一個高效的團隊在為本書的讀者服務，讀者在使用本書學習的過程中可以獲得持續的支持。http://www.engintime.com/forum/本書由哈爾濱工程大學劉剛、北京英真時代科技有限公司趙鵬翀編著，參編人員包括北京英真時代科技有限公司劉建成等。全書由劉剛進行統稿。本書在撰寫過程中參閱了大量的文獻及資料，特此對這些作者表示誠摯的敬意。編譯技術的發展日新月異，新的技術也不斷出現。由于時間倉促及作者視野的限制，書中難免出現疏漏及不當之處，敬請廣大讀者批評指正。
編者2017年1月
目錄
CP Lab簡介1
實驗1實驗環境的使用3
實驗2NFA到DFA26
實驗3使用Lex自動生成掃描程序48
實驗4消除左遞歸(無替換)62
實驗5消除左遞歸(有替換)74
實驗6提取左因子89
實驗7First集合104
實驗8Follow集合117
實驗9Yacc分析程序生成器132
實驗10符號表的構建和使用137
實驗11三地址碼轉換為P\|代碼146
實驗12GCC編譯器案例綜合研究156
附錄ATINY編譯器和TM機167
參考文獻225第1章數據結構課程設計概述1
1.1數據結構簡介1
1.2課程設計目標和特點2
1.3編寫說明3
1.4課程設計實例的標準格式4
第2章線性表的應用6
2.1存儲結構與基本運算的算法6
2.2集合的交、并運算15
2.3學生成績管理18
2.4多項式求導25
2.5約瑟夫環問題30
2.6數據庫管理系統34
第3章棧的應用58
3.1存儲結構與基本運算的算法58
3.2括號匹配63
3.3漢諾塔問題66
3.4算術表達式求值69
3.5馬踏棋盤76
第4章隊列的應用82
4.1存儲結構與基本運算的算法82
4.2看病排隊候診問題88
4.3數制的轉換91
4.4停車場管理99
4.5基數排序107
第5章串的應用114
5.1存儲結構與基本運算的算法114
5.2KMP算法118
5.3最長公共子串121
5.4大整數計算器123
編譯原理實驗教程目錄第6章多維數組和廣義表的應用130
6.1存儲結構與基本運算的算法130
6.2魔方陣139
6.3稀疏矩陣的加法運算143
6.4本科生導師制問題151
第7章樹狀結構的應用169
7.1存儲結構與基本運算的算法169
7.2線索二叉樹的創建與遍歷172
7.3由遍歷確定二叉樹175
7.4電文的編碼和譯碼177
7.5家族關系查詢系統183
第8章圖狀結構的應用201
8.1存儲結構與基本運算的算法201
8.2地鐵建設問題209
8.3安排教學計劃214
8.4校園導航218
附錄A課程設計實例軟件包224
參考文獻227
新書資訊