Hi :
I'm using bison for a sub-set grammar of C language . But I
encounter a difficult . flowing is the core part of my grammar
file;
/*
grammar for subset of C language
*/
%left OR_OP
%left AND_OP
%left '+'
%left '-'
%left '*'
%left '/'
%%
%start file
;
file
:
|declaration file
|function_define file
;
function_define : declaration_specifier pointer IDENTIFIER '('
parameter_declaration_list ')' compound_statement
| declaration_specifier IDENTIFIER '('
parameter_declaration_list
')' compound_statement
| declaration_specifier pointer IDENTIFIER '(' ')'
compound_statement
| declaration_specifier IDENTIFIER '(' ')' compound_statement
;
compound_statement
: '{' '}'
| '{' statement_list '}'
| '{' declaration_list '}'
| '{' declaration_list statement_list'}'
;
statement_list
:statement statement_list
;
statement
:compound_statement
|iteration_statement
|expression_statement
|select_statement
|jump_statement
;
iteration_statement
: FOR '(' expression_statement expression_statement expr ')'
statement
;
select_statement
: IF '(' expr ')' statement
| IF '(' expr ')' statement ELSE statement
;
jump_statement :BREAK ';'
|CONTINUE ';'
|RETURN ';'
|RETURN expr ';'
;
expression_statement
:';'
| expr ';'
;
expr
:assignment_expr
|unary_expr
|binary_expr
;
assignment_expr :unary_expr '=' expr
;
unary_expr :postfix_expr
|INC_OP unary_expr
|DEC_OP unary_expr
|unary_operator unary_expr
;
binary_expr
:expr '*' expr
|expr '/' expr
|expr '+' expr
|expr '-' expr
|expr AND_OP expr
|expr OR_OP expr
;
unary_operator :'&'
|'*'
|'-'
|'!'
|'~'
;
postfix_expr :primary_expr
;
primary_expr : IDENTIFIER
| CONSTANT
| '(' expr ')'
;
declaration_list: declaration declaration_list
;
declaration : declaration_specifier declarator_list ';'
;
declarator_list : declarator ',' declarator_list
| declarator
;
declarator :var_declarator
|function_declarator
;
var_declarator :var_declarator2
|pointer var_declarator2
;
var_declarator2 :'(' var_declarator ')'
|var_declarator2 '[' ']'
|var_declarator2 '[' const_expr ']'
;
const_expr :CONSTANT
;
function_declarator: function_declarator2
pointer function_declarator2
;
function_declarator2: IDENTIFIER '(' parameter_declaration_list ')'
|IDENTIFIER '(' ')'
;
parameter_declaration_list: parameter_declaration ','
parameter_declaration_list
|parameter_declaration
;
//reduce shift conflict
parameter_declaration : declaration_specifier pointer
|declaration_specifier
|declaration_specifier var_declarator
;
pointer :'*'
|'*' pointer
;
declaration_specifier : INT
| DOUBLE
| FLOAT
| VOID
;
/*
xx.output
*/
Nonterminals useless in grammar
statement_list
statement
iteration_statement
select_statement
jump_statement
expression_statement
expr
assignment_expr
unary_expr
binary_expr
unary_operator
postfix_expr
primary_expr
declaration_list
var_declarator
var_declarator2
const_expr
Terminals unused in grammar
CONSTANT
FOR
BREAK
CONTINUE
RETURN
IF
ELSE
INC_OP
DEC_OP
AND_OP
OR_OP
'+'
'-'
'/'
'='
'&'
'!'
'~'
'['
']'
Rules useless in grammar
26 compound_statement: '{' statement_list '}'
27 | '{' declaration_list '}'
28 | '{' declaration_list statement_list '}'
29 statement_list: statement statement_list
30 statement: compound_statement
31 | iteration_statement
32 | expression_statement
33 | select_statement
34 | jump_statement
35 iteration_statement: FOR '(' expression_statement
expression_statement expr ')' statement
36 select_statement: IF '(' expr ')' statement
37 | IF '(' expr ')' statement ELSE statement
38 jump_statement: BREAK ';'
39 | CONTINUE ';'
40 | RETURN ';'
41 | RETURN expr ';'
42 expression_statement: ';'
43 | expr ';'
44 expr: assignment_expr
45 | unary_expr
46 | binary_expr
47 assignment_expr: unary_expr '=' expr
48 unary_expr: postfix_expr
49 | INC_OP unary_expr
50 | DEC_OP unary_expr
51 | unary_operator unary_expr
52 binary_expr: expr '*' expr
53 | expr '/' expr
54 | expr '+' expr
55 | expr '-' expr
56 | expr AND_OP expr
57 | expr OR_OP expr
58 unary_operator: '&'
59 | '*'
60 | '-'
61 | '!'
62 | '~'
63 postfix_expr: primary_expr
64 primary_expr: IDENTIFIER
65 | CONSTANT
66 | '(' expr ')'
67 declaration_list: declaration declaration_list
68 declarator: var_declarator
69 var_declarator: var_declarator2
70 | pointer var_declarator2
71 var_declarator2: '(' var_declarator ')'
72 | var_declarator2 '[' ']'
73 | var_declarator2 '[' const_expr ']'
74 const_expr: CONSTANT
75 parameter_declaration: declaration_specifier var_declarator
Grammar
0 $accept: file END
1 file: /* empty */
2 | declaration file
3 | function_define file
4 function_define: declaration_specifier pointer IDENTIFIER '('
parameter_declaration_list ')' compound_statement
5 | declaration_specifier IDENTIFIER '('
parameter_declaration_list ')' compound_statement
6 | declaration_specifier pointer IDENTIFIER '('
')' compound_statement
7 | declaration_specifier IDENTIFIER '(' ')'
compound_statement
8 compound_statement: '{' '}'
9 declaration: declaration_specifier declarator_list ';'
10 declarator_list: declarator ',' declarator_list
11 | declarator
12 declarator: function_declarator
13 function_declarator: function_declarator2 pointer function_declarator2
14 function_declarator2: IDENTIFIER '(' parameter_declaration_list ')'
15 | IDENTIFIER '(' ')'
16 parameter_declaration_list: parameter_declaration ','
parameter_declaration_list
17 | parameter_declaration
18 parameter_declaration: declaration_specifier pointer
19 | declaration_specifier
20 pointer: '*'
21 | '*' pointer
22 declaration_specifier: INT
23 | DOUBLE
24 | FLOAT
25 | VOID
Terminals, with rules where they appear
END (0) 0
'!' (33)
'&' (38)
'(' (40) 4 5 6 7 14 15
')' (41) 4 5 6 7 14 15
'*' (42) 20 21
'+' (43)
',' (44) 10 16
'-' (45)
'/' (47)
';' (59) 9
'=' (61)
'[' (91)
']' (93)
'{' (123) 8
'}' (125) 8
'~' (126)
error (256)
IDENTIFIER (258) 4 5 6 7 14 15
CONSTANT (259)
FOR (260)
BREAK (261)
CONTINUE (262)
RETURN (263)
IF (264)
ELSE (265)
INC_OP (266)
DEC_OP (267)
AND_OP (268)
OR_OP (269)
INT (270) 22
DOUBLE (271) 23
FLOAT (272) 24
VOID (273) 25
Nonterminals, with rules where they appear
$accept (35)
on left: 0
file (36)
on left: 1 2 3, on right: 0 2 3
function_define (37)
on left: 4 5 6 7, on right: 3
compound_statement (38)
on left: 8, on right: 4 5 6 7
declaration (39)
on left: 9, on right: 2
declarator_list (40)
on left: 10 11, on right: 9 10
declarator (41)
on left: 12, on right: 10 11
function_declarator (42)
on left: 13, on right: 12
function_declarator2 (43)
on left: 14 15, on right: 13
parameter_declaration_list (44)
on left: 16 17, on right: 4 5 14 16
parameter_declaration (45)
on left: 18 19, on right: 16 17
pointer (46)
on left: 20 21, on right: 4 6 13 18 21
declaration_specifier (47)
on left: 22 23 24 25, on right: 4 5 6 7 9 18 19
state 0
0 $accept: . file END
1 file: . [END]
2 | . declaration file
3 | . function_define file
4 function_define: . declaration_specifier pointer IDENTIFIER '('
parameter_declaration_list ')' compound_statement
5 | . declaration_specifier IDENTIFIER '('
parameter_declaration_list ')' compound_statement
6 | . declaration_specifier pointer IDENTIFIER '('
')' compound_statement
7 | . declaration_specifier IDENTIFIER '(' ')'
compound_statement
9 declaration: . declaration_specifier declarator_list ';'
22 declaration_specifier: . INT
23 | . DOUBLE
24 | . FLOAT
25 | . VOID
INT shift, and go to state 1
DOUBLE shift, and go to state 2
FLOAT shift, and go to state 3
VOID shift, and go to state 4
$default reduce using rule 1 (file)
file go to state 5
function_define go to state 6
declaration go to state 7
declaration_specifier go to state 8
state 1
22 declaration_specifier: INT .
$default reduce using rule 22 (declaration_specifier)
state 2
23 declaration_specifier: DOUBLE .
$default reduce using rule 23 (declaration_specifier)
state 3
24 declaration_specifier: FLOAT .
$default reduce using rule 24 (declaration_specifier)
state 4
25 declaration_specifier: VOID .
$default reduce using rule 25 (declaration_specifier)
state 5
0 $accept: file . END
END shift, and go to state 9
state 6
1 file: . [END]
2 | . declaration file
3 | . function_define file
3 | function_define . file
4 function_define: . declaration_specifier pointer IDENTIFIER '('
parameter_declaration_list ')' compound_statement
5 | . declaration_specifier IDENTIFIER '('
parameter_declaration_list ')' compound_statement
6 | . declaration_specifier pointer IDENTIFIER '('
')' compound_statement
7 | . declaration_specifier IDENTIFIER '(' ')'
compound_statement
9 declaration: . declaration_specifier declarator_list ';'
22 declaration_specifier: . INT
23 | . DOUBLE
24 | . FLOAT
25 | . VOID
INT shift, and go to state 1
DOUBLE shift, and go to state 2
FLOAT shift, and go to state 3
VOID shift, and go to state 4
$default reduce using rule 1 (file)
file go to state 10
function_define go to state 6
declaration go to state 7
declaration_specifier go to state 8
state 7
1 file: . [END]
2 | . declaration file
2 | declaration . file
3 | . function_define file
4 function_define: . declaration_specifier pointer IDENTIFIER '('
parameter_declaration_list ')' compound_statement
5 | . declaration_specifier IDENTIFIER '('
parameter_declaration_list ')' compound_statement
6 | . declaration_specifier pointer IDENTIFIER '('
')' compound_statement
7 | . declaration_specifier IDENTIFIER '(' ')'
compound_statement
9 declaration: . declaration_specifier declarator_list ';'
22 declaration_specifier: . INT
23 | . DOUBLE
24 | . FLOAT
25 | . VOID
INT shift, and go to state 1
DOUBLE shift, and go to state 2
FLOAT shift, and go to state 3
VOID shift, and go to state 4
$default reduce using rule 1 (file)
file go to state 11
function_define go to state 6
declaration go to state 7
declaration_specifier go to state 8
state 8
4 function_define: declaration_specifier . pointer IDENTIFIER '('
parameter_declaration_list ')' compound_statement
5 | declaration_specifier . IDENTIFIER '('
parameter_declaration_list ')' compound_statement
6 | declaration_specifier . pointer IDENTIFIER '('
')' compound_statement
7 | declaration_specifier . IDENTIFIER '(' ')'
compound_statement
9 declaration: declaration_specifier . declarator_list ';'
10 declarator_list: . declarator ',' declarator_list
11 | . declarator
12 declarator: . function_declarator
13 function_declarator: . function_declarator2 pointer function_declarator2
14 function_declarator2: . IDENTIFIER '(' parameter_declaration_list ')'
15 | . IDENTIFIER '(' ')'
20 pointer: . '*'
21 | . '*' pointer
IDENTIFIER shift, and go to state 12
'*' shift, and go to state 13
declarator_list go to state 14
declarator go to state 15
function_declarator go to state 16
function_declarator2 go to state 17
pointer go to state 18
state 9
0 $accept: file END .
$default accept
state 10
3 file: function_define file .
$default reduce using rule 3 (file)
state 11
2 file: declaration file .
$default reduce using rule 2 (file)
state 12
5 function_define: declaration_specifier IDENTIFIER . '('
parameter_declaration_list ')' compound_statement
7 | declaration_specifier IDENTIFIER . '(' ')'
compound_statement
14 function_declarator2: IDENTIFIER . '(' parameter_declaration_list ')'
15 | IDENTIFIER . '(' ')'
'(' shift, and go to state 19
state 13
20 pointer: . '*'
20 | '*' . [IDENTIFIER, ')', ',']
21 | . '*' pointer
21 | '*' . pointer
'*' shift, and go to state 13
$default reduce using rule 20 (pointer)
pointer go to state 20
state 14
9 declaration: declaration_specifier declarator_list . ';'
';' shift, and go to state 21
state 15
10 declarator_list: declarator . ',' declarator_list
11 | declarator . [';']
',' shift, and go to state 22
$default reduce using rule 11 (declarator_list)
state 16
12 declarator: function_declarator .
$default reduce using rule 12 (declarator)
state 17
13 function_declarator: function_declarator2 . pointer function_declarator2
20 pointer: . '*'
21 | . '*' pointer
'*' shift, and go to state 13
pointer go to state 23
state 18
4 function_define: declaration_specifier pointer . IDENTIFIER '('
parameter_declaration_list ')' compound_statement
6 | declaration_specifier pointer . IDENTIFIER '('
')' compound_statement
IDENTIFIER shift, and go to state 24
state 19
5 function_define: declaration_specifier IDENTIFIER '(' .
parameter_declaration_list ')' compound_statement
7 | declaration_specifier IDENTIFIER '(' . ')'
compound_statement
14 function_declarator2: IDENTIFIER '(' . parameter_declaration_list ')'
15 | IDENTIFIER '(' . ')'
16 parameter_declaration_list: . parameter_declaration ','
parameter_declaration_list
17 | . parameter_declaration
18 parameter_declaration: . declaration_specifier pointer
19 | . declaration_specifier
22 declaration_specifier: . INT
23 | . DOUBLE
24 | . FLOAT
25 | . VOID
INT shift, and go to state 1
DOUBLE shift, and go to state 2
FLOAT shift, and go to state 3
VOID shift, and go to state 4
')' shift, and go to state 25
parameter_declaration_list go to state 26
parameter_declaration go to state 27
declaration_specifier go to state 28
state 20
21 pointer: '*' pointer .
$default reduce using rule 21 (pointer)
state 21
9 declaration: declaration_specifier declarator_list ';' .
$default reduce using rule 9 (declaration)
state 22
10 declarator_list: . declarator ',' declarator_list
10 | declarator ',' . declarator_list
11 | . declarator
12 declarator: . function_declarator
13 function_declarator: . function_declarator2 pointer function_declarator2
14 function_declarator2: . IDENTIFIER '(' parameter_declaration_list ')'
15 | . IDENTIFIER '(' ')'
IDENTIFIER shift, and go to state 29
declarator_list go to state 30
declarator go to state 15
function_declarator go to state 16
function_declarator2 go to state 17
state 23
13 function_declarator: function_declarator2 pointer . function_declarator2
14 function_declarator2: . IDENTIFIER '(' parameter_declaration_list ')'
15 | . IDENTIFIER '(' ')'
IDENTIFIER shift, and go to state 29
function_declarator2 go to state 31
state 24
4 function_define: declaration_specifier pointer IDENTIFIER . '('
parameter_declaration_list ')' compound_statement
6 | declaration_specifier pointer IDENTIFIER . '('
')' compound_statement
'(' shift, and go to state 32
state 25
7 function_define: declaration_specifier IDENTIFIER '(' ')' .
compound_statement
8 compound_statement: . '{' '}'
15 function_declarator2: IDENTIFIER '(' ')' . ['*']
'{' shift, and go to state 33
$default reduce using rule 15 (function_declarator2)
compound_statement go to state 34
state 26
5 function_define: declaration_specifier IDENTIFIER '('
parameter_declaration_list . ')' compound_statement
14 function_declarator2: IDENTIFIER '(' parameter_declaration_list . ')'
')' shift, and go to state 35
state 27
16 parameter_declaration_list: parameter_declaration . ','
parameter_declaration_list
17 | parameter_declaration . [')']
',' shift, and go to state 36
$default reduce using rule 17 (parameter_declaration_list)
state 28
18 parameter_declaration: declaration_specifier . pointer
19 | declaration_specifier . [')', ',']
20 pointer: . '*'
21 | . '*' pointer
'*' shift, and go to state 13
$default reduce using rule 19 (parameter_declaration)
pointer go to state 37
state 29
14 function_declarator2: IDENTIFIER . '(' parameter_declaration_list ')'
15 | IDENTIFIER . '(' ')'
'(' shift, and go to state 38
state 30
10 declarator_list: declarator ',' declarator_list .
$default reduce using rule 10 (declarator_list)
state 31
13 function_declarator: function_declarator2 pointer function_declarator2 .
$default reduce using rule 13 (function_declarator)
state 32
4 function_define: declaration_specifier pointer IDENTIFIER '(' .
parameter_declaration_list ')' compound_statement
6 | declaration_specifier pointer IDENTIFIER '(' .
')' compound_statement
16 parameter_declaration_list: . parameter_declaration ','
parameter_declaration_list
17 | . parameter_declaration
18 parameter_declaration: . declaration_specifier pointer
19 | . declaration_specifier
22 declaration_specifier: . INT
23 | . DOUBLE
24 | . FLOAT
25 | . VOID
INT shift, and go to state 1
DOUBLE shift, and go to state 2
FLOAT shift, and go to state 3
VOID shift, and go to state 4
')' shift, and go to state 39
parameter_declaration_list go to state 40
parameter_declaration go to state 27
declaration_specifier go to state 28
state 33
8 compound_statement: '{' . '}'
'}' shift, and go to state 41
state 34
7 function_define: declaration_specifier IDENTIFIER '(' ')'
compound_statement .
$default reduce using rule 7 (function_define)
state 35
5 function_define: declaration_specifier IDENTIFIER '('
parameter_declaration_list ')' . compound_statement
8 compound_statement: . '{' '}'
14 function_declarator2: IDENTIFIER '(' parameter_declaration_list
')' . ['*']
'{' shift, and go to state 33
$default reduce using rule 14 (function_declarator2)
compound_statement go to state 42
state 36
16 parameter_declaration_list: . parameter_declaration ','
parameter_declaration_list
16 | parameter_declaration ',' .
parameter_declaration_list
17 | . parameter_declaration
18 parameter_declaration: . declaration_specifier pointer
19 | . declaration_specifier
22 declaration_specifier: . INT
23 | . DOUBLE
24 | . FLOAT
25 | . VOID
INT shift, and go to state 1
DOUBLE shift, and go to state 2
FLOAT shift, and go to state 3
VOID shift, and go to state 4
parameter_declaration_list go to state 43
parameter_declaration go to state 27
declaration_specifier go to state 28
state 37
18 parameter_declaration: declaration_specifier pointer .
$default reduce using rule 18 (parameter_declaration)
state 38
14 function_declarator2: IDENTIFIER '(' . parameter_declaration_list ')'
15 | IDENTIFIER '(' . ')'
16 parameter_declaration_list: . parameter_declaration ','
parameter_declaration_list
17 | . parameter_declaration
18 parameter_declaration: . declaration_specifier pointer
19 | . declaration_specifier
22 declaration_specifier: . INT
23 | . DOUBLE
24 | . FLOAT
25 | . VOID
INT shift, and go to state 1
DOUBLE shift, and go to state 2
FLOAT shift, and go to state 3
VOID shift, and go to state 4
')' shift, and go to state 44
parameter_declaration_list go to state 45
parameter_declaration go to state 27
declaration_specifier go to state 28
state 39
6 function_define: declaration_specifier pointer IDENTIFIER '('
')' . compound_statement
8 compound_statement: . '{' '}'
'{' shift, and go to state 33
compound_statement go to state 46
state 40
4 function_define: declaration_specifier pointer IDENTIFIER '('
parameter_declaration_list . ')' compound_statement
')' shift, and go to state 47
state 41
8 compound_statement: '{' '}' .
$default reduce using rule 8 (compound_statement)
state 42
5 function_define: declaration_specifier IDENTIFIER '('
parameter_declaration_list ')' compound_statement .
$default reduce using rule 5 (function_define)
state 43
16 parameter_declaration_list: parameter_declaration ','
parameter_declaration_list .
$default reduce using rule 16 (parameter_declaration_list)
state 44
15 function_declarator2: IDENTIFIER '(' ')' .
$default reduce using rule 15 (function_declarator2)
state 45
14 function_declarator2: IDENTIFIER '(' parameter_declaration_list . ')'
')' shift, and go to state 48
state 46
6 function_define: declaration_specifier pointer IDENTIFIER '('
')' compound_statement .
$default reduce using rule 6 (function_define)
state 47
4 function_define: declaration_specifier pointer IDENTIFIER '('
parameter_declaration_list ')' . compound_statement
8 compound_statement: . '{' '}'
'{' shift, and go to state 33
compound_statement go to state 49
state 48
14 function_declarator2: IDENTIFIER '(' parameter_declaration_list ')' .
$default reduce using rule 14 (function_declarator2)
state 49
4 function_define: declaration_specifier pointer IDENTIFIER '('
parameter_declaration_list ')' compound_statement .
$default reduce using rule 4 (function_define)
when I use bison :
bison -r all -d -o xx.cpp xx.ypp
there is all waring , no shift/reduce or reduce/reduce conflict !!!
I want to know , Why bison think the "comound_statement" as
useless noterminater ???
why I have so many useless rule and no-terminator ???
please Help Me !!
_______________________________________________
address@hidden http://lists.gnu.org/mailman/listinfo/help-bison