在Haskell中解析一个简单的解释器

Question

我对Haskell相对较新,主要编程背景来自OO语言.我正在尝试使用解析器编写一个解释器来编写简单的编程语言.到目前为止,我有一个解释器处于一个我很满意的状态,但我正在与解析器稍微挣扎.

这是我遇到问题的一段代码

data IntExp
 = IVar Var
 | ICon Int
 | Add IntExp IntExp
 deriving (Read, Show)

whitespace = many1 (char ' ')

parseICon :: Parser IntExp
parseICon =
  do x <- many (digit)
     return (ICon (read x :: Int))

parseIVar :: Parser IntExp
parseIVar = 
  do x <- many (letter)
     prime <- string "'" <|> string ""
     return (IVar (x ++ prime))

parseIntExp :: Parser IntExp
parseIntExp =
  do x <- try(parseICon)<|>try(parseIVar)<|>parseAdd
     return x

parseAdd :: Parser IntExp
parseAdd =
  do x <- parseIntExp   
     whitespace
     string "+"
     whitespace
     y <- parseIntExp
     return (Add x y)

runP :: Show a => Parser a -> String -> IO ()
runP p input
  = case parse p "" input of
      Left err ->
        do putStr "parse error at "
           print err
      Right x -> print x

语言稍微复杂一点,但这足以说明我的问题.

所以在IntExp类型中ICon是一个常量,而IVar是一个变量,但现在问题就出现了.例如,这成功运行

runP parseAdd"5 + 5"

给出(Add(ICon 5)(ICon 5)),这是预期的结果.使用IVars而不是ICons时会出现问题,例如

runP parseAdd"n + m"

这导致程序错误地说有一个意外的"n",其中有一个数字是预期的.这让我相信parseIntExp没有像我预期的那样工作.我的意图是它将尝试解析ICon,如果失败则尝试解析IVar等等.

所以我认为问题存在于parseIntExp中,或者我在parseIVar和parseICon中遗漏了一些东西.

我希望我已经提供了足够的关于我的问题的信息,我很清楚.

感谢你给与我的帮助!

Answer 1

你的问题实际上是parseICon:

parseICon =
  do x <- many (digit)
     return (ICon (read x :: Int))

该many组合子匹配零次或多个出现,所以它通过匹配零位,那么当可能接替死去的"M" read失败.

虽然我在这里,因为你是Haskell的新手,这里有一些未经请求的建议:

• 不要使用假括号.many (digit)应该只是many digit.这里的括号只是分组,它们不是功能应用所必需的.

• 你不需要这样做ICon (read x :: Int).数据构造函数ICon只能接受Int,因此编译器可以自己弄清楚你的意思.

• 你现在不需要try前两个选项parseIntExp- 没有输入会导致任何一个输入在失败之前消耗一些输入.它们要么立即失败(不需要try),要么在匹配单个字符后成功.

• 在解析之前首先进行标记化通常是一个更好的主意.在语法处理的同时处理空白是一件令人头疼的事.

• 在Haskell中使用($)运算符来避免使用括号是很常见的.它只是函数应用程序,但具有非常低的优先级,所以many1 (char ' ')可以编写类似的东西many1 $ char ' '.

此外,做这种事情是多余的和不必要的:

parseICon :: Parser IntExp
parseICon =
  do x <- many digit
     return (ICon (read x))

当你所做的只是将常规函数应用于解析器的结果时,你可以使用fmap:

parseICon :: Parser IntExp
parseICon = fmap (ICon . read) (many digit)

他们是完全一样的.如果导入Control.Applicative模块,可以使事物看起来更好,它可以为您提供fmap调用的操作符版本(<$>),以及(<*>)允许您使用多个参数的函数执行相同操作的另一个操作符.还有运营商(<*)和(*>)该丢弃分别向右或向左值,在这种情况下,您可以解析的东西,而丢弃的结果,例如,空格和这样的.

以下是您的代码的轻微修改版本,其中包含一些上述建议以及其他一些小的风格调整:

whitespace = many1 $ char ' '

parseICon :: Parser IntExp
parseICon = ICon . read <$> many1 digit

parseIVar :: Parser IntExp
parseIVar = IVar <$> parseVarName

parseVarName :: Parser String
parseVarName = (++) <$> many1 letter <*> parsePrime

parsePrime :: Parser String
parsePrime = option "" $ string "'"

parseIntExp :: Parser IntExp
parseIntExp = parseICon <|> parseIVar <|> parseAdd

parsePlusWithSpaces :: Parser ()
parsePlusWithSpaces = whitespace *> string "+" *> whitespace *> pure ()

parseAdd :: Parser IntExp
parseAdd = Add <$> parseIntExp <* parsePlusWithSpaces <*> parseIntExp