0

I am trying to write a bison parser and contextual precedence does not seem to work...

One of my productions (simplified and ommiting the c code) is the following:

    '''constant_inner_expression : constant_expression t_PLUS             op_attribute_instance_list constant_expression %prec BIN_APLUS
                                 | constant_expression t_MINUS            op_attribute_instance_list constant_expression %prec BIN_AMINUS
                                 | constant_expression t_ASTERISK         op_attribute_instance_list constant_expression %prec BIN_AMULT
                                 | constant_expression t_SLASH            op_attribute_instance_list constant_expression %prec BIN_ADIV
                                 | constant_expression t_PERCENT          op_attribute_instance_list constant_expression %prec BIN_AMOD
                                 | constant_expression t_ISEQUAL          op_attribute_instance_list constant_expression %prec BIN_LEQUALS
                                 | constant_expression t_NISEQUAL         op_attribute_instance_list constant_expression %prec BIN_LNEQUALS
                                 | constant_expression t_CISEQUAL         op_attribute_instance_list constant_expression %prec BIN_CEQUALS
                                 | constant_expression t_NCISEQUAL        op_attribute_instance_list constant_expression %prec BIN_CNEQUALS
                                 | constant_expression t_WISEQUAL         op_attribute_instance_list constant_expression %prec BIN_WEQUALS
                                 | constant_expression t_NWISEQUAL        op_attribute_instance_list constant_expression %prec BIN_WNEQUALS
                                 | constant_expression t_DOUBLEAMPERSAND  op_attribute_instance_list constant_expression %prec BIN_LAND
                                 | constant_expression t_DOUBLEPIPE       op_attribute_instance_list constant_expression %prec BIN_LOR
                                 | constant_expression t_DOUBLEASTERISK   op_attribute_instance_list constant_expression %prec BIN_AEXP
                                 | constant_expression t_LT               op_attribute_instance_list constant_expression %prec BIN_RLT
                                 | constant_expression t_LE               op_attribute_instance_list constant_expression %prec BIN_RLE
                                 | constant_expression t_GT               op_attribute_instance_list constant_expression %prec BIN_RGT
                                 | constant_expression t_GE               op_attribute_instance_list constant_expression %prec BIN_RGE
                                 | constant_expression t_AMPERSAND        op_attribute_instance_list constant_expression %prec BIN_BAND
                                 | constant_expression t_PIPE             op_attribute_instance_list constant_expression %prec BIN_BOR
                                 | constant_expression t_CARET            op_attribute_instance_list constant_expression %prec BIN_BXOR
                                 | constant_expression t_NEGCARET         op_attribute_instance_list constant_expression %prec BIN_BXNOR
                                 | constant_expression t_RSHIFT           op_attribute_instance_list constant_expression %prec BIN_LRSHIFT
                                 | constant_expression t_LSHIFT           op_attribute_instance_list constant_expression %prec BIN_LLSHIFT
                                 | constant_expression t_ARSHIFT          op_attribute_instance_list constant_expression %prec BIN_ARSHIFT
                                 | constant_expression t_ALSHIFT          op_attribute_instance_list constant_expression %prec BIN_ALSHIFT
                                 | constant_expression t_IMPLICATION      op_attribute_instance_list constant_expression %prec BIN_LIMPLICATION
                                 | constant_expression t_EQUIVALENCE      op_attribute_instance_list constant_expression %prec BIN_LEQUIVALENCE

As you can see a constant_inner_expression can be an operation between two constant_expressions, and I need to prioritize some over the others.

My precedence rules are the following:

%precedence  RANGE_SEPARATOR
%precedence  BIN_ASSIGNMENT BIN_INCASSIGN BIN_DECASSIGN BIN_TIMESASSIGN 
            BIN_DIVASSIGN BIN_MODASSIGN BIN_BANDASSIGN BIN_BXORASSIGN BIN_BORASSIGN 
            BIN_LLSHIFTASSIGN BIN_LRSHIFTASSIGN BIN_ALSHIFTASSIGN BIN_ARSHIFTASSIGN
%left  BIN_LIMPLICATION BIN_LEQUIVALENCE
%left  CONDITIONAL_OPERATOR
%left  BIN_LOR
%left  BIN_LAND
%left  BIN_BOR
%left  BIN_BXOR BIN_BXNOR
%left  BIN_BAND
%left  BIN_LEQUALS BIN_LNEQUALS BIN_CEQUALS BIN_CNEQUALS BIN_WEQUALS 
    BIN_WNEQUALS
%left  BIN_RLT BIN_RGT BIN_RLE BIN_RGE
%left  BIN_LLSHIFT BIN_LRSHIFT BIN_ALSHIFT BIN_ARSHIFT
%left  BIN_APLUS BIN_AMINUS
%left  BIN_AMULT BIN_ADIV BIN_AMOD
%left  BIN_AEXP
%precedence  UNARY_PLUS UNARY_MINUS UNARY_LNOT UNARY_LRNOT UNARY_LRAND 
            UNARY_LRNAND UNARY_LROR UNARY_LRNOR UNARY_LRXOR UNARY_LRXNOR UNARY_INC 
            UNARY_DEC
%precedence  PARENTHESIS BRACKETS SCOPE DOT

When I try to parse an expression, for example 2+3*5 with the GLR algorithm I get an ambiguity error, since a GLR parser creates two branches and non of those dies off. Note I am not saying one should be discarded with a %dprec, the point is only one branch should be created to start with.

On the other hand, If I substitute the precedence contextual tokens for the actual tokens, for example, I substitute BIN_APLUS for t_PLUS and BIN_AMULT for t_ASTERISK then the parser works fine and a potentialy ambiguous expression like 2+3*5 gets build correctly. However since my tokens can have different meaning and precedence depending on the context I really need to avoid this approach... This leads me to beliave my rules are fine...

Has anybody come across a similar situation?

EDIT: as rici pointed out this question was already raised on this thread: Happy Context-Dependent Operator Precedence

Sorry but I did not find it before posting mine

Community
  • 1
  • 1
viterbi
  • 419
  • 5
  • 11
  • You are not defining precedence for any operator token, so no precedence relationship exists. Please read [this answer](http://stackoverflow.com/a/41839421/1566221) which I believe is a duplicate question evrn though you are using a different yacc-derivative. – rici Jan 30 '17 at 03:32
  • Thanks @rici, indeed I think that is what I am after, however, If precedence is always between a production and a terminal, imagine I have the following in the stack: exp t_PLUS exp, and a t_ASTERISK is waiting to be shifted in. I want to tell the parser to give precedence to the shifting of t_ASTERISK, as it is a multiplication, however I can not really give a precedence to t_ASTERISK over t_PLUS in a contextual way, since t_ASTERISK must have a precedence defined for the token itself, what should that precedence be? t_ASTERISK might mean different things depending on it's context... – viterbi Jan 30 '17 at 11:05
  • there are limitations to the precedence mechanism. For example, there are operator precedence grammars in which the precedence relationships are not transitive so they cannot be reduced to numerical comparison. Those cases are rare in practice. I don't think that is your problem, though. A complete (though reduced) example showing two contexts would help. – rici Jan 30 '17 at 13:54

0 Answers0