Algorytm do generowania gramatyki bezkontekstowej z dowolnego regexa

Question

Czy każdy może wyznaczyć dla mnie algorytm, który może przekonwertować dowolny dany regex na równoważny zestaw reguł CFG?

wiem, jak zmierzyć się z elementarnej rzeczy takie jak (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) 

jednak mam jakiś problem formalizujący go do właściwego algorytmu zwłaszcza w bardziej złożonych wyrażeń, które mogą mieć wiele operacji zagnieżdżonych.

Answer 1

Jeśli dopiero mówić o wyrażeniach regularnych z teoretycznego punktu widzenia, są te trzy konstrukcje:

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

Co można następnie po prostu zrobić:

• utworzyć regułę S -> (fullRegex)
• za każdy powtarzający się termin (x)* w fullRegex utwórz regułę X -> x X i X -> ε, a następnie zamień (x)* na X.
• dla każdego naprzemiennie (a|b|c) tworzyć reguły Y -> a, Y -> b i Y -> c, a następnie zastąpić (a|b|c) z Y

Wystarczy powtórzyć to rekurencyjnie (zauważ, że wszystkie x,a, b i c wciąż może być złożone wyrażenia regularne). Pamiętaj, że do każdego kroku musisz użyć unikalnych identyfikatorów.

To powinno wystarczyć. To z pewnością nie zapewni najbardziej eleganckiej i wydajnej gramatyki, ale na tym polega normalizacja (i powinno się to zrobić w oddzielnym kroku i do tego jest well-defined steps).

Jeden przykład: 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