将正则表达式转换为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 

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

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

Answer 2

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

其中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?，简单地把它分成一个产生空的规则和一个产生x的规则。

Answer 3

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

当然，你可以构造一个给定的正则表达式的CFG。以上答案显示了一些实现此目的的方法。

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