一種基于改進PCFG句法分析的需求模板符合性檢查優化方法

曹步展，王立松，康介祥，高忠杰，王 輝，尹 偉，于夢元

1(南京航空航天大學 計算機科學與技術學院，南京 210000) 2(中國航空無線電電子研究所 軟件部，上海 200233)

1 引 言

在軟件工程領域中，軟件需求通常采用自然語言描述.自然語言擁有易于理解，且適用于多種領域的需求描述等優點.但與此同時，自然語言在運用過程中可能會帶有歧義，導致難以自動分析等問題.因此，軟件需求的描述可能存在二義性、不完整性等特點[1].需求工程(Requirement Engineering，RE)是軟件開發的基礎[2].在需求工程中，使用需求模板對自然語言需求進行規范化，則能夠盡可能地減少歧義.需求模板是對需求的一種規范描述[3]，是減少自然語言需求中二義性的一種有效工具[4].它能夠使自然語言需求更加易于自動分析，因此被廣泛應用于航空電子、汽車工業、核工業等安全關鍵領域中.同時，需求模板符合性檢查是自然語言處理在需求領域的重要研究方向.傳統的手工檢查不僅耗時耗力，而且當需求發生變化時，還需要反復進行符合性檢查，因此效率較為低下.針對這一問題，許多學者展開了研究，并提出了一些基于組塊分析的需求模板符合性自動檢查方法[5-8].這些方法大大提高了需求模板符合性檢查的效率.圖1展示了常用的需求模板之一，Rupp模板[9].除此之外，還有EARS模板[10].

圖1 Rupp模板[9]

在需求模板符合性檢查方法中，最重要的是組塊分析，分為名詞組塊分析和動詞組塊分析[5-8].現有方法是只根據分詞和詞性標注的結果，按照一定的規則將幾個連續的單詞序列組合成名詞組塊或者動詞組塊.與完整的句法分析相比，組塊分析有復雜性低、可擴展性好、健壯性好等優勢，并且句法分析不能保證生成一棵句法分析樹.然而，僅僅通過組塊分析并不能最終準確地提取出最佳的名詞短語或動詞短語，因此書寫需求的工作者需要避免使用過于復雜的名詞短語.然而，在部分場合中為了將需求的參與者或者對象描述清楚，不得不使用較為復雜的名詞短語.現有的很多方法[5-8]僅使用組塊分析，并未采用句法分析樹，因此只能找到組成復雜短語的原子短語，而不能揭示需求語句的完整語義，無法識別復雜的短語，進而導致難以提取最佳的組塊.

針對以上問題，本文提出一種基于改進PCFG句法分析的需求模板符合性檢查方法，對需求進行句法分析，然后提取解析器得到的所有名詞組塊.根據詞性、名詞組塊以及動詞組塊，提取出需求中所有的建模元素，通過建模元素判斷需求是否符合模板.這種基于改進PCFG句法分析的需求模板符合性檢查方法，考慮了結構之間的依存關系、詞匯對句法結構的影響以及上下文間單詞詞性的相互影響，具有較高的準確率.

2 PCFG4TCC方法

本節介紹一種基于改進PCFG句法分析的需求模板符合性檢查方法——PCFG4TCC方法.該方法主要用到了自然語言處理的關鍵技術之一，即句法分析.作為自然語言處理的一個關鍵環節，句法分析的主要任務是確定句子的句法結構或句子中詞匯之間的依存關系.句法分析分為句法結構分析和依存關系分析.句法結構分析又稱為句法成分分析或短語結構分析.獲取整個句子的句法結構稱為完全句法分析或完全短語結構分析.獲得局部成分的句法分析稱為局部分析或淺層分析.依存關系分析又稱為依存句法分析或依存結構分析，簡稱依存分析.

2.1 組塊分析

組塊分析是一項核心的NLP技術，是局部句法分析的一個重要任務.簡而言之，組塊分析是將句子劃分為幾個不重疊的片段的過程.組塊分析最重要的部分是名詞組塊分析和動詞組塊分析，即提取出句子中的名詞短語和動詞短語.名詞短語是動詞的主語或賓語.動詞短語(VP)有時也被稱為動詞詞組，是一個包含動詞、情態動詞、助詞和修飾語(通常是副詞)的片段.組塊具有扁平結構，而由自然語言處理解析器(如Stanford Parser[11])產生的片段可以有任意深度.

