如何在一个常规语法模型中实现通配符、字符类、否定字符类等？

Question

DR：如何在计算上对语法的产生进行建模，以便在同一个左手边存在不确定数量的乘积？在

---

我正在做一个关于形式语言理论的项目，并试图编写一个类来构建可以传递给有限状态机的正则语法对象。我天真的尝试是创建一个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中包含了我的定义：

^{pr2}$

可以很容易地看出，我是显式地将备选方案拆分为单独的产品。我这样做是为了便于实施。但我一直在想我应该如何去学习角色课程之类的。我希望production_rules是从每个左手边到对应的右手边的一组映射。但现在看来不可行。在

Answer 1

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

下面是我最近实现的一种处理类似约束的方法：

[RegEx] Character Groups

下面是一个实现上述定义的示例：

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  + "]+)"

注意：我更喜欢转义所有符号，因为某些字符，如^，有上下文转义要求。如果它们总是被漏掉，就不太可能遇到问题。在