Re: Resolving shift/reduce conflict in Bison grammar

[Martin Alexander David Neumann]

Hi Anand,

the problem is in your productions of "external_declaration".
Informally: Imagine the shift-reduce parser generated by bison sees one
of the following terminals as the next symbol in the input: STATIC,
CONST, VOLATILE, EXTERN, INT or UNSIGNED. The parser now can reduce the
init_dec rule, as one of the aforementioned terminals is expected after
init_dec according to the productions of declaration, but the machine
could also be shifting the terminal as instructed by the production of
function_definition.

If you are not familiar with the way the shift-reduce parser operates,
have a look e.g. at wiki. If you get how the machine operates, the
output from bison --verbose will hopefully make sense to you.

Cheers, Alex


On 07/31/2010 03:54 PM, anandvn wrote:
> 
> Hi,
> 
> Could any one please help me in resolving the shift/reduce in the following
> grammar?
> 
> %{
> #include <stdio.h>
> extern char yytext[];
> extern int column;
> void yyerror(char const *s);
> %}
> 
> %union
> {
>       unsigned int tokVal;
>       unsigned char *tokValStr;
> }
> 
> /* C operators */
> %token <tokVal> STATIC CONST VOLATILE EXTERN INT UNSIGNED VARNAME EQUAL
> COLON OP_BRACE CL_BRACE IDENTIFIER
> 
> %type <tokVal> declaration translation_unit declaration_specifiers
> storage_class_specifier type_specifier type_qualifier init_declarator_list
> 
> /* Parsing starts with this transalation unit */
> %start translation_unit
> 
> %%
> 
> translation_unit
>       : external_declaration
>       | translation_unit external_declaration
>       ;
> 
> external_declaration
>       : function_definition
>       | declaration
>       ;
> 
> function_definition
>       : declaration_specifiers declarator compound_statement
>       ;
> 
> declarator
>       : IDENTIFIER
>       ;
> 
> compound_statement
>       : OP_BRACE CL_BRACE
>       ;
>       
> declaration
>       : init_dec declaration_specifiers COLON
>       | init_dec declaration_specifiers init_declarator_list COLON
>       ;       
> 
> init_dec
>       : {printf("*** Process for Initialization ***\n\n");}
>       
> init_declarator_list
>       :       EQUAL VARNAME
>       ;
>       
> declaration_specifiers
>       : storage_class_specifier
>       | storage_class_specifier declaration_specifiers
>       | type_specifier
>       | type_specifier declaration_specifiers
>       | type_qualifier
>       | type_qualifier declaration_specifiers
>       ;
>       
> storage_class_specifier
>       : EXTERN
>       | STATIC
>       ;
> 
> type_specifier
>       : INT
>       | UNSIGNED
>       ;       
>       
> type_qualifier
>       : CONST
>       | VOLATILE
>       ;
>       
> %%
> 
> void yyerror(char const *s)
> {
>       fflush(stdout);
>       printf("\n%*s\n%*s\n", column, "^", column, s);
> }
> 
> In the rule "declaration", I want to perform initalization activities using
> the empty rule "init_dec" (original code here 
> http://old.nabble.com/file/p29313133/Test.zip Test.zip ). But i'm getting
> shift/reduce conflict. Since I'm new to this bison, i need help from you to
> resolve this conflict. I tried by i felt very difficult.
> 
> Thanks
> Anand V