Algoritmo per generare una grammatica senza contesto da qualsiasi regex

Question

Qualcuno può delineare per me un algoritmo in grado di convertire qualsiasi regex in un insieme equivalente di regole CFG?

so come affrontare le cose elementari, come (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) 

Tuttavia, sto avendo qualche problema di formalizzare in un apposito algoritmo in particolare con le espressioni più complesse che possono avere molte operazioni annidate.

Answer 1

Se sono solo parlando di espressioni regolari da un punto di vista teorico, ci sono queste tre costrutti:

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

Che cosa si potrebbe poi basta fare:

• creare una regola S -> (fullRegex)
• per ogni termine ripetuto (x)* in fullRegex creare una regola X -> x X e X -> ε, quindi sostituire (x)* con X.
• per ogni alternanza (a|b|c) creare regole Y -> a, Y -> b e Y -> c, quindi sostituire (a|b|c) con Y

sufficiente ripetere questo modo ricorsivo (si noti che tutto x,a, b e c può ancora essere complesse espressioni regolari). Si noti che ovviamente è necessario utilizzare identificatori univoci per ogni passaggio.

Questo dovrebbe essere sufficiente. Questo certamente non darà la grammatica più elegante o efficiente, ma è a questo che serve la normalizzazione (e dovrebbe essere fatto in un passaggio separato e ci sono well-defined steps per farlo).

Un esempio: 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