减少/减少冲突 - yacc（标识符）

Question

我正在尝试为 c 编写简单的解析器。我得到的错误是："reduce /reduce conflict"

1) 规则 exp 需要获取 IDENTIFIER 例如：a-b(identifier-identifier)-> exp-exp->exp

2) 规则 ident_list 也需要到达 IDENTIFIER 。此规则用于变量声明。例如：a,b,c(identifier,identifier,identifier)-> ident_list .

因此我需要两个规则，ident_list 和 exp 去 ->IDENTIFIER 。这导致 "reduce /reduce conflict"。知道如何解决这个问题吗？

-------------*yac code*:---------------


%{
        #include <stdio.h>
        #include <stdlib.h>
        #include <string.h>
        typedef struct node
        {
                char* token;
                struct node* left;
                struct node* right;
                char* type;
        }node;
         typedef struct obj
        {
                char* type;
                char* name;
                struct obj* next;


        }obj;

         typedef struct symTbl
        {
                struct obj* first;
                struct obj* last;
                int size;
        }symTbl;


        node* mknode (char* token,node* left, node* right,char* Type);
        void put(symTbl* tbl, char* type,char* name);
        void printtree(node* tree);
        #define YYSTYPE struct node*
%}
%start s
%token WHILELOOP
%token STATIF
%token ELSE
%token MAIN
%token POINTERERR
%token COMMENT
%token POINTER
%token GREATEREQUAL
%token LESSEREQUAL
%token DBLAND
%token GREATER
%token LESSER
%token POWER
%token MULTIPLY
%token MINUS
%token PLUS
%token AND
%token OR
%token NOT
%token NOTEQUAL
%token CHARERROR
%token STRINGERROR
%token POINTER
%token INTEGER
%token BOOLEAN
%token DEVIDE
%token ASSIGN
%token EQUAL
%token TYPE
%token IDENTIFIER
%token HEX IF
%token LITERCHAR
%token OCTAL
%token BINARYINT
%token LTRLSTRING
%token COMMA COLON SEMICOLON VAR RETURN RPARENC LPARENC
%left COMMA LPAREN RPAREN ELSE
%left PLUS IF WHILELOOP TYPE
%left MINUS DEVIDE RPARENC LPARENC
%left MULTIPLY EQUAL NOTEQUAL OR AND LESSEREQUAL GREATEREQUAL GREATER LESSER
%%
s:progrem{printtree();}
        progrem:exp|var_dec|if_stnt|ident_list|bool_exp| mul_ident;

        exp: exp PLUS exp{$$=mknode("+",,,"arit");}
            |exp MINUS exp {$$=mknode("-",,,"arit");}
            |exp DEVIDE exp {$$=mknode("/",,,"arit");}
            |exp MULTIPLY exp {$$=mknode("*",,,"arit");}
            |MINUS exp {$$=mknode("-",,NULL,"arit");}
            |IDENTIFIER {$$=mknode(yytext,NULL,NULL,"id");}
    |LPAREN exp RPAREN {$$= ;};
        bool_exp : exp EQUAL exp {$$=mknode("=",,,"bool");}
            |exp NOTEQUAL exp {$$=mknode("!=",,,"bool");}
            |exp OR exp {$$=mknode("||",,,"bool");}
            |exp AND exp {$$=mknode("&&",,,"bool");}
            |exp GREATEREQUAL exp {$$=mknode(">=",,,"bool");}
            |exp LESSER exp {$$=mknode("<",,,"bool");}
            |exp LESSEREQUAL exp {$$=mknode("<=",,,"bool");}
            |exp GREATER exp {$$=mknode(">",,,"bool");}
            |LPAREN bool_exp RPAREN {$$= ;};


          var_dec:ident_list COLON  ident_list {$$=mknode(":",,,"dec");};

          ident_list: ident_list COMMA ident_list {$$=mknode(",", , ,"id_list");}
                    |ident_list TYPE ident_list{$$=mknode(yytext,,NULL,"id");}
                    |VAR {$$= mknode("var",NULL,NULL,"id");}
                    |SEMICOLON  {$$= mknode(";",NULL,NULL,"id");};
                    |IDENTIFIER {$$=;}


         if_stnt:IF LPAREN bool_exp RPAREN  {$$=mknode("if",,NULL,"if_state");};
%%
#include "lex.yy.c"
main()
{
        yyin=fopen("text.txt","r");
        return yyparse();
}
node* mknode( char* token,node*left,node* right,char* Type)
{

        node* newnode=(node*)malloc(sizeof(node));
        char* newstr=(char*)malloc(sizeof(token)+1);
        char* type = (char*)malloc (sizeof(Type)+1);
        type[sizeof(token)]='[=10=]';
        newstr[sizeof(token)]='[=10=]';
        strcpy(newstr,token);
        strcpy(type,Type);
        newnode->left=left;
        newnode->type=type;
        newnode->right=right;
        newnode->token=newstr;
        return newnode;
}

 void put(symTbl* tbl, char* type,char* name)
{
         symTbl* tbl1=(symTbl*)malloc(sizeof(symTbl));

        int size = tbl->size;
        obj* newobj=(obj*)malloc(sizeof(obj));
        newobj= tbl->first;
        int i;
                for( i =0; i<size; i++){
                        if(newobj->name == name){

 yyerror();
                        newobj=newobj->next;
                }
           }
        tbl->last->next=newobj;
        tbl->last=tbl->last->next;

}

