How to get left assoc operators with scala combina

2019-07-25 14:43发布

问题:

I've tried

/* inside RegexParser class */
def exp : Parser[Exp] = 
  term~addop_chain ^^ {case l~ThenAdd(optype,r) => AritOp(l,optype,r)}

def addop_chain : Parser[Exp] = 
  ("+"|"-")~term~addop_chain ^^ {case sym~term~ThenAdd(optype,r) => ThenAdd(sym, AritOp(term,optype,r)) }  |
  ("+"|"-")~term ^^ {case sym~term => ThenAdd(sym, term)}

def term = /* right now, only int literal. code unrelevant */

/* Case classes for storing: */
case class ThenAdd(sym: String, r: Exp)
case class AritOp(l: Exp, sym: String, r: Exp)

Which works!, but is right-assoc (not left-assoc), e.g. 5+(3-2), which is not what I want.

What I want is something like:

5+3-2

should become

AritOp(AritOp(5,+,3), -, 2)

(left assoc) But this feels almost impossible without (proper?) left recursion. What can I do?

(constriant: I can't use rep, repsep, opt (I'm doing an assignment, so the grammer should be as BNF as possible (ie. not EBNF)))