compiler-errors - 简单 C 语法中的移位/减少冲突

Question

我正在用简单的 C 为编译器编写解析器，我试图理解为什么我有
yacc:22 个 shift/reduce 冲突，15 个 reduce/reduce 冲突。

文件

 letter      [a-zA-Z]
Hexdigits   [A-F|0-9]
OctalDigit  [0-7]
digit       [0-9]
digitMZ     [1-9]
newline     (\n)
integerNum  "0"|{digitMZ}{digit}*
HexNumber   ("0X"|"0x"){Hexdigits}+
OctalNumber ["0"]{OctalDigit}+
BinaryNumber ["0"|"1"]+"b"
identifier  {letter}({letter}|{digit}|"_")*
char        "'"."'"
wordString  \"[^\"]*\"
Comment     "/%"[^"%/"]+"%/"
StrDec      "["{integerNum}"]"

%{

%}

%option yylineno

%%
"string"" "*{StrDec} { return STRING_DECLERATION;}
boolean     { return BOOLEAN; } 
else        { return ELSE; }
if          { return IF; }
integer     { return INTEGER; }
procedure   { return PROCEDURE; }
char        { return CHAR; }
string      { return STRING; }
var         { return VAR; }
intptr      { return INTPTR; }
charptr     { return CHARPTR; }
return      { return RETURN; }
void        { return VOID; }
while       { return WHILE; }
"isprint()" { return IS_PRINT; }

true|false  { return BOOLCONSTANT; } 
":"         { return COLON; }
"+"         { return PLUS; }
"&"         { return ADDRESS; }
"^"         { return DEREFERENCE; }
"-"         { return MINUS; }              
"*"         { return MULTIPLICATION; }
"&&"        { return AND; }
"/"         { return DIVISION; }
"<="        { return LESSEQUAL; }
"<"         { return LESS; }
">"         { return GREATER; }
">="        { return GREATEREQUAL; }
"=="        { return EQUAL; }
"!="        { return NOTEQUAL; }
"="         { return ASSIGN; }
";"         { return SEMICOLON; }
","         { return COMMA; }
"("         { return LEFTPAREN; }
")"         { return RIGHTPAREN; }
"["         { return LEFTBRACKET; }
"]"         { return RIGHTBRACKET; }
"{"         { return LEFTBRACE; }
"}"         { return RIGHTBRACE; }
"||"        { return OR; }
"!"         { return NOT; }
" "+        { }
"|"     {return ABS_LENGTH;}
"   "+  {}

{newline}       { }
{Comment}   {}
{wordString}    {return WORDSTRING; }
{integerNum}    {return INTEGER_CONST; }
{char}          {return CHAR_IDENTIFIER; }
{identifier}    {return IDENTIFIER; }
{HexNumber}     {return HEX_NUMBER; }
{OctalNumber}   {return OCTAL_NUMBER; }
{BinaryNumber}  {return BINARY_NUMBER; }
.               {return ERROR; }

%%

yacc 文件

    %{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define YYDEBUG 1
#define YYSTYPE struct node*
int yyerror(char*);
int yylex();
typedef struct node
{
    char * rtoken;
    struct node * left;
    struct node * right;
    char * ltoken;
}node;

node * mknode(char * ltoken, node * left, node * right,char * rtoken);
void printtree(node * tree);
char * getLT(node *);

extern char *yytext;



%}

