递归表达式的解析器在 ghci 中挂起

Question

我正在尝试为以下递归数据类型创建解析器：

data Expr = Val Int
          | Var Char
          | App Op Expr Expr
  deriving Show

data Op = Add | Sub | Mul | Div
  deriving Show

例如，它应该将 "(1 + (a / -2))" 解析为 App Add (Val 1) (App Div (Var 'a') (Val (-2)))。我已经设法为 Val 和 Var 构造函数以及 Op 的构造函数编写解析器，如下所示：

import Text.Regex.Applicative
import Data.Char

rNonnegativeIntegral :: (Read a, Integral a) => RE Char a
rNonnegativeIntegral = read <$> some (psym isDigit)

rNegativeIntegral :: (Read a, Integral a) => RE Char a
rNegativeIntegral = negate <$> (sym '-' *> rNonnegativeIntegral)

rIntegral :: (Read a, Integral a) => RE Char a
rIntegral = rNonnegativeIntegral <|> rNegativeIntegral

rVal :: RE Char Expr
rVal = Val <$> rIntegral

rVar :: RE Char Expr
rVar = Var <$> psym isAlpha

rOp = aux <$> (foldr1 (<|>) $ map sym "+-*/")
  where
    aux '+' = Add
    aux '-' = Sub
    aux '*' = Mul
    aux '/' = Div

当它加载到 ghci 中时，它可以产生以下输出：

ghci> findLongestPrefix rVal "-271"
Just (Val (-271), "")
ghci> findLongestPrefix rVar "a"
Just (Var 'a', "")
ghci> findLongestPrefix rOp "-"
Just (Sub, "")

当我为 App 构造函数引入这个递归定义时，麻烦来了：

whiteSpace :: RE Char String
whiteSpace = many $ psym isSpace

strictWhiteSpace :: RE Char String
strictWhiteSpace = some $ psym isSpace

rApp :: RE Char Expr
-- flip App :: Expr -> Op -> Expr
-- strictWhiteSpace after rOp to avoid conflict with rNegativeInteger
rApp = flip App <$> (sym '(' *> whiteSpace *> rExpr)
               <*> (whiteSpace *> rOp <* strictWhiteSpace)
               <*> (rExpr <* whiteSpace <* sym ')')

rExpr :: RE Char Expr
rExpr = rVal <|> rVar <|> rApp

这很好地加载到 ghci 中，并且所有以前的构造函数仍然有效。但是 findLongestPrefix rApp "(1 + a)" 和许多类似的表达式导致 ghci 挂起并且没有输出。

通过实验，我发现当 rExpr 作为第一个参数传递给 <* 时，问题通常会发生。例如，findLongestPrefix (rExpr <* whiteSpace) "a)" 也会导致 ghci 挂起。

此外，当 rExpr 的定义被

替换时

rExpr = rVal <|> rVar

所有这些悬而未决的问题都消失了。可以解析像"(1 + a)"这样的简单表达式，但是不支持递归表达式。

如何在此处实现递归解析器而不会出现挂起问题？

Answer 1

您描述的表达语言不规则。所以你必须使用不同的库。

幸运的是，本质上相同的解析器结构应该可以与大多数其他解析器组合器库一起正常工作。它应该像用新库的名称替换一些基本解析器来代替它们的正则表达式应用类似物一样简单。

递归表达式的解析器在 ghci 中挂起

Parser for recursive expressions hangs in ghci

regex

parsing

haskell