librelist archives

confused about reduce/reduce conflict

From:

Drew Roos

Date:

2011-10-06 @ 02:25

hello,

i'm trying to parse xpath (working with cory zue). i'm adapting a grammar we
wrote for java CUP [http://www2.cs.tum.edu/projects/cup/]. the grammar
generates fine in CUP but jison complains about a conflict. here's the
simplified version:

=======================

%lex
%%

"*"   return 'MULT'
"+"   return 'PLUS'
"/"   return 'SLASH'
"["   return 'LBRACK'
"]"   return 'RBRACK'
"("   return 'LPAREN'
")"   return 'RPAREN'
<<EOF>> return 'EOF'

[a-zA-Z]+  return 'NAME'
[0-9]+     return 'NUM'

\s+   /* skip */

/lex

%left 'PLUS'
%left 'MULT'

%start root

%%

root : expr EOF   {return $1;}
     ;

expr : base_expr
     | op_expr
     | path_expr
     ;

base_expr : LPAREN expr RPAREN
          | NUM
          ;

op_expr : expr PLUS expr
        | expr MULT expr
        ;

path_expr : loc_path
          | filter_expr SLASH rel_loc_path
          ;

filter_expr : filter_expr predicate
            | base_expr
            ;

predicate : LBRACK expr RBRACK
          ;

loc_path : rel_loc_path
         | SLASH rel_loc_path
         | SLASH
         ;

rel_loc_path : NAME
             ;

=======================

the error message suggests the conflict is, when finding a 'base_expr', not
knowing whether to reduce to a 'filter_expr' or an 'expr'. however, by my
calculations, a 'filter_expr' can only be followed by '[' or '/', whereas an
'expr' cannot be followed by either of these. therefore, this situation can
be disambiguated with lookahead of 1.

given that CUP (another bison-based parser) doesn't complain, is there a
problem in jison, or am i missing something?