Herhangi bir regex'ten bağlamdan bağımsız dilbilgisi oluşturmak için algoritma

Question

Herhangi biri, herhangi bir düzenli ifadeyi eşdeğer CFG kuralları kümesine dönüştürebilen bir algoritmayı özetleyebilir mi?

ben gibi temel şeyler mücadele bilen (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) 

Ancak, özellikle olabilir daha karmaşık ifadelerle uygun bir algoritma haline resmileştiren bazı sorun yaşıyorum iç içe geçmiş operasyonlar.

Answer 1

sadece bir görüş teorik açıdan normal ifadeler bahsediyoruz, bu üç yapılar vardır:

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

sonra sadece yapabileceği Ne:

• bir kural oluşturmak S -> (fullRegex)
• fullRegex'daki her tekrarlanan (x)* için X -> x X ve X -> ε kurallarını oluşturun ve (x)*'uile değiştirin. kuralları Y -> a, Y -> b ve Y -> c oluşturmak (a|b|c) her münavebe için
ardından Basitçe yinelemeli bu tekrarlamak Y

ile (a|b|c) yerine (bütün x,a, b ve c hala karmaşık normal ifadeler olabilir dikkat edin). Elbette her adım için benzersiz tanımlayıcılar kullanmanız gerektiğini unutmayın.

Bu yeterli olmalıdır. Bu kesinlikle en zarif veya verimli dilbilgisi vermeyecektir, ancak normalizasyonun ne olduğu (ve ayrı bir adımda yapılması ve bunu yapmak için well-defined steps olması gerekir) budur.

Bir örnek: 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