parsing - Haskell 解析器到 AST 数据类型，赋值

Question

我已经在互联网上搜索了几天，试图得到我的问题的答案，我终于承认失败了。
我得到了一个语法:
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
我被告知使用这种语法解析、评估和打印表达式
其中运营商* + -有它们的正常含义
具体任务是写一个函数parse :: String -> AST
当输入的格式正确时(我可以假设它是)，它接受一个字符串作为输入并返回一个抽象语法树。

有人告诉我，我可能需要一个合适的数据类型，并且该数据类型可能需要从其他一些类派生。

遵循示例输出data AST = Leaf Int | Sum AST AST | Min AST | ...
此外，我应该考虑编写一个函数tokens::String -> [String]将输入字符串拆分为 token 列表
解析应该用
ast::[String] -> (AST,[String])其中输入是一个标记列表，它输出一个 AST，为了解析子表达式，我应该简单地递归使用 ast 函数。

我还应该制作一个 printExpr 方法来打印结果，以便printE: AST -> StringprintE(parse "* 5 5")产生 "5*5"或 "(5*5)"以及一个评估表达式的函数evali :: AST -> Int
我只想指出我可能开始的正确方向。我一般对 Haskell 和 FP 知之甚少，为了解决这个任务，我用 Java 制作了一些字符串处理函数，这让我意识到我偏离了轨道。
所以在正确的方向上有一个小指针，也许是对 AST 应该是什么样子的“如何”的解释
连续第三天仍然没有运行代码，我真的很感谢任何帮助我找到解决方案的尝试!
提前致谢!
编辑

我可能一直不清楚:
我想知道我应该如何从读取和标记输入字符串到制作 AST。

Answer 1

将标记解析为抽象语法树

好的，让我们来看看你的语法

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

这是一个很好的简单语法，因为您可以从第一个标记中看出它将是哪种类型的表达。
(如果有更复杂的东西，比如 + 介于数字之间，或者 - 被用作减法
以及否定，你需要成功列表技巧，解释在
Functional Parsers .)

让我们有一些示例原始输入:

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"]

适合您的 sample 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

我已经命名了 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]通过我们的定义，定义方法
弄乱解析器( map )的输出并组合
多个解析器合二为一(提升)。

清理代码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 语句的各个部分，
提升一个忽略 "=" 的函数和 "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会有点长，感觉有点乱。

进一步清理 - 非常好的 Applicative 方式

应用仿函数是要走的路。
记得我建议重构为

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等等。

阅读有关应用仿函数的信息。他们很棒。

Applicative in Learn You a Haskell for Great Good!

Applicative in Haskell wikibook

使解析器适用的提示:pure不会更改列表。<*>就像 liftP2 ，但该函数不是来自外部，而是来自 p1 的输出.