如何用Earley库实现带特征与合一的FCFG解析？

Earley完全可以实现带特征合一的FCFG解析，无需将FCFG转成普通CFG导致文法膨胀。核心思路是将非终结符的特征作为参数嵌入解析规则，在解析过程中动态执行特征合一检查，以下是具体实现步骤和示例：

1. 定义特征与合一逻辑 #

首先用代数数据类型表示特征值和特征变量，再实现特征合一函数：

{-# LANGUAGE OverloadedStrings #-}
import Text.Earley
import Data.Map (Map)
import qualified Data.Map as Map

-- 表示数一致特征：单数/复数
data NumAgreement = SG | PL deriving (Eq, Show)

-- 特征表达式：常量或变量
data FeatureExpr a = Const a | Var String deriving (Eq, Show)

-- 合一函数：返回变量绑定Map（成功）或失败（Nothing）
unify :: Eq a => FeatureExpr a -> FeatureExpr a -> Maybe (Map String a)
unify (Const x) (Const y) | x == y = Just Map.empty
unify (Var v) (Const x) = Just $ Map.singleton v x
unify (Const x) (Var v) = Just $ Map.singleton v x
unify (Var v1) (Var v2) | v1 == v2 = Just Map.empty
                         | otherwise = Just $ Map.singleton v1 (error "Unbound variable") -- 简化处理，实际可优化为更严谨的变量绑定逻辑
unify _ _ = Nothing

2. 编写带特征约束的Earley规则 #

将每个非终结符定义为接受特征约束的函数，在解析动作中加入合一检查：

-- 名词短语：接受期望的特征表达式，返回解析结果和绑定的特征Map
np :: FeatureExpr NumAgreement -> Grammar r (Prod r String String (Map String NumAgreement))
np feat = rule $
  -- 匹配John/Mary，要求特征为SG
  ("John" <|> "Mary") *> pure (unify feat (Const SG) >>= const (Just Map.empty))
  <|>
  -- 匹配det + n，要求n的特征与np的特征合一
  do
    detRes <- det
    nBind <- n feat
    pure $ unify feat (Const (getAgreement nBind)) -- 简化获取n的特征值，实际可从绑定中提取
  where
    det = rule $ "the" *> pure (Just Map.empty)
    n reqFeat = rule $
      ("boys" <|> "girls") *> pure (unify reqFeat (Const PL) >>= const (Just PL))
      <|>
      ("John" <|> "Mary") *> pure (unify reqFeat (Const SG) >>= const (Just SG))
    getAgreement (Just agr) = agr
    getAgreement Nothing = error "Feature unification failed"

-- 动词短语：接受期望的特征表达式
vp :: FeatureExpr NumAgreement -> Grammar r (Prod r String String (Map String NumAgreement))
vp feat = rule $
  ("runs" <|> "walks") *> pure (unify feat (Const SG) >>= const (Just Map.empty))
  <|>
  ("run" <|> "walk") *> pure (unify feat (Const PL) >>= const (Just Map.empty))

-- 句子：要求np和vp的特征合一
sentence :: Grammar r (Prod r String String ())
sentence = rule $ do
  -- 用变量?x表示np和vp的特征一致
  let xVar = Var "x"
  npBind <- np xVar
  vpBind <- vp xVar
  -- 合并两次合一的绑定，确保无冲突
  case mergeBinds npBind vpBind of
    Just _ -> pure ()
    Nothing -> empty -- 合一失败则丢弃该分支
  where
    mergeBinds :: Maybe (Map String NumAgreement) -> Maybe (Map String NumAgreement) -> Maybe (Map String NumAgreement)
    mergeBinds Nothing _ = Nothing
    mergeBinds _ Nothing = Nothing
    mergeBinds (Just m1) (Just m2) =
      if Map.all (\k -> Map.lookup k m1 == Map.lookup k m2) (Map.keys m1 ++ Map.keys m2)
        then Just $ Map.union m1 m2
        else Nothing

3. 测试解析 #

用Earley的解析函数测试示例输入：

main :: IO ()
main = do
  let parseSent = fullParses (parser sentence)
  print $ parseSent ["John", "runs"] -- 成功：[()]
  print $ parseSent ["the", "boys", "walks"] -- 失败：[]
  print $ parseSent ["the", "boys", "walk"] -- 成功：[()]

关键说明 #

• 特征合一通过unify函数动态完成，无需预先生成所有特征组合的CFG规则，彻底避免文法膨胀。
• Earley的非确定性解析会自动遍历所有可能的特征绑定分支，自动丢弃合一失败的路径。
• 实际应用中可扩展特征类型（如格、性）和合一逻辑，支持更复杂的FCFG规则，比如多变量约束、特征继承等。

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