Haskell 中的解析函数，制作映射函数时遇到问题

Question

我是 Haskell 的新手，正在处理一项作业，我试图为一种简单的计算器语言创建解析函数。

给我一个语法，不允许我更改。我试图通过遍历字符串并递归地使用我的解析函数来解决它。

语法应该是

Expr -> Int | -Expr | + Expr Expr | * Expr Expr
Int -> Digit | Digit Int 
Digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

所以我的函数将 Expr 语言中的字符串作为参数，并生成这种格式的抽象语法树

data Ast = Tall Int | Sum Ast Ast | Mult Ast Ast| Min Ast| Var String deriving (Eq, Show)

Ast应该是一棵抽象语法树

这就是我目前在解析函数中得到的结果

parseEx :: [String] -> (Ast, [String])
parseEx [] = error "empty string"
parseEx (s:ss) | all isDigit s = (Tall (read s), ss)
               | s == "-"      = let (ast, ss') = parseEx ss in (Min ast, ss') 
               | s == "+"      = let (ast, ss'), let(ast',ss'') = parseEx ss in (Sum ast ast', ss') parseEx ss' (ast', ss'')  
               | s == "*"      = (Mult ast ast', ss'') where
                   (ast, ss'')   = parseEx ss'
                   (ast', ss''') = parseEx ss''

我可以清楚地看到 + 的条件是错误的，我不能在那里有两个 let。我也有点迷失在所有这些列表中。我在想 map 函数可能是我的问题的解决方案，也许它会让我的代码看起来更整洁一些。但我不确定如何开始，因为它必须采用 [String]->Ast 的形式。简单地坚持我已有的代码并尝试使其工作是否更容易？

Answer 1

parseEx 只能 return 两个东西，根据类型签名，所以

let (ast, ast', ss') = parseEx ...

没有意义。您需要 chain lets —— 也就是说，将一个变量绑定到下一个解析的输入：

let (ast, ss') = parseEx ss
    (ast', ss'') = parseEx ss'
in ...

（确保对齐 let 的子句，这在 Haskell 中很重要！）

请注意我们如何将 ss' 第一次解析的余数作为第二次解析的输入。这表示 "parse an AST from ss, and give me back the remainder of the string in ss'; and in that remainder, parse another AST".

仔细考虑在解析完整的 + 表达式后 return 余数。

此外，由于此功能相当复杂，我建议您在开发它时撒上 undefined 以使其逐渐进行类型检查。例如，从

开始

parseEx :: [String] -> (Ast, [String])
parseEx [] = error "empty string"
parseEx (s:ss) | all isDigit s = (Tall (read s), ss)
               | otherwise     = undefined

编译它，（修复它），并在 ghci 中测试它（解释结果可能需要一些细微差别的理解 undefined 和懒惰——但它也会建立这种直觉） .然后执行下一个子句，编译、测试、冲洗和重复。

Answer 2

I am not sure how to begin on that, since it would have to be on the form [String] -> Ast.

And is it easier to simply stick with the code that I have, and try to make it work?

一个是你导出的类型签名，另一个是你的内部实现。

例如，您可以像这样构建您的解析器：

parseEx :: String -> Ast
parseEx s = parseTokens (tokenize s [])

data Token = TokDigit Int | TokPlus | TokMinus | TokMult
type DigitStack = String

tokDigit :: DigitStack -> Token
tokDigit s = TokDigit (read (reverse s))

tokenize :: String -> DigitStack -> [Token]
tokenize [] digits =
  if null digits
  then []
  else [tokDigit digits]

tokenize (c:cs) digits
  | isDigit c = tokenize cs (c:digits)
  | not (null digits) = tokDigit digits : tokenize (c:cs) []
  | isSpace c = tokenize cs digits
  | otherwise = case c of
      '+' -> TokPlus : tokenize cs digits
      '-' -> TokMinus : tokenize cs digits
      '*' -> TokMult : tokenize cs digits
      _ -> error ("Unknown symbol " + show c)

parseTokens :: [Token] ->  Ast
parseTokens (t:ts) = ...

并不是说标记化对于您的简单语法来说是绝对必要的，但关键是您的解析器的内部表示不必受到 [String] -> Ast 签名的限制。您甚至可以使用像 Megaparsec 这样的解析器组合器库，并且仍然导出函数 [String] -> Ast.

Haskell 中的解析函数，制作映射函数时遇到问题

Parsing function in Haskell, trouble making a map function

string

parsing

haskell

abstract-syntax-tree