Haskell正则RE类型实现firsts函数 提取正则语言所有首符号

需求定义 #

函数签名 #

firsts :: RE sym -> [sym]
firsts = undefined

RE正则表达式数据类型 #

data RE sym -- sym为字母表符号类型
    = RSym sym  -- 匹配单个符号
    | REps      -- 匹配空字符串
    | RZero     -- 不匹配任何字符串
    | RStar (RE sym)    -- 0次或多次重复
    | RPlus (RE sym)    -- 1次或多次重复
    | RAlt (RE sym) (RE sym) -- 二选一（或操作）
    | RSeq (RE sym) (RE sym) -- 拼接操作
    deriving (Show)

注：原定义中构造函数的注释存在错位，已按正则表达式常规语义修正

测试用字母表 #

data Alphabet = A | B | C deriving (Show, Eq)

功能要求 #

firsts re需要返回正则表达式re对应语言中所有字符串的可能首符号集合，不需要去重、不需要排序，满足以下3个条件：

• 返回列表长度有限，即使正则对应语言是无限集合
• 列表中每个符号都一定是正则语言中某个字符串的首符号
• 正则语言中所有字符串的首符号都必须出现在返回列表中

示例：若正则表示A(C|B)|BC，对应语言包含AB、AC、BC三个字符串，firsts re返回[A,B]即符合要求。 #

实现思路 #

需要先实现一个辅助函数nullable，用于判断当前正则表达式是否可以匹配空字符串，这是处理拼接（RSeq）场景的关键：如果拼接的第一个正则可以匹配空串，那么第二个正则的首符号也属于整个拼接正则的首符号集合。 #

完整实现代码 #

-- 辅助函数：判断正则是否可匹配空串
nullable :: RE sym -> Bool
nullable REps = True
nullable (RStar _) = True
nullable (RAlt a b) = nullable a || nullable b
nullable (RSeq a b) = nullable a && nullable b
nullable (RPlus a) = nullable a
nullable (RSym _) = False
nullable RZero = False

-- 目标函数实现
firsts :: RE sym -> [sym]
firsts (RSym s) = [s]
firsts REps = []
firsts RZero = []
firsts (RAlt a b) = firsts a ++ firsts b
firsts (RSeq a b) = if nullable a then firsts a ++ firsts b else firsts a
firsts (RStar a) = firsts a
firsts (RPlus a) = firsts a

实现说明 #

1. 所有分支都直接递归处理子正则表达式，返回列表长度必然有限，满足第一个要求
2. 仅返回正则语义下真实存在的首符号，不会引入无关符号，满足第二个要求
3. 覆盖了所有正则构造场景的首符号收集逻辑，不会遗漏任何合法首符号，满足第三个要求
4. 没有使用任何Eq或Ord约束的操作，不需要去重排序，符合类型签名约束

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