%token STRING_DECLERATION
%token STRING 
%token WORDSTRING
%token BOOLEAN
%token BREAK
%token ELSE
%token IF
%token IMPLEMENTS
%token INTEGER
%token PROCEDURE
%token CHAR
%token VAR
%token INTPTR
%token CHARPTR
%token RETURN
%token VOID
%token WHILE
%token IS_PRINT
%token BOOLCONSTANT
%token PLUS
%token COLON
%token ADDRESS
%token DEREFERENCE
%token MINUS
%token MULTIPLICATION
%token AND
%token DIVISION
%token LESS
%token LESSEQUAL
%token GREATER
%token GREATEREQUAL
%token EQUAL 
%token NOTEQUAL
%token ASSIGN
%token SEMICOLON
%token COMMA
%token LEFTPAREN
%token RIGHTPAREN
%token LEFTBRACKET
%token RIGHTBRACKET
%token LEFTBRACE
%token RIGHTBRACE
%token OR
%token NOT
%token ABS_LENGTH
%token CHAR_IDENTIFIER
%token HEX_NUMBER
%token OCTAL_NUMBER
%token BINARY_NUMBER
%token ERROR
%token INTEGER_CONST
%token IDENTIFIER
%% 

start: s{printtree($1);}
        ;

s:      expr {$$=$1;}
        |expr s {node *yu = mknode("",$1,NULL,"\n");$$= mknode("",yu,$2,"");}
        ;

expr:       function {$$=$1;}
        |assignment SEMICOLON {$$=$1;}
        |decleration SEMICOLON   {$$=$1;}
        |condition  {$$=$1;}
        |BRACES {$$=$1;}

        ;

function:   PROCEDURE iden LEFTPAREN argListOpt RIGHTPAREN RETURN identifiertype compondStmt
        {node *z =mknode("RETURN:",$7,NULL,"\n");node *o =mknode(getLT($2),$4,z,""); $$ = mknode("(PROCEDURE",o,$8,"\n)\n");}
        |PROCEDURE iden LEFTPAREN RIGHTPAREN RETURN identifiertype compondStmt
        {node *z2 = mknode("",NULL,NULL,"");node *z1 =mknode("RETURN:",$6,NULL,"\n");
        node *o =mknode(getLT($2),z2,z1,""); $$ = mknode("(PROCEDURE",o,$7,"\n)\n");}   
        ;

argListOpt: multidentifier COLON identifiertype SEMICOLON argListOpt
        {node *fg =mknode("",$1,$3,""); $$ = mknode("recive:",fg,$5,"");}
        |multidentifier COLON identifiertype{$$ = mknode("recive:",$1,$3,"");}
        ;

compondStmt:    BRACES{$$=$1;}
        |SEMICOLON{$$ = mknode("",NULL,NULL,"");}
        ;

functionCall:   iden LEFTPAREN sendArgs RIGHTPAREN{node *Sgl = mknode("(",$3,NULL,")");$$= mknode("",$1,Sgl,"");}
        |iden LEFTPAREN RIGHTPAREN {node *Sgg = mknode("(",NULL,NULL,")");$$= mknode("",$1,Sgg,"");}
        ;

sendArgs:   return_val {$$=$1;}
        |sendArgs COMMA return_val {node *SA = mknode("",$1,NULL,",");$$= mknode("",SA,$3,"");}
        ;


BRACES:     LEFTBRACE All RIGHTBRACE    {$$ = mknode("\n{BRACES\n",$2,NULL,"\n}");}
        |LEFTBRACE RIGHTBRACE{$$ = mknode("\n{BRACES\n",NULL,NULL,"\n}");}
        |LEFTBRACE BRACES RIGHTBRACE{$$ = mknode("\n{BRACES\n",$2,NULL,"\n}");}
        ;


All:        RETURN return_val SEMICOLON{$$ = mknode("RETURN",$2,NULL,"\n");}
        |All RETURN return_val SEMICOLON{node * K = mknode("RETURN",$2,NULL,"");$$ = mknode("",$1,K,"\n");}
        |All function{$$ = mknode("",$1,$2,"\n");}
        |function {$$=$1;}
        |assignment {$$ = mknode("(",$1,NULL,")\n");}
        |assignment SEMICOLON   {$$ = mknode("(",$1,NULL,")\n");}
        |decleration SEMICOLON{$$=$1;}
        |decleration{$$=$1;}
        |All decleration SEMICOLON  {$$ = mknode("",$1,$2,"\n");}
        |All assignment SEMICOLON {$$ = mknode("",$1,$2,"\n");}
        |condition{$$=$1;}
        |All condition{$$ = mknode("",$1,$2,"\n");}
        |All BRACES {$$ = mknode("",$1,$2,"\n");}
        |BRACES All {$$ = mknode("",$1,$2,"\n");}
        ;

