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

Question

我很难在 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。我怎样才能达到这个结果？

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 或 sepBy 来完成这个。

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

Defining a left-to-right parser for arithmetic expressions

parsing

haskell

arithmetic-expressions

left-to-right