算法從任何正則表達式生成上下文無關語法

任何人都可以爲我概述一種算法，可以將任何給定的正則表達式轉換爲CFG規則的等效集合嗎？算法從任何正則表達式生成上下文無關語法

我知道如何解決這個基本的東西，如（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)

不過，我有一些問題，正式入適當的算法，尤其是更復雜的表達式，可以有許多嵌套操作。

來源

2012-10-30 gamerx

我希望你是在開玩笑，當你問我們的算法整體概況。正如你可能已經注意到這將是很多工作。如果您對特定問題有任何疑問，請隨時提問，但不要求我們爲您設計實際的代碼。 – Jasper

你的cfg不應該是'S - > a S; S - > b S; S - > epsilon'？我認爲你提供的cfg唯一的字符串是「」，因爲它接受的其他字符串是有限的。 – Wug

這也取決於你想允許哪個正則表達式語法元素？只有理論意義上的正則表達式？或者在大多數引擎中使用它的擴展意義上的正則表達式？ –

如果你只是從理論角度講正則表達式，有這三種結構：

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

，那麼你可以只是做什麼：

創建規則S -> (fullRegex)
對於每個重複項(x)*在fullRegex創建規則X -> x X和X -> ε，然後用0123代替。
每一個交替(a|b|c)創建規則Y -> a，Y -> b和Y -> c，然後用Y

更換(a|b|c)簡單的遞歸重複此（注意，所有x,a，b和c仍然可以是複雜的正則表達式）。請注意，當然你必須爲每一步使用唯一的標識符。

這應該夠了。這肯定不會給出最優雅或有效的語法，但這就是正常化的原因（並且它應該在一個單獨的步驟中完成，並且有well-defined steps這樣做）。

一個例子：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

來源

2012-10-30 13:38:36

算法從任何正則表達式生成上下文無關語法

回答

相關問題