return_val: int_num{$$=$1;}
        |iden {$$=$1;}
        |wstring{$$ = $1;}
        |exp{$$=$1;}
        |char_id{$$ = mknode(yytext,NULL,NULL,"");}
        |bool{$$=$1;}
        |wordlength{$$=$1;}
        |absolute{$$=$1;}
        |identifierabs{$$=$1;}
        ;

decleration:    VAR multidentifier COLON identifiertype {$$ = mknode("",$2,$4,"\n");}
        ;

multidentifier: iden {$$=$1;}
        | multidentifier COMMA iden{node *er = mknode("",$1,NULL,",");$$= mknode("",er,$3,"");}
        ;

bool: BOOLCONSTANT{$$ = mknode(yytext,NULL,NULL,"");}
        ;

assignment :    iden ASSIGN functionCall {node *pop = mknode("=",$1,NULL,"");$$ = mknode("\t(",pop,$3,")");}
        | iden ASSIGN exp {node *rop = mknode("=",$1,NULL,"");$$ = mknode("\t(",rop,$3,")");}
        | iden ASSIGN bool{node *nop = mknode("=",$1,NULL,"");$$ = mknode("\t(",nop,$3,")");}
        | iden ASSIGN pointeroperator iden
        {node *gh= mknode("",$3,$4,"");node *e1 = mknode("=",$1,NULL,"");$$ = mknode("\t(",e1,gh,")");}
        | iden ASSIGN iden {node *e2 = mknode("=",$1,NULL,"");$$ = mknode("\t(",e2,$3,")");}
        | iden ASSIGN wstring {node *e3 = mknode("=",$1,NULL,"");$$ = mknode("\t(",e3,$3,")");}
        | iden ASSIGN char_id{node *e4 = mknode("=",$1,NULL,"");$$ = mknode("\t(",e4,$3,")");}
        | iden ASSIGN "null"{node *e5 = mknode("=",$1,NULL,"");$$ = mknode("\t(",e5,NULL,"NULL)");}
        ;
char_id: CHAR_IDENTIFIER {$$ = mknode(yytext,NULL,NULL,"");}
        ;

exp:        int_num {$$=$1;}  
            |exp methoperator exp  {node *y = mknode(getLT($2),$1,NULL,"");$$ = mknode("(",y,$3,")");}
            |LEFTPAREN exp methoperator exp RIGHTPAREN {node *y = mknode(getLT($3),$2,NULL,"");$$ = mknode("(",y,$4,")");}/**/
        |iden {$$=$1;}
        |LEFTPAREN exp RIGHTPAREN {$$ = mknode("(",$2,NULL,")");}/**/
            ;

condition:  whileCond{$$=$1;}
        |ifCond{$$=$1;}
        ;

ifCond:     IF LEFTPAREN innercond RIGHTPAREN BRACES{$$ = mknode("(COND \n",$3,$5,"\n)\n");}
        |IF LEFTPAREN innercond RIGHTPAREN BRACES ELSE BRACES{node *yk= mknode("ELSE",$7,NULL,"");
        node *j= mknode("",$5,yk,"");$$ = mknode("(COND \n",$3,j,"\n)\n");}
        ;

whileCond:  WHILE LEFTPAREN innercond RIGHTPAREN BRACES {$$ = mknode("(LOOP \n",$3,$5,"\n)\n");}    
        ;

wstring: WORDSTRING{$$ = mknode(yytext,NULL,NULL,"");}
        ;
