Haskell解析器转换为AST数据类型,赋值 [英] Haskell parser to AST data type, assignment
问题描述
我一直在搜索这些互联网了几天,试图得到我的问题的答案,并且我终于承认失败。
我给了一个语法:
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 |让Var = Expr in Expr
我已被告知使用此语法分析,评估和打印表达式
其中操作符 * + -
具有其正常含义
具体任务是编写函数 parse :: String - > ; AST
将字符串作为输入并在输入格式正确时返回抽象语法树(我可以推测它是)。
我被告知我可能需要一个合适的数据类型,并且该数据类型可能需要从其他类派生。
以下示例输出
data AST = Leaf Int |总和AST AST | Min AST | ...
另外,我应该考虑编写一个函数
tokens ::字符串 - > [String]
将输入字符串拆分为一个令牌列表
解析应该使用
ast :: [String] - > (AST,[String])
其中input是一个记号列表,它输出一个AST,并且解析子表达式,我应该简单地递归地使用ast函数。
我还应该使用printExpr方法来打印结果,以便
printE:AST - >字符串
printE(parse* 5 5)
产生5 * 5
或(5 * 5)
以及一个函数来评估表达式
evali :: AST - > Int
我只想指出我可以从哪里开始的正确方向。我对Haskell和FP一般知之甚少,并试图解决这个任务,我从Java中创建了一些字符串处理函数,这让我意识到我的方式偏离了轨道。
因此,正确的方向,也许解释'怎么'AST应该看起来像
连续第三天,仍然没有运行代码,我真的很感谢任何帮助我找到解决方案的尝试!
在此先感谢!
编辑
我可能不清楚:
I' m想知道如何从阅读和标记输入字符串到制作AST。
语法树
好的,让我们拿你的语法
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 |在Expr
中使Var = Expr b
这是一个很好的简单语法,因为您可以从第一个令牌它会是什么样的表现。 让我们来看一些示例原始输入: 我从语法中理解的代表 符合语法,但您可能已获得 $ C> A ST 更好。我认为这是一种很好的做法,在你的语法部分命名你的AST后,命名为 with 我已经命名了 您可以通过添加 Yikes!太多让子句模糊含义, 处理这个问题的标准方法是编写一些组合器; 首先我们应该定义 nonono,甚至阅读!我们需要一个类型同义词: 但是如果我这样做的话,那真的会更好。 所以我可以做 我会让你知道你是否喜欢。 当我们有两个解析器运行时,我们还需要处理这种情况, 甚至可能包含三个解析器: 我会让你考虑如何做到这一点。 以及其他一些帮助。 实际上, 现在我们准备清理 '一切都很好。真的,没关系。但是 Applicative Functors是最好的选择。 所以你可以使它成为 这看起来很像您的语法定义,因此很容易编写第一次运行的代码。 阅读有关Applicative Functors的内容。他们很棒。 使解析器适用性的提示: I have been searching around the interwebs for a couple of days, trying to get an answer to my questions and i'm finally admitting defeat. And i have been told to parse, evaluate and print expressions using this grammar that takes a string as input and returns an abstract syntax tree when the input is in the correct format (which i can asume it is). I am told that i might need a suitable data type and that data type might need to derive from some other classes. Following an example output Further more, i should consider writing a function I should also make a printExpr method to print the result so that I would just like to be pointed in the right direction of where i might start. I have little knowledge of Haskell and FP in general and trying to solve this task i made some string handling function out of Java which made me realize that i'm way off track. I might have been unclear:
I'm wondering how i should go about from having read and tokenized an input string to making an AST. OK, let's take your grammar This is a nice easy grammar, because you can tell from the first token what sort of epression it will be.
(If there was something more complicated, like Let's have some sample raw input: Which I understand from the grammar represents which fits the grammar, but you might well have got which fits your sample with I've named the bits of an You could use Yikes! Too many let clauses obscuring the meaning,
and we'll be writing the same code for The standard way of dealing with this is to write some combinators;
instead of tiresomely threading the input First we should define nonono, I can't even read that! We need a type synonym: But really this would be better if I did so I could do I'll leave that for you to figure out if you fancy. We also need to deal with the situation when we have two parsers to run,
and we want to combine their results using a function. This is called lifting the function to parsers. or maybe even three parsers: I'll let you think how to do that.
In the let statement you'll need and a couple more to help out with this. Actually, Now we're ready to clean up That'd all work fine. Really, it's OK. But Applicative Functors is the way to go.
Remember I suggested refactoring as so you could make it an instance of Which looks a lot like your grammar definition, so it's easy to write code that works first time.
This is how I like to write Parsers. In fact, it's how I like to write an awful lot of things.
You'd only have to define Read up about Applicative Functors. They're great. Hints for making Parser applicative: 这篇关于Haskell解析器转换为AST数据类型,赋值的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
(如果有更复杂的东西,比如数字之间的 +
,或者是用于减法的 -
作为
以及否定,你需要成功列表技巧,在
rawinput = - 6 + 45 let x = - 5 in * xx
( - 6(+ 45(let x = -5 in(* xx))))
,
,我假设你将它标记为
tokenised_input'= [ - ,6,+ ,4,5,let,x,=, - ,5,in,*,x,x]
tokenised_input = [ - ,6,+,45,let,x,=, - ,5,in ,*,x,x]
,这样我就可以继续并替换
data AST = Leaf Int |总和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}
派生显示
E_Let
中的各个部分,使它们更清晰地表示它们。
编写解析函数
import Data.Char(isDigit)来使用
isDigit
code>来帮忙:
expr :: [String] - > (Expr,[String])
expr [] =错误意外的输入结束
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'')其中
(e,ss')= expr ss
(e',ss'')= expr ss'
- 更多情况
,我们将为 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]))
type Parser a = [String] - > (a,[String])
pmap ::(a - > b) - >解析器a - >解析器b
pmap f p = \ss - >让(a,ss')= p ss
in(fa,ss')
data Parser a = Par [String] - > (a,[String])
instance Functor Parser其中
fmap f(Par p)= Par(pmap fp)
清理代码2:合并两个解析器
,并且我们想要使用一个函数来组合它们的结果。这被称为解析器的功能。
liftP2 ::(a - > b - > c) - >解析器a - >解析器b - >解析器c
$ p(
liftP2 f p1 p2 = \ ss0 - > (fab,ss2)
$ b $ $ p
pre $ lt; code> liftP3 ::(a - > b - > c - > d) - >解析器a - >解析器b - >解析器c - >解析器d
在let语句中,需要 liftP5
来解析let语句的部分,
提取一个忽略=
和in
。你可以使
$ b $ pre $ equals_ :: Parser()
equals_ [] = errorequals_:expected =但是结束了的输入
equals_(=:ss)=((),ss)
equals_(s:ss)= error $equals_:expected = but got++ s
pmap
也可以被称为 liftP1
,但是map是这种类型的传统名称。
使用漂亮的组合器重写
expr
:
expr :: [String] - > (Expr,[String])
expr [] =错误意外的输入结束
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])
函子
?也许你不想要
,因为为了完美的工作 pmap $,所有你已经获得的是一个新的名字
fmap
c $ c>和
,你必须处理所有那些混乱你的代码的 Par
构造函数。
也许这会让你重新考虑,我们可以导入Control.Applicative
,
然后使用 data
声明,我们可以
define < />
,这意味着然后
并使用< $> ;
代替 pmap
,其中 *>
意思是
< *> - 但是忘记了左手边的结果
,所以你可以写下
expr(s:ss)| s ==let= E_Let< $> var *> equals_< *> expr< *> in_ *> expr
这就是我喜欢写Parsers的方式。事实上,这就是我喜欢写很多东西的方式。
您只需要定义 fmap
,<>
和纯
,所有简单的,并且没有长重复 liftP3
, liftP4
等
纯粹
不会更改列表。
<>
就像 liftP2
,但该函数不是来自外部,它来自 p1
。
的输出
I have been given a grammar: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
where the operators * + -
has their normal meaning
The specific task is to write a function parse :: String -> AST
data AST = Leaf Int | Sum AST AST | Min AST | ...
tokens::String -> [String]
to split the input string into a list of tokens
Parsing should be accomplished with
ast::[String] -> (AST,[String])
where the input is a list of tokens and it outputs an AST, and to parse sub-expressions i should simply use the ast function recursively.
printE: AST -> String
printE(parse "* 5 5")
yields either "5*5"
or "(5*5)"
and also a function to evaluate the expression
evali :: AST -> Int
So a little pointer in the right direction, and maybe an explantion to 'how' the AST should look like
Third day in a row and still no running code, i really appreciate any attempt to help me find a solution!
Thanks in advance!
Edit Parsing tokens into an Abstract Syntax Tree
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
+
coming between numbers, or -
being used for subtraction as
well as negation, you'd need the list-of-successes trick, explained in
Functional Parsers.)rawinput = "- 6 + 45 let x = - 5 in * x x"
"(- 6 (+ 45 (let x=-5 in (* x x))))"
,
and I'll assume you tokenised it astokenised_input' = ["-","6","+","4","5","let","x","=","-","5","in","*","x","x"]
tokenised_input = ["-","6","+","45","let","x","=","-","5","in","*","x","x"]
AST
better. I think it's good practice to name your AST after bits of your grammar,
so I'm going to go ahead and replacedata 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
to make it clearer what they represent.Writing a parsing function
isDigit
by adding import Data.Char (isDigit)
to help out: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
and very much worse for E_Let
.
Let's get this sorted out! [String]
s through our definition, define ways to
mess with the output of parsers (map) and combine
multiple parsers into one (lift).Clean up the code 1: map
pmap
, our own equivalent of the map
function so we can do pmap E_Neg (expr1 ss)
instead of let (e,ss') = expr1 ss in (E_Neg e,ss')
pmap :: (a -> b) -> ([String] -> (a,[String])) -> ([String] -> (b,[String]))
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)
Clean up the code 2: combining two parsers
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
liftP5
to parse the sections of a let statement,
lifting a function that ignores the "="
and "in"
. You could makeequals_ :: Parser ()
equals_ [] = error "equals_: expected = but got end of input"
equals_ ("=":ss) = ((),ss)
equals_ (s:ss) = error $ "equals_: expected = but got "++s
pmap
could also be called liftP1
, but map is the traditional name for that sort of thing.Rewritten with the nice combinators
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
is going to be a bit long, and feels messy. Taking the cleanup further - the ultra-nice Applicative way
data Parser a = Par [String] -> (a,[String])
Functor
? Perhaps you don't want to,
because all you've gained is a new name fmap
for the perfectly working pmap
and
you have to deal with all those Par
constructors cluttering up your code.
Perhaps this will make you reconsider, though; we can import Control.Applicative
,
then using the data
declaration, we can
define <*>
, which sort-of means then
and use <$>
instead of pmap
, with *>
meaning
<*>-but-forget-the-result-of-the-left-hand-side
so you would writeexpr (s:ss) | s == "let" = E_Let <$> var *> equals_ <*> expr <*> in_ *> expr
fmap
, <*>
and pure
, all simple ones, and no long repetative liftP3
, liftP4
etc.pure
doesn't change the list.
<*>
is like liftP2
, but the function doesn't come from outside, it comes as the output from p1
.