5

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

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

4

1 回答 1

12

如果您只是从理论角度谈论正则表达式，则有以下三种构造：

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

只需递归地重复此操作（注意 allx, 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
于 2012-10-30T13:38:36.527 回答