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]
将输入字符串拆分为一个标记列表
解析应该完成
ast::[String] -> (AST,[String])
输入是一个标记列表并输出一个AST,并解析子表达式我应该只使用ast函数递归.

我还应该作出printExpr方法打印结果使得
printE: AST -> String
printE(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"]

更适合您的样品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

哎呀!太多让条款模糊了含义,我们将编写相同的代码E_Prod并且非常糟糕E_Let.让我们解决这个问题吧!

解决这个问题的标准方法是编写一些组合器; 而不是[String]通过我们的定义厌倦线程输入s,定义混淆解析器输出的方法(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 Functors是最佳选择.记得我建议重构为

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

这看起来很像你的语法定义,因此编写第一次有效的代码很容易.这就是我喜欢编写Parsers的方法.事实上,这就是我喜欢写很多东西的方式.你只需要定义fmap,<*>和pure所有简单的,没有长期的重复liftP3,liftP4等等.

阅读有关Applicative Functors的信息.他们很棒.

• 适用于学习你的Haskell为伟大的好!
• 适用于Haskell wikibook

使Parser适用的提示:pure不会更改列表. <*>就像liftP2,但功能不是来自外部,它来自于输出p1.