在 bison c++ 中解析谓词逻辑
Parsing predicate logic in bison c++
我正在开发一个软件来简化 predicate logic 符号中的公式，应用一些逻辑法则以 合取范式 输出公式。 我会尽量解释清楚。我知道这不是一个数学网站，但我必须解释一些概念以获得具体的答案。
软件会做什么？
该软件将有一个条目，用户可以在其中插入一个公式，程序将处理直到达到其合取范式。所以我必须做一个解析器来处理输入并将每个标记放在某个结构中，然后根据需要对其进行处理。我将使用以下工具：
- C++.
- Qt 框架。
- Bison 和 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 to simulate an abstract syntax tree然后改造它。假设现在公式 a && b || c 在我的树中表示为：
&&
/ \
a ||
/ \
b c
也就是说，父级始终是一个运算符，子级是操作数或一些表达式。如果我有像 a && (b || c) 这样的表达式，那么我必须包含括号：
&&
/ \
a (
\
||
/ \
b c
这样，(右边的所有token都会被围成一组。因此，我可以使用 简单公式 （使用 not、and、|| 和 () 运算符的二元或多项运算; 我也可以解析嵌套公式并应用 De Morgan 定律），这非常有效 :D.
所以，问题是什么？
好的，正如我上面所说，它只适用于简单的公式。但是，如果输入有运算符 ->（暗示）或 <->（当且仅当）会怎样？ (...) 该程序不起作用。我所要做的就是应用该逻辑运算符的定义：
P->Q: !P || Q (1)P<->Q: (P->Q) && (Q->P): (!P || Q) && (!Q || P) (2)
因此，我要做的第一件事是使用规则 (1) 和 (2) 转换 -> 和 <-> 操作。一旦我有了所有包含元素运算符的表达式（&&、||、! 和 ()），我就必须使用 De Morgan 的方法来分发 ! 运算符定律并将 || 分布到 returns 其合取范式。听起来很简单，但实际上并非如此（至少对我来说不是）。
你还记得我说过规则不是按照令牌到达的顺序执行的吗？。在这种情况下，我可以应用 -> 运算符：让 a->b 在左侧表达式 (a) 中添加一个 ! 并在这两个表达式之间插入 || （a 和 b）。我可以这样做，在我的树中添加一个父节点 (!)、一个右子节点 a、一个 || 父节点和另一个子节点 b:
||
/ \
! b
\
a
所以，在这种情况下可行，但我不能用 <-> 运算符做同样的事情！
所以，我的问题是：我该如何解决这些问题？您是否推荐使用另一种结构来存储令牌？您知道这样做的任何技术吗？
密码
parser.y
%{
#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 {
$$ = ;
cout << "ACA ENTRO A LA REGLA 0" << endl;
tree.pushSymbol();
}
| LEFT_PAR expr RIGHT_PAR {
$$ = ;
tree.pushLogicOperator("()");
}
| NOT expr {
$$ = ;
tree.pushLogicOperator("!");
}
| DIST expr RIGHT_PAR {
$$ = ;
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();
tree.pushLogicOperator("||");
tree.pushLogicOperator("!");
}
%%
void yyerror(char *s) {
}
scanner.l
%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;
}
[ [=15=][=15=]] {
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)[=16=][=16=]");
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：如果我写错了或者有什么不明白的地方，请问我，这样我才能更好的表达；我的英语很差（我来自阿根廷），我觉得这个问题很难解释，所以我希望你能理解。
使用这个伪代码：
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++ 解析字符串来实现。确保以一致的方式从左到右或从右到左解析。这将决定逻辑是左结合还是右结合。
如果您发现此替换方案有歧义，请告诉我。
我正在开发一个软件来简化 predicate logic 符号中的公式，应用一些逻辑法则以 合取范式 输出公式。 我会尽量解释清楚。我知道这不是一个数学网站，但我必须解释一些概念以获得具体的答案。
软件会做什么？
该软件将有一个条目，用户可以在其中插入一个公式，程序将处理直到达到其合取范式。所以我必须做一个解析器来处理输入并将每个标记放在某个结构中，然后根据需要对其进行处理。我将使用以下工具：
- C++.
- Qt 框架。
- Bison 和 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 to simulate an abstract syntax tree然后改造它。假设现在公式 a && b || c 在我的树中表示为：
&&
/ \
a ||
/ \
b c
也就是说，父级始终是一个运算符，子级是操作数或一些表达式。如果我有像 a && (b || c) 这样的表达式，那么我必须包含括号：
&&
/ \
a (
\
||
/ \
b c
这样，(右边的所有token都会被围成一组。因此，我可以使用 简单公式 （使用 not、and、|| 和 () 运算符的二元或多项运算; 我也可以解析嵌套公式并应用 De Morgan 定律），这非常有效 :D.
所以，问题是什么？
好的，正如我上面所说，它只适用于简单的公式。但是，如果输入有运算符 ->（暗示）或 <->（当且仅当）会怎样？ (...) 该程序不起作用。我所要做的就是应用该逻辑运算符的定义：
P->Q:!P || Q(1)P<->Q:(P->Q) && (Q->P):(!P || Q) && (!Q || P)(2)
因此，我要做的第一件事是使用规则 (1) 和 (2) 转换 -> 和 <-> 操作。一旦我有了所有包含元素运算符的表达式（&&、||、! 和 ()），我就必须使用 De Morgan 的方法来分发 ! 运算符定律并将 || 分布到 returns 其合取范式。听起来很简单，但实际上并非如此（至少对我来说不是）。
你还记得我说过规则不是按照令牌到达的顺序执行的吗？。在这种情况下，我可以应用 -> 运算符：让 a->b 在左侧表达式 (a) 中添加一个 ! 并在这两个表达式之间插入 || （a 和 b）。我可以这样做，在我的树中添加一个父节点 (!)、一个右子节点 a、一个 || 父节点和另一个子节点 b:
||
/ \
! b
\
a
所以，在这种情况下可行，但我不能用 <-> 运算符做同样的事情！
所以，我的问题是：我该如何解决这些问题？您是否推荐使用另一种结构来存储令牌？您知道这样做的任何技术吗？
密码
parser.y
%{
#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 {
$$ = ;
cout << "ACA ENTRO A LA REGLA 0" << endl;
tree.pushSymbol();
}
| LEFT_PAR expr RIGHT_PAR {
$$ = ;
tree.pushLogicOperator("()");
}
| NOT expr {
$$ = ;
tree.pushLogicOperator("!");
}
| DIST expr RIGHT_PAR {
$$ = ;
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();
tree.pushLogicOperator("||");
tree.pushLogicOperator("!");
}
%%
void yyerror(char *s) {
}
scanner.l
%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;
}
[ [=15=][=15=]] {
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)[=16=][=16=]");
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：如果我写错了或者有什么不明白的地方，请问我，这样我才能更好的表达；我的英语很差（我来自阿根廷），我觉得这个问题很难解释，所以我希望你能理解。
使用这个伪代码：
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++ 解析字符串来实现。确保以一致的方式从左到右或从右到左解析。这将决定逻辑是左结合还是右结合。
如果您发现此替换方案有歧义，请告诉我。