时间戳

首页 > 解决方案 > 在 Haskell 中使用组合器进行表达式评估

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

问题描述

我正在尝试在 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）评估表达式时，解析器将失败。

我怎么能说 anadd_sub可以是其他两个add_subs 之间的操作而不创建无限循环？

标签： parsinghaskellevaluation

解决方案

正如@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

推荐阅读