c++ - 在Bison C++中解析谓词逻辑

Question

我正在开发一种软​​件，以简化predicate logic表示法的公式，应用一些逻辑定律以合取范式形式输出公式。我将尝试尽可能清楚地解释一切。我知道这不是一个数学站点，但是我必须解释一些概念以获得具体答案。



该软件将做什么？

该软件将具有一个条目，用户可以在其中输入公式，程序将进行处理，直到达到其合法范式为止。因此，我必须做一个解析器，可以处理输入并将每个令牌放入某种结构中，然后根据需要对其进行格式化。我将使用以下工具：


C ++。
Qt框架。
野牛和Flex。


如何获得公式的conjunctive normal form？


F=!(a && b)，则输出将为F[cnf]=!a || !b（应用De Morgan's law）。
F=(a && b)，则输出将为F[cnf]=a && b（相同，因为输入已经采用这种形式）。
F=a && (b || c)，然后是F[cnf]= (a || b) && (a || c)（distributive law）。


因此，基本上是相同的公式，但由&&标记分隔。

施工状况

我尝试操纵输入公式的各个部分时遇到的第一个问题是处理语法规则的递归。

假设以下规则：

expr:
         SYMBOL                                  { cout << " 0 "; }
    |    LEFT_PARENTHESES expr RIGHT_PARENTESES  { cout << " 1 "; }
    |    expr AND expr                           { cout << " 2 "; }
;

然后输入 (a && b)，程序将打印： 0 - 0 - 1 - 2，这是：从最后执行的规则到第一个规则。我已经意识到，使用 queue并使用 push_back()方法插入每个令牌，然后可以按照这些规则对所有令牌进行排序。但是我想使用这些表达式，不仅要验证她的语法并打印标记，所以我不得不创建一个更复杂的结构（不是那么复杂），创建一个 binary tree来模拟 abstract syntax tree并对其进行转换。现在假设在我的树中表示的公式 a && b || c将是：

      &&
     /  \
    a    ||
        /  \
       b    c

