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