Haskell Ast -> IO ()

Question

我一直在做关于 Haskell 中解析的作业。我已经创建了将字符串解析为抽象语法树的函数，它可以正常工作。

解析器如何使用我之前编写的代码的简短示例：

tokenize :: String -> [String]
tokenize [] = []
tokenize xs @ (x : xs')
    | x `elem` t = [x] : tokenize xs'
    | isDigit x = [y | y <- takeWhile isDigit xs] : (tokenize (dropWhile isDigit xs))
    | otherwise = tokenize xs'
        where t = ['+', '-', '*']

--parseExpr recursively goes through list and produces ast
parseExpr :: [String] -> (Ast,[String])
parseExpr [] = error "Error!"
parseExpr (s:ss) | all isDigit s = (Int (read s),ss)
             | s == "-" = let (e,ss') = parseExpr ss in (Min e,ss')
             | s == "*" = (Mult e e',ss'')
             | s == "+" = (Sum e e',ss'') where
                          (e,ss') = parseExpr ss
                          (e',ss'') = parseExpr ss'

-- parse returns the first in the tuple returned from parseExpr
parse :: String -> Ast
parse [] = error "Empty string"
parse str = fst $ parseExpr x
  where x = tokenize str

parse "+ 8 * 9 10"
>> Sum (Int 8) (Mult (Int 9) (Int 10))

现在我要做的是编写一个函数，以正确的缩进打印 given ast。

函数如下：

showw :: Ast -> String

showw ast = ???

show :: Ast -> IO ()

show ast = putStr (showw ast)

所以：

show (parse "+ 8 * 9 10")
Sum
   Int 8
   Mult
      Int 9
      Int 10

我是否需要写 showw :: Ast -> String 以便它 returns 字符串 "Sum\n---Int 8\n---Mult\n------Int9\n------Int10" （“-”仅用于可视化空格）（我在正确的轨道上吗？将如果没有一些非常复杂的代码，这甚至是可能的？）。我还必须使打印树的缩进增加 3 个空格（我该怎么做？）。从我的研究中，我遇到了一种叫做 prettyprint 的东西，但问题是我不允许导入除 Data.Char.

以外的任何东西

顺便说一句，我不能更改任何功能

非常感谢帮助

Answer 1

您需要换行符和随深度增加的间距。

spacing n = concat $ take n (repeat "   ")

showw :: Ast -> String
showw ast = showw2 ast 0

showw2 :: Ast -> Int -> String
showw2 (Mult a a') n = spacing n ++ "Mult"  ++ "\n" ++ showw2 a (n+1) ++ showw2 a' (n+1)
showw2 (Sum a a' ) n = spacing n ++ "Sum"   ++ "\n" ++ showw2 a (n+1) ++ showw2 a' (n+1)
showw2 (Min a a' ) n = spacing n ++ "Min"   ++ "\n" ++ showw2 a (n+1) ++ showw2 a' (n+1)
showw2 (Int i    ) n = spacing n ++ "Int " ++ show i ++ "\n"

示例输出

putStr $ showw $ parse "+ 8 * 9 10"

Sum
   Int 8
   Mult
      Int 9
      Int 10
*Main>

Haskell Ast -> IO ()

Haskell Ast -> IO ()

parsing

haskell

pretty-print

abstract-syntax-tree