NOT 代币在 bison 中的分布

Question

给定一个用 C++ 编写的 if 条件（仅条件部分）的输入，我想根据德摩根定律分配 "nots"。问题是根据我的规则，递归不允许我在找到符号“！”时立即得到括号内的表达式，然后我可以分配。让我用一个例子来解释：

输入： (!(a&&(b&&!(c&&d))))

输出（在找到每个令牌的时间。）： c AND d ) ( b AND NOT b ) ( a AND ) ( ) ( NOT

输出被递归打乱了，但是在这种情况下，我该如何应用德摩根定律？，在这个输入的情况下，我想得到：

(!(a&&(b&&!(c&&d))))->(!a&&!(b&&!(c&&d)))->(!a&&b&&(c||d))

请注意，每次我找到一个 ! 令牌时，都会立即用于下一个括号中的分发。如果我得到 (!a&&b)，我不必使用它，只有当我找到 ! 和 ( 作为下一个符号时才使用它。

所以，问题是：我无法在下一组条件中分配 ! 令牌，因为我得到的所有令牌都是无序的。

这可能吗？我该如何定义我的规则来做到这一点？

main.cpp:

#include <iostream>
#include <string>
#include "lex.yy.c"

using namespace std;

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

int main(int argc, char** argv) {

    char condition[] = "(!(a&&(b&&!(c&&d)))) [=11=][=11=]";

    yy_scan_buffer(condition, sizeof(condition));

    yyparse();

    return 0;
}

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;
}

[ [=12=][=12=]] {
    return END;
}

"("     {
    return LEFT_PAR;
}

")"     {
    return RIGHT_PAR;
}

%%

bison.y:

%{
    #include <iostream>
    #include <string>

    using namespace std;

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

    #define YYSTYPE string
%}

%token  LEFT_PAR
        RIGHT_PAR
        SYMBOL
        END
        NOT

%left
        AND
        OR

%start input

%%

input:

    |   input terms
;

terms:
        LEFT_PAR terms close_terms        {  
            cout << " ( ";
        }
    |   LEFT_PAR condition close_terms       {  
            cout << " ( ";
        }
    |   LEFT_PAR NOT condition close_terms   {
            cout << " ( NOT ";
        }
    |   LEFT_PAR NOT terms close_terms    {
            cout << " ( NOT ";
        }
;

close_terms:
    RIGHT_PAR { 
        cout << " ) ";
    }
;

binary_condition:
        terms AND terms   { 
            cout << " AND ";
        }
    |   SYMBOL AND terms    {
            cout <<  << " AND ";
        }
    |   SYMBOL AND NOT terms {
            cout <<  << " AND NOT " << ;
        }
    |   terms AND SYMBOL    {
            cout << " AND " << ;
        }
    |   SYMBOL AND SYMBOL     {
            cout <<  << " AND " << ;
        }
    |   SYMBOL AND NOT SYMBOL {
            cout <<  << " AND NOT " << ;
        }



    |   terms OR terms    { 
            cout << " OR ";
        }
    |   SYMBOL OR terms     {
            cout <<  << " OR ";
        }
    |   SYMBOL OR NOT terms {
            cout <<  << " OR NOT ";
        }
    |   terms OR SYMBOL     {
            cout << " OR " << ;
        }
    |   SYMBOL OR SYMBOL      {
            cout <<  << " OR " << ;
        }
    |   SYMBOL OR NOT SYMBOL {
            cout <<  << " OR NOT " << ;
        }
;


condition:
        SYMBOL                         {
            cout << ;
        }          
    |   binary_condition
    |   binary_condition AND condition  
    |   binary_condition OR condition
;

%%

void yyerror(char *s) {

}

谢谢！

Answer 1

通常最有意义的做法是让你的语法尽可能简单以用于你想要解析的内容，然后将你想要进行的任何转换视为对解析树的转换，而不是试图改变语法某种程度上来说。在你的情况下，你有一个非常混乱的语法——你已经使 AND 和 OR 右递归并且优先级相等（尽管 %left 声明没有效果，因为有没有冲突需要解决。）

所以你从简单的表达式语法开始：

%left '|'
%left '&'   /* & and | are left recursive, with & having higher precedence */
%%

input: /* empty */ | input expr '\n' ;

expr: SYMBOL | '(' expr ')' | '!' expr | expr '&' expr | expr '|' expr

然后添加规则来构建表达式树数据结构并转换它们：

input: /* empty */ | input expr '\n' { PrintExpr(ConvertToNormalForm()); }
expr: SYMBOL { $$ = CreateSymbolNode(); }
    | '(' expr ')' { $$ = ; }
    | '!' expr { $$ = CreateUnaryNode('!', ); }
    | expr '&' expr { $$ = CreateBinaryNode('&', , ); }
    | expr '|' expr { $$ = CreateBinaryNode('|', , ); }

NOT 代币在 bison 中的分布

Distribution of NOT token in bison

c++

parsing

bison

flex-lexer