Bison 编译器：消除冲突

Question

我正在使用 Bison 和 Flex 为类 C 语言开发编译器。目前，编译器能够识别具有声明、赋值和打印语句以及算术和逻辑表达式（仅使用 int 变量）的语言。它生成一个 3AC（以及一些用于管理内存的指令）。这是我的野牛代码：

%{

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include "list.h"

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

TList list = NULL;
int i=0;

char* tmp() {
    char* t = (char*)malloc(sizeof(char*));
    sprintf(t, "t%d", i);
    i++;
    return t;
}

%}

%union {
    int number;
    char* identifier;
}

%token <number> NUM
%token <identifier> ID
%token PRINT INT ENDFILE 
%left '+' '-'
%left '*' '/'
%right UMINUS
%left OR
%left AND
%right NOT
%nonassoc EQ LT GT LE GE NE
%type <identifier> expr
%type <identifier> comp
%type <identifier> bexpr


%%
program :   lstmt ENDFILE               { return 0; }
            ;

lstmt       : lstmt stmt ';'
            | stmt ';'
            | lstmt openb lstmt closeb
            | openb lstmt closeb
            ;

openb       : '{'                       { printf("list = insertElement(list);\n"); }
            ;

closeb      :  '}'                      { printf("list = removeElement(list);\n"); }
            ;

stmt        : INT ID                    { printf("addVar(\"%s\", &list->table);\n", ); }
            | INT ID '=' NUM            {
                                            printf("addVar(\"%s\", &list->table);\n", );
                                            printf("setVarList(\"%s\", %d, list);\n", , );
                                        }
            | ID '=' expr               { printf("setVarList(\"%s\", %s, list);\n", , ); }
            | PRINT '(' ID ')'          { printf("printf(\"%%s: %%d\n\", \"%s\", getVarList(\"%s\", list));\n", , ); }
            | ID '=' bexpr              { printf("setVarList(\"%s\", %s, list);\n", , ); }
            ;

bexpr       : bexpr OR bexpr            {
                                            $$ = tmp();
                                            printf("%s = %s || %s;\n", $$, , );
                                        }
            | bexpr AND bexpr           {
                                            $$ = tmp();
                                            printf("%s = %s && %s;\n", $$, , );
                                        }
            | expr OR bexpr             {
                                            $$ = tmp();
                                            printf("%s = %s || %s;\n", $$, , );
                                        }
            | expr AND bexpr            {
                                            $$ = tmp();
                                            printf("%s = %s && %s;\n", $$, , );
                                        }
            | bexpr OR expr             {
                                            $$ = tmp();
                                            printf("%s = %s || %s;\n", $$, , );
                                        }
            | bexpr AND expr            {
                                            $$ = tmp();
                                            printf("%s = %s && %s;\n", $$, , );
                                        }
            | NOT bexpr                 {
                                            $$ = tmp();
                                            printf("%s = !%s;\n", $$, );
                                        }
            | '(' bexpr ')'             { $$ = ; }
            | comp                      { $$ = ; }
            ;

comp        : expr LT expr              {
                                            $$ = tmp();
                                            printf("%s = %s < %s;\n", $$, , );
                                        }
            | expr LE expr              {
                                            $$ = tmp();
                                            printf("%s = %s <= %s;\n", $$, , );
                                        }
            | expr GT expr              {
                                            $$ = tmp();
                                            printf("%s = %s > %s;\n", $$, , );
                                        }
            | expr GE expr              {
                                            $$ = tmp();
                                            printf("%s = %s >= %s;\n", $$, , );
                                        }
            | expr EQ expr              {
                                            $$ = tmp();
                                            printf("%s = %s == %s;\n", $$, , );
                                        }
            | expr NE expr              {
                                            $$ = tmp();
                                            printf("%s = %s != %s;\n", $$, , );
                                        }
            | expr AND expr             {
                                            $$ = tmp();
                                            printf("%s = %s && %s;\n", $$, , );
                                        }
            | expr OR expr              {
                                            $$ = tmp();
                                            printf("%s = %s || %s;\n", $$, , );
                                        }
            | NOT expr                  {
                                            $$ = tmp();
                                            printf("%s = !%s;\n", $$, );
                                        }
            ;

