“編譯原理”是計算機科學與技術(shù)專業(yè)重要的專業(yè)(基礎(chǔ))課程。 本書是普通高等教育“十二五”國家級規(guī)劃 教材,也是國家精品課程、國家級精品資源共享課程主講教材,是作者合三十余年在哈爾濱工業(yè)大學、北京工業(yè)大學講授該課程的經(jīng)驗和體會,根據(jù)將其作為本科生專業(yè)技術(shù)基礎(chǔ)課教學的實際需要選擇和組織有關(guān)內(nèi)容撰寫而成的,包含了“編譯原理”課程所需涵蓋的知識。 本書將以知識為載體,對本學科問題求解的典型思想和方法進行探討,致力于學生四大專業(yè)基本能力的培養(yǎng),為 “能力導向”的課程教學提供有力支持。 為了便于讀者學習和掌握有關(guān)內(nèi)容,面向工程應(yīng)用型學生的培養(yǎng),在附 錄中給出了相應(yīng)的課程設(shè)計。 本書適合于高等學校計算機科學與技術(shù)學科本科生“編譯原理”課程教學使用,也可供有關(guān)專業(yè)的學生、教 師和科研人員參考。
從2006年開始,計算機科學與技術(shù)專業(yè)作為我國工程教育專業(yè)認證的試點專業(yè)之一,便開始了旨在追求國際等效的工程教育專業(yè)認證工作。2016年6月,我國成為《華盛頓協(xié)議》的正式成員,標志著我國的工程教育在實現(xiàn)國際接軌上邁出了極其重要的一步。從一定意義上講,那些通過工程教育專業(yè)認證的計算機類專業(yè)點的教育是國際等效的。目前,加快包括計算機科學與技術(shù)專業(yè)在內(nèi)的計算機類專業(yè)的內(nèi)涵發(fā)展步伐,快速提升專業(yè)教育水平和質(zhì)量,使2785個計算機類專業(yè)的專業(yè)點有更多達到工程教育專業(yè)認證的標準,是我們共同的追求。
按照《華盛頓協(xié)議》,兩年制?,定位于培養(yǎng)學生解決狹義工程問題的能力;三年制的大專教育,定位于培養(yǎng)學生解決廣義工程問題的能力;而本科教育,定位于培養(yǎng)學生解決復雜工程問題的能力。中國工程教育專業(yè)認證協(xié)會發(fā)布的《工程教育認證標準(2015版)》和《華盛頓協(xié)議》所給的畢業(yè)要求標準,明確地聚焦到了這一基本定位。
那么,什么是復雜工程問題?《華盛頓協(xié)議》用如下7個特征進行刻畫。其中第(1)條是必備的,第(2)到第(7)條是可選的。必備的條款指出了復雜工程問題的本質(zhì),可選的條款可以看作是復雜工程問題的表象。
。1)必須運用深入的工程原理經(jīng)過分析才可能解決;
。2)需求涉及多方面的技術(shù)、工程和其他因素,并可能相互有一定沖突;
。3)需要通過建立合適的抽象模型才能解決,在建模過程中需要體現(xiàn)出創(chuàng)造性;
。4)不是僅靠常用方法就可以完全解決的;
(5)問題中涉及的因素可能沒有完全包含在專業(yè)標準和規(guī)范中;
。6)問題相關(guān)各方利益不完全一致;
(7)具有較高的綜合性,包含多個相互關(guān)聯(lián)的子問題。
“編譯原理”的教學內(nèi)容幾乎吻合了以上全部條款。它包含求解計算機問題和利用計算機技術(shù)求解問題的基本原理、最典型最基本的方法;編譯原理課程所涉及的問題都需要進行深入的分析;這些問題的解決必須建立恰當?shù)某橄竽P,并基于模型進行分析和處理;很多問題需要根據(jù)設(shè)計開發(fā)的實際,綜合運用恰當?shù)姆椒,要在多種因素和“指標”中進行折中,以求全局的優(yōu)化和良好的系統(tǒng)性能;不僅要設(shè)計和實現(xiàn)詞法分析器、語法分析器、語義分析器、代碼優(yōu)化器、代碼生成器等一系列子系統(tǒng),還要對它們進行綜合和集成,以構(gòu)成編譯系統(tǒng)。所以,該課程不僅使學生掌握“基本原理”“基本技術(shù)”“基本方法”,還提供了一個使學生經(jīng)歷計算機“復雜工程”構(gòu)建過程的機會——構(gòu)建一個適當規(guī)模的教學型編譯系統(tǒng)。難怪許多年以前,AlfredV.Aho就在其編著的《編譯原理》的開篇寫道“編寫編譯器的原理和技術(shù)具有十分普遍的意義,以至于在每個計算機科學家的研究生涯中,本書中的原理和技術(shù)都會反復用到。”
就我國目前的教育需求來看,我們不再將編譯原理這門課程當作專業(yè)課,而是作為專業(yè)技術(shù)基礎(chǔ)課,旨在向?qū)W生傳授計算機問題求解的基本思想和方法,引導他們經(jīng)歷“復雜工程問題”的求解過程,培養(yǎng)他們包括計算思維能力(狹義的,包括模型的認知、建立和使用在內(nèi))、算法設(shè)計與分析能力、程序設(shè)計與實現(xiàn)能力、系統(tǒng)能力在內(nèi)的專業(yè)能力,以及承擔解決復雜工程問題相關(guān)的非技術(shù)性能力和素質(zhì)。
按照人才培養(yǎng)方案的系統(tǒng)化設(shè)計和實施的要求,本門課程將具體支持相關(guān)畢業(yè)要求的達成。雖然這門課程全面地體現(xiàn)了支持培養(yǎng)學生解決復雜工程問題能力的需要,我們還是將其目標主要集中在3個方面,并認為通過恰當?shù)慕虒W設(shè)計,對另外3個方面也會提供相應(yīng)的支撐,具體我們將在附錄中給出。
蔣宗禮,北京工業(yè)大學教授,博士生導師,國家教學名師,CCF杰出教育獎獲得者,中國工程教育專業(yè)認證資深專家。
1978年3月至1984年7月在哈爾濱工業(yè)大學計算機學科學習,先后到美國、加拿大進修,1984年起先后在哈爾濱工業(yè)大學和北京工業(yè)大學主講編譯原理、形式語言與自動機理論、數(shù)據(jù)庫系統(tǒng)原理、人工神經(jīng)網(wǎng)絡(luò)、新生研討課等課程。
國家精品課程、國家精品資源共享課程“編譯原理”負責人,主編國家“十一五”“十二五”規(guī)劃教材(包括國家普通高等教育精品教材1部,市精品教材多部),《人工神經(jīng)網(wǎng)絡(luò)導論》等研究生教材,國家優(yōu)秀教學團隊負責人。獲國家教學成果獎2項,各種省市級教學、科研成果20余項。曾獲中國高校優(yōu)秀青年學者、寶鋼優(yōu)秀教師、航天部優(yōu)秀青年教師等榮譽稱號。
主要學術(shù)兼職有全國工程教育專業(yè)認證協(xié)會學術(shù)委員會、結(jié)論審議委員會、計算機類專業(yè)認證委員會委員,教育部高校計算機類專業(yè)教學指導委員會副主任,全國高校計算機教育研究會副理事長,中國計算機學會教育專業(yè)委員會副主任。
姜守旭,哈爾濱工業(yè)大學教授,教學帶頭人,博士生導師,黑龍江省師德先進個人,寶鋼優(yōu)秀教師獎獲得者,國家優(yōu)秀教學團隊骨干成員,中國工程教育專業(yè)認證專家。
1986年9月至1990年7月在哈爾濱工業(yè)大學計算機系學習,1993年以來在哈爾濱工業(yè)大學主講編譯原理、數(shù)據(jù)庫系統(tǒng)、集合論與圖論等課程。
主要從事普適計算、無線網(wǎng)絡(luò)、智能交通系統(tǒng)、物聯(lián)網(wǎng)等方面的研究,主持或參加國家973計劃、國家自然科學基金重點及面上、國防預研及省部級科研項目等20余項,獲省部級科技進步三等獎2項,獲國家教學成果二等獎1項、省級教學成果一等獎1項、二等獎1項,在VLDB、ICDE、VLDB Journal、TKDE、軟件學報等國內(nèi)外重要學術(shù)會議或?qū)W術(shù)刊物上發(fā)表學術(shù)論文60余篇,編著國家“十一五”“十二五”規(guī)劃教材(包括國家精品教材1部,市精品教材多部)、譯著1部,國家精品資源共享課“集合論與圖論”和黑龍江省精品課“編譯原理”負責人,國家雙語教學示范課和黑龍江省精品課“形式語言”骨干成員。
第1章 引論
1.1 程序設(shè)計語言
1.2 程序設(shè)計語言的翻譯
1.3 編譯程序的總體結(jié)構(gòu)
1.4 編譯程序的組織
1.5 編譯程序的生成
1.6 本章小結(jié)
習題
第2章 高級語言及其文法
2.1 語言概述
2.2 基本定義
2.3 文法的定義
2.4 文法的分類
2.5 CFG的語法樹
2.6 CFG的二義性
2.7 本章小結(jié)
習題
第3章 詞法分析
3.1 詞法分析器的功能
3.1.1 單詞的分類與表示
3.1.2 詞法分析器的輸出
3.1.3 源程序的輸入緩沖與預處理
3.1.4 詞法分析階段的錯誤處理
3.1.5 詞法分析器的位置
3.2 單詞的描述
3.2.1 正則文法
3.2.2 正則表達式
3.2.3 正則表達式與正則文法的等價性
3.2.4 有窮狀態(tài)自動機
3.2.5 狀態(tài)轉(zhuǎn)換圖
3.2.6 正則表達式轉(zhuǎn)換為狀態(tài)轉(zhuǎn)換圖
3.3 單詞的識別
3.3.1 有窮狀態(tài)自動機與單詞識別的關(guān)系
3.3.2 單詞識別的狀態(tài)轉(zhuǎn)換圖表示
3.3.3 幾種典型的單詞識別問題
3.3.4 狀態(tài)轉(zhuǎn)換圖的實現(xiàn)
3.3.5 詞法分析程序的編寫
3.4 詞法分析程序的自動生成
3.4.1 Lex源程序
3.4.2 Lex的實現(xiàn)原理
3.5 本章小結(jié)
習題
第4章 自頂向下的語法分析
4.1 語法分析概述
4.2 自頂向下的語法分析面臨的問題與文法的改造
4.2.1 自頂向下分析面臨的問題
4.2.2 對上下文無關(guān)文法的改造
4.2.3 11(1)文法
4.3 預測分析法
4.3.1 預測分析器的構(gòu)成
4.3.2 預測分析表的構(gòu)造
4.3.3 預測分析中錯誤的處理
4.4 遞歸下降分析法
4.4.1 遞歸下降分析法的基本思想
4.4.2 語法圖和遞歸子程序法
4.4.3 基于語法圖的語法分析器的工作方式
4.4.4 語法圖的化簡與實現(xiàn)
4.4.5 遞歸子程序法的實現(xiàn)步驟
4.5 本章小結(jié)
習題
第5章 自底向上的語法分析
5.1 自底向上的語法分析概述
5.1.1 移進-歸約分析
5.1.2 優(yōu)先法
5.1.3 狀態(tài)法
5.2 算符優(yōu)先分析法
5.2.1 算符優(yōu)先文法
5.2.2 算符優(yōu)先矩陣的構(gòu)造
5.2.3 算符優(yōu)先分析算法
5.2.4 優(yōu)先函數(shù)
5.2.5 算符優(yōu)先分析的出錯處理
5.3 LR分析法
5.3.1 LR分析算法
5.3.2 LR(O)分析表的構(gòu)造
5.3.3 SLR(1)分析表的構(gòu)造
5.3.4 LR(1)分析表的構(gòu)造
5.3.5 LALR(1)分析表的構(gòu)造
5.3.6 二義性文法的應(yīng)用
5.3.7 LR分析中的出錯處理
5.4 語法分析程序的自動生成工具Yacc
5.4.1 Yacc源程序的結(jié)構(gòu)
5.4.2 Yacc源程序的聲明部分
5.4.3 Yacc源程序的規(guī)則部分
5.4.4 Yacc源程序的例程部分
5.4.5 Yacc對二義性文法的處理
5.4.6 Yacc的出錯處理
5.5 本章小結(jié)
習題
第6章 語法制導翻譯與屬性文法
6.1 語法制導翻譯概述
6.2 語法制導定義
6.3 屬性計算
6.3.1 依賴圖
6.3.2 屬性的計算順序
6.3.3 S-屬性定義
6.3.4 1-屬性定義
6.3.5 屬性計算示例
6.4 翻譯模式
6.4.1 翻譯模式與語義動作的執(zhí)行時機
6.4.2 S-屬性定義的自底向上翻譯
6.4.3 1-屬性定義的自頂向下翻譯
6.4.4 1-屬性定義的自底向上翻譯
6.5 本章小結(jié)
習題
第7章 語義分析與中間代碼生成
7.1 中間代碼的形式
7.1.1 逆波蘭表示
7.1.2 三地址碼
7.1.3 圖表示
7.2 聲明語句的翻譯
……
第8章 符號表管理
第9章 運行時的存儲組織
第10章 代碼優(yōu)化
第11章 代碼生成
附錄 “編譯原理”課程教學設(shè)計
縮寫符號
詞匯索引
參考文獻