从任何正则表达式生成上下文无关语法的算法

Question

任何人都可以为我概述一个算法,可以将任何给定的正则表达式转换为一组等效的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)

但是,我遇到了一些问题,将其形式化为适当的算法,特别是对于可以具有许多嵌套操作的更复杂的表达式.

Answer 1

如果您只是从理论的角度讨论正则表达式,那么有以下三种结构:

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

那么你可以做什么:

• 制定规则 S -> (fullRegex)
• 每一个重复项(x)*中fullRegex创建一个规则X -> x X和X -> ?,然后替换(x)*用X.
• 每一个交替(a|b|c)创建规则Y -> a,Y -> b并且Y -> c,然后替换(a|b|c)用Y

简单地重复这个(注意所有x, a,b并且c仍然可以是复杂的正则表达式).请注意,您当然必须为每个步骤使用唯一标识符.

这应该足够了.这肯定不会给出最优雅或最有效的语法,但这就是规范化的目的(它应该在一个单独的步骤中完成,并且有明确定义的步骤来执行此操作).

一个例子: 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