張明新

【摘 要】本文通過建立邏輯函數(shù)的預處理算法和數(shù)據(jù)存儲結(jié)構，解析邏輯函數(shù)結(jié)構；在構建邏輯函數(shù)的語法樹時，利用解析的數(shù)據(jù)可以提高產(chǎn)生式匹配的準確性，實現(xiàn)優(yōu)化回溯方法。

【關鍵詞】邏輯函數(shù)；語法樹；文法；算法，數(shù)據(jù)結(jié)構

中圖分類號： 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 引言

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

1 文法定義與設計

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

文法設計就是建立一套規(guī)則，為構造語法樹提供實現(xiàn)方法。

設文法G=（VT，VN，P，S），P是一組產(chǎn)生的規(guī)則：

（1）S->S+S

（2）S->S*S

（3）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只做為非終結(jié)符。

2 數(shù)據(jù)結(jié)構設計

2.1 樹結(jié)點結(jié)構

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

2.2 葉子結(jié)點結(jié)構

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

2.3 邏輯函數(shù)預處理

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

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

H1：表示第一層掃描的數(shù)據(jù)鏈表。

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

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

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

（1）ch=read（str）；

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

do

{ 遇到str結(jié)束符，將當前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 ?。╟h=="+"）{ sdata=sdata+ch；} //剔除布爾表達式非括號中的或運算符“+”

（8） goto （1）

（9）end

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

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

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

3 語法樹構造方法

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

語法樹構造算法分析：

（1）：創(chuàng)建根結(jié)點；

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

{

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

}

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

{

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

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

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

}

4 實驗結(jié)果

4.1 技術背景

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

4.2 數(shù)據(jù)結(jié)構的設計

數(shù)據(jù)結(jié)構主要有鏈表結(jié)點、語法樹結(jié)點和葉子結(jié)點三種，采用泛型數(shù)據(jù)。

4.2.1 鏈表結(jié)點

public class LinkNode

{

public T Data { set； get； } //數(shù)據(jù)域，當前結(jié)點數(shù)據(jù)

public T Flag { set； get； }

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

public LinkNode （T item， T item1）

{

this.Data = item；

this.Flag = item1；

this.Next = null；

}

public LinkNode （T item） //構造頭結(jié)點

{

this.Data = item；

this.Next = null；

}

public LinkNode （）

{

this.Data = default（T）；

this.Flag = default（T）；

this.Next = null；

}

}

4.2.2 三叉樹結(jié)點

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） //構造頭結(jié)點

{

this.Data = item；

this.Next = null；

}

public Node（）

{

this.Data = default（T）；

this.Flag = default（T）；

this.Next = null；

}

}

4.2.3 葉子結(jié)點

public class LeafNode

{

public T Data1 { set； get； } //數(shù)據(jù)域，當前結(jié)點數(shù)據(jù)

public T Data12 { set； get； }

public LeafNode （T item， T item1）

{

this.Data1 = item；

this.Data2 = item1；

}

}

4.2.4 實驗分析與結(jié)果

用邏輯函數(shù)F=A+（A+B*C）+A*C+?。ˋ+B）進行測試，實現(xiàn)鏈表的功能，構造了語法樹，現(xiàn)僅以鏈表給出實驗結(jié)果，如圖5。

圖5 邏輯函數(shù)生成的鏈表數(shù)據(jù)

5 結(jié)束語

通過對邏輯函數(shù)的預處理，建立布爾表達式的數(shù)據(jù)結(jié)構，解析了邏輯函數(shù)內(nèi)在的計算關系，按照在自頂向下的語法樹構造方法，結(jié)合最右推導規(guī)則，以及約定條件，實現(xiàn)語法樹生成過程的回溯優(yōu)化。

【參考文獻】

[1]黃沛杰，黃強，吳秀鵬，吳桂盛，郭慶文，陳楠挺，陳楚萍.語法和語義相結(jié)合的中文對話系統(tǒng)問題理解研究[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]許萌.應用于詞法分析器的算法分析優(yōu)化[J].科教之窗，2017 年第5 期，154-155.

[9]楊超，朱東華，衡曉帆，汪雪鋒.基于語法樹的SAO結(jié)構識別方法研究[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版.