優化構建邏輯函數的語法樹

張明新

【摘 要】本文通過建立邏輯函數的預處理算法和數據存儲結構，解析邏輯函數結構；在構建邏輯函數的語法樹時，利用解析的數據可以提高產生式匹配的準確性，實現優化回溯方法。

【關鍵詞】邏輯函數；語法樹；文法；算法，數據結構

中圖分類號： TP312 文獻標識碼： A 文章編號： 2095-2457（2018）08-0078-003

Optimize the Syntax Tree for Building Logic Functions

ZHANG Ming-xin

（College of Information，Huaibei Normal University，Huaibei 235000，Anhui，China）

【Abstract】This paper establishes the logic function preprocessing algorithm and data storage structure and analyzes the structure of the logic function.When constructing the syntax tree of the logic function，using the parsed data can improve the accuracy of production matching and realize the optimized backtracking method.

【Key words】Logic function；Syntax tree；Grammar；Algorithm；Data structure

0 引言

邏輯函數是一組邏輯變量之間計算關系的組合，（設：F=f（Al，A2，…，An） ；其中：Al，A2，...，An為輸入邏輯變量；F為輸出邏輯變量，取值是0或l），這組合也確定了函數的內在功能；邏輯函數的表達式可以采用最小項或最大項進行描述，這種形式更直接表達了邏輯參量之間的組合關系。構建邏輯函數的語法樹，就是建立一套規則和方法，采用樹或圖的結構來表達邏輯函數的這種組合關系，從而便于掌握和理解、應用它們的結構關系。

1 文法定義與設計

在形式上，邏輯函數是等式構成，主題特征是等式右邊的布爾表達式，也是構造語法樹的對象。布爾表達式是由邏輯運算符、邏輯變量、括號等字符組成，邏輯運算包括非、與、或三種基本運算（其他運算可以轉換為這三種基本運算），本文定義非、與、或三種基本運算為：！、*、+，以及括號運算符：（、）；邏輯變量采用英文字母（含大小寫形式）A、B、C、a、b、c；邏輯反變量用！A，！a等表示。

文法設計就是建立一套規則，為構造語法樹提供實現方法。

設文法G=（VT，VN，P，S），P是一組產生的規則：

（1）S->S+S

（2）S->S*S

（3）S->（S） |！（S）

（4）S->KS|K

（5）S->ε

（6）K->（|）|！|*|+|

（7）K->A|B|C|A？|B？|C？|a|b|c|a？|b？|c？|…

約定S、K只做為非終結符。

2 數據結構設計

2.1 樹結點結構

對邏輯函數運算與、或是二目運算，三叉樹能夠組織運算的表達關系，對于一目的非運算，可以采用二叉樹結構，但為數據一致性結構，本文約定非運算定義為三叉樹結構，在語法樹生成過程中，對非運算與計算項之間增加一個且僅為連接作用符“@”，用@符作為葉子結點。 Lpointer、Mpointer、Rpointer分別是左中右指針，Data1，是計算項數據域，Data2是輔助信息域，樹結點結構見圖1。

2.2 葉子結點結構

葉子結點結構存儲布爾表達式中具體計算符號，結構見圖2。Data是葉子邏輯變量、運算符號數據域，D1等是輔助信息域。

2.3 邏輯函數預處理

在語法樹構造過程中，始終存在產生式匹配問題，如同一非終結符有N個產生式，當匹配不成功時，要回溯處理，用下一個產生式進行匹配處理，如此，正確匹配一個產生式平均要達到N/2次。為優化回溯方法，建立對布爾表達式預處理環節，提高產生式匹配的確定性[1-6]。

邏輯函數預處理就是建立掃描識別算法，按照或運算為單位，對邏輯函數右端布爾表達式進行識別，找到對應計算項，并將計算項采用鏈表結構進行組織存儲。數據結構圖3：

H1：表示第一層掃描的數據鏈表。

邏輯函數預處理掃描識別算法（用類C語言描述）：

設邏輯函數的布爾表達式為str；計數器i；括號運算符標志f；計算項sdata；

初始化 i=0；f=0；sdata=""；

（1）ch=read（str）；

（2）if （ ch=="#"）

do

{ 遇到str結束符，將當前sdata添加到鏈表中；

i=0；

sdata=""；

goto （9）； }//即最后一個計算項的處理

（3）if （f==0 and ch=="+" ）

do

{此sdata字符串作為一個計算項添加到鏈表中；

i=0；

sdata=""；

goto （1）；}

try{處理計算項拼寫異常；}

（4）i++；

（5）if （ ch=="（" ） f++；

（5）if （ ch=="）" ） f--；

（6）if ！（ch=="+"）{ sdata=sdata+ch；} //剔除布爾表達式非括號中的或運算符“+”

（8） goto （1）

（9）end

從預處理可知，各個計算項及其產生式的匹配關系就能夠精準定位，但是，識別的計算項任然是布爾表達式，可能存在三種情況，或是獨立邏輯元素項；或是邏輯元素的與運算項、非運算項；或是存在括號組合的式子，對前兩種運算式可直接用產生式（7）和產生式（2）就能夠匹配生成，對括號組合的式子需要進一步識別，直到識別出相應產生式[7-9]。

括號組合的式子的處理，首先，要對上述算法進行調整，一是對鏈表結點結構增加一個數據域，表明此計算項是否為具有括號運算，再是，當某個計算項sdata在進行識別的時候，一旦f>0，就可以設置對應數據域為1，表明此項含有括號運算。如果存在嵌套括號組合的式子，需要逐層進行識別，直到處理完所有括號計算項。Hi（i=1…m）：表示第i次掃描的數據鏈表，鏈表結構如圖4。

