为算术表达式定义从左到右的解析器

Question

我很难在Haskell中定义从左到右的算术表达式解析器。到目前为止，我所做的就是按照“ G. Hutton，Haskell中的编程”一书定义从右到左的解析器。

-- the aexpr integer parser
aexpr_int :: Parser Int
aexpr_int = do
              a1 <- aterm_int
              s <- sign -- return 1 for "+" and -1 for "-"
              a2 <- aexpr_int
              return (a1 + (s * a2))
            <|>
            aterm_int

-- the aterm integer parser
aterm_int :: Parser Int
aterm_int = do
              a1 <- aterm_int
              char '*'
              a2 <- afactor_int
              return (a1 * a2);
            <|>
            do
              a1 <- afactor_int
              char '/'
              a2 <- aterm_int
              return (div a1 a2)
            <|>
            afactor_int

-- afactor_int
afactor_int :: Parser Int
afactor_int = do
                token (char '(')
                e <- aexpr_int
                token (char ')')
                return e
              <|> 
              do
                s <- sign 
                ic <- aexpr_int 
                return (s * ic)
              <|>  
              token int_const   

因此将1 - 2 - 3 - 4解析为1 - (2 - (3 - 4))，但我希望将其解析为((1 - 2) - 3) - 4。如何获得此结果？

Answer 1

这里的诀窍是定义一个aexpr_int解析器，该解析器首先解析aterm_int，然后递归，使用累加表达式上的辅助函数，检查sign >> aterm_int的多次出现，然后添加累加器的附加条件。它可能看起来像这样：

-- the aexpr integer parser
aexpr_int :: Parser Int
aexpr_int = do
  a1 <- aterm_int
  go a1
  where go expr =
          do
            s <- sign
            a2 <- aterm_int
            go (expr + (s * a2))
          <|> return expr

连同以下内容：

-- the aterm integer parser
aterm_int :: Parser Int
aterm_int = do
  a1 <- afactor_int
  go a1
  where go expr =
          do
            char '*'
            a2 <- afactor_int
            go (expr * a2)
          <|>
          do
            char '/'
            a2 <- afactor_int
            go (div expr a2)
          <|> return expr

-- afactor_int
afactor_int :: Parser Int
afactor_int = do
                token (char '(')
                e <- aexpr_int
                token (char ')')
                return e
              <|>
              do
                s <- sign
                ic <- afactor_int
                return (s * ic)
              <|>
              token int_const

这似乎正常工作：

> parseTest aexpr_int "1-2-3-4"
-8

[请注意，如果您使用的是真正的解析器库，而不是出于学习目的而尝试编写自己的解析器代码，则需要使用该库的内置表达式解析器或名称为chainl或[ C0]为此。