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-function可能是解决我的问题的一个解决方案，也许它会让我的代码看起来更整洁一些。但我不知道如何开始，因为它必须在表单[String]->Ast上。那么，简单地坚持我所拥有的代码，并使其工作起来是否更容易呢？

Answer 1

parseEx只能返回两件事情，按照类型签名，所以

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

没有道理。您需要链接lets --也就是说，将一个绑定在其中的变量提供给下一个解析的输入：

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

(确保使let的子句对齐，这在Haskell中很重要！)

注意我们是如何将ss' (第一个解析中的余数)作为输入传递给第二个解析的。这表示“从AST解析ss，并返回ss'中字符串的剩余部分；在该余数中，解析另一个AST”。

仔细考虑解析完整的+-expression后将返回的余数。

另外，由于这个函数相当复杂，我建议开发它，您可以四处撒点undefined，以便让它一点一点地输入check。例如，从

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

编译它，(修复它)，并在ghci中测试它(解释结果可能需要一些细微差别--理解undefined和懒惰--但它也会建立这种直觉)。然后做下一个子句，编译，测试，漂洗和重复。

Answer 2

我不知道如何开始，因为它必须在表单[String] -> Ast上。 那么，简单地坚持我所拥有的代码并使其工作是否更容易呢？

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

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

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签名的限制。您甚至可以使用像兆赫秒这样的解析器组合器库，并且仍然可以导出函数[String] -> Ast。