使用Haskell编写一个解析器及其相应的AST

解析器 (Parser) 是一种程序，用于将输入字符串转换成抽象语法树 (Abstract Syntax Tree, AST)，以供进一步分析和处理。Haskell 提供了一种强大的解析器库叫做 Parsec，可以用它来编写解析器。

下面是一个使用 Haskell 和 Parsec 库编写的简单计算器解析器，可以解析简单的数学表达式，并将其转换成相应的 AST：

import Text.ParserCombinators.Parsec

-- AST 数据类型
data Expr = Number Int
          | Add Expr Expr
          | Subtract Expr Expr
          | Multiply Expr Expr
          | Divide Expr Expr

-- 解析器
expr :: Parser Expr
expr = chainl1 term addop

term :: Parser Expr
term = chainl1 factor mulop

factor :: Parser Expr
factor = number <|> parens expr

number :: Parser Expr
number = do
  n <- many1 digit
  return (Number (read n))

addop :: Parser (Expr -> Expr -> Expr)
addop =   do { char '+'; return Add }
      <|> do { char '-'; return Subtract }

mulop :: Parser (Expr -> Expr -> Expr)
mulop =   do { char '*'; return Multiply }
      <|> do { char '/'; return Divide }

parens :: Parser a -> Parser a
parens p = do
  char '('
  x <- p
  char ')'
  return x

-- 测试解析器
parseExpr :: String -> Either ParseError Expr
parseExpr input = parse expr "" input

main :: IO ()
main = do
  putStrLn "Enter a simple math expression:"
  input <- getLine
  case parseExpr input of
    Left err -> putStrLn $ "Error: " ++ show err
    Right ast -> putStrLn $ "AST: " ++ show ast

在上面的代码中，首先定义了一个自定义的数据类型 Expr，它表示 AST 中的节点，包括数字 (Number)、加法 (Add)、减法 (Subtract)、乘法 (Multiply) 和除法 (Divide)。然后，定义了 expr、term、factor 和 number 四个解析器，它们分别表示表达式、项、因子和数字的解析规则。addop 和 mulop 是两个解析中最重要的部分，它们表示加法和乘法运算符的解析规则。parens 函数用于解析括号中的表达式。最后，parseExpr 函数将给定的输入字符串解析成 AST，并返回结果。在 main 函数中，我们可以输入一个简单的数学表达式，程序将会打印出解析后的 AST。

使用例子：

输入：2 + 3 * (4 - 1)

输出：

AST: Add (Number 2) (Multiply (Number 3) (Subtract (Number 4) (Number 1)))

输入：10 / 2 + 5

输出：

AST: Add (Divide (Number 10) (Number 2)) (Number 5)

这个简单的解析器例子只支持几种基本的数学运算符和括号，并且不支持运算符优先级，但它演示了如何使用 Haskell 和 Parsec 库来编写一个解析器和相应的 AST。