基本理论

理论的东西谁看了都头大，我就能减则减了，就说一点点。

正则表达式

正则表达式和我们平常使用的正则表达式差不多，只不过为了方便起见，我们只使用了$\cdot$、$*$和$|$三个运算符，实际上，大部分其他运算符的功能都可以被这三个运算符所替代1。

  • $\cdot$ 代表两个正则字符串的连接，如 $a\cdot b$ 就能匹配 ab，习惯上可以省略。
  • $|$代表并集，如$a|b$能匹配 $a$，也能匹配 $b$
  • $*$ 代表重复0次或更多，如 $a*$能匹配 $\epsilon$、$a$、$aa$、$aaa$等等，这里 $\epsilon$ 代表的是空字符串。

规定 $*$ 优先级最高，$\cdot$ 次之，$|$ 优先级最低，当然我们也有 $()$ 来表示优先计算。 显然有：

  • $\cdot$和$|$满足结合律
  • $\cdot$满足对$|$的分配律，如$a(b|c)\leftrightarrow ab|ac$
  • $|$满足交换律
  • $$满足幂等率，$(a)* \leftrightarrow a*$
  • $\epsilon|a\leftrightarrow a$，$\epsilon \cdot a\leftrightarrow a$，$a \cdot \epsilon \leftrightarrow a$

正规文法产生式

产生式是这样一个东西：

$$ A \rightarrow \epsilon $$ or $$ A \rightarrow abc $$ or $$ B \rightarrow aA $$ or $$ aC \rightarrow aAbBc $$ or $$ aAb \rightarrow Bac $$ or $$ A \rightarrow a|b* $$

意思就是左边的东西代表了右边的东西，我们习惯用小写字母代表真正的字母（称为终结符），用大写字母代表代表另一些字母的一个符号（称为非终结符）。

有个直观感受就行了，具体定义除了让人头大以外没啥意义。

正规文法

正规文法2是这样一个东西：

正规文法就是一堆产生式的集合3，这些产生式要满足：

  • 左边只有一个非终结符
  • 右边是：
    • $\epsilon$
    • 终结符
    • 一个终结符$\cdot$一个非终结符

明显这些产生式在替换的时候就会比较方便，而且日后拿来化 NFA 就非常容易了。

实践

实践证明，书上给的算法还是偏理论，实际应用起来还是会有很多问题。自己实现的时候还是要做很多的考虑。

我们结合我的代码来分析。代码使用Kotlin写成，项目地址在这里。

正则表达式

我们先将正则表达式中的元素抽象为接口4：

interface RegexComponent

那么哪些东西该实现这个接口呢？

字母

abstract class Character(private val name: String) : RegexComponent, Comparable<Character>
class NonTerminalCharacter(name: String) : Character(name)
open class TerminalCharacter(name: String) : Character(name)
object nullCharacter : TerminalCharacter("ε")

正则表达式中的元素之间运算的结果

class Concated(val components: List<RegexComponent>) : RegexComponent
class Optioned(val components: Set<RegexComponent>) : RegexComponent
class Repeated(val toRepeat: RegexComponent) : RegexComponent

开始我对把各个运算的业务逻辑放在哪里感到摇摆不定，因为我希望尽可能地使用分配律和结合率，来让后面的工作变得简单，但这样就不可避免地使用运行时类型识别，这有一点反模式的意味，因为一般来说都是建议Replace Conditional with Polymorphism的，但多态其实难以解决这里的问题，反而会造成Duplicated Code，例如运用对$|$的分配律的时候要分别在Character、Repeated和Concated中进行对Optioned类型的判断，如果试图用Polymorphism为所有RegexComponent添加一个返回这时要被分配出来的东西的属性，那么代码量就会平白无故多出很多，而且至少本人无法为这个属性命名（通常这意味着引入这个属性并非好主意）。

最终我决定干脆把所有业务逻辑塞到一个地方，反正这种学术性问题不存在改需求。

然后就做了一个factory出来：

