我正在为简单的C编译器编写一个解析器，我试图理解为什么我有 yacc：22次/减少冲突，15减少/减少冲突。
lex文件
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;
}
我运行调试，我明白为什么所有这些冲突，但我真的不明白这意味着什么。
这是我的调试输出（我添加了链接，因为它是长文档）
冲突不是错误，它们基本上意味着解析器生成器无法决定在某些阶段应用哪个规则。转换/减少冲突是指您可以完成规则（减少）或使用下一个令牌（转移）并从该状态继续。典型的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分支将成为内部语句的一部分，但如果它减少，则外部语句将拥有它。通常，移位减少冲突通过移位而不是减少来处理。
现在，当你的语法中有致命错误时会发生减少 - 减少冲突，因为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); }
;
所以看看你的语法，找到那些减少 - 减少冲突！
如果你只是学习解析，你应该考虑的事情，尝试首先推出自己的解析器（如自上而下的递归下降解析器）！它并不是那么糟糕，你将使用的最复杂的算法可能是数学表达式的分流码算法。此外，您将受益于更好的错误处理和自定义语法，无法使用解析器生成器解析（无需黑客攻击）。