Haskell迷你Prolog解析器functorP与ruleP实现求助

首先默认你项目中AST的类型定义如下（和现有Parser代码逻辑匹配）：

-- AST.hs 参考结构
data Term = Atom String | Var String | Func String [Term] deriving (Show, Eq)
data Rel = Cut | Rel String [Term] deriving (Show, Eq)
data Rule = Rule Rel [Rel] deriving (Show, Eq)
newtype Program = Program [Rule] deriving (Show, Eq)

functorP实现 #

Prolog中函子与关系的语法结构完全一致，格式为标识符(项1, 项2, ...)，解析逻辑就是按顺序匹配标识符、括号、分隔的参数列表即可：

functorP :: Parser (String, [Term])
functorP = do
  -- 匹配函子/关系名称，必须是原子类型（不能是变量）
  funcName <- tokenP (\t -> case t of
                  TName s -> Just s
                  _ -> Nothing)
  -- 匹配左括号
  _ <- symbol "("
  -- 解析逗号分隔的项列表作为参数，sepBy1要求至少有一个参数
  args <- termP `sepBy1` symbol ","
  -- 匹配右括号
  _ <- symbol ")"
  return (funcName, args)

逻辑说明 #

• 该函数返回的二元组刚好适配relHeadP里的uncurry Rel调用，会直接把函子名和参数列表包装成Rel类型
• 零参数的谓词不需要调用该解析器，现有termP里的逻辑会直接返回Atom类型，符合Prolog语法习惯

ruleP实现 #

Prolog的规则分为两类：事实（无规则体）和带体规则，两类规则均以.作为结尾标记：

ruleP :: Parser Rule
ruleP = do
  -- 解析规则头，只能是合法关系，不能是cut操作符
  ruleHead <- relHeadP
  -- 两种分支匹配：
  -- 1. 带体规则：匹配:-后接逗号分隔的子目标列表，最后匹配.
  -- 2. 事实：直接匹配.，规则体为空列表
  ruleBody <- (symbol ":-" *> (relP `sepBy` symbol ",") <* symbol ".")
              <|> ([] <$ symbol ".")
  return $ Rule ruleHead ruleBody

示例验证 #

• 解析事实parent(tom, jerry).
  1. 解析头得到Rel "parent" [Atom "tom", Atom "jerry"]
  2. 匹配到.，规则体为空列表
  3. 最终结果：Rule (Rel "parent" [Atom "tom", Atom "jerry"]) []
• 解析带cut的规则ancestor(X,Y) :- parent(X,Z), !, ancestor(Z,Y).
  1. 解析头得到Rel "ancestor" [Var "X", Var "Y"]
  2. 匹配:-后解析子目标列表：[Rel "parent" [Var "X", Var "Z"], Cut, Rel "ancestor" [Var "Z", Var "Y"]]
  3. 匹配.后完成解析
  4. 最终结果：Rule (Rel "ancestor" [Var "X", Var "Y"]) [Rel "parent" [Var "X", Var "Z"], Cut, Rel "ancestor" [Var "Z", Var "Y"]]

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