另外，括號組合的式子存在兩種情形，一是完全由括號組織的式子，如：（…）；另一種情況就是包含“非”運算的括號式子，如：！（…），根據前面的約定對此式構成：！@（…）二目運算格式，同理，對反變量也采用二目運算格式。

3 語法樹構造方法

通過預處理，得到若干鏈表組成的布爾表達式計算關系，按照自頂向下構造方法，并且采用最右推導法，就能夠快速建立基于文法 G的語法樹。

語法樹構造算法分析：

（1）：創建根結點；

（2）：按Hi，i=1 to m 掃描每一個Hi鏈表；

{

對H1，則存儲的是整個布爾表達式按照或運算的各計算項，若空，則是空樹；若只有一個結點，則樹只有一個葉子結點；若有多個結點，則選擇前兩個結點，按照產生式（1），構造語法樹，再用右結點與H1的后續結點，繼續構造語法樹，依次進行。直到H1構造完成為止。

}

（3）：遍歷語法樹，對每個節點進行處理；

{

若是獨立邏輯變量，用產生式（4）和（7），逐層推進，直到生成葉子節點；

若是與運算式、非運算式（按約定條件），用產生式（2）、（4）和（7），逐層推進，直到生成葉子節點；

若是括號運算式，調用對應Hi，按照H1計算，產生語法樹，最后用產生式（3）、（4）和（7），逐層推進，直到生成葉子節點；

}

4 實驗結果

4.1 技術背景

實驗測試基于Microsoft Visual Studio 2008的Windows Presentation Foundation in .NET4.0（簡稱WPF）平臺[10]，利用C#編寫測試軟件，實現邏輯函數的布爾表達式預處理和語法樹的構造。

4.2 數據結構的設計

數據結構主要有鏈表結點、語法樹結點和葉子結點三種，采用泛型數據。

4.2.1 鏈表結點

public class LinkNode

{

public T Data { set； get； } //數據域，當前結點數據

public T Flag { set； get； }

public LinkNode Next { set； get； } //位置域，下一個結點地址

public LinkNode （T item， T item1）

{

this.Data = item；

this.Flag = item1；

this.Next = null；

}

public LinkNode （T item） //構造頭結點

{

this.Data = item；

this.Next = null；

}

public LinkNode （）

{

this.Data = default（T）；

this.Flag = default（T）；

this.Next = null；

}

}

4.2.2 三叉樹結點

public class TreeNode

{

public T Data1 { set； get； }

public T Data2 { set； get； }

public TreeNode LNext { set； get； }

public TreeNode MNext { set； get； }

public TreeNode RNext { set； get； }

public TreeNode （T item， T item1）

{

this.Data1 = item；

this.Data2 = item1；

this.LNext = null；

this.MNext = null；

this.RNext = null；

}

public TreeNode （T item） //構造頭結點

{

this.Data = item；

this.Next = null；

}

public Node（）

{

this.Data = default（T）；

this.Flag = default（T）；

this.Next = null；

}

}

4.2.3 葉子結點

public class LeafNode

{

public T Data1 { set； get； } //數據域，當前結點數據

public T Data12 { set； get； }

public LeafNode （T item， T item1）

{

this.Data1 = item；

this.Data2 = item1；

}

}

4.2.4 實驗分析與結果

用邏輯函數F=A+（A+B*C）+A*C+！（A+B）進行測試，實現鏈表的功能，構造了語法樹，現僅以鏈表給出實驗結果，如圖5。

圖5 邏輯函數生成的鏈表數據

5 結束語

通過對邏輯函數的預處理，建立布爾表達式的數據結構，解析了邏輯函數內在的計算關系，按照在自頂向下的語法樹構造方法，結合最右推導規則，以及約定條件，實現語法樹生成過程的回溯優化。

【參考文獻】

[1]黃沛杰，黃強，吳秀鵬，吳桂盛，郭慶文，陳楠挺，陳楚萍.語法和語義相結合的中文對話系統問題理解研究[J].中文信息學報.2014年11月.第28卷，第6期70-78.

[2]Ch Youngblut. Educational uses of virtual reality technology [R].

Institute for Defense Analysis， IDA Document D-2128. Alexandria，VA： Insitute for Defense Analyses， January 1998.

[3]Ouyang Yang， Dong Yabo， Zhu Miaoliang， et al. ECVlab： A web-based Virtual Laboratory System for Electronic Circuit Simulation [C]// Proceedings of International Conference on Computational Science. Germany： Springer， 2005： 1027-1034.

[4]石野，黃龍和，車天陽，高斯，王健.基于語法樹的程序相似度判定方法[J].吉林大學學報（ 信息科學版）.2014年1月第32 卷第1期95-100.

[5]C C Ko， B M Chen， S Y Hu， et.al. A web-based virtual laboratory on afrequency modulation experiment [J]. IEEE Transactions on Systems，Man， and Cybernetics， Part C： Applications and Reviews （S1094-6977）， 2001， 31（3）： 295-303.

[6]張素琴，呂映芝，蔣維杜，戴桂蘭.編譯原理（第2版）[D].清華大學出版社，2005年2月第版.

[7]王鑒全，季紹波.基于中文語法樹的概念圖挖掘研究[J].大連海事大學學報.2012年11月.第38卷第4期52-55.

[8]許萌.應用于詞法分析器的算法分析優化[J].科教之窗，2017 年第5 期，154-155.

[9]楊超，朱東華，衡曉帆，汪雪鋒.基于語法樹的SAO結構識別方法研究[J].圖書情報工作.第60 卷第21 期2016 年11 月 113-121.

[10]Matthew MacDonald. Pro WPF in C# 2010： Windows Presentation Foundation in .NET4.0[D].清華大學出版社，2011年6月第1版.