如何在正则语法模型中实现通配符、字符类、否定字符类等功能？

Question

简而言之：

如何在计算机模型中对语法产生式进行建模，以便同一左部具有无限数量的产生式？

---

我正在研究形式语言理论，并试图编写一个用于构建正则文法对象的类，这些对象可以传递给有限状态机。我的天真尝试是为每个允许的输入创建一个产生式API。下面是一个简化版本（基于正式文法定义 G =（N，Σ，P，S））：

class ContextFreeGrammar:
    def __init__(self, variables, alphabet, production_rules, start_variable):
        self.variables = variables
        self.alphabet = alphabet
        self.production_rules = production_rules
        self.start_variable = start_variable

    def __repr__(self):
        return '{}({}, {}, {}, {})'.format(
            self.__class__.__name__,
            self.variables,
            self.alphabet,
            self.production_rules,
            self.start_variable
        )


class RegularGrammar(ContextFreeGrammar):
    _regular_expression_grammar = None # TODO

    @classmethod
    def from_regular_expression(cls, regular_expression):
        raise NotImplementedError()

我还没有开始编写有限状态自动机或下推自动机。

正则表达式的语法是上下文无关的，因此我在 WSN 中包含了我的定义：

syntax = expression .
expression = term "|" expression .
expression = term .
term = factor repetition term .
term = factor term .
term = .
repetition = "*" .
repetition = "+" .
repetition = "?" .
repetition = "{" nonnegative_integer "," nonnegative_integer "}" .
repetition = "{" nonnegative_integer ",}" .
repetition = "{," nonnegative_integer "}" .
nonnegative_integer = nonzero_arabic_numeral arabic_numerals .
nonnegative_integer = arabic_numeral .
nonzero_arabic_numeral = "1" .
nonzero_arabic_numeral = "2" .
nonzero_arabic_numeral = "3" .
nonzero_arabic_numeral = "4" .
nonzero_arabic_numeral = "5" .
nonzero_arabic_numeral = "6" .
nonzero_arabic_numeral = "7" .
nonzero_arabic_numeral = "8" .
nonzero_arabic_numeral = "9" .
arabic_numeral = nonzero_arabic_numeral .
arabic_numeral = "0" .
arabic_numerals = arabic_numeral .
arabic_numerals = arabic_numeral arabic_numerals .
factor = "(" expression ")" .
factor = character_class .
factor = character .
escaped_character = "\\." .
escaped_character = "\\(" .
escaped_character = "\\)" .
escaped_character = "\\+" .
escaped_character = "\\*" .
escaped_character = "\\?" .
escaped_character = "\\[" .
escaped_character = "\\]" .
escaped_character = "\\\\" .
escaped_character = "\\{" .
escaped_character = "\\}" .
escaped_character = "\\|" .
character -> TODO ;
character_class = TODO .

可以很容易地看出，我明确地将替代项分成单独的产生式。我这样做是为了方便实现。但是我不知道如何处理字符类等内容。我希望production_rules是从每个左侧到其相应右侧集合的映射。但现在看起来不可行。

- Tyler Crompton

---

你需要字符类别成为非终结符的特定原因吗？试图将字符类别转换为 CFG 产生式并不是很实际。 - user2357112

如果你指的是我提供的WSN，我只是想把它作为一个变量，以使WSN更易于阅读。 - Tyler Crompton

我认为你的优先级有误，或者至少你正在使用一种不常见的习惯。通常，“ab*”表示“一个a后面跟着任意数量的b”，而不是“任意数量的ab”。 - rici

无论如何，我看不出有什么问题。你知道字母表是什么，所以你可以枚举所有可能的“字符”生成；除了需要转义的字符之外，每个字母表中的字符都会有一个生成。 - rici

如果使用 . 通配符，我知道它可以是任何可能的字符。但是如果我假设我正在使用 Unicode，那么就有很多可能的字符。Unicode 7.0 包含 112,956 个字符。我认为为了包含需要多个代码点的字符，我将放弃字符类中的范围。这使得这个问题稍微容易一些。我想我可能会为普通字符类和否定字符类分别创建一个子类 set 或类似的东西，并将句点转换为空的否定字符类。 - Tyler Crompton

@TylerCrompton：如果你正在寻找实际解决方案而不是理论解决方案，我很乐意回答，但这似乎是一个不同的问题。实际解决方案的主要见解是，很少有语法实际上区分112,956个不同的字符；通常可以将语法的字母表减少到几十个等价类。 （等价类的示例：在您的语法中，[1-9]。） - rici

Answer 1

我并不完全理解你的问题，但从评论中看来，你正在尝试在一个排除了其他Unicode和ASCII字符的预定义字符集内工作。

这里有一种我最近实现的类似限制条件下的方法：

[正则表达式] 字符组

以下是实施上述定义的示例：

global rx_Trim_FromAlphaNumeric
rx_Trim_FromAlphaNumeric =                          \
    "[" + rx_AlphaNumeric                  + "]+" + \
    "[" + rx_ValidCharacters_WithLineSpace + "]*"

global rx_StartsWithSymbol
rx_StartsWithSymbol =                                \
    "[^" + rx_AlphaNumeric                  + "]"  + \
    "["  + rx_Symbols                       + "]+" + \
    "["  + rx_LineSpace + rx_Symbols        + "]*" + \
    "["  + rx_AlphaNumeric                  + "]+" + \
    "["  + rx_ValidCharacters_WithLineSpace + "]*"

global rx_StartsWithLetter
rx_StartsWithLetter =                                \
    "^[" + rx_Alphabetic                    + "]+" + \
    "["  + rx_ValidCharacters_WithLineSpace + "]+"

global rx_StartsWithNumber
rx_StartsWithNumber =                                \
    "^[" + rx_Numeric                       + "]+" + \
    "["  + rx_ValidCharacters_WithLineSpace + "]+"

global rx_WordSegments
rx_WordSegments =                  \
    "([" + rx_Symbols    + "]+|" + \
    "["  + rx_Numeric    + "]+|" + \
    "["  + rx_Alphabetic + "]+|" + \
    "["  + rx_LineSpace  + "]+)"

注意：我更喜欢转义所有符号，因为某些字符（例如^）具有上下文转义要求。如果始终转义它们，则遇到问题的可能性较小。

- Enteleform