Regulärer Ausdruck für kontextfreie Grammatik

Weiß jemand, ob es einen Algorithmus zum direkten Schreiben der kontextfreien Grammatik gibt, die einen bestimmten regulären Ausdruck erzeugt?

Ich gehe davon aus, dass Sie eine Grammatik erhalten möchten, die dieselbe Sprache wie der angegebene reguläre Ausdruck generiert.

Sie können dies durch die folgenden Schritte erreichen:

1. Übersetzen Sie den regulären Ausdruck in eine NFA.
2. Übersetzen Sie die NFA in eine (rechts-) reguläre Grammatik.

Beide Übersetzungen sind Standard und werden in grundlegenden Lehrbüchern zu formalen Sprachen und Automaten behandelt. Beachten Sie, dass jede reguläre Grammatik auch kontextfrei ist.

Ja. Ich gebe die Antwort auf hoher Ebene ohne viele Details.

Zuerst müssen Sie die Ausdrücke analysieren. Dies kann mit einem einfachen rekursiven anständigen Parser erfolgen. Einige Beispiele im Web.

Dann sollten Sie dem Parser "semantische" Regeln hinzufügen, wenn Sie von der Rekursion zurückkehren. Diese sind Standard in jedem formalen Sprachtheoriekurs. Wenn$S_1$ und $S_2$ sind Nicht-Terminals, die Ausdrücke erzeugen $E_1$ und $E_2$ dann können wir erzeugen $E_1+E_2$ durch $S$ und die Regeln $S\to S_1$, $S\to S_2$. Wir können Verkettung erzeugen$E_1 E_2$ durch $S$ und die Regel $S\to S_1 S_2$. $E_1*$ durch $S$ und die Regeln $S\to S_1 S$, $S\to \lambda$. Angenommen, wir wählen jedes Mal neue Nicht-Terminals.

Wie bei einer früheren Antwort gehe ich davon aus, dass Sie eine Grammatik erhalten möchten, die dieselbe Sprache wie der angegebene reguläre Ausdruck generiert $r$.

Ein rekursiver Algorithmus zum Erstellen einer kontextfreien Grammatik $G$ mit $L(G) = L(r)$ geht wie folgt:

• wenn $r = \emptyset$, geben Sie eine Grammatik ohne Produktionsregeln aus (oder $S \to S$ wenn es eine Regel haben muss).
• wenn $r = \Lambda$, Ausgabe $S \to \Lambda$.
• wenn $r = a$ (Der Ausdruck ist nur ein einzelner Buchstabe), Ausgabe $S \to a$.
• wenn $r = a \cup b$ (Vereinigung, auch als + oder | bezeichnet): Konstruieren Sie disjunkte Grammatiken für $a$ und $b$ mit Startsymbolen $S_a$ und $S_b$, kombiniere sie und füge hinzu $S \to S_a \mid S_b$.
• wenn $r = lr$ (Verkettung, auch notiert als $\cdot$): disjunkte Grammatiken konstruieren für $l$ und $r$ mit Startsymbolen $S_l$ und $S_r$, kombiniere sie und füge hinzu $S \to S_l S_r$.
• wenn $r = x^*$ (Kleene Stern): Konstruieren Sie eine Grammatik für $x$ mit Startsymbol $S_x$ und hinzufügen $S \to S_x S \mid \Lambda$.

Dies entspricht im Wesentlichen Hendriks Antwort, enthält jedoch weitere Einzelheiten, die nützlich sein können.