Haskell结合State与Alternative：解析器及生成式规则验证问题

嘿，看起来你已经搭好了解析器的核心基础框架——用ExceptT处理错误、State管理Token流，还有consumeToken和peekToken这两个关键工具函数，接下来要做的就是用这些来实现生成式规则的验证，也就是经典的递归下降解析啦！我给你梳理下具体的实现思路和实用例子：

每个生成式规则对应一个独立的Parser函数，比如规则Expr → Term ( '+' Term )*就对应parseExpr :: Parser Expr。我们用peekToken预判当前Token是否符合规则的起始符号，符合就用consumeToken消耗它，再递归调用子规则的Parser来组合最终结果。

先写一个matchToken函数，把peekToken+consumeToken的逻辑封装起来，避免重复代码：

matchToken :: (Token -> Bool) -> Parser Token
matchToken predicate = do
  currentTok <- peekToken
  if predicate currentTok
    then consumeToken  -- 匹配成功就消耗该Token
    else throwE $ UnexpectedToken currentTok (expectedFromPredicate predicate)
-- 这里需要你补充`expectedFromPredicate`函数，根据传入的匹配逻辑返回对应的ExpectedToken，方便错误提示

假设我们有这样的生成式规则：

Expr → Term ( ( '+' | '-' ) Term )*
Term → Factor
Factor → Number | '(' Expr ')'

先定义对应的AST类型（你可以根据需求调整）：

data Expr = Literal Int | Add Expr Expr | Subtract Expr Expr deriving (Show)

然后逐个实现规则的Parser：

解析Factor #

parseFactor :: Parser Expr
parseFactor = do
  tok <- peekToken
  case tok of
    -- 匹配数字：消耗Token并返回Literal节点
    Number n -> do
      consumeToken
      return $ Literal n
    -- 匹配括号：消耗左括号后递归解析Expr，再确保右括号存在
    LParen -> do
      consumeToken
      innerExpr <- parseExpr
      _ <- matchToken (== RParen)
      return innerExpr
    -- 既不是数字也不是左括号，抛出明确错误
    _ -> throwE $ UnexpectedToken tok ExpectedNumberOrLParen

解析Term #

因为Term直接对应Factor，逻辑非常简单：

parseTerm :: Parser Expr
parseTerm = parseFactor

解析Expr #

这里要处理重复的(+/- Term)部分，用many组合子匹配零次或多次：

parseExpr :: Parser Expr
parseExpr = do
  -- 先解析第一个Term
  firstTerm <- parseTerm
  -- 解析后续所有的"+ Term"或"- Term"
  restTerms <- many parseOpTerm
  -- 把所有Term用运算符组合成完整的Expr
  return $ foldl combineExpr firstTerm restTerms
  where
    combineExpr acc (op, term) = case op of
      Plus -> Add acc term
      Minus -> Subtract acc term
      _ -> error "Unexpected operator (这部分实际不会触发，因为parseOpTerm已做匹配校验)"

-- 解析单个"+ Term"或"- Term"
parseOpTerm :: Parser (Token, Expr)
parseOpTerm = do
  -- 匹配+或-运算符
  op <- matchToken (\t -> t == Plus || t == Minus)
  -- 解析运算符后的Term
  term <- parseTerm
  return (op, term)

如果生成式有分支（比如Stmt → ExprStmt | VarDecl），可以用<|>组合子（需要导入Control.Applicative）：

parseStmt :: Parser Stmt
parseStmt = parseExprStmt <|> parseVarDecl

如果有可选部分（比如OptionalExpr → Expr | ε），用optional组合子：

parseOptionalExpr :: Parser (Maybe Expr)
parseOptionalExpr = optional parseExpr

最后写一个顶层函数来启动解析，把Token流转换成AST或者错误信息：

runParser :: Parser a -> [Token] -> Either ParseError a
runParser parser tokens = case runState (runExceptT parser) tokens of
  (Left err, _) -> Left err
  (Right result, _) -> Right result

• 错误信息要明确：抛出错误时尽量携带预期的Token类型，调试时能快速定位问题
• 避免左递归：递归下降解析不支持左递归规则（比如Expr → Expr '+' Term），要改成Expr → Term ( '+' Term )*这种右递归形式
• 利用Monad特性：Parser是Monad，用do语法可以轻松组合子Parser，处理顺序依赖的规则

内容的提问来源于stack exchange，提问作者Graham