臺灣博碩士論文加值系統

計算程式切片（Ｐｒｏｇｒａｍ ｓｌｉｃｅｓ）的方法一向被認為是資料流程（ｄ
ａｔａ－ｆｌｏｗ）的問題，但事實上，計算程式切片的過程受到各種程式語言的語
意（ｓｅｍａｎｔｉｃｓ）影響很大，這一點卻是很多研究程式切片的學者所忽略的
。為了說明這個現象，本研究中首先列舉六個實例，以說明許多程式語言的語意如何
影響到程式切片的計算。一個好的程式切片計算方法，除了要正確的算出存在於程式
中的資料流程外，更要能針對不同的程式語言，反應其語意上的差異。換言之，針對
不同的程式語言，就要有不同的程式切片計算方法。
基於這個事實，本研究的次一步工作就是探討利用屬性文法（Ａｔｔｒｉｂｕｔｅ
ｑｒａｍｍａｒ）來計算程式切片的問題，這項研究工作包括以兩個步驟：寫出屬性
文性的規格，和建立一個屬性文法評估器做為程式切片器（ｐｒｏｇｒａｍ ｓｌｉ
ｃｅｒｓ）的核心。程式切片器是一個程式，用來計算程式切片。
採用屬性文法的作法，使得程式切片的計算方法較能夠兼顧到程式語言的語意和資料
流程兩項因素。同時，由於這項方法的改進，針對某一個程式語言的程式切片器可以
用生產（ｇｅｎｅｒａｔｉｏｎ）的方式來製作。對於不同的程式語言，只要更改屬
性文法規格即可，生產的過程較為經濟。
本研究中，將根據一程式語言樣本來討論屬性文法的規格。該程式語言包括：結構化
敘和程序呼叫。程序呼叫可允許真接遞迴，間接遞迴和多重遞迴。針對這樣的程式語
言，本論文中將逐一討論其屬性文法規格，並同時建立一套數學理論，來證明這些屬
性文法規格。
利用這一套數學理論，可以很快的導出在屬性文法評估器中，需要具備何種計算能力
：有兩種計算方法是程式切片所須要的：其中一個是處厘迴路敘述，另一個是處理遞
迴呼叫。

Table of Contents
Abstract
Acknowledgement
List of Tables
List of Figurres
List of Definitions and Theorems
List of Rules
Chapter 1 Introduction
1.1 The Problem of Program Slicing
1.2 An Overview of the Dissertation
Chapter 2 The Influence of Language Semantics on Program Slices
2.1 An Introduction to Program Slicing
2.2 The requirement of Program Slices
2.3 Supporting Observations for Semantic Dependency
2.4 A Summary
Chapter 3 Previous Work Concerning Program Slicers
3.1 Data Influences
3.2 Weiser''s Work
3.3 Yau''s Work
3.4 Bergeretti''s Work
3.5 Farrante''s Work
3.6 A Comparison of these Four Methods
Chapter 4 Insufficiencies of Existing Methods and an Alternative
4.1 Insufficiecies of the Existing Methods
4.2 A Proposal for a New Method
Chapter 5 An Introduction to Attribute Grammare
5.1 The Historical Development of Attribute Grammare
5.2 Basic Definitions for Attribute Grammars
5.3 Attributes Evaluation Methods
Chapter 6 Finding Slices for Structured Statements
6.1 Information Flow Relations and Poset Theory
6.2 An AG Specification for Structured Statements
6.3 Complexity Analysis
Chapter 7 Interprocedural Slicing
7.1 Related Work about Interprocedural Slicing
7.2 An AG Specification for Interprocedural slicing
7.3 A Summary
Chapter 8 Finding SLices for Recursive Procedures
8.1 Problems to Find SLices for Recursive Procedures
8.2 Defining a General recursive Scheme
8.3 Defining Complete SLices for Recursive Procedures
8.4 The Computation Process
8.5 Developing an Algorithm
8.6 A Supporting Example
8.7 An Extension to Multiple and Indirect Recursions
8.8 An AG Specification for Procedural Calls
Chapter 9 some Final Remarks
9.1 Concluding Remarks of the Dissertation
9.2 Future Research Topics
Appendix
Reference