regex - 将正则表达式转换为 CFG

Question

如何将一些常规语言转换为其等效的上下文无关语法？是否有必要构造对应于该正则表达式的 DFA 或者是否有一些规则可以进行这种转换？

例如，考虑以下正则表达式

01+10(11) ^*

如何描述上述RE对应的语法？

Answer 1

• 把A+B改成语法

  G -> A
  G -> B
  

• 将 A* 更改为

  G -> (empty)
  G -> A G
  

• 将 AB 更改为

  G -> AB
  

并在 A 和 B 上递归进行。基本情况是空语言（没有产生式）和单个符号。

在你的情况下

 A -> 01
 A -> 10B
 B -> (empty)
 B -> 11B

如果语言由有限自动机描述：

• 使用状态作为非终结符号
• 使用语言作为终端符号集
• 在原始自动机中的字母 a 上为任何转换 p -> q 添加转换 p -> aq
• 在语法中使用初始状态作为初始符号

Answer 2

我猜您的意思是将其转换为具有 V->w 形式规则的正式语法，其中 V 是非终结符，w 是一串终结符/非终结符。首先，您可以简单地说（混合 CFG 和正则表达式语法）：

S -> 01+10(11)*

其中 S 是开始符号。现在让我们把它分解一下（为了清楚起见，添加空格）：

S -> 0 A 1 0 B
A -> 1+
B -> (11)*

关键是将*es和+es转换为递归。首先，我们将通过插入一个接受空字符串的中间规则将 Kleene 星号转换为加号：

S -> 0 A 1 0 B
A -> 1+
B -> (empty)
B -> C
C -> (11)+

最后，我们将+符号转换为递归：

S -> 0 A 1 0 B
A -> 1
A -> A 1
B -> (empty)
B -> C
C -> 11
C -> C 11

要处理x?，只需将其拆分为产生 empty 的规则和产生 x 的规则。

Answer 3

实际上，不同的 CFG 语法可以产生相同的语言。所以给定一个正则表达式（正则语言），它映射回一个 CFG 不是唯一的。

当然，您可以构造一个产生给定正则表达式的 CFG。上面的答案显示了一些实现这一目标的方法。

希望这能给你一个高层次的想法。