我有一项作业,但我不知道如何定义答案。
作业
编写函数exp::[String] -> (AST, [String])
AST
:
- 如果
x
是数字,则应显示Number x
。 - 如果它是“+”和“-”,则应显示
Atom x
。 - 如果读取的是“(”,那么“(”后面直到出现“)”的所有内容都应该是一个列表
[AST]
。
这样输出将是:
exp (token "(hi (4) 32)")
> (List [Atom "hi", List [Number 4], Number 32], [])
exp (token "(+ 3 42 654 2)")
> (List [Atom "+", Number 3, Number 42, Number 654, Number 2], [])
exp (token "(+ 21 444) junk")
> (List [Atom "+", Number 21, Number 444], ["junk"])
到目前为止我所拥有的
我已经有了 token 函数,token::String -> [String]
,它可以创建一个列表。
`token "( + 2 ( + 2 3 ) )"
> ["(","+","2","(","+","2","3",")",")"]`
exp
函数如下所示:
exp :: [String] -> (AST, [String])
exp [] = error "Empty list"
exp (x:xs) | x == ")" = error ""
| x == "(" = let (e, ss') = exp xs in (List [getAst xs], ss')
| x == "+" = let (e, ss') = exp xs in (Atom (read x), ss')
| x == "-" = let (e, ss') = exp xs in (Atom (read x), ss')
| otherwise = exp xs`
其中 getAst
函数:
getAst :: [String] -> AST
getAst [] = error ""
getAst (x:xs)
| x == ")" = error ""
| x == "(" = (List [getAst xs])
| isAtom x = (Atom x)
| isNum x = (Number (read x))
| otherwise = getAst xs`
(是的,我是 Haskell 的初学者..)
最佳答案
我想我可以尽力帮助你。
问题的表现方式你应该能够通过查看下一个来做到这一点 输入/ token 并从那里决定去哪里。
一些假设
数据表示为[String] -> (Ast, [String])
的方式我假设它是一个常见的解析器,其中
解析器尝试读取输入的某些部分,并返回解析/转换后的输出以及未转换的输入的其余部分(因此只有元组的两个部分 - Ast
和其余的输入)。
AST 类型
因为您没有包含它,所以我认为它是:
data Ast
= Number Int
| Atom String
| List [Ast]
deriving Show
我需要一些东西
我需要一些东西:
import Prelude hiding (exp)
import Control.Applicative ((<$>))
import Data.Maybe (fromJust, isJust)
我必须隐藏 exp
因为我们想将其用作函数名称。
然后我想通过 Maybe
进行 fmap
,因此我包含了 Control.Applicative
中的运算符。
这实际上就是这样,以防您之前没有看到它:
f <$> Nothing = Nothing
f <$> Just a = Just (f a)
我想要一些帮助也许
:
isJust
检查是否为Just _
- 和
fromJust
从Just a
获取a
最后,我需要这个辅助函数来读取
更安全一点:
tryRead :: (Read a) => String -> Maybe a
tryRead input =
case readsPrec 0 input of
(a,_):_ -> Just a
_ -> Nothing
这将尝试在此处读取一个数字 - 如果 n 是数字,则返回 Just n
,否则返回 Nothing
。
第一次尝试
这是一个未完成首先解决您的问题:
exp :: [String] -> (Ast, [String])
exp (lookat:rest)
| isJust number = (fromJust number, rest)
| lookat == "(" = parseList rest []
where number = Number <$> tryRead lookat
parseList :: [String] -> [Ast] -> (Ast, [String])
parseList inp@(lookat:rest) acc
| lookat == ")" = (List (reverse acc), rest)
| otherwise = let (el, rest') = exp inp
in parseList rest' (el:acc)
正如你所看到的,我只是基于 lookat
进行分支,但略有不同:
如果我看到一个数字,我会返回该数字和剩余 token 列表。
如果我看到 (
,我会启动另一个解析器 parseList
。
parseList
也会做同样的事情:
- 它查看第一个 token
- 如果 token 是 )
它完成当前列表(它使用累加器技术)并返回。
- 如果不是,它使用现有的 exp
解析器递归地获取列表的元素。
这是一个运行示例:
λ> let input = ["(", "2", "(", "3", "4", ")", "5", ")"]
λ> exp input
(List [Number 2,List [Number 3,Number 4],Number 5],[])
待办事项
还有一些边界情况需要您决定(如果没有输入标记怎么办?)。
当然,您必须添加 Atom 的情况 - 才能完成此练习。
完整解决方案
好的 - 3 小时后,OP 没有再次 checkin ,所以我想我可以发布完整的解决方案。 我希望我没有忘记任何边缘情况,并且这肯定不是最有效的实现(想到了 token ) - 但OP给出的示例全部匹配:
module Ast where
import Prelude hiding (exp)
import Control.Applicative ((<$>))
import Data.Char (isSpace, isControl)
import Data.Maybe (fromJust, isJust)
data Ast
= Number Int
| Atom String
| List [Ast]
| Empty
deriving Show
type Token = String
main :: IO ()
main = do
print $ parse "(hi (4) 32)"
print $ parse "(+ 3 42 654 2)"
print $ parseAst . tokens $ "(+ 21 444) junk"
parse :: String -> Ast
parse = fst . parseAst . tokens
parseAst :: [Token] -> (Ast, [Token])
parseAst [] = (Empty, [])
parseAst (lookat:rest)
| isJust number = (fromJust number, rest)
| lookat == "(" = parseList rest []
| otherwise = (Atom lookat, rest)
where number = Number <$> tryRead lookat
parseList :: [Token] -> [Ast] -> (Ast, [Token])
parseList [] _ = error "Syntax error: `)` not found"
parseList inp@(lookat:rest) acc
| lookat == ")" = (List (reverse acc), rest)
| otherwise = let (el, rest') = parseAst inp
in parseList rest' (el:acc)
tokens :: String -> [Token]
tokens = split ""
where split tok "" = add tok []
split tok (c:cs)
| c == '(' || c == ')' = add tok $ [c] : split "" cs
| isSpace c || isControl c = add tok $ split "" cs
| otherwise = split (tok ++ [c]) cs
add "" tks = tks
add t tks = t : tks
tryRead :: (Read a) => Token -> Maybe a
tryRead input =
case readsPrec 0 input of
(a,_):_ -> Just a
_ -> Nothing
示例运行
λ> :main
List [Atom "hi",List [Number 4],Number 32]
List [Atom "+",Number 3,Number 42,Number 654,Number 2]
(List [Atom "+",Number 21,Number 444],["junk"])
关于parsing - Haskell 中的 AST 和解析,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26230759/