4

我很难在 Haskell 中定义从左到右的算术表达式解析器。到目前为止，我所做的是定义一个从右到左的解析器，遵循“G. Hutton, Programming in 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。我怎样才能达到这个结果？

4

1 回答 1

2

这里的技巧是定义一个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器sepBy来完成此操作。

于 2019-12-21T20:13:12.563 回答