利用屬性文法尋找程式切片之研究

Abstract

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