基于Megaparsec的Lambda演算解释器：如何移除指令分隔分号？

问题背景 #

我正在用Haskell的Megaparsec库开发支持术语定义的Lambda演算解释器，语法规则如下：

term := var | lambda var . term | term term
def := var = term
instruction := :e t | def

解析器需返回instruction列表，其中:e t用于归约求值，def用于命名定义。此前实现了带分号分隔的指令语法，现在希望移除分号，将program解析器改为program = sc *> some (definition <|> commandEval) <* eof后，解析器无法在遇到var = ...时停止解析当前term。

例如输入：

a = (lambda x . x)
    x

:e b a

b = lambda y . y

会触发报错：

6:3:
  |
6 | b = lambda y . y
  |   ^
unexpected '='
expecting ":e", "lambda", '(', end of input, lowercase letter, or newline

尝试给term解析器添加notFollowedBy排除定义语法，但未生效，需要实现无分号的指令解析，让解析器遇到var = term时自动停止当前term的解析。

核心问题分析 #

问题根源在于Megaparsec的<|>选择解析器是左优先的：当输入是var = ...时，解析器会优先尝试把var当作term的一部分（比如命令中的term参数、term应用的左操作数），而非识别为定义的开头。同时term的递归解析会贪婪消耗输入，导致后续的=被判定为term的非法字符。

具体解决方案 #

1. 优先识别定义的开头 #

不能直接使用definition <|> commandEval的顺序，需要给定义的开头添加预判，确保var后面紧跟=时，优先触发定义解析：

definition :: Parser Instruction
definition = do
  v <- varParser
  -- 预判：var后面不能是term的延续元素（比如空格后接lambda、(、var等）
  notFollowedBy $ lookAhead $ choice [symbol "lambda", symbol "(", varParser, eof]
  symbol "="
  t <- termParser
  pure $ Def v t

2. 区分顶层与内部term解析 #

定义的指令是顶层语法，因此顶层term解析完成后，不能紧跟=，而lambda体、括号内的term不受此限制。拆分term解析逻辑：

-- 顶层term：解析完成后不能紧跟=，用于命令参数和定义的右侧term
topLevelTerm :: Parser Term
topLevelTerm = termParser <* notFollowedBy (symbol "=")

-- 普通term：用于lambda体、括号内等内部场景
termParser :: Parser Term
termParser = choice
  [ Lambda <$> (symbol "lambda" *> varParser) <*> (symbol "." *> termParser)
  , parens termParser
  , do
      v <- varParser
      rest <- many termParser -- 处理term应用
      pure $ foldl App (Var v) rest
  ]

3. 调整命令解析逻辑 #

命令中的term参数使用顶层term解析，避免把后续的定义开头当作term应用的一部分：

commandEval :: Parser Instruction
commandEval = do
  symbol ":e"
  ts <- some topLevelTerm
  pure $ Eval ts

4. 确保空白解析器正确处理换行 #

空白解析器需要将换行识别为指令分隔符，示例实现：

sc :: Parser ()
sc = space1 -- 可扩展为包含注释的空白解析，核心是识别换行作为分隔

5. 最终program解析器 #

保持原有结构即可，此时定义和命令的优先级已通过预判调整：

program :: Parser [Instruction]
program = sc *> some (definition <|> commandEval) <* eof

为什么之前的notFollowedBy未生效？ #

之前的尝试可能将notFollowedBy加在了错误位置：比如仅在varParser后添加，但term的应用逻辑会继续消耗后续输入，导致=出现在term解析的中间，而非var的直接后续。只有在顶层term解析完成后或定义的var后添加预判，才能正确识别指令边界。

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