优化构建逻辑函数的语法树
2018-06-08张明新
张明新
【摘 要】本文通过建立逻辑函数的预处理算法和数据存储结构，解析逻辑函数结构；在构建逻辑函数的语法树时，利用解析的数据可以提高产生式匹配的准确性，实现优化回溯方法。
【关键词】逻辑函数；语法树；文法；算法，数据结构
中图分类号： 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
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
public TreeNode
public TreeNode
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版.
