Regulärer Ausdruck für kontextfreie Grammatik

7

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

Marco L.
quelle
5
Möchten Sie die CFG, die die gültigen Zeichenfolgen für reguläre Ausdrücke wie "a * (a | b)" generiert, oder möchten Sie die CFG, die Zeichenfolgen wie "aaaaab" für den regulären Ausdruck "a * (a | b)" generiert?
Alex Ten Brink

Antworten:

9

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.

Raphael
quelle
Ja, besser als meine Antwort.
Hendrik
4

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. WennS1 und S2 sind Nicht-Terminals, die Ausdrücke erzeugen E1 und E2 dann können wir erzeugen E1+E2 durch S und die Regeln SS1, SS2. Wir können Verkettung erzeugenE1E2 durch S und die Regel SS1S2. E1 durch S und die Regeln SS1S, Sλ. Angenommen, wir wählen jedes Mal neue Nicht-Terminals.

Hendrik Jan.
quelle
1

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=, geben Sie eine Grammatik ohne Produktionsregeln aus (oder SS wenn es eine Regel haben muss).
  • wenn r=Λ, Ausgabe SΛ.
  • wenn r=a (Der Ausdruck ist nur ein einzelner Buchstabe), Ausgabe Sa.
  • wenn r=ab (Vereinigung, auch als + oder | bezeichnet): Konstruieren Sie disjunkte Grammatiken für a und b mit Startsymbolen Sa und Sb, kombiniere sie und füge hinzu SSaSb.
  • wenn r=lr (Verkettung, auch notiert als ): disjunkte Grammatiken konstruieren für l und r mit Startsymbolen Sl und Sr, kombiniere sie und füge hinzu SSlSr.
  • wenn r=x (Kleene Stern): Konstruieren Sie eine Grammatik für x mit Startsymbol Sx und hinzufügen SSxSΛ.

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

Jonas Kölker
quelle