递归表达式的解析器挂在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

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

幸运的是，本质上相同的解析器结构应该可以与大多数其他解析器组合子库一起工作。它应该很简单，只需将新库的名称替换为几个基本的解析器，而不是它们的regex应用程序类似程序。