时间戳

首页 > 解决方案 > Haskell 函数来检查正则表达式是否为空

haskell - Haskell 函数来检查正则表达式是否为空

问题描述

嗨，我有以下用于正则表达式的数据类型：

data RE a            -- regular expressions over an alphabet defined by 'a'
= Empty          -- empty regular expression
| Sym a          -- match the given symbol
| RE a :+: RE a  -- concatenation of two regular expressions
| RE a :|: RE a  -- choice between two regular expressions
| Rep (RE a)     -- zero or more repetitions of a regular expression
| Rep1 (RE a)    -- one or more repetitions of a regular expression
deriving (Show)

我需要设计一种方法来检查该正则表达式是否包含空字符串。例如 (Rep (Sym 'a' :+: Sym 'b')) 为真， (Sym 'a') 为假。我将如何让这个方法返回一个布尔值？

标签： haskell

解决方案

计算 Salomaa 的空字属性（有时也称为“可空”）通常是通过将正则表达式转换为正常形式来完成的，该形式利用代数属性来删除多余的 Kleene 星，然后检查表达式中是否仍有星运算符或如果表达式具有或本身Empty就是您所定义的。这是一个例子。

-- decide if the language defined by r contains ε, i.e.
-- nullable (r) ⇔ ε ∈ ℒ(r)
-- Also know as Salomaa's Empty Word Property (EWP)
nullable ∷ (Ord s) ⇒ RegExp s → Bool
nullable = nullable' . normalize
  where nullable' Zero     = False
        nullable' One      = True
        nullable' (Lit  _) = False
        nullable' (α :| β) = nullable' α || nullable' β
        nullable' (α :. β) = nullable' α && nullable' β
        nullable' (Star _) = True

添加一个案例Rep1看起来像nullable' (Rep1 α) = nullable' α.

推荐阅读