Bison - shift/reduce 冲突标识符
Bison - shift/reduce conflict identifier
我在状态 19 有 1 个 shift/reduce 冲突。我认为 'identifier' 的不同出现可能有问题，但我正在努力理解野牛报告并解决冲突.下面是我的语法，后面是带有状态信息的野牛报告：
%{
#include <cstdio>
#include <iostream>
using namespace std;
extern "C" int yylex();
extern "C" int yyparse();
void yyerror(const char *s);
%}
%union{
int int_val;
double d_val;
char *strng;
}
%token TLINEC TBLOCKC TPRINT
%token TASSIGN TCPA TOB TCB TCOMMA TSEMIC
%token TIF TELSE TFOR
%token TINT TFLOAT TD TCHAR
%token TPLUS TMINUS TDIV TMULT
%token TLT TGT TAND TOR TEQUAL TNE
%token<int_val> TINTEGER
%token<d_val> TDOUBLE
%token<strng> TID
%token TOPA
%start program
%%
program : command_list
command_list : declaration
| command_list declaration
declaration : function_dec
| variable_dec
| expression
variable_dec : type identifier TSEMIC
| type assignment TSEMIC
assignment : identifier TASSIGN expression
var_list : expression
| var_list TCOMMA expression
|
function_dec : type identifier TOPA p_list TCPA scope
p_list : variable_dec
| p_list TCOMMA variable_dec
type : TINT
| TD
| TFLOAT
| TCHAR
/* inside function scope */
scope : TOB command_list TCB
| TOB TCB
function_call : identifier TOPA var_list TCPA TSEMIC
/* expression rules */
expression : assignment
| function_call
| TOPA expression TCPA
| constant arithmetic_op expression
| constant logical_op expression
| constant
constant : identifier
| num
identifier : TID
num : TINTEGER
| TDOUBLE
arithmetic_op : TPLUS | TMINUS | TDIV | TMULT
logical_op : TLT | TGT | TAND | TOR | TEQUAL | TNE
%%
int main(int, char**){
int y=0;
do{
y=yyparse();
}while(y);
}
void yyerror(const char *s){
cout << "parse error! Message: " << s << endl;
exit(-1);
}
野牛报告：
State 19 conflicts: 1 shift/reduce
Grammar
0 $accept: program $end
1 program: command_list
2 command_list: declaration
3 | command_list declaration
4 declaration: function_dec
5 | variable_dec
6 | expression
7 variable_dec: type identifier TSEMIC
8 | type assignment TSEMIC
9 assignment: identifier TASSIGN expression
10 var_list: expression
11 | var_list TCOMMA expression
12 | /* empty */
13 function_dec: type identifier TOPA p_list TCPA scope
14 p_list: variable_dec
15 | p_list TCOMMA variable_dec
16 type: TINT
17 | TD
18 | TFLOAT
19 | TCHAR
20 scope: TOB command_list TCB
21 | TOB TCB
22 function_call: identifier TOPA var_list TCPA TSEMIC
23 expression: assignment
24 | function_call
25 | TOPA expression TCPA
26 | constant arithmetic_op expression
27 | constant logical_op expression
28 | constant
29 constant: identifier
30 | num
31 identifier: TID
32 num: TINTEGER
33 | TDOUBLE
34 arithmetic_op: TPLUS
35 | TMINUS
36 | TDIV
37 | TMULT
38 logical_op: TLT
39 | TGT
40 | TAND
41 | TOR
42 | TEQUAL
43 | TNE
Terminals, with rules where they appear
$end (0) 0
error (256)
TLINEC (258)
TBLOCKC (259)
TPRINT (260)
TASSIGN (261) 9
TCPA (262) 13 22 25
TOB (263) 20 21
TCB (264) 20 21
TCOMMA (265) 11 15
TSEMIC (266) 7 8 22
TIF (267)
TELSE (268)
TFOR (269)
TINT (270) 16
TFLOAT (271) 18
TD (272) 17
TCHAR (273) 19
TPLUS (274) 34
TMINUS (275) 35
TDIV (276) 36
TMULT (277) 37
TLT (278) 38
TGT (279) 39
TAND (280) 40
TOR (281) 41
TEQUAL (282) 42
TNE (283) 43
TINTEGER (284) 32
TDOUBLE (285) 33
TID (286) 31
TOPA (287) 13 22 25
Nonterminals, with rules where they appear
$accept (33)
on left: 0
program (34)
on left: 1, on right: 0
command_list (35)
on left: 2 3, on right: 1 3 20
declaration (36)
on left: 4 5 6, on right: 2 3
variable_dec (37)
on left: 7 8, on right: 5 14 15
assignment (38)
on left: 9, on right: 8 23
var_list (39)
on left: 10 11 12, on right: 11 22
function_dec (40)
on left: 13, on right: 4
p_list (41)
on left: 14 15, on right: 13 15
type (42)
on left: 16 17 18 19, on right: 7 8 13
scope (43)
on left: 20 21, on right: 13
function_call (44)
on left: 22, on right: 24
expression (45)
on left: 23 24 25 26 27 28, on right: 6 9 10 11 25 26 27
constant (46)
on left: 29 30, on right: 26 27 28
identifier (47)
on left: 31, on right: 7 9 13 22 29
num (48)
on left: 32 33, on right: 30
arithmetic_op (49)
on left: 34 35 36 37, on right: 26
logical_op (50)
on left: 38 39 40 41 42 43, on right: 27
state 18
26 expression: constant . arithmetic_op expression
27 | constant . logical_op expression
28 | constant . [$end, TCPA, TCB, TCOMMA, TSEMIC, TINT, TFLOAT, TD, TCHAR, TINTEGER, TDOUBLE, TID, TOPA]
34 arithmetic_op: . TPLUS
35 | . TMINUS
36 | . TDIV
37 | . TMULT
38 logical_op: . TLT
39 | . TGT
40 | . TAND
41 | . TOR
42 | . TEQUAL
43 | . TNE
TPLUS shift, and go to state 26
TMINUS shift, and go to state 27
TDIV shift, and go to state 28
TMULT shift, and go to state 29
TLT shift, and go to state 30
TGT shift, and go to state 31
TAND shift, and go to state 32
TOR shift, and go to state 33
TEQUAL shift, and go to state 34
TNE shift, and go to state 35
$default reduce using rule 28 (expression)
arithmetic_op go to state 36
logical_op go to state 37
state 19
9 assignment: identifier . TASSIGN expression
22 function_call: identifier . TOPA var_list TCPA TSEMIC
29 constant: identifier . [$end, TCPA, TCB, TCOMMA, TSEMIC, TINT, TFLOAT, TD, TCHAR, TPLUS, TMINUS, TDIV, TMULT, TLT, TGT, TAND, TOR, TEQUAL, TNE, TINTEGER, TDOUBLE, TID, TOPA]
TASSIGN shift, and go to state 38
TOPA shift, and go to state 39
TOPA [reduce using rule 29 (constant)]
$default reduce using rule 29 (constant)
state 20
30 constant: num .
$default reduce using rule 30 (constant)
根据 bison 的输出，从状态 19 开始，可以在 ( 的前瞻中减少 expression。这怎么可能？换句话说,什么情况下expression后面可以跟左括号?
通过语法搜索只发现 TOPA 的三种用法。其中两个（函数声明和函数调用）跟在identifier后面，identifier不能推导出expression，所以一定是第三个：
expression: TOPA expression TCPA;
但是，在 ( 的这个实例之前立即减少 expression 的唯一方法是如果两个 expressions 是可能的连续发生。通常，在类似 C 的语言中，通过要求 ; 来分隔语句（可能以 expression 开始或结束）来消除这种可能性，我想那是你的意图。
但是，我们看到：
command_list: declaration
| command_list declaration
declaration: expression
允许两个连续的表达式，中间没有分号。
一如既往，我鼓励在野牛语法中使用更具可读性的标记。 '(' 比 TOPA 更容易理解，老实说我不知道 COB 可能是什么。但这是风格问题。
我在状态 19 有 1 个 shift/reduce 冲突。我认为 'identifier' 的不同出现可能有问题，但我正在努力理解野牛报告并解决冲突.下面是我的语法，后面是带有状态信息的野牛报告：
%{
#include <cstdio>
#include <iostream>
using namespace std;
extern "C" int yylex();
extern "C" int yyparse();
void yyerror(const char *s);
%}
%union{
int int_val;
double d_val;
char *strng;
}
%token TLINEC TBLOCKC TPRINT
%token TASSIGN TCPA TOB TCB TCOMMA TSEMIC
%token TIF TELSE TFOR
%token TINT TFLOAT TD TCHAR
%token TPLUS TMINUS TDIV TMULT
%token TLT TGT TAND TOR TEQUAL TNE
%token<int_val> TINTEGER
%token<d_val> TDOUBLE
%token<strng> TID
%token TOPA
%start program
%%
program : command_list
command_list : declaration
| command_list declaration
declaration : function_dec
| variable_dec
| expression
variable_dec : type identifier TSEMIC
| type assignment TSEMIC
assignment : identifier TASSIGN expression
var_list : expression
| var_list TCOMMA expression
|
function_dec : type identifier TOPA p_list TCPA scope
p_list : variable_dec
| p_list TCOMMA variable_dec
type : TINT
| TD
| TFLOAT
| TCHAR
/* inside function scope */
scope : TOB command_list TCB
| TOB TCB
function_call : identifier TOPA var_list TCPA TSEMIC
/* expression rules */
expression : assignment
| function_call
| TOPA expression TCPA
| constant arithmetic_op expression
| constant logical_op expression
| constant
constant : identifier
| num
identifier : TID
num : TINTEGER
| TDOUBLE
arithmetic_op : TPLUS | TMINUS | TDIV | TMULT
logical_op : TLT | TGT | TAND | TOR | TEQUAL | TNE
%%
int main(int, char**){
int y=0;
do{
y=yyparse();
}while(y);
}
void yyerror(const char *s){
cout << "parse error! Message: " << s << endl;
exit(-1);
}
野牛报告：
State 19 conflicts: 1 shift/reduce
Grammar
0 $accept: program $end
1 program: command_list
2 command_list: declaration
3 | command_list declaration
4 declaration: function_dec
5 | variable_dec
6 | expression
7 variable_dec: type identifier TSEMIC
8 | type assignment TSEMIC
9 assignment: identifier TASSIGN expression
10 var_list: expression
11 | var_list TCOMMA expression
12 | /* empty */
13 function_dec: type identifier TOPA p_list TCPA scope
14 p_list: variable_dec
15 | p_list TCOMMA variable_dec
16 type: TINT
17 | TD
18 | TFLOAT
19 | TCHAR
20 scope: TOB command_list TCB
21 | TOB TCB
22 function_call: identifier TOPA var_list TCPA TSEMIC
23 expression: assignment
24 | function_call
25 | TOPA expression TCPA
26 | constant arithmetic_op expression
27 | constant logical_op expression
28 | constant
29 constant: identifier
30 | num
31 identifier: TID
32 num: TINTEGER
33 | TDOUBLE
34 arithmetic_op: TPLUS
35 | TMINUS
36 | TDIV
37 | TMULT
38 logical_op: TLT
39 | TGT
40 | TAND
41 | TOR
42 | TEQUAL
43 | TNE
Terminals, with rules where they appear
$end (0) 0
error (256)
TLINEC (258)
TBLOCKC (259)
TPRINT (260)
TASSIGN (261) 9
TCPA (262) 13 22 25
TOB (263) 20 21
TCB (264) 20 21
TCOMMA (265) 11 15
TSEMIC (266) 7 8 22
TIF (267)
TELSE (268)
TFOR (269)
TINT (270) 16
TFLOAT (271) 18
TD (272) 17
TCHAR (273) 19
TPLUS (274) 34
TMINUS (275) 35
TDIV (276) 36
TMULT (277) 37
TLT (278) 38
TGT (279) 39
TAND (280) 40
TOR (281) 41
TEQUAL (282) 42
TNE (283) 43
TINTEGER (284) 32
TDOUBLE (285) 33
TID (286) 31
TOPA (287) 13 22 25
Nonterminals, with rules where they appear
$accept (33)
on left: 0
program (34)
on left: 1, on right: 0
command_list (35)
on left: 2 3, on right: 1 3 20
declaration (36)
on left: 4 5 6, on right: 2 3
variable_dec (37)
on left: 7 8, on right: 5 14 15
assignment (38)
on left: 9, on right: 8 23
var_list (39)
on left: 10 11 12, on right: 11 22
function_dec (40)
on left: 13, on right: 4
p_list (41)
on left: 14 15, on right: 13 15
type (42)
on left: 16 17 18 19, on right: 7 8 13
scope (43)
on left: 20 21, on right: 13
function_call (44)
on left: 22, on right: 24
expression (45)
on left: 23 24 25 26 27 28, on right: 6 9 10 11 25 26 27
constant (46)
on left: 29 30, on right: 26 27 28
identifier (47)
on left: 31, on right: 7 9 13 22 29
num (48)
on left: 32 33, on right: 30
arithmetic_op (49)
on left: 34 35 36 37, on right: 26
logical_op (50)
on left: 38 39 40 41 42 43, on right: 27
state 18
26 expression: constant . arithmetic_op expression
27 | constant . logical_op expression
28 | constant . [$end, TCPA, TCB, TCOMMA, TSEMIC, TINT, TFLOAT, TD, TCHAR, TINTEGER, TDOUBLE, TID, TOPA]
34 arithmetic_op: . TPLUS
35 | . TMINUS
36 | . TDIV
37 | . TMULT
38 logical_op: . TLT
39 | . TGT
40 | . TAND
41 | . TOR
42 | . TEQUAL
43 | . TNE
TPLUS shift, and go to state 26
TMINUS shift, and go to state 27
TDIV shift, and go to state 28
TMULT shift, and go to state 29
TLT shift, and go to state 30
TGT shift, and go to state 31
TAND shift, and go to state 32
TOR shift, and go to state 33
TEQUAL shift, and go to state 34
TNE shift, and go to state 35
$default reduce using rule 28 (expression)
arithmetic_op go to state 36
logical_op go to state 37
state 19
9 assignment: identifier . TASSIGN expression
22 function_call: identifier . TOPA var_list TCPA TSEMIC
29 constant: identifier . [$end, TCPA, TCB, TCOMMA, TSEMIC, TINT, TFLOAT, TD, TCHAR, TPLUS, TMINUS, TDIV, TMULT, TLT, TGT, TAND, TOR, TEQUAL, TNE, TINTEGER, TDOUBLE, TID, TOPA]
TASSIGN shift, and go to state 38
TOPA shift, and go to state 39
TOPA [reduce using rule 29 (constant)]
$default reduce using rule 29 (constant)
state 20
30 constant: num .
$default reduce using rule 30 (constant)
根据 bison 的输出，从状态 19 开始，可以在 ( 的前瞻中减少 expression。这怎么可能？换句话说,什么情况下expression后面可以跟左括号?
通过语法搜索只发现 TOPA 的三种用法。其中两个（函数声明和函数调用）跟在identifier后面，identifier不能推导出expression，所以一定是第三个：
expression: TOPA expression TCPA;
但是，在 ( 的这个实例之前立即减少 expression 的唯一方法是如果两个 expressions 是可能的连续发生。通常，在类似 C 的语言中，通过要求 ; 来分隔语句（可能以 expression 开始或结束）来消除这种可能性，我想那是你的意图。
但是，我们看到：
command_list: declaration
| command_list declaration
declaration: expression
允许两个连续的表达式，中间没有分号。
一如既往，我鼓励在野牛语法中使用更具可读性的标记。 '(' 比 TOPA 更容易理解，老实说我不知道 COB 可能是什么。但这是风格问题。