[發明專利]一種從非合流圖文法到合流圖文法的轉換方法

無效

• 申請號: 201110298346.0
• 申請日: 2011-09-28
• 公開（公告）號: CN102289377A
• 公開（公告）日: 2011-12-21
• 發明（設計）人: 鄒陽;曾曉勤
• 申請（專利權）人: 河海大學
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 許方

1.一種從非合流圖文法到合流圖文法的轉換方法，用于隱式上下文相關圖文法，其特征在于，首先判斷圖文法實例是否合流，如果非合流，則找出所有非合流的產生式對以及相應的導致非合流的產生式合并圖的集合；然后依據非合流的產生式合并圖在非合流的產生式對中引入變量構造約束將非合流的產生式集合轉換成合流的產生式集合。

2.?如權利要求1所述從非合流圖文法到合流圖文法的轉換方法，其特征在于，具體包含以下步驟：

1)?輸入某種隱式上下文相關圖文法形式框架的一個圖文法實例???????????????????????????????????????????????；

2)?判斷實例的產生式集P是否合流，如果是，則轉換過程結束；否則，構建所有非合流產生式對的集合；具體為：

2.1)?記ncps為所有非合流產生式對的集合，置ncps為空；

2.2)?記nrds為非合流產生式對的不可約簡合并圖集的集合，置nrds為空；

2.3)?對P中任一對產生式p_i與p_j，i?≠?j，判斷其是否合流，如果非合流，則將{p_i，p_j}加入集合ncps中；

2.4)?如果ncps為空，則P是合流的，直接輸出P，轉換過程結束，否則，轉2.5；

2.5)?令ncs為ncps中所有產生式的集合，即P中所有非合流產生式的集合；

3)?對ncps構造合流約束，即對ncps中任一對{p_i，p_j}及nrds中的nrd_ij，構造約束C使p_i.C與p_j.C相對于nrd_ij互斥；具體為：

3.1)?置p_i與p_j公共變量集V和基于V的語義約束C為空；

3.2)?對nrd_ij中任一圖G，構造變量集v及約束c使p_i.c與p_j.c相對于G互斥；

3.3)?將V和C分別并入產生式p_i和p_j的變量集和約束集；

4)?令tcs為轉換后的ncps中所有產生式的集合，從P中刪除產生式集合ncs，再并入集合tcs；輸出P。

3.?如權利要求2所述從非合流圖文法到合流圖文法的轉換方法，其特征在于，步驟2.3包括以下步驟：

2.3.1)?構造p_i與p_j的合并集m_ij，即p_i右圖與p_j右圖的所有可能重疊所構成圖的集合；

2.3.2)?令nrd_ij為m_ij中的不可約簡子集，初值置空；

2.3.3)?對于任一m_ij中的圖G，判斷G是否關于p_i與p_j可約簡，如果G不可約簡，則將G加入集合nrd_ij中；

2.3.4)?如果nrd_ij不為空，則將{p_i，p_j}加入集合ncps中；并將nrd_ij加入集合nrds中；

步驟3.2包括以下步驟：

3.2.1)?判斷p_i.C與p_j.C是否相對于G互斥，如果互斥，則繼續判斷nrd_ij中下一圖；否則，轉下一步；

3.2.2)引入變量v并構造v上的約束c使p_i.c與p_j.c相對于G互斥；

3.2.3)?將v和c分別加入集合V和C。