編譯原理

前言

第1章 編譯程序概論

1.1什么是編譯程序

1.2編譯過程概述

1.3編譯程序的結(jié)構(gòu)

1.4編譯階段的組合

1.5編譯技術(shù)和軟件工具

第2章 PL/0編譯程序的實(shí)現(xiàn)

2.1PL/0語言描述

2.1.1PL/0語言的語法描述圖

2.1.2PL/0語言文法的EBNF

表示

2.2PL/0編譯程序的結(jié)構(gòu)

2.3PL/0編譯程序的詞法分析

2.4PL/0編譯程序的語法分析

2.5PL/0編譯程序的目標(biāo)代碼結(jié)構(gòu)

和代碼生成

2.6PL/0編譯程序的語法錯(cuò)誤

處理

2.7PL/0編譯程序的目標(biāo)代碼解釋

執(zhí)行時(shí)的存儲(chǔ)分配

2.8練習(xí)

第3章 文法和語言

3.1文法的直觀概念

3.2符號(hào)和符號(hào)串

3.3文法和語言的形式定義

3.4文法的類型

3.5上下文無關(guān)文法及其語法樹

3.6句型的分析

3.6.1自上而下的分析方法

3.6.2自下而上的分析方法

3.6.3句型分析的有關(guān)問題

3.7有關(guān)文法實(shí)用中的一些說明

3.7.1有關(guān)文法的實(shí)用限制

3.7.2上下文無關(guān)文法中的

ε規(guī)則

3.8練習(xí)

第4章 詞法分析

4.1詞法分析程序的設(shè)計(jì)

4.1.1詞法分析程序與語法

分析程序的接口方式

4.1.2詞法分析程序的輸出

4.1.3將詞法分析工作分離

的考慮

4.2單詞的描述工具

4.2.1正規(guī)文法

4.2.2正規(guī)式

4.2.3正規(guī)文法到正規(guī)式

4.3有窮自動(dòng)機(jī)

4.3.1確定的有窮

自動(dòng)機(jī)（DFA）

4.3.2不確定的有窮

自動(dòng)機(jī)（NFA）

4.3.3NFA→DFA的轉(zhuǎn)換

4.3.4確定有窮自動(dòng)機(jī)的化簡(jiǎn)

4.4正規(guī)式和有窮自動(dòng)機(jī)的等

價(jià)性

5正規(guī)文法和有窮自動(dòng)機(jī)間

的轉(zhuǎn)換

4.6詞法分析程序的自動(dòng)構(gòu)造

工具

4.6.1LEX語言

4.7練習(xí)

第5章 自頂向下語法分析方法

5.1確定的自頂向下分析思想

5.2LL（1）文法的判別

5.3某些非LL（1）文法到LL（1）

文法的等價(jià)變換

5.4不確定的自頂向下分析思想

5.5確定的自頂向下分析方法

5.5.1遞歸子程序法

5.5.2預(yù)測(cè)分析方法

5.6練習(xí)

第6章 自底向上優(yōu)先分析法

6.1自底向上優(yōu)先分析法概述

6.2簡(jiǎn)單優(yōu)先分析法

6.2.1優(yōu)先關(guān)系

6.2.2簡(jiǎn)單優(yōu)先文法的定義

6.2.3簡(jiǎn)單優(yōu)先分析法

6.3算符優(yōu)先分析法

6.3.1直觀算符優(yōu)先分析法

6.3.2算符優(yōu)先文法的定義

6.3.3算符優(yōu)先關(guān)系表的構(gòu)造

6.3.4算符優(yōu)先分析算法

6.3.5優(yōu)先函數(shù)

6.3.6算符優(yōu)先分析法的

局限性

6.4練習(xí)

第7章 LR分析法

7.1LR分析概述

7.2LR（0）分析

7.2.1可歸前綴和子前綴

7.2.2識(shí)別活前綴的有限

自動(dòng)機(jī)

7.2.3活前綴及其可歸前綴的

一般計(jì)算方法

7.2.4LR（0）項(xiàng)目集規(guī)范族

的構(gòu)造

7.3SLR（1）分析

7.4LR（1）分析

7.4.1LR（1）項(xiàng)目集族的

構(gòu)造

7.4.2LR（1）分析表的構(gòu)造

7.5LALR（1）分析

7.6二義性文法在LR分析中

的應(yīng)用

7.7練習(xí)

第8章 語法制導(dǎo)翻譯和中間代碼生成

8.1屬性文法

8.2語法制導(dǎo)翻譯概論

8.3中間代碼的形式

8.3.1逆波蘭記號(hào)

8.3.2三元式和樹形表示

8.3.3四元式

8.4簡(jiǎn)單賦值語句的翻譯

8.5布爾表達(dá)式的翻譯

8.5.1布爾表達(dá)式的翻譯方法

8.5.2控制語句中布爾表達(dá)式

的翻譯

8.6控制結(jié)構(gòu)的翻譯

8.6.1條件轉(zhuǎn)移

8.6.2開關(guān)語句

8.6.3for循環(huán)語句

8.6.4出口語句

8.6.5goto語句

8.6.6過程調(diào)用的四元式產(chǎn)生

8.7說明語句的翻譯

8.7.1簡(jiǎn)單說明句的翻譯

8.7.2過程中的說明

8.8數(shù)組和結(jié)構(gòu)的翻譯

8.8.1數(shù)組說明和數(shù)組元

素的引用

8.8.2結(jié)構(gòu)（記錄）說明和引

用的翻譯

8.9練習(xí)

第9章 符號(hào)表

9.1符號(hào)表的作用和地位

9.2符號(hào)的主要屬性及作用