condexp:    exp signoperator exp {$$ = mknode(getLT($2),$1,$3,"");}
        |wstring IsEqual wstring {$$ = mknode(getLT($2),$1,$3,"");}
        |iden signoperator exp{$$ = mknode(getLT($2),$1,$3,"");}
        |bool{$$=$1;}
        |iden IsEqual wstring {$$ = mknode(getLT($2),$1,$3,"");}
        |wstring IsEqual iden{$$ = mknode(getLT($2),$1,$3,"");}
        |char_id IsEqual char_id {$$ = mknode(getLT($2),$1,$3,"");}
        |iden IsEqual char_id {$$ = mknode(getLT($2),$1,$3,"");}
        |char_id IsEqual iden{$$ = mknode(getLT($2),$1,$3,"");}
        |exp signoperator wordlength {$$ = mknode(getLT($2),$1,$3,"");}
        |wordlength signoperator exp {$$ = mknode(getLT($2),$1,$3,"");}
        |exp signoperator absolute{$$ = mknode(getLT($2),$1,$3,"");}    
        |absolute signoperator exp{$$ = mknode(getLT($2),$1,$3,"");}
        |wordlength signoperator absolute{$$ = mknode(getLT($2),$1,$3,"");} 
        |absolute signoperator wordlength {$$ = mknode(getLT($2),$1,$3,"");}
        |identifierabs signoperator exp {$$ = mknode(getLT($2),$1,$3,"");}
        |identifierabs signoperator wordlength{$$ = mknode(getLT($2),$1,$3,"");}
        |identifierabs signoperator absolute{$$ = mknode(getLT($2),$1,$3,"");}
        |identifierabs signoperator identifierabs{$$ = mknode(getLT($2),$1,$3,"");}
        ;


wordlength: ABS_LENGTH wstring ABS_LENGTH {$$ = mknode("|",$2,NULL,"|");}
        ;

absolute :  ABS_LENGTH int_num ABS_LENGTH{$$ = mknode("|",$2,NULL,"|");}    
        ;

identifierabs:  ABS_LENGTH iden ABS_LENGTH {$$ = mknode("|",$2,NULL,"|");}
        ;

innercond:  condexp {$$=mknode("\t(",$1,NULL,")");}
        |LEFTPAREN condexp RIGHTPAREN{$$ = mknode("(",$2,NULL,")");}
        |LEFTPAREN condexp RIGHTPAREN condoperator innercond{node *t  = mknode("",$4,$5,"");$$ = mknode("(",$2,t,")");}
        |condexp condoperator innercond
        {node *lolo = mknode("(",$1,NULL,"");node *Sr = mknode(getLT($2),lolo,NULL,")");$$= mknode(" ",Sr,$3,"");}
        |LEFTPAREN condexp condoperator innercond RIGHTPAREN
        {node *lili = mknode("(",$2,NULL,"");node *Sr = mknode(getLT($3),lili,NULL,",");$$= mknode(" ",Sr,$4,")");}
        ;


methoperator:   PLUS    {$$ = mknode(yytext,NULL,NULL,"");}
        |MINUS  {$$ = mknode(yytext,NULL,NULL,"");}
        |MULTIPLICATION     {$$ = mknode(yytext,NULL,NULL,"");}
        |DIVISION   {$$ = mknode(yytext,NULL,NULL,"");}
        ;

pointeroperator:ADDRESS {$$ = mknode(yytext,NULL,NULL,"");} 
        |DEREFERENCE    {$$ = mknode(yytext,NULL,NULL,"");}
        ;
identifiertype: STRING_DECLERATION  {$$ = mknode(yytext,NULL,NULL,"");}
        |BOOLEAN    {$$ = mknode(yytext,NULL,NULL,"");}
        |INTEGER    {$$ = mknode(yytext,NULL,NULL,"");}
        |CHAR   {$$ = mknode(yytext,NULL,NULL,"");}
        |INTPTR     {$$ = mknode(yytext,NULL,NULL,"");}
        |CHARPTR    {$$ = mknode(yytext,NULL,NULL,"");}
        |int_num{$$=$1;}
        ;

