Algorithmus zur Generierung kontextfreier Grammatik aus beliebigen Regex

Question

Kann mir jemand einen Algorithmus skizzieren, der eine gegebene Regex in eine äquivalente Menge von CFG-Regeln umwandeln kann?

Ich weiß, wie die elementaren Dinge in Angriff zu nehmen, wie (a | b) *:

S -> a A 
S -> a B 
S -> b A 
S -> b B 
A -> a A 
A -> a B 
A -> epsilon 
B -> b A 
B -> b B 
B -> epsilon 
S -> epsilon (end of string) 

Aber ich habe einig Problem, das es in einen geeigneten Algorithmus vor allem bei komplexeren Ausdrücken Formalisierung, die haben viele verschachtelte Operationen.

Answer 1

Wenn Sie nur über reguläre Ausdrücke aus theoretischer Sicht sprechen, gibt es diese drei Konstrukte:

ab  # concatenation 
a|b  # alternation 
a*  # repetition or Kleene closure 

Was Sie könnten dann nur tun:

• erstellen Sie eine Regel S -> (fullRegex)
• für jede wiederholte Amtszeit (x)* in fullRegex erstellen Sie eine Regel X -> x X und X -> ε, ersetzen Sie dann (x)* durch X.
• für jeden Wechsel (a|b|c)Y -> a, Y -> b und Y -> c Regeln erstellen, dann ersetzen (a|b|c) mit Y

Ganz einfach rekursiv wiederholen (beachten Sie, dass alle x,a, b und c noch komplexer regulärer Ausdrücke sein können). Beachten Sie, dass Sie für jeden Schritt natürlich eindeutige Bezeichner verwenden müssen.

Das sollte genug sein. Dies wird sicherlich nicht die eleganteste oder effizienteste Grammatik ergeben, aber dafür ist die Normalisierung gedacht (und es sollte in einem separaten Schritt geschehen, und dazu gibt es well-defined steps).

Ein Beispiel: a(b|cd*(e|f)*)*

S -> a(b|cd*(e|f)*)* 

S -> a X1; X1 -> (b|cd*(e|f)*) X1; X1 -> ε 

S -> a X1; X1 -> Y1 X1; X1 -> ε; Y1 -> b; Y1 -> cd*(e|f)* 

S -> a X1; X1 -> Y1 X1; X1 -> ε; Y1 -> b; Y1 -> c X2 (e|f)*; X2 -> d X2; X2 -> ε 

... and a few more of those steps, until you end up with: 

S -> a X1 
X1 -> Y1 X1 
X1 -> ε 
Y1 -> b 
Y1 -> c X2 X3 
X2 -> d X2 
X2 -> ε 
X3 -> Y2 X3 
X3 -> ε 
Y2 -> e 
Y2 -> f