9.3符號(hào)表的組織

9.3.1符號(hào)表的總體組織

9.3.2符號(hào)表項(xiàng)的排列

9.3.3關(guān)鍵字域的組織

9.3.4其它域的組織

9.3.5下推鏈域的組織

9.4符號(hào)表的管理

9.4.1符號(hào)表的初始化

9.4.2符號(hào)的登錄

9.4.3符號(hào)的查找

9.4.4符號(hào)表中分程序結(jié)構(gòu)

層次的管理

9.5練習(xí)

第10章 目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織

10.1數(shù)據(jù)空間的三種不同使用方法和

管理方法

10.1.1靜態(tài)存儲(chǔ)分配

10.1.2動(dòng)態(tài)存儲(chǔ)分配

10.1.3棧式動(dòng)態(tài)存儲(chǔ)分配

10.1.4堆式動(dòng)態(tài)存儲(chǔ)分配

10.2棧式存儲(chǔ)分配的實(shí)現(xiàn)

10.2.1簡(jiǎn)單的棧式存儲(chǔ)分配的

實(shí)現(xiàn)

10.2.2嵌套過程語言的棧式

實(shí)現(xiàn)

10.2.3分程序結(jié)構(gòu)的存儲(chǔ)

管理

10.3參數(shù)傳遞

10.3.1傳值

10.3.2傳地址

10.3.3過程參數(shù)

10.4過程調(diào)用、過程進(jìn)入和過程

返回

10.5練習(xí)

第11章 代碼優(yōu)化

11.1優(yōu)化技術(shù)簡(jiǎn)介

11.1.1優(yōu)化技術(shù)簡(jiǎn)介

11.2局部?jī)?yōu)化

11.2.1基本塊的劃分

11.2.2基本塊的變換

11.2.3基本塊的DAG表示

11.2.4DAG的應(yīng)用

11.2.5DAG構(gòu)造算法討論

11.3控制流分析和循環(huán)優(yōu)化

11.3.1程序流圖與循環(huán)

11.3.2循環(huán)

11.3.3循環(huán)的查找

11.3.4可歸約流圖

11.3.5循環(huán)優(yōu)化

11.4數(shù)據(jù)流的分析與全局優(yōu)化

11.4.1一些主要的概念

11.4.2數(shù)據(jù)流方程的一般

形式

11.4.3到達(dá)一定值數(shù)據(jù)流

方程

11.4.4可用表達(dá)式及其數(shù)據(jù)

流方程

11.4.5活躍變量數(shù)據(jù)流方程

11.4.6復(fù)寫傳播

11.5練習(xí)

第12章 代碼生成

12.1代碼生成概述

12.2一個(gè)計(jì)算機(jī)模型

12.3一個(gè)簡(jiǎn)單的代碼生成器

12.3.1寄存器分配的原則

12.3.2待用信息鏈表法

12.3.3代碼生成算法

12.4代碼生成研究現(xiàn)狀

12.4.1中間語言的選擇

12.4.2代碼生成的自動(dòng)化

研究

12.5練習(xí)

第13章 編譯程序?qū)崿F(xiàn)的途徑

13.1編譯程序的書寫語言與T

型圖

13.2編譯程序的自展技術(shù)

13.3交叉編譯與編譯程序的移植

13.4編譯程序的構(gòu)造工具

13.4.1基于LALR（1）的語法

分析程序的生成器

YACC

13.4.2基于LL（2）文法的編

譯器的構(gòu)造工具

（SD&EBNF－LL（2））

13.4.3詞法分析程序的

生成器LEX

13.5練習(xí)

附錄A PL/0編譯程序文本

附錄B 詞法分析程序生成器LEx的使

用方法

B.1LEX概述

B.2LEX源程序的格式

B.3LEX用的正規(guī)式

B.4LEX源程序中的動(dòng)作

B.5識(shí)別規(guī)則的二義性

B.6LEX源程序中的輔助定義

部分

B.7怎樣在UNIX系統(tǒng)中使

用LEX

B.8LEX源程序例子

B.9再談上下文相關(guān)性的處理

B.10LEX源程序格式總結(jié)

附錄C 語法分析程序自動(dòng)產(chǎn)生器YACC

的使用方法

C.1YACC概述

C.2YACC源程序的一般格式

C.3YACC源程序說明部分的寫法

C.3.1頭文件表

C.3.2宏定義

C.3.3數(shù)據(jù)類型定義

C.3.4全局變量定義

C.3.5語法開始符定義

C.3.6語義值類型定義

C.3.7終結(jié)符定義

C.3.8運(yùn)算符優(yōu)先級(jí)及結(jié)合

性定義

C.4YACC源程序中語法規(guī)則部分

的寫法

C.4.1語法規(guī)則的書寫格式

C.4.2語義動(dòng)作

C.4.3YACC解決二義性和沖突

的方法

C.4.4語法分析中的錯(cuò)誤

處理

C.5程序段部分

C.5.1主程序

C.5.2錯(cuò)誤信息報(bào)告程序

C.5.3詞法分析程序

C.5.4其它程序段

C.6YACC源程序例子說明

C.6.1YACC的源程序例1

C.6.2YACC的源程序例2

附錄D 編譯原理實(shí)驗(yàn)要求

附錄E 編譯原理輔助教學(xué)軟件功能介紹

和使用說明

E.1功能介紹

E.1.1THPLoCAI的功能

E.1.2TH－CCAIS的功能

E.2使用說明

E.2.1THPLoCAI使用說明

E.2.2TH－CCAIS使用說明

E.2.3其它補(bǔ)充說明

參考文獻(xiàn)