根据逻辑算式生成语法树(一)

编程与算法

根据一个已知的逻辑算式例如(((￢p)∧q) → (p∧(q∨(￢r))))，生成它的语法树。并通过图形化的方式来展示出来。

生成语法树的语言使用C++,而图形化的方法通过graphviz提供的dot格式进行显示。

一般的逻辑算式可以看做是一颗二叉树的中序遍历，但是仅仅靠中序遍历是没办法确定一颗二叉树的。所以采取另外一种方法进行二叉树的生成。

目前没有进行该算法的正确性验证，但是对于一般算式应该是正确的。

下面介绍一下这个算法的思路：

算法简单思路

  1. 首先对括号进行处理
  2. 然后对蕴含符号进行处理
  3. 然后对逻辑符号（析取、合取）进行处理
  4. 最后对否定符号进行处理

    1 消去括号

    每个括号里面的内容都可以看成一颗无括号的子式，这个子式可以放到其他函数中进行处理，这里先不予以考虑。从算式中最里面的括号开始计算，
    将括号中的子式合并为一个元素。用一种不太严谨的符号暂时来表示:

P::=p|(P)-P //p表示原子或者原子的否定 P表示一个子式 -表示任一逻辑运算符

然后这个函数从内向外依次将括号消去。按照上文中的样例进行计算：

1
2
3
4
5
6
7
(((￢p)∧q) → (p∧(q∨(￢r))))
用 P1 表示 ￢p 则原始算式变为 ((P1∧q) → (p∧(q∨(￢r))))
用 P2 表示 P1∧q 则原始算式变为 (P2 → (p∧(q∨(￢r))))
用 P3 表示 ￢r 则原始算式变为 (P2 → (p∧(q∨P3)))
用 P4 表示 q∨P3 则原始算式变为 (P2 → (p∧P4))
用 P5 表示 p∧P4 则原始算式变为 (P2 → P5)
用 P6 表示 P2 → P5 则原始算式变为 P6

经过上述计算，可以将原始式分为多个无括号的子式。而子式也可以看成一个无括号的子树，我们用P1 - P6来表示每个子树的指针。

如此就引出了下面的问题，如何处理无括号的算式。

2 消去蕴含

逻辑符号优先级最低的为蕴含符号。所以对于每一个无括号的子式，如果含有蕴含符号，他的语法树的根节点肯定为最后一个蕴含符号。

也用一种不太严谨的符号进行表示：

Q::=P|P->Q //Q表示可能包含蕴含符号的子式 ->表示蕴含符号 P表示不包含蕴含符号的子式

所以本方法的主要目的是从前往后依次消去所有的蕴含符号，并且对于每个蕴含符号建立一颗子树。而蕴含符号的前件后件就是一个不包含蕴含符号的子式。这个子式交给下一个函数去处理。
按照上文（消去括号）的结果，进行进一步的计算：

（因为只有最后一个子式P6包含蕴含符号，所以这里只讨论最后一个子式，其他子式直接进去下一个函数）

1
2
3
4
P2 → P5
将 P2 放入下一个函数进行子树的生成，并且得到这颗子树的根节点指针作为返回值 *P2
将 P5 放入下一个函数进行子树的生成，并且得到这颗子树的根节点指针作为返回值 *P5
建立一个节点，左儿子指针为*P2 ，右儿子指针为*P5,该节点指针为*P6 并且将*P6返回

蕴含符号的前件和后件都是一个不包含蕴含符号的子式，所以下面来讨论如何对这种子式进行进一步的处理。

3 消去析取合取

现在需要处理的子式只包含：析取符号，合取符号，否定符号

在这个函数中我们进行析取和合取的消去。

在这里同样中一种不严谨的符号进行表示：

Q::=P|P$Q //Q表示可能包含析取或合取的子式 P表示不包含析取或合取的子式 $表示析取或合取符号

因为这个子式中，不包含括号，不包含蕴含，所以计算顺序就是从前向后计算。
计算方法为，从前向后扫描，将析取或合取两侧的元素放到下一个方法中计算，并且得到两个子树根节点指针作为左右儿子，建立一颗树。
同样取上述的一个例子进行下一步计算：

