Shift/Reduce conflict in bison

Question

I was trying to do a simple parsing of general html codes.

Here's my entire bison file (example4.y).

%{
#include <iostream>
#include <cstring>
using namespace std;

extern "C" int yylex();
extern "C" int yyparse();
extern "C" FILE *yyin;

void yyerror(const char *str)
{
    cout<<"Error: "<<str<<"\n";
}

int yywrap()
{
    return 0;
}

main()
{
    yyparse();
}

%}

%token NUMBER LANGLE CLOSERANGLE RANGLE SLASH ANYTHING

%union
{
    int intVal;
    float floatVal;
    char *strVal;
}

%%

tag:    |   
        opening_tag anything closing_tag 
        {
          if(strcmp($<strVal>1,$<strVal>3)==0){
                cout<<"\n[i] Tag Matches: "<<$<strVal>1;
                cout <<"\n[!] The text: "<<$<strVal>2;
            } else {
                cout<<"\n[!] Tag Mismatch: "<<$<strVal>1<<" and "<<$<strVal>3;
            }
            $<strVal>$ = $<strVal>2;
        }
        |
        opening_tag tag closing_tag 
        {
          if(strcmp($<strVal>1,$<strVal>3)==0){
                cout<<"\n[i] Tag Matches: "<<$<strVal>1;
                cout <<"\n[!] The text: "<<$<strVal>2;
            } else {
                cout<<"\n[!] Tag Mismatch: "<<$<strVal>1<<" and "<<$<strVal>3;
            }
        }
        ;
opening_tag:
        LANGLE ANYTHING RANGLE
        {
            $<strVal>$ = $<strVal>2;
        }
        ;
anything:
        ANYTHING
        {
            $<strVal>$ = $<strVal>1;
        }
        ;
closing_tag:
        LANGLE SLASH ANYTHING RANGLE
        {
            $<strVal>$= $<strVal>3;
        }        
%%

The error i get is: example4.y: conflicts: 1 shift/reduce

I think it has to do something with opening_tag tag closing_tag but i could not think what's happening here? Any help?

Answer 1

The problem is that tag can be empty, so that <x>< might be the beginning of opening_tag tag closing_tag or of opening_tag opening_tag. Consequently, bison cannot tell whether to reduce an empty tag before shifting the <.

You should be able to fix it by removing the empty production for tag and adding an explicit production for opening_tag closing_tag.

Answer 2

It's because of two rules that start with opening_tag. The parser has to decide between the rules by lookint at most one token ahead, but it cannot. <FOO> may lead to either rule, and this requires two more tokens of lookahead.

You can do this:

 tag     : /* nothing */
         | opening_tag contents closing_tag
         ;
 contents: tag
         | anything
         ;

UPDATE This new grammar has a different shift/reduce conflict. (UPDATE2: or perhaps it's the same one). Because a tag can be empty, the parser cannot decide what to do at this input:

<Foo> <...
     ^
     |
     input is here

If the next symbol is a slash, then we have a closing tag, and the empty tag rule should be matched. If the next symbol is not a slash, then we have an opening tag, and the non-empty tag rule should be matched. But the parser cannot know, it is only allowed to look at <.

The solution would be to create a new token, LANGLE_SLASH, for the </ combination.