将标记解析为抽象语法树
好吧，让我们来看看你的语法
Dig ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Int ::= Dig | Dig Int
Var ::= a | b | ... z | A | B | C | ... | Z
Expr ::= Int | - Expr | + Expr Expr | * Expr Expr | Var | let Var = Expr in Expr
这是一个很好的简单语法，因为你可以从第一个标记中看出它将是什么类型的 epression。（如果有一些更复杂的东西，比如+出现在数字之间，或者-用于减法和求反，您需要成功列表技巧，在
功能解析器中进行了解释。）
让我们有一些示例原始输入：
rawinput = "- 6 + 45 let x = - 5 in * x x"
我从语法中理解的代表"(- 6 (+ 45 (let x=-5 in (* x x))))"，我假设您将其标记为
tokenised_input' = ["-","6","+","4","5","let","x","=","-","5","in","*","x","x"]
这符合语法，但你很可能已经得到
tokenised_input = ["-","6","+","45","let","x","=","-","5","in","*","x","x"]
更适合您的样品AST。我认为用你的语法来命名你的 AST 是个好习惯，所以我要继续替换
data AST = Leaf Int | Sum AST AST | Min AST | ...
和
data Expr = E_Int Int | E_Neg Expr | E_Sum Expr Expr | E_Prod Expr Expr | E_Var Char
| E_Let {letvar::Char,letequal:: Expr,letin::Expr}
deriving Show
我已经命名了 an 的各个部分E_Let，以便更清楚地了解它们所代表的含义。
编写解析函数
您可以isDigit通过添加import Data.Char (isDigit)帮助来使用：
expr :: [String] -> (Expr,[String])
expr [] = error "unexpected end of input"
expr (s:ss) | all isDigit s = (E_Int (read s),ss)
| s == "-" = let (e,ss') = expr ss in (E_Neg e,ss')
| s == "+" = (E_Sum e e',ss'') where
(e,ss') = expr ss
(e',ss'') = expr ss'
-- more cases
哎呀！太多的 let 子句模糊了意思，我们会E_Prod为E_Let. 让我们解决这个问题！
处理这个问题的标准方法是编写一些组合器；与其在我们的定义中烦人地处理输入[String]s，不如定义一些方法来混淆解析器的输出（map）并将多个解析器组合成一个（lift）。
清理代码1：map
首先我们应该定义pmap我们自己的等价map函数，这样我们就可以pmap E_Neg (expr1 ss)
代替let (e,ss') = expr1 ss in (E_Neg e,ss')
pmap :: (a -> b) -> ([String] -> (a,[String])) -> ([String] -> (b,[String]))
nonono，我什至看不懂！我们需要一个类型同义词：
type Parser a = [String] -> (a,[String])
pmap :: (a -> b) -> Parser a -> Parser b
pmap f p = \ss -> let (a,ss') = p ss
in (f a,ss')
但如果我这样做真的会更好
data Parser a = Par [String] -> (a,[String])
所以我可以做
instance Functor Parser where
fmap f (Par p) = Par (pmap f p)
我会把它留给你看你是否喜欢。
清理代码2：组合两个解析器
当我们有两个解析器要运行时，我们还需要处理这种情况，并且我们想使用一个函数来组合它们的结果。这称为将函数提升到解析器。
liftP2 :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
liftP2 f p1 p2 = \ss0 -> let
(a,ss1) = p1 ss0
(b,ss2) = p2 ss1
in (f a b,ss2)
甚至可能是三个解析器：
liftP3 :: (a -> b -> c -> d) -> Parser a -> Parser b -> Parser c -> Parser d
我会让你想想怎么做。在 let 语句中，您需要liftP5解析 let 语句的各个部分，提升忽略"="and的函数"in"。你可以做
equals_ :: Parser ()
equals_ [] = error "equals_: expected = but got end of input"
equals_ ("=":ss) = ((),ss)
equals_ (s:ss) = error $ "equals_: expected = but got "++s
还有几个可以帮助解决这个问题。
实际上，pmap也可以称为liftP1，但 map 是这类东西的传统名称。
用漂亮的组合器重写
现在我们准备清理expr：
expr :: [String] -> (Expr,[String])
expr [] = error "unexpected end of input"
expr (s:ss) | all isDigit s = (E_Int (read s),ss)
| s == "-" = pmap E_Neg expr ss
| s == "+" = liftP2 E_Sum expr expr ss
-- more cases
那一切都很好。真的，没关系。但是liftP5会有点长，感觉很乱。
进一步清理 - 超好的应用方式
应用函子是要走的路。记得我建议重构为
data Parser a = Par [String] -> (a,[String])
所以你可以让它成为一个实例Functor？也许您不想这样做，因为您所获得的只是fmap完美工作的新名称，pmap并且您必须处理所有那些Par使您的代码混乱的构造函数。不过，也许这会让您重新考虑；我们可以import Control.Applicative，然后使用data声明，我们可以定义<*>, 哪种方式表示then并使用<$>而不是pmap,*>有意义
<*>-but-forget-the-result-of-the-left-hand-side所以你会写
expr (s:ss) | s == "let" = E_Let <$> var *> equals_ <*> expr <*> in_ *> expr
这看起来很像您的语法定义，因此很容易编写第一次工作的代码。这就是我喜欢编写解析器的方式。事实上，这就是我喜欢写很多东西的方式。您只需要定义fmap,<*>和pure，所有简单的，并且不再重复liftP3等liftP4。
阅读有关应用函子的信息。他们真棒。
使 Parser 适用pure的提示：不更改列表。
<*>就像liftP2，但函数不是来自外部，它来自p1.