Resolving Shift/Reduce Conflicts With Operator Precedence

One of the major selling points of LR parsing is the ability to write expression grammars with a higher degree of ambiguity than would otherwise be allowed. When designing an expression grammar there are ways to encode the operators precedence and associativity right into the production rules.

There are situations where it may be desireable to have a "flat" expression grammar. A "flat" expression grammar uses a single non-terminal for an arguably more human-friendly representation.

E ::= E + E | E - E | E * E | E / E
E ::= -E
E ::= NUM | ( E )

This grammar when fed to a parser generator will spit out all kinds of shift/reduce conflicts and not be able to create useable tables.

So if that's the case than what am I even talking about this for? Well, I mention it because the grammar above can't be used as-is but it can be used: we just need to give it a bit more information. In todays post i'm going to talk about doing just that: Using operator precedence to resolve shift/reduce conflicts during LR parser construction.

Controlled Ambiguity

If we take our "flat" expression grammar, and format it in the style of BNF expected by MGCPGen (one production rule per line), we get the following, ambiguous grammar spec(dont worry about the action symbols).

sp ::= STMT
STMT ::= TK_PRINT EXP @mkprint
STMT ::= EXP @mkexprstmt
EXP ::= EXP TK_PLUS EXP @binop
EXP ::= EXP TK_MINUS EXP @binop
EXP ::= EXP TK_MUL EXP @binop
EXP ::= EXP TK_DIV EXP @binop
EXP ::= TK_LPAREN EXP TK_RPAREN @pass
EXP ::= TK_MINUS EXP @unary
EXP ::= TK_NUM @num

If we feed MGCPGen the grammar as is, we're left with the following:

max@laptop:~/lr_gen/ex$ mgcpgen -slr ambig_exp.mgrm 
No way to resolve Shift/Reduce conflict: [13][TK_DIV] s11
No way to resolve Shift/Reduce conflict: [13][TK_MINUS] s8
No way to resolve Shift/Reduce conflict: [13][TK_MUL] s9
No way to resolve Shift/Reduce conflict: [13][TK_PLUS] s10
No way to resolve Shift/Reduce conflict: [14][TK_DIV] s11
No way to resolve Shift/Reduce conflict: [14][TK_MINUS] s8
No way to resolve Shift/Reduce conflict: [14][TK_MUL] s9
No way to resolve Shift/Reduce conflict: [14][TK_PLUS] s10
No way to resolve Shift/Reduce conflict: [15][TK_DIV] s11
No way to resolve Shift/Reduce conflict: [15][TK_MINUS] s8
No way to resolve Shift/Reduce conflict: [15][TK_MUL] s9
No way to resolve Shift/Reduce conflict: [15][TK_PLUS] s10
No way to resolve Shift/Reduce conflict: [16][TK_DIV] s11
No way to resolve Shift/Reduce conflict: [16][TK_MINUS] s8
No way to resolve Shift/Reduce conflict: [16][TK_MUL] s9
No way to resolve Shift/Reduce conflict: [16][TK_PLUS] s10
No way to resolve Shift/Reduce conflict: [17][TK_DIV] s11
No way to resolve Shift/Reduce conflict: [17][TK_MINUS] s8
No way to resolve Shift/Reduce conflict: [17][TK_MUL] s9
No way to resolve Shift/Reduce conflict: [17][TK_PLUS] s10
max@laptop:~/lr_gen/ex$

As you can see, and as would be expected, the generator can't decide what to do when it encounters an operator. Using the `set_token_prec` declaration in MGCPGen, (similar to Yacc/Bisons %prec) is used to assign an explicit precedence level and associativity to the designated token. 

set_token_prec TK_MINUS 5 left
set_token_prec TK_PLUS 5 left
set_token_prec TK_MUL 10 left
set_token_prec TK_DIV 10 left
sp ::= STMT
STMT ::= TK_PRINT EXP @mkprint
STMT ::= EXP @mkexprstmt
EXP ::= EXP TK_PLUS EXP @binop
EXP ::= EXP TK_MINUS EXP @binop
EXP ::= EXP TK_MUL EXP @binop
EXP ::= EXP TK_DIV EXP @binop
EXP ::= TK_LPAREN EXP TK_RPAREN @pass
EXP ::= TK_MINUS EXP @unary
EXP ::= TK_NUM @num

Running the grammar once again through pgen now generates a much different output:

