递归表达式的解析器挂在 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构造函数以及 for的构造函数编写了解析器，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

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

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