優(yōu)化構(gòu)建邏輯函數(shù)的語法樹

張明新

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

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

中圖分類號(hào)： TP312 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ù)是一組邏輯變量之間計(jì)算關(guān)系的組合，（設(shè)：F=f（Al，A2，…，An） ；其中：Al，A2，...，An為輸入邏輯變量；F為輸出邏輯變量，取值是0或l），這組合也確定了函數(shù)的內(nèi)在功能；邏輯函數(shù)的表達(dá)式可以采用最小項(xiàng)或最大項(xiàng)進(jìn)行描述，這種形式更直接表達(dá)了邏輯參量之間的組合關(guān)系。構(gòu)建邏輯函數(shù)的語法樹，就是建立一套規(guī)則和方法，采用樹或圖的結(jié)構(gòu)來表達(dá)邏輯函數(shù)的這種組合關(guān)系，從而便于掌握和理解、應(yīng)用它們的結(jié)構(gòu)關(guān)系。

1 文法定義與設(shè)計(jì)

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

文法設(shè)計(jì)就是建立一套規(guī)則，為構(gòu)造語法樹提供實(shí)現(xiàn)方法。

設(shè)文法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é)構(gòu)設(shè)計(jì)

2.1 樹結(jié)點(diǎn)結(jié)構(gòu)

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

2.2 葉子結(jié)點(diǎn)結(jié)構(gòu)

葉子結(jié)點(diǎn)結(jié)構(gòu)存儲(chǔ)布爾表達(dá)式中具體計(jì)算符號(hào)，結(jié)構(gòu)見圖2。Data是葉子邏輯變量、運(yùn)算符號(hào)數(shù)據(jù)域，D1等是輔助信息域。

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

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

邏輯函數(shù)預(yù)處理就是建立掃描識(shí)別算法，按照或運(yùn)算為單位，對(duì)邏輯函數(shù)右端布爾表達(dá)式進(jìn)行識(shí)別，找到對(duì)應(yīng)計(jì)算項(xiàng)，并將計(jì)算項(xiàng)采用鏈表結(jié)構(gòu)進(jìn)行組織存儲(chǔ)。數(shù)據(jù)結(jié)構(gòu)圖3：

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

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

設(shè)邏輯函數(shù)的布爾表達(dá)式為str；計(jì)數(shù)器i；括號(hào)運(yùn)算符標(biāo)志f；計(jì)算項(xiàng)sdata；

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

（1）ch=read（str）；

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

do

{ 遇到str結(jié)束符，將當(dāng)前sdata添加到鏈表中；

i=0；

sdata=""；

goto （9）； }//即最后一個(gè)計(jì)算項(xiàng)的處理

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

do

{此sdata字符串作為一個(gè)計(jì)算項(xiàng)添加到鏈表中；

i=0；

sdata=""；

goto （1）；}

try{處理計(jì)算項(xiàng)拼寫異常；}

（4）i++；

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

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

（6）if ?。╟h=="+"）{ sdata=sdata+ch；} //剔除布爾表達(dá)式非括號(hào)中的或運(yùn)算符“+”

（8） goto （1）

（9）end

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

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

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

3 語法樹構(gòu)造方法

通過預(yù)處理，得到若干鏈表組成的布爾表達(dá)式計(jì)算關(guān)系，按照自頂向下構(gòu)造方法，并且采用最右推導(dǎo)法，就能夠快速建立基于文法 G的語法樹。

語法樹構(gòu)造算法分析：

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

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

{

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

}

（3）：遍歷語法樹，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行處理；

{

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

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

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

}

4 實(shí)驗(yàn)結(jié)果

4.1 技術(shù)背景

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

4.2 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

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

4.2.1 鏈表結(jié)點(diǎn)

public class LinkNode

{

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

public T Flag { set； get； }

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

public LinkNode （T item， T item1）

{

this.Data = item；

this.Flag = item1；

this.Next = null；

}

public LinkNode （T item） //構(gòu)造頭結(jié)點(diǎn)

{

this.Data = item；

this.Next = null；

}

public LinkNode （）

{

this.Data = default（T）；

this.Flag = default（T）；

this.Next = null；

}

}

4.2.2 三叉樹結(jié)點(diǎn)

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） //構(gòu)造頭結(jié)點(diǎn)

{

this.Data = item；

this.Next = null；

}

public Node（）

{

this.Data = default（T）；

this.Flag = default（T）；

this.Next = null；

}

}

4.2.3 葉子結(jié)點(diǎn)

public class LeafNode

{

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

public T Data12 { set； get； }

public LeafNode （T item， T item1）

{

this.Data1 = item；

this.Data2 = item1；

}

}

4.2.4 實(shí)驗(yàn)分析與結(jié)果

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

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

5 結(jié)束語

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

【參考文獻(xiàn)】

[1]黃沛杰，黃強(qiáng)，吳秀鵬，吳桂盛，郭慶文，陳楠挺，陳楚萍.語法和語義相結(jié)合的中文對(duì)話系統(tǒng)問題理解研究[J].中文信息學(xué)報(bào).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].吉林大學(xué)學(xué)報(bào)（ 信息科學(xué)版）.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].清華大學(xué)出版社，2005年2月第版.

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

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

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

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