object RegexComponentFactory {
    fun concated(component1: RegexComponent, component2: RegexComponent): RegexComponent
    fun optioned(component1: RegexComponent, component2: RegexComponent): RegexComponent
    fun repeated(component: RegexComponent): RegexComponent
    // ...
}

既然是factory，干脆把从字符串构造RegexComponent的方法也塞进去：

/**
 * 补上省略的'.'号
 */
private fun addOmittedDotOperator(str: String): String {
    val theString = StringBuilder()
    for ((index, ch) in str.withIndex()) {
        theString.append(ch)
        if (index != str.length - 1) {
            if ((ch.isLowerCase() || ch.isDigit() || ch == ')') &&
                    (str[index + 1].isLowerCase() || str[index + 1].isDigit() || str[index + 1] == '(') ||
                    (ch == '*' && !isRegexOperator(str[index + 1]) && str[index + 1] != ')')) {
                theString.append('.')
            }
        }
    }
    return theString.toString()
}

/**
* 实际构造过程
*/
private fun fromFormalString(string: String): RegexComponent {
    if (string == "")
        return nullCharacter
    try {
        return when {
            string.startsWith('(') && pairedRightBracketIndex(string) == string.length - 1 ->
                fromFormalString(eraseUselessBracketPairs(string))
            string.length == 1 ->
                TerminalCharacter(string)
            string.firstLayerContain('|') ->
                string.splitFirstLayerBy('|').map { fromFormalString(it) }.reduce { acc, regexPart -> acc or regexPart }
            string.firstLayerContain('.') ->
                string.splitFirstLayerBy('.').map { fromFormalString(it) }.reduce { acc, regexPart -> acc concat regexPart }
            string.endsWith('*') ->
                if (string.startsWith('(')) {
                    fromFormalString(string.slice(1 until string.length - 2)).repeat()
                } else {
                    fromFormalString(string.slice(0 until string.length - 1)).repeat()
                }
            else ->
                throw IllegalArgumentException("Can not construct from string $string")
        }
    } catch (_: StringIndexOutOfBoundsException) {
        throw IllegalArgumentException("Can not construct from string $string")
    } catch (_: IllegalArgumentException) {
        throw IllegalArgumentException("Can not construct from string $string")
    }
}

/**
 * 从字符串中构造 RegexComponent
 */
fun fromString(string: String): RegexComponent {
    return fromFormalString(addOmittedDotOperator(string))
}

其中用到的几个帮助函数，实现可以在 Tools.kt 中找到。

/**
 * 判断 @arg char 是否是正则表达式运算符
 */
fun isRegexOperator(char: Char) = char == '|' || char == '*' || char == '.'

/**
 * 找到和某个'('相匹配的')'
 */
fun pairedRightBracketIndex(str: String, leftBracketIndex: Int = 0)

/**
 * 移除一个字符串两侧无用的括号
 */
fun eraseUselessBracketPairs(str: String): String

/**
 * 判断一个字符串的第一层是否有某个字符
 * "第一层"指所有括号之外
 */
fun String.firstLayerContain(char: Char): Boolean

/**
 * 将第一层用 @arg char split开
 */
fun String.splitFirstLayerBy(char: Char): List<String>

到这里为止，我们已经能让计算机从我们输入的字符串中“读懂”一个正则了。

接下来我们看文法那一边。

正规文法

要有正规文法，首先要有生成式：

class Generator(
        val from: NonTerminalCharacter,
        val to: RegexComponent
)

我们的文法是按照书上写的正规文法来的：

class Grammar(
        val nonTerminals: Set<NonTerminalCharacter>,
        val terminals: Set<TerminalCharacter>,
        val rules: Set<Generator>,
        val start: NonTerminalCharacter
) {
    // 我们都知道使用一些Generator就能完成初始化了
	constructor(rles: Collection<Generator>) : this(
            rles.map { it.from }.toSet(),
            rles.map { it.alphabet }.reduce { acc, set -> acc + set },
            rles.toSet(),
            rles.minBy { it.from }!!.from
    )
}

