TL; DR: Wie modelliert man die Produktionen einer Grammatik rechnerisch so, dass für die gleiche linke Seite eine unbestimmte Anzahl von Produkten existiert?Wie implementiert man Platzhalter, Zeichenklassen, negierte Zeichenklassen usw. in einem Modell für eine normale Grammatik?
Ich arbeite an einem Projekt, formale Sprachtheorie in Bezug auf und ich versuche, eine Klasse für den Aufbau von regulären Grammatik Objekte zu schreiben, die zu einer endlichen Zustandsmaschine übergeben werden kann. Mein naive Versuch war es, eine API für das Hinzufügen einer Produktion für jeden zulässigen Eingang zu erstellen. Eine abgespeckte Version von meinem Versuch ist wie folgt (bezogen auf die formale Definition einer formalen Grammatik 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()
Ich habe nicht tatsächlich das Schreiben des endlichen Automaten oder den Kellerautomat noch an den Punkt gelangt .
Die Grammatik für einen regulären Ausdruck ist kontextfrei, so habe ich meine Definition in WSN unten enthalten:
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 .
Man kann leicht sehen, dass ich ausdrücklich Splitting Abwechslungen in getrennte Produktionen. Ich mache das für eine einfache Implementierung. Aber ich stehe fest darauf, wie ich Charakterklassen und ähnliches machen soll. Ich wollte production_rules eine Karte von jeder linken Seite zu einer Reihe von jeder der entsprechenden rechten Seiten sein. Aber das sieht jetzt unmöglich aus.
Gibt es einen besonderen Grund, warum Sie Zeichenklassen als Nichtterminals verwenden müssen? Der Versuch, eine Charakterklasse in eine CFG-Produktion umzuwandeln, ist nicht sehr praktisch. – user2357112
Wenn Sie sich auf die WSN beziehen, die ich bereitgestellt habe. Ich wollte nur, dass es eine Variable ist, nur um das WSN leichter lesbar zu machen. –
Ich denke, Sie haben Ihre Priorität falsch, oder zumindest verwenden Sie eine ungewöhnliche Konvention. "Ab *" bedeutet normalerweise "ein' a' gefolgt von einer beliebigen Anzahl von 'b's", nicht "irgendeiner Anzahl von' ab's. – rici