Wie reguläre Grammatik mit Rekursion und Alternationen in reguläre Ausdruck konvertieren

Question

Eine Grammatik ist regelmäßig, wenn es entweder rechts-linear oder links-linear ist. This tutorial behauptet, dass aus diesem Grunde hat die besondere Eigenschaft:

Eine regelmäßige Grammatik hat eine besondere Eigenschaft: von jedem Nicht-End-Substitution (mit Ausnahme der Wurzel eins) mit seiner rechten Seite, können Sie es zu einer Verringerung unten Einzelfertigung für die Wurzel, mit nur Terminals und Betreibern auf der rechte Seite ... die reduzierten Expression von Terminals und Operatoren kann in einer noch kompakten Form geschrieben werden, genannt einen regulären Ausdruck

Also habe ich beschlossen, das zu testen Idee und die Normal-EcmaScript grammar for IdentifierName in Normal-Ausdrücke konvertieren:

IdentifierName :: 
    IdentifierStart 
    IdentifierName IdentifierPart 

Es sei IdentifierStart und IdentifierPart sind beschränkt auf die folgenden:

IdentifierStart ::  IdentifierPart :: 
    A      A     
    B      C 
    C      & 
    $      
    _ 

Aber ich bin nicht sicher, wie da die Grammatik sowohl für IdentifierName muss gehen Rekursion und Alternation. Irgendeine Hilfe?

Ich interessiere mich eher für den Ansatz als für das Finden der resultierenden Regexp, die wie @Bergi zeigte [ABC$_][AC&]*.

Answer 1

Dieses Tutorial verwendet einige nicht standardmäßige (und überraschend implizite) Definitionen.

Zuerst verwenden sie Wiederholungsoperatoren in ihrer Grammatik, wie sie in regulären Ausdrücken oder EBNF gefunden werden könnten. Dann definieren sie implizit eine reguläre Grammatik als eine, die nur diese Wiederholungsoperatoren und keine Rekursion verwendet. Angesichts dessen ist es trivial, eine "reguläre Grammatik" in eine Regex zu verwandeln, indem man einfach alle Nicht-Terminals einordnet. Aber nach dieser Definition ist die Grammatik der JS-Spezifikation für Bezeichner nicht regulär, weil sie Rekursion enthält. Bevor Sie also alles inline einfügen können, müssen Sie zuerst die Rekursion durch Wiederholungsoperatoren ersetzen.

Dies ist jedoch nicht die Standarddefinition dessen, was eine normale Grammatik ist. Die Standarddefinition ist wie gesagt: Eine Grammatik ist regulär, wenn sie entweder links-linear oder rechts-linear ist - das heißt, wenn nur der äußerste linke Teil einer Produktion ein nicht-terminaler oder nur der rechte ist. Wiederholungsoperatoren existieren nicht in der üblichen Definition einer formalen Grammatik.

Nun können diese regulären Grammatiken auch in reguläre Ausdrücke konvertiert werden, jedoch nicht durch bloßes Anwenden der im Lernprogramm beschriebenen Methode. Ein Weg wäre, die Grammatik in einen endlichen Automaten umzuwandeln und dann den Algorithmus anzuwenden, der zum Beispiel in this answer beschrieben ist.

In der Praxis jedoch, wenn Sie die Konvertierung von Hand (anstatt ein Programm zu tun), die einfachste und gebräuchlichste Art, die Konvertierung durchzuführen, ist darüber nachzudenken, welche Sprache die Grammatik beschreibt (in diesem Fall "die Sprache aller Wörter, die mit einem IdentifierStart-Symbol beginnen und dann 0 oder mehr IdentifierPart-Symbole enthalten ") und dann einen regulären Ausdruck erstellen, der diese Sprache ausdrückt (aka der" Schau dir das Problem wirklich an, bis du den Lösungsalgorithmus siehst ") .