parsing - 括号如何与自定义数据类型一起使用？

Question

目前，我正在研究 Haskell 中解析和显示表达式的问题。

type Name = String
data Expr = Val Integer
          | Var Name
          | Expr :+: Expr
          | Expr :-: Expr
          | Expr :*: Expr
          | Expr :/: Expr
          | Expr :%: Expr

这是我的数据类型 Expr 的代码，这就是我定义 show 函数的方式:

instance Show Expr where
  show (Val x) = show x
  show (Var y) = y
  show (p :+: q) = par (show p ++ "+" ++ show q)
  show (p :-: q) = par (show p ++ "-" ++ show q)
  show (p :/: q) = par (show p ++ "/" ++ show q)
  show (p :*: q) = par (show p ++ "*" ++ show q)
  show (p :%: q) = par (show p ++ "%" ++ show q)

par :: String -> String
par s = "(" ++ s ++ ")"

后来我尝试将字符串输入转换为表达式，但遇到了以下问题:我不明白第二种情况下的括号在Haskell中是如何实现的。

*Main> Val 2 :*:Val 2 :+: Val 3 
((2*2)+3)
*Main> Val 2 :*:(Val 2 :+: Val 3) 
(2*(2+3))

因此，我对如何将字符串中的括号转换为表达式感到有点困惑。目前我正在使用以下函数进行解析，但现在它只是忽略括号，这不是预期的行为:

toExpr :: String -> Expr
toExpr str = f (lexer str) (Val 0)
   where 
    f [] expr = expr
    f (c:cs) expr
     |isAlpha (head c)  = f cs (Var c)
     |isDigit (head c)  = f cs (Val (read c))
     |c == "+"  = (expr :+: f cs (Val 0))
     |c == "-"  = (expr :-: f cs (Val 0))
     |c == "/"  = (expr :/: f cs (Val 0))
     |c == "*"  = (expr :*: f cs (Val 0))
     |c == "%"  = (expr :%: f cs (Val 0))
     |otherwise = f cs expr

编辑:一些语法错误

Answer 1

I don't understand how parentheses in the second case are implemented in Haskell.

括号只是优先考虑要解析的表达式的特定部分。问题不在于您呈现的括号。我认为问题在于您没有为运算符分配优先级。这意味着，除非您指定括号，Haskell 将认为所有运算符具有相同的优先级，并从左到右解析这些运算符。这意味着 x ⊕ y ⊗ z 被解析为 (x ⊕ y) ⊗ z。

您可以使用 infixl 定义 :+:、:* 等运算符的优先级:

infixl 7 :*:, :/:, :%:
infixl 5 :+:, :-:

type Name = String
data Expr = Val Integer
          | Var Name
          | Expr :+: Expr
          | Expr :-: Expr
          | Expr :*: Expr
          | Expr :/: Expr
          | Expr :%: Expr

对于您的解析器(toExpr)，您将需要像 LALR parser [wiki] 这样的解析机制。将结果存储在堆栈上，从而进行正确的操作。