张明新

【摘 要】本文通过建立逻辑函数的预处理算法和数据存储结构，解析逻辑函数结构；在构建逻辑函数的语法树时，利用解析的数据可以提高产生式匹配的准确性，实现优化回溯方法。

【关键词】逻辑函数；语法树；文法；算法，数据结构

中图分类号： 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 树结点结构

对逻辑函数运算与、或是二目运算，三叉树能够组织运算的表达关系，对于一目的非运算，可以采用二叉树结构，但为数据一致性结构，本文约定非运算定义为三叉树结构，在语法树生成过程中，对非运算与计算项之间增加一个且仅为连接作用符“@”，用@符作为叶子结点。……