也就是说，父代始终是运算符，子代是操作数或某些表达式。如果我有一个类似 a && (b || c)的表达式，则必须包括括号：

      &&
     /  \
    a    (
          \
          ||
         /  \
        b    c

这样， (右侧的所有令牌将被封装在一组中。因此，我可以使用简单的公式（使用 not， and， ||和 ()运算符进行二进制或多次运算；我也可以解析嵌套公式并应用De Morgan的定律），而且效果很好：D。

所以有什么问题？

好的，如上所述，它仅适用于简单公式。但是，如果输入包含运算符 ->（暗示）或 <->（当且仅当）时会发生什么？ （...）程序不起作用。我要做的就是应用该逻辑运算符的定义：


P->Q： !P || Q（1）
P<->Q： (P->Q) && (Q->P)： (!P || Q) && (!Q || P)（2）


因此，我要做的第一件事是使用规则（1）和（2）转换 ->和 <->操作。一旦有了元素运算符（ &&， ||， !和 ()）的所有表达式，就必须使用德摩根定律分配 !运算符并分配 ||以返回其合取范式。听起来很简单，但事实并非如此（至少对我而言不是）。

您还记得我提到规则没有按照令牌到达的顺序执行吗？在这种情况下，我可以应用 ->运算符：让 a->b在左侧表达式（ !）中添加 a，然后在这两个表达式（ ||和 a）之间插入 b。我可以在树中添加一个父级（ !），一个正确的子级 a，一个 ||父级和另一个子级 b：

      ||
     /  \
    !    b
     \   
      a  

因此，在这种情况下可行，但是我无法使用 <->运算符执行相同操作！

所以，我的问题是：如何解决这些问题？您是否建议使用其他结构存储令牌？您知道执行此操作的任何技术吗？



代码

解析器

%{
    #include <iostream>
    #include "parsingtree.h"

    using namespace std;

    #define YYSTYPE string

    int yylex(void);
    void yyerror(char *);

    ParsingTree tree;
%}

%token  LEFT_PAR
        RIGHT_PAR
        SYMBOL
        END
        NOT
        DIST

%left   AND
        OR
        THEN
        IFF

%start input

%%

input:
        /* empty */
    |   input expr
;

expr:
        SYMBOL {
            $$ = $1;
            cout << "ACA ENTRO A LA REGLA 0" << endl;
            tree.pushSymbol($1);
        }
    |   LEFT_PAR expr RIGHT_PAR {
            $$ = $2;
            tree.pushLogicOperator("()");
        }
    |   NOT expr {
            $$ = $2;
            tree.pushLogicOperator("!");
        }
    |   DIST expr RIGHT_PAR {
            $$ = $2;
            tree.pushLogicOperator("!");
        }
    |   expr AND expr {
            tree.pushLogicOperator("&&");
        }
    |   expr OR expr {
            tree.pushLogicOperator("||");
        }
    |   expr THEN expr {
            tree.pushLogicOperator("||");
            tree.pushLogicOperator("!");
        }
;

            tree.pushLogicOperator("||");
            tree.pushLogicOperator("!");

        }
    |   SYMBOL THEN expr {
            tree.pushSymbol($1);
            tree.pushLogicOperator("||");
            tree.pushLogicOperator("!");
        }
%%

void yyerror(char *s) {

}

扫描仪

%option noyywrap
%{
    #include <iostream>
    #include "parser.tab.c"
    using namespace std;
%}

%%

[a-zA-Z0-9<>=]+  {
    yylval = strdup(yytext);
    return SYMBOL;
}

"&&" {
    return AND;
}

"||" {
    return OR;
}

"!" {
    return NOT;
}

"!(" {
    return DIST;
}

[ \0\0] {
    return END;
}

"("     {
    return LEFT_PAR;
}

")"     {
    return RIGHT_PAR;
}

"->"    {
    return THEN;
}

"<->"   {
    return IFF;
}

%%

main.cpp

#include "parsingtree.h"
#include "lex.yy.c"

typedef yy_buffer_state *YY_BUFFER_STATE;
extern int yyparse();
extern YY_BUFFER_STATE yy_scan_string(char *, size_t);

int main(int argc, char *argv[]) {
    yy_scan_string("(a&&(d->g))->(b&&c)\0\0");
    yyparse();

    tree.printTree();
}

parsingtree.h

#ifndef PARSINGTREE_H
#define PARSINGTREE_H
#include <QString>
#include <QList>
#include <QDebug>
#include <iostream>

using namespace std;

class ParsingTree
{
public:
    ParsingTree();
    void pushSymbol(string data);
    void pushLogicOperator(string data);
    void printTree();

private:
    struct treeNode
    {
        string data;
        treeNode* leftNode;
        treeNode* rightNode;
    };
    QList<treeNode*> auxList; //guarda el arbol en formación
    treeNode* tree; //pedir el ultimo elemento de la lista, ese es el arbol

    void printTree(treeNode* rTree);
    string latest(treeNode* rTree);
};

#endif // PARSINGTREE_H

parsingtree.cpp

#include "parsingtree.h"

ParsingTree::ParsingTree()
{
    tree= NULL;
}

void ParsingTree::pushSymbol(string data)
{
    treeNode* node = new treeNode;
    node->data = data;
    node->leftNode = NULL;
    node->rightNode= NULL;
    auxList.push_back(node);
}

void ParsingTree::pushLogicOperator(string data)
{
    //binarios
    if ((data == "||") || (data == "&&"))
    {
         treeNode* node = new treeNode;
         node->data = data;
         node->rightNode=auxList.last();
         auxList.removeLast();
         node->leftNode=auxList.last();
         auxList.removeLast();
         auxList.push_back(node);
    }
    //unarios
    if ((data == "!") || (data == "()"))
    {
        treeNode* node = new treeNode;
        node->data = data;
        node->rightNode=auxList.last();
        auxList.removeLast();
        node->leftNode= NULL;
        auxList.push_back(node);
    }
}

void ParsingTree::printTree()
{
    tree = auxList.last();
    printTree(tree);
}

void ParsingTree::printTree(ParsingTree::treeNode* rTree)
{
    if (rTree != NULL)
    {

        printTree(rTree->leftNode);
        if (rTree->data == "()")
        {
            cout << "$(";
            printTree(rTree->rightNode);
            cout << ")$";
        }
        else
        {
            cout << rTree->data + " ";
            printTree(rTree->rightNode);
        }
    }
}

谢谢！ ：D

PS：如果我写错了什么，或者您看不懂某些东西，请问我，以便我更好地表达自己；我的英语很差（我来自阿根廷），我觉得这个问题很难解释，所以希望您能理解。

Answer 1

使用此伪代码：

P and Q are atomic OR expr between last ')' and corresponding '('

while '<=>' occurs
    P <=> Q |= (P => Q) && (Q => P)

while '=>' occurs
    P => Q |= !P || Q

while '!(P || Q)' || '!(P && Q)' occurs
    apply De Morgan

while 'P || (Q && R)' || '(Q & R) || P' occurs
    |= (P || Q) && (P || R)

apply these rules after each wile:
while 'P || (Q || R)' || '(P || Q) || R' occurs
    |= P || Q || R
while 'P && (Q && R)' || '(P && Q) && R' occurs
    |= P && Q && R

您可以使用正则表达式替换来实现，也可以使用c ++解析字符串。确保以一致的方式从左到右或从右到左解析。这将确定逻辑是左还是右关联。

如果您发现此替换方案不明确，请告诉我。