转换

正则表达式 $\rightarrow$ 正规文法

我们先构造一个产生式，其左侧是一个新的非终结符，右侧是要转换的正则表达式本身。

针对某个产生式，我们可能会面临这几种情况：

  • 这个产生式右侧最外层是$\cdot$运算 在这种情况下，我们还要考虑：

    • 如果这个产生式右侧以一个非终结符结尾，即形如 $A → a ⋅ b ⋅ B$ 或 $A → ( a | b ) ⋅ B$ 或 $A → a ∗ ⋅ B$ 的形式，我们要对这一非终结符左边的表达式的类型进行分类讨论：
      • 如果这个表达式最外层是$\cdot$运算，则我们可以直接将最右侧的两个字母结合起来： $$ C → b ⋅ B $$ 然后把前面那部分加进来： $$ A → a ⋅ C $$
      • 不可能会碰到这个表达式最外层是$|$运算的情况，因为我们前面已经使用了分配律将$|$运算符分配进去了5
      • 如果这个表达式最外层是$*$运算，我们可以构造出： $$ A → a A $$ 和 $$ A → B $$
    • 否则，就是一个形如 $$ A → a ⋅ b ⋅ c $$ 的式子，我们可以将其变为 $$ A → a ⋅ B $$ $$ B → b c $$ 这样的形式。

  • 这个产生式右侧最外层是$|$运算，即形如 $$ A → a | b | c $$ 的式子，将其变为 $$ A → a $$ 和 $$ A → b $$ 和 $$ A → c $$ 即可。

  • 这个产生式右侧最外层是$*$运算，即形如 $$ A → a ∗ $$ 这再简单没有了，只要化为： $$ A → ϵ $$ 和 $$ A → a ⋅ A $$ 即可。

我们只需要不断对还没有化到符合正规文法的生成式不断使用上面的规则，直到所有生成式都无法用上面的方法进一步化简的时候就能停止了。

此时的结果还不完全是正规文法，因为存在$A\rightarrow B$这样的直接推导到另外一个非终结符的推导式。

这时我们可以把所有产生式中的$A$都替换成$B$，然后移除这个产生式即可。

另外还有一些不被其他推导式使用的推导式，也可以移除。

完成这些之后，我们就完成了将正则表达式化为正规文法的过程了。

正规文法 $\rightarrow$ 正则表达式

要将一个正规文法转化为正则表达式，只需按照下面的算法进行即可：

  1. 将同一左侧但不同右侧的产生式用$|$结合成一个产生式 如$B\rightarrow b$ 和 $B → b ⋅ A$ 和 $B → b ⋅ B$ 化为 $B\rightarrow a|b\cdot A|b\cdot B$
  2. 将所有左侧包含右侧的产生式化为左侧不含右侧的产生式，如： $A → a ⋅ A$ 化为$A\rightarrow a*$ $B → a | b ⋅ A | b ⋅ B$ 化为 $B \rightarrow b* \cdot a|b* \cdot b \cdot A$
  3. 取一个左侧不是文法开始字符的产生式，将其他产生式中的对应这个选取的产生式的左侧的非终止字符替换成对应的串。
  4. 重复3.，直到只剩下一个产生式为止。
  5. 这个产生式右侧即位所求。

具体情况请见代码。

1

在有限字母表上定义了这三个算子、空字符串$\epsilon$和空集$\varnothing$之后就形成了一个神仙玩意：克莱尼代数

2

这里其实说的是右线性文法，还有左线性文法，这两者统称正规文法，为方便考虑取右线性文法作为例子来研究

3

其实真正的定义上，正规文法还包含了字母表，终结符表，非终结符表等等，然而这些都能从产生式中拿到，故其实意义不大

4

其实这个接口不仅仅是作为正则的一部分出现的，更好的名字是“实现了克莱尼代数的”，但这玩意看上去就太高深了……

5

但是我在代码中仍然保留了这一分枝