Shift/Reduce conflict: [13][TK_DIV] s11: Keeping the shift
Shift/Reduce conflict: [13][TK_MINUS] s8: Reduced on associativity
Shift/Reduce conflict: [13][TK_MUL] s9: Keeping the shift
Shift/Reduce conflict: [13][TK_PLUS] s10: Reduced on associativity
Shift/Reduce conflict: [14][TK_DIV] s11: Keeping the shift
Shift/Reduce conflict: [14][TK_MINUS] s8: Reduced on associativity
Shift/Reduce conflict: [14][TK_MUL] s9: Keeping the shift
Shift/Reduce conflict: [14][TK_PLUS] s10: Reduced on associativity
Shift/Reduce conflict: [15][TK_DIV] s11: Reduced on associativity
Shift/Reduce conflict: [15][TK_MINUS] s8: Made to reduce on precedence for TK_MINUS
Shift/Reduce conflict: [15][TK_MUL] s9: Reduced on associativity
Shift/Reduce conflict: [15][TK_PLUS] s10: Made to reduce on precedence for TK_PLUS
Shift/Reduce conflict: [16][TK_DIV] s11: Keeping the shift
Shift/Reduce conflict: [16][TK_MINUS] s8: Reduced on associativity
Shift/Reduce conflict: [16][TK_MUL] s9: Keeping the shift
Shift/Reduce conflict: [16][TK_PLUS] s10: Reduced on associativity
Shift/Reduce conflict: [17][TK_DIV] s11: Reduced on associativity
Shift/Reduce conflict: [17][TK_MINUS] s8: Made to reduce on precedence for TK_MINUS
Shift/Reduce conflict: [17][TK_MUL] s9: Reduced on associativity
Shift/Reduce conflict: [17][TK_PLUS] s10: Made to reduce on precedence for TK_PLUS

Instead of unresolvable shift/reduce conflicts, mgcpgen can take the appropriate action to resolve the conflicts it encounters!

We still have a problem though. Unary minus should have a higher precedence than binary minus - and binary multiplication/division for that matter. So how do we assign two precedence levels to a single token? The answer is laughably simple, but also beautiful in its simplicity: We assign an override token, which we attach to a production instead of the token itsself.

set_token_prec TK_MINUS 5 left
set_token_prec TK_PLUS 5 left
set_token_prec TK_MUL 10 left
set_token_prec TK_DIV 10 left
set_token_prec TK_UNARY_MINUS 15 left
sp ::= STMT
STMT ::= TK_PRINT EXP @mkprint
STMT ::= EXP @mkexprstmt
EXP ::= EXP TK_PLUS EXP @binop
EXP ::= EXP TK_MINUS EXP @binop
EXP ::= EXP TK_MUL EXP @binop
EXP ::= EXP TK_DIV EXP @binop
EXP ::= TK_LPAREN EXP TK_RPAREN @pass
EXP ::= TK_MINUS EXP @unary prec_override TK_UNARY_MINUS
EXP ::= TK_NUM @num

Now when we encounter the production for EXP ::= TK_MINUS EXP mgcpgen will quietly swap out TK_MINUS for TK_UNARY_MINUS but only during the conflict resolution phase of table generation. Now when we run the grammar file through mgcpgen, we can see unary minus override it's precedence:

mgoren@~/mgcpgen/ex$ mgcpgen ambig_expr.mgrm 
Got an override directive: TK_UNARY_MINUS
Production prec symbol:  (override)TK_UNARY_MINUS
Shift/Reduce conflict: [13][TK_DIV] s11: Made to reduce on precedence for TK_DIV
Production prec symbol:  (override)TK_UNARY_MINUS
Shift/Reduce conflict: [13][TK_MINUS] s8: Made to reduce on precedence for TK_MINUS
Production prec symbol:  (override)TK_UNARY_MINUS
Shift/Reduce conflict: [13][TK_MUL] s9: Made to reduce on precedence for TK_MUL
Production prec symbol:  (override)TK_UNARY_MINUS
Shift/Reduce conflict: [13][TK_PLUS] s10: Made to reduce on precedence for TK_PLUS
Production prec symbol: TK_MINUS
Shift/Reduce conflict: [14][TK_DIV] s11: Keeping the shift
Production prec symbol: TK_MINUS
Shift/Reduce conflict: [14][TK_MINUS] s8: Reduced on associativity
Production prec symbol: TK_MINUS
Shift/Reduce conflict: [14][TK_MUL] s9: Keeping the shift
Production prec symbol: TK_MINUS
Shift/Reduce conflict: [14][TK_PLUS] s10: Reduced on associativity
Production prec symbol: TK_MUL
Shift/Reduce conflict: [15][TK_DIV] s11: Reduced on associativity
Production prec symbol: TK_MUL
Shift/Reduce conflict: [15][TK_MINUS] s8: Made to reduce on precedence for TK_MINUS
Production prec symbol: TK_MUL
Shift/Reduce conflict: [15][TK_MUL] s9: Reduced on associativity
Production prec symbol: TK_MUL
Shift/Reduce conflict: [15][TK_PLUS] s10: Made to reduce on precedence for TK_PLUS
Production prec symbol: TK_PLUS
Shift/Reduce conflict: [16][TK_DIV] s11: Keeping the shift
Production prec symbol: TK_PLUS
Shift/Reduce conflict: [16][TK_MINUS] s8: Reduced on associativity
Production prec symbol: TK_PLUS
Shift/Reduce conflict: [16][TK_MUL] s9: Keeping the shift
Production prec symbol: TK_PLUS
Shift/Reduce conflict: [16][TK_PLUS] s10: Reduced on associativity
Production prec symbol: TK_DIV
Shift/Reduce conflict: [17][TK_DIV] s11: Reduced on associativity
Production prec symbol: TK_DIV
Shift/Reduce conflict: [17][TK_MINUS] s8: Made to reduce on precedence for TK_MINUS
Production prec symbol: TK_DIV
Shift/Reduce conflict: [17][TK_MUL] s9: Reduced on associativity
Production prec symbol: TK_DIV
Shift/Reduce conflict: [17][TK_PLUS] s10: Made to reduce on precedence for TK_PLUS

