python - 如何在常规语法模型中实现通配符，字符类，否定字符类等？

TL; 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中包含了我的定义:

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成为从每个左侧到每个对应的右侧的集合的映射。但这现在不可行。

最佳答案

我不完全理解您的问题，但是从注释看来，您似乎正在尝试在不包含其他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  + "]+)"

注意:我更喜欢转义所有符号，因为某些字符(例如^)具有上下文转义的要求。如果它们始终处于逃避状态，则遇到问题的可能性较小。