【摘要】：文法件是一類用文法描述和解答問題的系統(tǒng),其測試工作不同于其他程序:文法件的測試用例是符合文法規(guī)則的句子,獲取途徑主要是各種句子生成算法;文法件的測試代價通常較高,實踐中要求使用少量高質(zhì)量的測試用例發(fā)現(xiàn)盡可能多的錯誤。因此,生成具有較高檢錯效率的句子成為了文法件測試的重要課題�，F(xiàn)有句子生成算法中,基于規(guī)則覆蓋方式生成的句子集合在實際測試中因句子不足導(dǎo)致檢錯能力低下,需使用隨機生成方式進行補充。隨機生成方式雖然可以彌補規(guī)則覆蓋方式的不足,但生成的句子可能存在相似甚至相同的情況,導(dǎo)致測試效率降低。本文通過引入自適應(yīng)隨機測試方法,使隨機生成的句子均勻分布,從而提高句子質(zhì)量與測試效率。本文通過實驗驗證了句子隨機生成方式對規(guī)則覆蓋方式的補充作用;針對隨機生成方式在實踐中存在的循環(huán)問題,提出設(shè)置最大推導(dǎo)次數(shù)加以解決。給出了句子自適應(yīng)隨機生成算法框架,對關(guān)鍵的距離定義問題進行深入探討。根據(jù)文法件輸入域特征,從字符串、產(chǎn)生式狀態(tài)、樹結(jié)構(gòu)三個角度為句子距離提出了若干假設(shè),并通過理論分析、直覺判斷、實驗驗證對每種距離進行了一一研究。此外,本文還闡述了句子枚舉與自適應(yīng)隨機測試的結(jié)合應(yīng)用。實驗表明,以產(chǎn)生式樹編輯距離作為句子距離定義有理論上的依據(jù),符合直覺上的判斷,在各實驗中表現(xiàn)良好,在計算效率上處于優(yōu)勢,是句子距離的合理定義。句子自適應(yīng)隨機生成方法在以產(chǎn)生式樹編輯距離為距離定義時,生成的句子普遍具有較高的測試質(zhì)量,可有效提高文法件的測試效率。
[Abstract]:Grammars are a class of systems which describe and solve problems by grammar. Their test work is different from other programs. The test cases of grammar parts are sentences that conform to the rules of grammar. The cost of testing grammars is usually high. In practice, a small number of high-quality test cases are required to detect as many errors as possible. Therefore, the generation of sentences with high error detection efficiency has become an important task in grammar testing. In the existing sentence generation algorithms, the sentence set generated by the rule coverage method has low error detection ability due to the lack of sentence in the actual test, so it needs to be supplemented by random generation method. Although random generation can make up for the lack of rule coverage, the generated sentences may have similar or even the same situation, resulting in lower test efficiency. In this paper, the adaptive random test method is introduced to make the randomly generated sentences distribute uniformly, thus improving the sentence quality and testing efficiency. This paper verifies the supplementary function of the random generation of sentences to the rule coverage through experiments, and puts forward setting the maximum derivation times to solve the cycle problem of random generation in practice. A framework of adaptive random sentence generation algorithm is presented, and the key problem of distance definition is discussed in detail. According to the input field features of grammar pieces, some assumptions about sentence distance are put forward from three angles: string, production state and tree structure. Through theoretical analysis, intuitive judgment, and experimental verification, each distance is studied one by one. In addition, this paper also describes the combination of sentence enumeration and adaptive random test. The experimental results show that the definition of sentence distance based on production tree editing distance has theoretical basis and is in accordance with intuitive judgment. It is a reasonable definition of sentence distance because of its good performance in each experiment and its advantage in computing efficiency. When the distance is defined by the distance of production tree, the generated sentences generally have high test quality and can effectively improve the test efficiency of grammar parts.
【學(xué)位授予單位】：華僑大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP311.53

【參考文獻】

相關(guān)期刊論文 前1條

1 ;Linear algorithm for lexicographic enumeration of CFG parse trees[J];Science in China(Series F:Information Sciences);2009年07期

，

本文編號：2392849