With unary minus having the highest precedence of the specified operators, we resolve by reducing on precedence for every conflict of that rule.

Adding Operator Precedence to SLR(1) Table Construction

Were going to add a new data structure to the CFG structure used for holding the information in the `set_token_prec` declarations from above. This information will be used to (hopefully) resolve any conflicts which arise when encountering the specified tokens.

struct OpPrec {
    Symbol sym;
    int prec_level;
    string assoc;
    OpPrec(Symbol s = "", int p = 0, string a = 0) : sym(s), prec_level(p), assoc(a) { }
};

struct Production {
   /* ... etc ... */
   Symbol precOverride;
};

struct Grammar {
/* .... */
       map<Symbol, OpPrec> precedenceMap;
};

It should be fairly obvious how the `set_token_prec` directive maps to the above structure when reading the grammar file. Great, so now that we have the needed information, how do we use it? The answer to that question lies in the refactoring of our action table generation procedure.

Using associativity and precedence to resolve  conflicts

In order to resolve a conflict between to tokens using precedence rules, then there needs to be an existing relationship between the two symbols. Meaning, If we get a shift/reduce conflict betwen '+' and '/' but we only have precedence information for '+', then we might as well not have any at all. With that in mind, the first thing we do when encountering a conflict is to check the precedence map for both symbols, only proceeding if both exist.

for (Symbol a : G.follow.at(p.lhs)) {
      if (!tab[s].count(a)) {
           tab[s][a] = "r"+to_string(p.pid);
       } else {
            string existing = tab[s][a];
            if (existing[0] == 's') {
                  Symbol prod_sym = get_production_precedence_symbol(p, G);
                  if (!G.precedenceMap.count(prod_sym) || !G.precedenceMap.count(a)) {
                     cout<<"No way to resolve Shift/Reduce conflict: ["<<s<<"]["<<a<<"] "<<existing<<endl;
                  } else {

 But where do we get the two symbols from? One of the conflicting symbols is from the current production being processed while the other symbol is from the follow set we generate lookaheads from. To obtain the correct symbol from the production we implement a procedure called 'get_production_precdence_symbol()' who's name should tell you it's purpose. But how does it know which symbol to return? That's actually simpler than you would think: a symbols right-most terminal symbol is responsible for the productions precedence. Unless of course, we have assigned the production a precedence override token, as was the case for unary minus. 

Symbol SLRGenerator::get_production_precedence_symbol(const Production& p, const Grammar& G) {
    cout<<"Production prec symbol: ";
    if (!p.precOverride.empty()) {
        cout<<" (override)"<<p.precOverride<<endl;
        return p.precOverride;
    }
    //productions inherit the precedence of the _right_ most terminal symbol
    //as such, we scan the production _backwards_ so we can exit on the first terminal encountered.
    for (auto it = p.rhs.rbegin(); it != p.rhs.rend(); ++it) {
        if (G.terminals.count(*it)) {
            cout<<*it<<endl;
            return *it;
        }
    }
    cout<<"None."<<endl;
    return "";
}

If we do have the needed precedence information, then we have a simple set of rules for resolving conflicts. 

If the lookaheads precedence level is greater than the production's, we keep the existing shift. If the productions precedence level is greater, we replace it with a reduction. If the two symbols have the same precedence, than we turn to associativity. 

If the lookahead symbol is left associative we reduce, otherwise we prefer the existing shift.

                     OpPrec pr = G.precedenceMap[prod_sym];
                     OpPrec la = G.precedenceMap[a];
                     cout<<"Shift/Reduce conflict: ["<<s<<"]["<<a<<"] "<<existing<<": ";
                     if (la.prec_level > pr.prec_level) {
                        cout<<"Keeping existing shift"<<endl;
                     } else if (pr.prec_level > la.prec_level) {
                        tab[s][a] = "r" + to_string(p.pid);
                        cout<<"Reduce on precedence for "<<a<<endl;
                     } else {
                         if (la.assoc == "left") {
                               tab[s][a] = "r" + to_string(p.pid);
                               cout<<"Reduced on associativity"<<endl;
                         } else {
                               cout<<"Keep existing shift."<<endl;
                         }
                     }
                  }
              } else {
                  cout<<"Reduce/Reduce conflict: ["<<s<<"]["<<a<<"] "<<existing<<endl;
              }
       }
}

After implementing the above rules, we can now resolve shift/reduce conflicts which previously would have put a stop to table generation. Thats what i've got for today, Happy Hacking!

Leave A Comment

Search
Recent Posts
Meta