expr        : expr '+' expr             {  
                                            $$ = tmp();
                                            printf("%s = %s + %s;\n", $$, , );
                                        }
            | expr '-' expr             { 
                                            $$ = tmp();
                                            printf("%s = %s - %s;\n", $$, , );
                                        }
            | expr '*' expr             {
                                            $$ = tmp();
                                            printf("%s = %s * %s;\n", $$, , );
                                        }
            | expr '/' expr             {
                                            $$ = tmp();
                                            printf("%s = %s / %s;\n", $$, , );
                                        }
            | '(' expr ')'              { $$ = ; }
            | '-' expr %prec UMINUS     { 
                                            $$ = tmp();
                                            printf("%s = -%s;\n", $$, ); 
                                        }
            | ID                        { 
                                            $$ = tmp();
                                            printf("%s = getVarList(\"%s\", list);\n", $$, );
                                        }
            | NUM                       {
                                            $$ = tmp();
                                            printf("%s = %d;\n", $$, );
                                        }
            ;

%%

int main () {
    list = insertElement(list);
    if(yyparse() !=0)
        fprintf(stderr, "Abonormal exit\n");

    fprintf(fopen("temp.h", "w"), "#include \"list.h\"\n\nTList list = NULL;\nint t" );
    for(int j=0; j<i-1; j++) {
        fprintf(fopen("temp.h", "a"), "%d, t", j);
    }
    fprintf(fopen("temp.h", "a"), "%d;", i-1);
    return 0;
}

void yyerror (char *s) {
    fprintf(stderr, "Error: %s\n", s);
}

如你所见，逻辑表达式的语法有点复杂，但编译器做了它应该做的。该行为类似于 C，因此可以在 AND/OR/NOT.

中使用整数值

我对语法的想法是这样的：

bexpr       : bexpr OR bexpr            
            | bexpr AND bexpr
            | NOT bexpr
            | '(' bexpr ')'
            | comp
            | expr
            ;

comp        : expr LT expr
            | expr LE expr
            | expr GT expr
            | expr GE expr
            | expr EQ expr
            | expr NE expr
            ;

但是这样我得到了两个冲突，1 shift/reduce 和 1 reduce/reduce。有没有办法简化语法？

Answer 1

我的建议是不要试图在语法上区分 bexpr 和 expr。它不能真正准确地完成，因为您允许将变量用作布尔值。可以肯定的是，您当前的语法是一项勇敢的努力，但是当您向语法中添加条件语句时，您会发现

if ((a)) ...

将被标记为语法错误（假设条件语句的语法类似于 C："if" '(' bexpr ')' stmt | "if" '(' bexpr ')' stmt "else" stmt）。并且很容易规避禁止使用算术表达式作为布尔运算符参数的尝试，因为 a AND (1 + -1) 是有效的 bexpr。有人可能还会问为什么 (a < b) == (b < c) 不应该是有效的语法。诚然，它有点模糊，但它是编写“b is between a and c”的一种便捷方式。

如果您真的想禁止使用算术运算作为布尔运算符 AND、OR 和 NOT 的参数，您可以通过创建两个并行层次结构来改进语法，或者通过简单地将表达式的类型标记为其语义值的一部分，并在每个语义操作中进行检查。第二个选项的优点是双重的：它简化了语法，消除了重复，并且提供了更精确的错误消息的可能性（"attempt to use arithmetic expression as boolean value" 而不是 "syntax error"）。

Bison 编译器：消除冲突

Bison compiler: remove conflicts

c

compiler-construction

bison

ambiguous-grammar