編譯原理

前言

第1章 編譯程序概論

1.1什么是編譯程序

1.2編譯過程概述

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

1.4編譯階段的組合

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

第2章 PL/0編譯程序的實現(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編譯程序的目標代碼結(jié)構(gòu)

和代碼生成

2.6PL/0編譯程序的語法錯誤

處理

2.7PL/0編譯程序的目標代碼解釋

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

2.8練習

第3章 文法和語言

3.1文法的直觀概念

3.2符號和符號串

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)文法實用中的一些說明

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

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

ε規(guī)則

3.8練習

第4章 詞法分析

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

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有窮自動機

4.3.1確定的有窮

自動機（DFA）

4.3.2不確定的有窮

自動機（NFA）

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

4.3.4確定有窮自動機的化簡

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

價性

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

的轉(zhuǎn)換

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

工具

4.6.1LEX語言

4.7練習

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

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

5.2LL（1）文法的判別

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

文法的等價變換

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

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

5.5.1遞歸子程序法

5.5.2預(yù)測分析方法

5.6練習

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

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

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

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

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

6.2.3簡單優(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練習

第7章 LR分析法

7.1LR分析概述

7.2LR（0）分析

7.2.1可歸前綴和子前綴

7.2.2識別活前綴的有限

自動機

7.2.3活前綴及其可歸前綴的

一般計算方法

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

的構(gòu)造

7.3SLR（1）分析

7.4LR（1）分析

7.4.1LR（1）項目集族的

構(gòu)造

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

7.5LALR（1）分析

7.6二義性文法在LR分析中

的應(yīng)用

7.7練習

第8章 語法制導翻譯和中間代碼生成

8.1屬性文法

8.2語法制導翻譯概論

8.3中間代碼的形式

8.3.1逆波蘭記號

8.3.2三元式和樹形表示

8.3.3四元式

8.4簡單賦值語句的翻譯

8.5布爾表達式的翻譯

8.5.1布爾表達式的翻譯方法

8.5.2控制語句中布爾表達式

的翻譯

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簡單說明句的翻譯

8.7.2過程中的說明

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

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

素的引用

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

用的翻譯

8.9練習

第9章 符號表

9.1符號表的作用和地位

9.2符號的主要屬性及作用

9.3符號表的組織

9.3.1符號表的總體組織

9.3.2符號表項的排列

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

9.3.4其它域的組織

9.3.5下推鏈域的組織

9.4符號表的管理

9.4.1符號表的初始化

9.4.2符號的登錄

9.4.3符號的查找

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

層次的管理

9.5練習

第10章 目標程序運行時的存儲組織

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

管理方法

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

10.1.2動態(tài)存儲分配

10.1.3棧式動態(tài)存儲分配

10.1.4堆式動態(tài)存儲分配

10.2棧式存儲分配的實現(xiàn)

10.2.1簡單的棧式存儲分配的

實現(xiàn)

10.2.2嵌套過程語言的棧式

實現(xiàn)

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

管理

10.3參數(shù)傳遞

10.3.1傳值

10.3.2傳地址

10.3.3過程參數(shù)

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

返回

10.5練習

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

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

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

11.2局部優(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到達一定值數(shù)據(jù)流

方程

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

流方程

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

11.4.6復(fù)寫傳播

11.5練習

第12章 代碼生成

12.1代碼生成概述

12.2一個計算機模型

12.3一個簡單的代碼生成器

12.3.1寄存器分配的原則

12.3.2待用信息鏈表法

12.3.3代碼生成算法

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

12.4.1中間語言的選擇

12.4.2代碼生成的自動化

研究

12.5練習

第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練習

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

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

用方法

B.1LEX概述

B.2LEX源程序的格式

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

B.4LEX源程序中的動作

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

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

部分

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

用LEX

B.8LEX源程序例子

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

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

附錄C 語法分析程序自動產(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ōu)先級及結(jié)合

性定義

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

的寫法

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

C.4.2語義動作

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

的方法

C.4.4語法分析中的錯誤

處理

C.5程序段部分

C.5.1主程序

C.5.2錯誤信息報告程序

C.5.3詞法分析程序

C.5.4其它程序段

C.6YACC源程序例子說明

C.6.1YACC的源程序例1

C.6.2YACC的源程序例2

附錄D 編譯原理實驗要求

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

和使用說明

E.1功能介紹

E.1.1THPLoCAI的功能

E.1.2TH－CCAIS的功能

E.2使用說明

E.2.1THPLoCAI使用說明

E.2.2TH－CCAIS使用說明

E.2.3其它補充說明

參考文獻