iden :      IDENTIFIER {$$ = mknode(yytext,NULL,NULL,"");}
        ;
signoperator:   LESS    {$$ = mknode(yytext,NULL,NULL,"");}
        |LESSEQUAL  {$$ = mknode(yytext,NULL,NULL,"");}
        |GREATER    {$$ = mknode(yytext,NULL,NULL,"");}
        |GREATEREQUAL   {$$ = mknode(yytext,NULL,NULL,"");}
        |IsEqual    {$$=$1;}
        ;

IsEqual:    EQUAL   {$$ = mknode(yytext,NULL,NULL,"");} 
        |NOTEQUAL   {$$ = mknode(yytext,NULL,NULL,"");}
        ;

condoperator:   AND {$$ = mknode(yytext,NULL,NULL,"");}
        |OR {$$ = mknode(yytext,NULL,NULL,"");}
        ;

int_num:    INTEGER_CONST   {$$ = mknode(yytext,NULL,NULL,"");}
        |BINARY_NUMBER  {$$ = mknode(yytext,NULL,NULL,"");}
        |OCTAL_NUMBER   {$$ = mknode(yytext,NULL,NULL,"");}
        |HEX_NUMBER {$$ = mknode(yytext,NULL,NULL,"");}
        ;

%%

#include "lex.yy.c"
int main()
{
return yyparse();
}
node* mknode(char * ltoken, node * left, node * right,char * rtoken)
{
node * newnode = (node*)malloc(sizeof(node));
char * newstr = (char*)malloc(sizeof(ltoken)+1);
strcpy(newstr, ltoken);
char * newstrr = (char*)malloc(sizeof(rtoken)+1);
strcpy(newstrr, rtoken);
newnode->left = left;
newnode->right = right;
newnode->ltoken = newstr;
newnode->rtoken = newstrr;
return newnode;
}

void printtree(node * tree)
{
printf("%s ", tree->ltoken);
if (tree->left)
    printtree(tree->left);
if (tree->right)
    printtree(tree->right);
printf("%s ", tree->rtoken);
}
int yyerror(char* s)
{
extern int yylineno;
printf("yacc error: %s at line %d\n",s,yylineno); return 0;
}
char * getLT(node * s)
{
return s->ltoken;
}

我运行调试，我明白为什么所有这些冲突，但我并不真正理解它的含义。

这是我的调试输出(我添加了链接，因为它是长文档)

debug output

Answer 1

冲突不是错误，它们基本上意味着解析器生成器无法决定在某些阶段应用哪个规则。移位/减少冲突是指您可以完成规则(减少)或使用下一个 token (移位)并从该状态继续。一个典型的 shift/reduce 问题是 if-else 语句:

if condition
    if another condition
        # Do something...
    else
        # Do something else

else 分支属于哪个 if 语句？看这个:

IF <condition> <statement> IF <condition> <statement> ELSE <statement>
                                  The parser is here ^

如果解析器决定转移，则 else 分支将成为内部语句的一部分，但如果它减少，则外部分支将拥有它。通常shift-reduce冲突是通过shift而不是reduce来处理的。

现在，当您的语法出现 fatal error 时，就会发生 reduce-reduce 冲突，因为 2 个规则适用于相同的输入。例如:

sequence:
       %empty         { printf ("empty sequence\n"); }
     | maybeword
     | sequence word  { printf ("added word %s\n", $2); }
     ;

maybeword:
       %empty    { printf ("empty maybeword\n"); }
     | word      { printf ("single word %s\n", $1); }
     ;

因此，请查看您的语法并找到那些减少-减少冲突!

如果您只是学习解析，则应该考虑的一件事是，首先尝试滚动您自己的解析器(例如自上而下的递归下降解析器)!这还不错，您将使用的最复杂的算法可能是用于数学表达式的调车场算法。另外，您将受益于更好的错误处理和自定义语法，这些是解析器生成器无法解析的(没有黑客攻击)。