1
2
3
4
5
P2
根据上面的例子P2 := P1∧q
将 P1 放入下一个函数进行子树生成，并且得到这颗子树的根节点指针作为返回值 *P1
将 p 放入下一个函数进行子树生成，并且得到这颗子树的根节点指针作为返回值 *p
建立一个节点，左儿子指针为*P1 ，右儿子指针为*p,该节点指针为*P2 并且将*P2返回

对于每一个包含析取合取的式子进行处理。最后得到只包含否定符号的子式或者不包含否定符号的原子。下面介绍最后一个方法。

4 消去否定，生成叶子节点

对于传入的参数有四种：

  • 包含否定的指针
  • 指针
  • 包含否定的原子
  • 原子

假如包含否定的原子则建立一颗只有一个子节点的长度为2的子树，叶子节点的内容为原子符号。并且返回这颗子树的根节点指针。

假如只是一个原子符号，则建立一个叶子节点，并且返回这个节点的指针。

假如是包含否定的指针，建立一个节点，它只有一个儿子就是否定符号后的指针，返回这个节点的指针。

假如是一个指针，则不做任何操作，将该指针返回。

伪流程

算法的基本原理介绍完了，因为本人语言表达能力较差，所以可能介绍的迷迷糊糊的。所以下面简单书写一下代码流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//消去括号
//输入为原始算式 formula
//输出为语法树根节点指针
function bracket_free(formula):
    遍历 formula 依次入栈:
        遍历到一个')':
            然后将这个括号的内容依次出栈（包含括号），得到该括号内的子式 subformula;
            将 subformula 放到 impl_free(subformula) 进行处理，得到该子树的根节点 subid;
            将subid入栈当做一个原子参与运算。继续该循环;
    取出栈中算式 new_formula;
    放到 impl_free(new_formula) 进行处理，得到该语法树的指针 rootid;
    返回 rootid;
//消去蕴含
//输入不包含括号的算式
//返回该算式构成的语法树的根节点指针
function impl_free(formula):
    遍历 formula 依次入栈：
        遍历到蕴含符号'->':
            将栈中所有字符串取出，作为前件sub1;
            向后遍历直到下一个蕴含符号或者字符串尾，作为后件sub2;
            将前件，后件放到 symbol_free(sub1) symbol_free(sub2)进行处理，得到两棵子树的指针sub1id,sub2id;
            建立一个节点，节点值为蕴含符号，左右儿子指针为 sub1id,sub2id;
            将新建节点的指针入栈，继续进行遍历（此时指针已经移到了下一个蕴含符号前，或者字符串尾）;
    取出栈中所有的字符串 new_formula(此时应为一个指针)；
    返回这个指针；
//消去析取合取
//输入 不包含蕴含和括号的算法
//输出 该算式的语法树根节点指针
function symbol_free(formula):
    遍历 formula 依次入栈:
        遍历到析取或合取符号：
            将栈中所有元素取出作为 sub1;
            向后遍历直到下一个析取或合取符号，作为sub2;
            将sub1,sub2放到 non_free(sub1) non_free(sub2)进行处理，得到两棵子树的指针sub1id,sub2id;
            建立一个节点，节点值为析取或合取符号，左右儿子指针为 sub1id,sub2id;
            将新建节点的指针入栈，继续进行遍历
    取出栈中所有的字符串 new_formula(此时应为一个指针)；
    返回这个指针；
//消去否定
//输入 只包含否定的算式
//输出 该算式的语法树根节点指针
function symbol_free(formula):      
    formula[0] 是 否定标记 且包含元素为原子：
        建立叶子节点，值为原子，指针为id;
        建立否定节点，值为否定符号，儿子指针为id;
        返回否定节点指针;
    formula[0] 是 否定标记 且包含元素为指针(id)：
        建立否定节点，值为否定符号，儿子指针为id;
        返回否定节点指针;
    formula 为原子:
        建立叶子节点，值为原子，指针为id;
        返回id;
    formula 为指针(id):
        返回id;

根据算法计算，(((￢p)∧q) → (p∧(q∨(￢r))))的语法树为:
pars_tree.png

具体C++代码请看下一篇博文。