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

发布时间：2020-12-14 02:30:04 所属栏目：百科来源：网络整理

导读：任何人都可以为我概述一个算法,可以将任何给定的正则表达式转换为一组等效的CFG规则吗？我知道如何处理基本的东西,如(a | b)*： S - a AS - a BS - b AS - b BA - a AA - a BA - epsilonB - b AB - b BB - epsilonS - epsilon (end of string) 但是,我遇到

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

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

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

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

那么你可以做什么：

>创建规则S – > (fullRegex)
>对于fullRegex中的每个重复项(x)*,创建规则X – > x X和X – > ε,然后用X替换(x)*.
>对于每次交替(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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!