組塊分析比起句法分析有兩個主要的優勢：計算成本較低，計算復雜度為O(n)，其中n表示句子的長度，而相比之下，句法分析的復雜度為O(n3)；其次，組塊分析必然會產生輸出結果，而句法分析無法保證產生語法解析樹，由此可見組塊分析方法擁有較好的魯棒性.

組塊分析的具體步驟如下.

1)分詞.通過分詞，將需求文檔分割成若干個單詞和數字，并標注上Token的標簽.Token可以是單詞、數字或者符號.

2)進行分句，將需求文檔劃分為若干個句子，并標注上Sentence的標簽.

3)進行詞性標注，對句子中的每個單詞和數字按照其詞性進行分類，在Token標簽上加上詞性(名詞、動詞或者形容詞等).詞性標注一般使用Penn Treebank標注集.

4)進行組塊分析，組塊分析主要可分為名詞組塊分析和動詞組塊分析.使用RETA Chunker和OpenNLP Chunker進行名詞組塊分析，即提取出名詞短語，并將名詞短語標注上NP的標簽.使用ANNIE Chunker進行動詞組塊分析，即提取出動詞短語，并將動詞短語標注上VP的標簽.名詞短語和動詞短語也稱作名詞組塊和動詞組塊.組塊分析部分的流程如圖2所示.

圖2 組塊分析流程圖

2.2 基于PCFG的句法分析方法

2.2.1 PCFG文法

PCFG文法是基于概率的上下文無關文法，被認為是統計和規則方法的結合.PCFG文法可以表示為一個五元組G=，其中：

1)X是終結符集.

2)V是非終結符集.

3)S是文法的開始符號，S∈V.

4)R是有序偶對(α，β)的集合，即產生的規則集.

5)P是每個產生規則的統計概率.

2.2.2 Viterbi算法

Viterbi算法是一種利用動態規劃思想計算所有句法分析樹中的最大概率的方法.Viterbi算法可以描述為如下形式：

Step 1.初始化：

Yii(A)=P(A→wi)，1≤i≤n

(1)

Step 2.歸納計算：j=1…n，i=1…n-j，重復如下計算：

(2)

(3)

其中，N為PCFG文法G(S)的非終結符集.

Step 3.終結：

(4)

2.2.3 使用改進的Viterbi算法進行句法分析

在3.1節的名詞組塊分析中，只是提取了自然語言需求中的原子名詞短語，無法識別復雜的短語，這影響了需求模板符合性檢查的效果.所以，在這一節引入了改進的Viterbi算法對自然語言需求進行完全句法分析，提取出自然語言需求的復雜名詞短語.

根據模板，使用改進的Viterbi算法，進行句法分析.改進的Viterbi算法使用PCFG方法，給定上下文無關文法G，以及句子S，通過將樹上每一個結點生成其分支結點的概率相乘，計算句法分析樹的概率P(T|S，G).若一個句子有多棵句法分析樹，可以根據概率值對所有的句法分析樹進行排序.PCFG可以使用句法排歧，面對多個分析結果選擇概率最大的分析樹作為句法分析的結果，即argmaxTP(T|S，G).如圖3所示，使用Viterbi算法進行句法分析能夠對需求語句生成一棵最優的句法分析樹.然后，檢索句法分析樹上的每個節點SyntaxTreeNode，提取其中cat屬性為NP的部分，即為名詞組塊，同樣標注上NP的標簽.使用appelt控制選項(第3行)，可以確保再同一文本區域中檢測到多個名詞組塊時，只標記長度最長的一個.使用3.1節與本節的這些標簽來進行需求模板符合性檢查.提取句法分析樹上父節點為NP的Token序列偽代碼如下：

圖3 句法分析樹

輸入：句法分析樹SyntaxTree

輸出：名詞組塊集合NPs

1. for each SyntaxTreeNode in SyntaxTree

2. if SyntaxTreeNode.cat==NP

3. NPs.add(SyntaxTreeNode)

4. end if

5. End for

6. Return NPs

2.3 模板定義

根據Rupp模板，給出Rupp模板的BNF語法，如表1所示.其中，，即<條件>.條件可以且只能出現在需求語句的開頭.Rupp模板對條件沒有具體的要求，只要求條件使用以下的，即<條件關鍵詞>：if表示邏輯條件；after、before、as soon as、when、while表示時間條件；in case表示目的條件.第1個，即<名詞短語>，表示出現在情態動詞短語之前的名詞短語，作為系統名稱.，即<情態動詞短語>，表示包含情態動詞的動詞短語.第2個，即<名詞短語>，表示出現在情態動詞短語之后的名詞短語，作為對象.