flex&bison shift/reduce 冲突
flex&bison shift/reduce conflict
这是我的部分语法：
expr_address
: expr_address_category expr_opt { $$ = new ExprAddress(,*);}
| axis axis_data { $$ = new ExprAddress(,*);}
;
axis_data
: expr_opt { $$ = ;}
| sign { if( == MINUS)
$$ = new IntergerExpr(-1000000000);
else if( == PLUS)
$$ = new IntergerExpr(+1000000000);}
;
expr_opt
: { $$ = new IntergerExpr(0);}
| expr { $$ = ;}
;
expr_address_category
: I { $$ = NCAddress_I;}
| J { $$ = NCAddress_J;}
| K { $$ = NCAddress_K;}
;
axis
: X { $$ = NCAddress_X;}
| Y { $$ = NCAddress_Y;}
| Z { $$ = NCAddress_Z;}
| U { $$ = NCAddress_U;}
| V { $$ = NCAddress_V;}
| W { $$ = NCAddress_W;}
;
expr
: '[' expr ']' {$$ = ;}
| COS parenthesized_expr {$$ = new BuiltinMethodCallExpr(COS,*);}
| SIN parenthesized_expr {$$ = new BuiltinMethodCallExpr(SIN,*);}
| ATAN parenthesized_expr {$$ = new BuiltinMethodCallExpr(ATAN,*);}
| SQRT parenthesized_expr {$$ = new BuiltinMethodCallExpr(SQRT,*);}
| ROUND parenthesized_expr {$$ = new BuiltinMethodCallExpr(ROUND,*);}
| variable {$$ = ;}
| literal
| expr '+' expr {$$ = new BinaryOperatorExpr(*,PLUS,*);}
| expr '-' expr {$$ = new BinaryOperatorExpr(*,MINUS,*);}
| expr '*' expr {$$ = new BinaryOperatorExpr(*,MUL,*);}
| expr '/' expr {$$ = new BinaryOperatorExpr(*,DIV,*);}
| sign expr %prec UMINUS {$$ = new UnaryOperatorExpr(,*);}
| expr EQ expr {$$ = new BinaryOperatorExpr(*,EQ,*);}
| expr NE expr {$$ = new BinaryOperatorExpr(*,NE,*);}
| expr GT expr {$$ = new BinaryOperatorExpr(*,GT,*);}
| expr GE expr {$$ = new BinaryOperatorExpr(*,GE,*);}
| expr LT expr {$$ = new BinaryOperatorExpr(*,LT,*);}
| expr LE expr {$$ = new BinaryOperatorExpr(*,LE,*);}
;
variable
: d_h_address {$$ = new AddressExpr(*);}
;
d_h_address
: D INTEGER_LITERAL { $$ = new IntAddress(NCAddress_D,);}
| H INTEGER_LITERAL { $$ = new IntAddress(NCAddress_H,);}
;
我希望我的语法支持：
H100=20;
X;
X+0;
X+;
X+H100; //means H100 variable ref
前两位与X0相同；顺便说一下，符号 -> +/-;
但是bison报告冲突，bison.output的关键部分：
State 108
11 expr: sign . expr
64 axis_data: sign .
INTEGER_LITERAL shift, and go to state 93
REAL_LITERAL shift, and go to state 94
'+' shift, and go to state 74
'-' shift, and go to state 75
COS shift, and go to state 95
SIN shift, and go to state 96
ATAN shift, and go to state 97
SQRT shift, and go to state 98
ROUND shift, and go to state 99
D shift, and go to state 35
H shift, and go to state 36
'[' shift, and go to state 100
D [reduce using rule 64 (axis_data)]
H [reduce using rule 64 (axis_data)]
$default reduce using rule 64 (axis_data)
State 69
62 expr_address: axis . axis_data
INTEGER_LITERAL shift, and go to state 93
REAL_LITERAL shift, and go to state 94
'+' shift, and go to state 74
'-' shift, and go to state 75
COS shift, and go to state 95
SIN shift, and go to state 96
ATAN shift, and go to state 97
SQRT shift, and go to state 98
ROUND shift, and go to state 99
D shift, and go to state 35
H shift, and go to state 36
'[' shift, and go to state 100
D [reduce using rule 65 (expr_opt)]
H [reduce using rule 65 (expr_opt)]
$default reduce using rule 65 (expr_opt)
State 68
61 expr_address: expr_address_category . expr_opt
INTEGER_LITERAL shift, and go to state 93
REAL_LITERAL shift, and go to state 94
'+' shift, and go to state 74
'-' shift, and go to state 75
COS shift, and go to state 95
SIN shift, and go to state 96
ATAN shift, and go to state 97
SQRT shift, and go to state 98
ROUND shift, and go to state 99
D shift, and go to state 35
H shift, and go to state 36
'[' shift, and go to state 100
D [reduce using rule 65 (expr_opt)]
H [reduce using rule 65 (expr_opt)]
$default reduce using rule 65 (expr_opt)
我不知道怎么处理，谢谢提前。
编辑：
我做一个最小语法：
%{
#include <stdio.h>
extern "C" int yylex();
void yyerror(const char *s) { printf("ERROR: %s/n", s); }
%}
%token PLUS '+' MINUS '-'
%token D H I J K X Y Z INT
/*%type sign expr var expr_address_category expr_opt
%type axis */
%start word_list
%%
/*Above grammar lost this rule,it makes ambiguous*/
word_list
: word
| word_list word
;
sign
: PLUS
| MINUS
;
expr
: var
| sign expr
| '[' expr ']'
;
var
: D INT
| H INT
;
word
: expr_address
| var '=' expr
;
expr_address
: expr_address_category expr_opt
/*| '(' axis sign ')'*/
| axis sign
;
expr_opt
: /* empty */
| expr
;
expr_address_category
: I
| J
| K
| axis
;
axis
: X
| Y
| Z
;
%%
希望可以支持：
X;
X0;
X+0; //the top three are same with X0
X+;
X+H100; //this means X's data is ref +H100;
X+H100=10; //two word on a block,X+ and H100=10;
XH100=10; //two word on a block,X and H100=10;
编辑2：
上面的编辑失去了这条规则。
block
: word_list ';'
| ';'
;
因为我必须允许这样的语法：
H000 = 100 H001 = 200 H002 = 300;
主要问题是它无法确定 word_list 中的一个 word 在哪里结束，下一个在哪里开始，因为单词之间没有分隔符。这与您的示例形成对比，您的示例都有 ; 终止符。因此，这提出了一个明显的解决方法——放入 ; 分隔符：
word: expr_address ';'
| var '=' expr ';'
这解决了大部分问题，但留下了前瞻冲突，当前瞻是 sign 时，它无法决定 axis 是否是 expr_address_category，因为这取决于符号后面是否有expr。您可以通过重构来推迟决定来解决这个问题：
expr_address
: expr_address_category expr_opt
| axis expr_opt
| axis sign
..并从 expr_address_category
中删除 axis
这本质上是经典的 LR(2) 语法，除了在您的情况下它是 LR(3)，因为您的变量由两个标记组成[注 1]:
var : D INT | H INT
基本问题是没有分隔符的单词连接：
word_list : word | word_list word
结合 word 的选项之一以可选 var 结尾的事实：
word: expr_address
expr_address: expr_address_category expr_opt
而另一个以 var:
开头
word: var '=' expr
= 使这一点变得明确，因为 expr 中的任何内容都不能包含该符号。但是在需要做出决定的时候，= 是不可见的，因为前瞻是 var 的第一个标记——要么是 H 或 D -- 并且等号还差两个标记。
这个 LR(2) 文法与 yacc/bison 本身使用的文法非常相似，我总是觉得这个事实很讽刺，因为 yacc 的文法不需要 ； 两次制作之间：
production: SYMBOL ':' | production SYMBOL /* Lots of detail omitted */
与您的语法一样，这使得无法知道 SYMBOL 是否应该移动或触发减少，因为消除歧义的 : 仍然不可见。
由于语法（我假设）是明确的，并且 bison 现在可以生成 GLR 解析器，这将是最简单的解决方案：只需添加
%glr-parser
你的 bison 序言（但请阅读 bison 手册中有关 GLR 解析器的部分以了解权衡）。
请注意，shift-reduce 冲突仍将报告为警告；由于无法可靠地确定语法是否有歧义，因此 bison 不会尝试这样做，如果存在歧义，将在 运行 时报告。
您还应该修复 中提到的关于重构 expr_address 的问题（尽管使用 GLR 解析器并不是绝对必要的）。
如果出于某种原因，您觉得 GLR 解析器不能满足您的需要，您可以在 yacc（包括 bison）的大多数实现中使用该解决方案，这是词法扫描器中的 hack。基本思想是在词法分析器中标记一个符号后面是否跟冒号，这样上面的产生式可以改写为：
production: SYMBOL_COLON | production SYMBOL
如果您愿意将字母和数字组合成一个标记，此解决方案将适用于您：
word: expr_address expr_opt
| VARIABLE_EQUALS expr
// ...
expr: VARIABLE
我的偏好是在围绕词法分析器的包装器中进行这种转换，它保留一个（单元素）待处理标记队列：
/* The use of static variables makes this yylex wrapper unreliable
* if it is reused after a syntax error.
*/
int yylex_wrapper() {
static int saved_token = -1;
static YYSTYPE saved_yylval = {0};
int token = saved_token;
saved_token = -1;
yylval = saved_yylval;
// Read a new token only if we don't have one in the queue.
if (token < 0) token = yylex();
// If the current token is IDENTIFIER, check the next token
if (token == IDENTIFIER) {
// Read the next token into the queue (saved_token / saved_yylval)
YYSTYPE temp_val = yylval;
saved_token = yylex();
saved_yylval = yylval;
yylval = temp_val;
// If the second token is '=', then modify the current token
// and delete the '=' from the queue
if (saved_token == '=') {
saved_token = -1;
token = IDENTIFIER_EQUALS;
}
}
return token;
}
备注
就我个人而言，我会首先制作一个 var 单个标记（你真的想让人们写：
H /* Some comment in the middle of the variable name */ 100
但这并不能解决任何问题；它只是将语法的前瞻要求从 LR(3) 减少到 LR(2)。
这是我的部分语法：
expr_address
: expr_address_category expr_opt { $$ = new ExprAddress(,*);}
| axis axis_data { $$ = new ExprAddress(,*);}
;
axis_data
: expr_opt { $$ = ;}
| sign { if( == MINUS)
$$ = new IntergerExpr(-1000000000);
else if( == PLUS)
$$ = new IntergerExpr(+1000000000);}
;
expr_opt
: { $$ = new IntergerExpr(0);}
| expr { $$ = ;}
;
expr_address_category
: I { $$ = NCAddress_I;}
| J { $$ = NCAddress_J;}
| K { $$ = NCAddress_K;}
;
axis
: X { $$ = NCAddress_X;}
| Y { $$ = NCAddress_Y;}
| Z { $$ = NCAddress_Z;}
| U { $$ = NCAddress_U;}
| V { $$ = NCAddress_V;}
| W { $$ = NCAddress_W;}
;
expr
: '[' expr ']' {$$ = ;}
| COS parenthesized_expr {$$ = new BuiltinMethodCallExpr(COS,*);}
| SIN parenthesized_expr {$$ = new BuiltinMethodCallExpr(SIN,*);}
| ATAN parenthesized_expr {$$ = new BuiltinMethodCallExpr(ATAN,*);}
| SQRT parenthesized_expr {$$ = new BuiltinMethodCallExpr(SQRT,*);}
| ROUND parenthesized_expr {$$ = new BuiltinMethodCallExpr(ROUND,*);}
| variable {$$ = ;}
| literal
| expr '+' expr {$$ = new BinaryOperatorExpr(*,PLUS,*);}
| expr '-' expr {$$ = new BinaryOperatorExpr(*,MINUS,*);}
| expr '*' expr {$$ = new BinaryOperatorExpr(*,MUL,*);}
| expr '/' expr {$$ = new BinaryOperatorExpr(*,DIV,*);}
| sign expr %prec UMINUS {$$ = new UnaryOperatorExpr(,*);}
| expr EQ expr {$$ = new BinaryOperatorExpr(*,EQ,*);}
| expr NE expr {$$ = new BinaryOperatorExpr(*,NE,*);}
| expr GT expr {$$ = new BinaryOperatorExpr(*,GT,*);}
| expr GE expr {$$ = new BinaryOperatorExpr(*,GE,*);}
| expr LT expr {$$ = new BinaryOperatorExpr(*,LT,*);}
| expr LE expr {$$ = new BinaryOperatorExpr(*,LE,*);}
;
variable
: d_h_address {$$ = new AddressExpr(*);}
;
d_h_address
: D INTEGER_LITERAL { $$ = new IntAddress(NCAddress_D,);}
| H INTEGER_LITERAL { $$ = new IntAddress(NCAddress_H,);}
;
我希望我的语法支持：
H100=20;
X;
X+0;
X+;
X+H100; //means H100 variable ref
前两位与X0相同；顺便说一下，符号 -> +/-;
但是bison报告冲突，bison.output的关键部分：
State 108
11 expr: sign . expr
64 axis_data: sign .
INTEGER_LITERAL shift, and go to state 93
REAL_LITERAL shift, and go to state 94
'+' shift, and go to state 74
'-' shift, and go to state 75
COS shift, and go to state 95
SIN shift, and go to state 96
ATAN shift, and go to state 97
SQRT shift, and go to state 98
ROUND shift, and go to state 99
D shift, and go to state 35
H shift, and go to state 36
'[' shift, and go to state 100
D [reduce using rule 64 (axis_data)]
H [reduce using rule 64 (axis_data)]
$default reduce using rule 64 (axis_data)
State 69
62 expr_address: axis . axis_data
INTEGER_LITERAL shift, and go to state 93
REAL_LITERAL shift, and go to state 94
'+' shift, and go to state 74
'-' shift, and go to state 75
COS shift, and go to state 95
SIN shift, and go to state 96
ATAN shift, and go to state 97
SQRT shift, and go to state 98
ROUND shift, and go to state 99
D shift, and go to state 35
H shift, and go to state 36
'[' shift, and go to state 100
D [reduce using rule 65 (expr_opt)]
H [reduce using rule 65 (expr_opt)]
$default reduce using rule 65 (expr_opt)
State 68
61 expr_address: expr_address_category . expr_opt
INTEGER_LITERAL shift, and go to state 93
REAL_LITERAL shift, and go to state 94
'+' shift, and go to state 74
'-' shift, and go to state 75
COS shift, and go to state 95
SIN shift, and go to state 96
ATAN shift, and go to state 97
SQRT shift, and go to state 98
ROUND shift, and go to state 99
D shift, and go to state 35
H shift, and go to state 36
'[' shift, and go to state 100
D [reduce using rule 65 (expr_opt)]
H [reduce using rule 65 (expr_opt)]
$default reduce using rule 65 (expr_opt)
我不知道怎么处理，谢谢提前。
编辑： 我做一个最小语法：
%{
#include <stdio.h>
extern "C" int yylex();
void yyerror(const char *s) { printf("ERROR: %s/n", s); }
%}
%token PLUS '+' MINUS '-'
%token D H I J K X Y Z INT
/*%type sign expr var expr_address_category expr_opt
%type axis */
%start word_list
%%
/*Above grammar lost this rule,it makes ambiguous*/
word_list
: word
| word_list word
;
sign
: PLUS
| MINUS
;
expr
: var
| sign expr
| '[' expr ']'
;
var
: D INT
| H INT
;
word
: expr_address
| var '=' expr
;
expr_address
: expr_address_category expr_opt
/*| '(' axis sign ')'*/
| axis sign
;
expr_opt
: /* empty */
| expr
;
expr_address_category
: I
| J
| K
| axis
;
axis
: X
| Y
| Z
;
%%
希望可以支持：
X;
X0;
X+0; //the top three are same with X0
X+;
X+H100; //this means X's data is ref +H100;
X+H100=10; //two word on a block,X+ and H100=10;
XH100=10; //two word on a block,X and H100=10;
编辑2：
上面的编辑失去了这条规则。
block
: word_list ';'
| ';'
;
因为我必须允许这样的语法：
H000 = 100 H001 = 200 H002 = 300;
主要问题是它无法确定 word_list 中的一个 word 在哪里结束，下一个在哪里开始，因为单词之间没有分隔符。这与您的示例形成对比，您的示例都有 ; 终止符。因此，这提出了一个明显的解决方法——放入 ; 分隔符：
word: expr_address ';'
| var '=' expr ';'
这解决了大部分问题，但留下了前瞻冲突，当前瞻是 sign 时，它无法决定 axis 是否是 expr_address_category，因为这取决于符号后面是否有expr。您可以通过重构来推迟决定来解决这个问题：
expr_address
: expr_address_category expr_opt
| axis expr_opt
| axis sign
..并从 expr_address_category
axis
这本质上是经典的 LR(2) 语法，除了在您的情况下它是 LR(3)，因为您的变量由两个标记组成[注 1]:
var : D INT | H INT
基本问题是没有分隔符的单词连接：
word_list : word | word_list word
结合 word 的选项之一以可选 var 结尾的事实：
word: expr_address
expr_address: expr_address_category expr_opt
而另一个以 var:
word: var '=' expr
= 使这一点变得明确，因为 expr 中的任何内容都不能包含该符号。但是在需要做出决定的时候，= 是不可见的，因为前瞻是 var 的第一个标记——要么是 H 或 D -- 并且等号还差两个标记。
这个 LR(2) 文法与 yacc/bison 本身使用的文法非常相似，我总是觉得这个事实很讽刺，因为 yacc 的文法不需要 ； 两次制作之间：
production: SYMBOL ':' | production SYMBOL /* Lots of detail omitted */
与您的语法一样，这使得无法知道 SYMBOL 是否应该移动或触发减少，因为消除歧义的 : 仍然不可见。
由于语法（我假设）是明确的，并且 bison 现在可以生成 GLR 解析器，这将是最简单的解决方案：只需添加
%glr-parser
你的 bison 序言（但请阅读 bison 手册中有关 GLR 解析器的部分以了解权衡）。
请注意，shift-reduce 冲突仍将报告为警告；由于无法可靠地确定语法是否有歧义，因此 bison 不会尝试这样做，如果存在歧义，将在 运行 时报告。
您还应该修复 expr_address 的问题（尽管使用 GLR 解析器并不是绝对必要的）。
如果出于某种原因，您觉得 GLR 解析器不能满足您的需要，您可以在 yacc（包括 bison）的大多数实现中使用该解决方案，这是词法扫描器中的 hack。基本思想是在词法分析器中标记一个符号后面是否跟冒号，这样上面的产生式可以改写为：
production: SYMBOL_COLON | production SYMBOL
如果您愿意将字母和数字组合成一个标记，此解决方案将适用于您：
word: expr_address expr_opt
| VARIABLE_EQUALS expr
// ...
expr: VARIABLE
我的偏好是在围绕词法分析器的包装器中进行这种转换，它保留一个（单元素）待处理标记队列：
/* The use of static variables makes this yylex wrapper unreliable
* if it is reused after a syntax error.
*/
int yylex_wrapper() {
static int saved_token = -1;
static YYSTYPE saved_yylval = {0};
int token = saved_token;
saved_token = -1;
yylval = saved_yylval;
// Read a new token only if we don't have one in the queue.
if (token < 0) token = yylex();
// If the current token is IDENTIFIER, check the next token
if (token == IDENTIFIER) {
// Read the next token into the queue (saved_token / saved_yylval)
YYSTYPE temp_val = yylval;
saved_token = yylex();
saved_yylval = yylval;
yylval = temp_val;
// If the second token is '=', then modify the current token
// and delete the '=' from the queue
if (saved_token == '=') {
saved_token = -1;
token = IDENTIFIER_EQUALS;
}
}
return token;
}
备注
就我个人而言，我会首先制作一个
var单个标记（你真的想让人们写：H /* Some comment in the middle of the variable name */ 100但这并不能解决任何问题；它只是将语法的前瞻要求从 LR(3) 减少到 LR(2)。