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