在 Haskell 中使用组合器进行表达式评估

Question

我正在尝试用 Hakell 制作一个表达式评估器：

data Parser i o
  = Success o [i]
  | Failure String [i]
  | Parser
      {parse :: [i] -> Parser i o}

data Operator = Add | Sub | Mul | Div | Pow

data Expr
  = Op Operator Expr Expr
  | Val Double

expr :: Parser Char Expr
expr = add_sub
  where
    add_sub =  calc Add '+' mul_div  <|>  calc Sub '-' mul_div  <|>  mul_div
    mul_div =  calc Mul '*' pow  <|>  calc Div '/' pow  <|>  pow
    pow     =  calc Pow '^' factor  <|>  factor
    factor  =  parens  <|>  val
    val     =  Val  <$>  parseDouble
    parens  =  parseChar '('  *>  expr  <*  parseChar ')'
    calc c o p =  Op c  <$>  (p  <*  parseChar o)  <*>  p

我的问题是，当我尝试使用两个具有相同优先级的运算符（例如

1+1-1

）评估表达式时，解析器将失败。

我怎么能说

add_sub

可以是另外两个

add_sub

之间的操作而不创建无限循环？

Answer 1

正如@chi所解释的，问题是

calc

使用了p两次，这不允许像

muldiv + .... | muldiv - ... | ...

这样的模式

我刚刚将

calc

的定义更改为：

calc c o p p2 = Op c <$> (p <* parseChar o) <*> p2

其中 p2 是当前优先级（

mul_div

定义中的

mul_div

）

它的效果要好得多，但计算顺序是相反的：

2/3/4

被解析为

2/(3/4)

而不是

(2/3)/4

Answer 2

您应该构建一个秒差距的模拟

chainl1

，引用：

消除表达式语法中通常出现的左递归。