void printtree(node* tree)
{

        printf("%s",tree->token);
        if(tree->left)printtree(tree->left);
        if(tree->right)printtree(tree->right);
}
int yyerror()
{
        printf("bla bla\n");
        return 0;
}

--------lex 代码:------------

minus "-"
colon ":"
semicolon ";"
space " "
parcent "%"
backslash "/"
charptr charptr
plus "+"
not "!"
notequal "!="
or "||"
and "&&"
multiply "*"
power "^"
dbland "&"
greater ">"
lesser "<"
type boolean|string|char|integer|intptr|charptr
return "return"
greaterequal {greater}{assign}
lesserequal {lesser}{assign}
singleQuotes \'
charERR {singleQuotes}+(({digit})+)*(({letter})+)*{singleQuotes}+
stringERR {doubleQuotes}{doubleQuotes}+|{doubleQuotes}
doubleQuotes \"
var "var"{space}*
octalDigit [1-7]
decimal {digit}|{digitNoZero}{digit}+
digitNoZero[1-9]
octal "0"{octalDigit}("0")*{octalDigit}*
integer {binaryInt}|{hex}|{octal}|{decimal}
binaryInt ("0"|"1")+"b"
hexLetter A|B|C|D|E|F
hex 0(x|X){digit}+{hexLetter}*|0(x|X){digit}*{hexLetter}+
literBool true|false
letter [a-zA-Z]
letters {letter}+
digit [0-9]
low "_"
equal "=="
assign "="
devide "/"
lparen "("
rparen ")"
lparenc "{"
rparenc "}"
identifier {letter}+{digit}*{letter}+{space}*|{space}*{letter}{space}*
literChar {singleQuotes}{letter}{singleQuotes}
ltrlString {doubleQuotes}{letters}*{decimal}*{hex}*{octal}*{binaryInt}*{dbland}*{devide}*{assign}*{equal}*{greater}*{lesser}*{greaterequal}*{lesserequal}*{mi$
pointer {colon}{space}{charptr}|"="{space}"&"{identifier}
comment {backslash}{parcent}{space}*({letters}*{space}*{identifier}*{space}*{decimal}*{space}*{hex}*{space}*{octal}*{space}*{binaryInt}*{space}*{dbland}*{dev$
pointerErr "&"{identifier}|{charptr}
statif "if"{space}*
ELSE "else"{space}*
comma ","
whileLoop "while"{space}*
main "main"
%%
{lparen} return LPAREN;
{rparen} return RPAREN;
{colon} return COLON;
{type} return TYPE;
{semicolon} return SEMICOLON;
{var} return VAR;
{whileLoop} return WHILELOOP;
{ELSE} return ELSE;
{statif} return IF;
{pointerErr} return POINTERERR;
{comment} return COMMENT;
{pointer} return POINTER;
{literChar} return LITERCHAR;
{charERR} return CHARERROR;
{stringERR} return STRINGERROR;
{ltrlString} return LTRLSTRING;
{binaryInt} return BINARYINT;
{octal} return OCTAL;
{hex} return HEX;
{return} return RETURN;
{greaterequal} return GREATEREQUAL;
{lesserequal} return LESSEREQUAL;
{dbland} return DBLAND;
{greater} return GREATER;
{lesser} return LESSER;
{lparenc} return LPARENC;
{rparenc} return RPARENC;
{power} return POWER;
{multiply} return MULTIPLY;
{plus} return PLUS;
{or} return OR;
{and} return AND;
{comma} return COMMA;
{not} return NOT;
{main} return MAIN;
{notequal} return NOTEQUAL;
{minus} return MINUS;
{integer} return INTEGER;
{literBool} return BOOLEAN;
{identifier} return IDENTIFIER;
{equal} return EQUAL;
{assign} return ASSIGN;
{devide} return DEVIDE;
. return yytext[0];

Answer 1

您是说 program 可以是 exp 或 ident_list，等等。这不是特别明智的开始，我想你的意图是进行某种调试。但它不会起作用，因为单个标识符可能是一个表达式或只包含一个标识符的列表，并且解析器没有明显的方法来猜测您的意思。这使您的语法含糊不清。

yacc/bison 在这种情况下所做的是选择语法文件中较早出现的产生式。这不是定义首选项的非常精确的方法，因此它会警告您存在冲突。但是它可以让你表达你的喜好。

否则，你必须消除歧义。例如，如果您决定单个标识符应该是 exp，您可以坚持 top-level 标识符列表至少有两个标识符。

减少/减少冲突 - yacc（标识符）

reduce/ reduce conflict - yacc (identifier)

yacc