编译原理：结合例题彻底理解文法四元式与正则文法

小鱼儿 2022-12-08 05:07 160阅读 0赞

这篇博客起源于一道很有趣的**正则文法**的题目。题目描述如下：

> 已知L=\{x|x∈\{0,1\}\+，且x中含有1011子串\}。  
> 构造接收语言L的正则文法。

什么是正则文法呢？首先需要了解什么是文法。我们知道，编译原理中的文法G是一个四元式：

> G = \{Vt,Vn,S,P\}

1.  Vt是一个非空有限集，它的每个元素为终结符号。也就是说**Vt是由文法中的终结符构成的集合**。
2.  Vn是一个非空有限集，它的每个元素称为非终结符号。也就是说**Vn是由文法中的非终结符构成的集合**。由于一个符号要么是终结符、要么是非终结符，因此Vt和Vn的交集为空。
3.  S是一个非终结符号，称为开始符号。S必须在某个产生式的左部出现一次。
4.  P是有限个产生式的集合，每个产生式形如：P->a。

在题目中，L=\{x|x∈\{0,1\}\+，且x中含有1011子串\}，也就是指**由0与1组成、包括1011子串**的串。一个可行的文法如下：

> G=\{Vt,Vn,S,P\}  
> Vt=\{0,1,ε\}  
> Vn=\{S,S1\}  
> P=\{S -> S11011S1  
> S1 \-> 0S1 | 1S1 | ε \}

也就是令子串1011前与后均为任意个0与1即可。比如01**1011**11。

那么什么是正则文法呢？正则文法相当于在文法的基础上进行了进一步的限制，本质上还是文法，只是它规定了文法的书写格式。正则文法，又称为3型文法，它规定：\*\*一个产生式的结果要么是一个终结符，要么是一个终结符加上一个非终结符。\*\*也就是说产生式的形式必须是：

> Si→ωSj 或 Si→ω

其中ω代表任意一个非终结符号，S代表任意一个终结符号。因为ε也是非终结符，所以自然也可以出现Si\->ε这种形式。

可以看出，正则文法实质上是要求在设计文法时，  
要**一个一个字符、一个一个状态地去考虑**。什么意思呢？我们先写出L的正则文法：

> G=\{Vt,Vn,S,P\}  
> Vt=\{0,1,ε\}  
> Vn=\{S,S1,S2,S3,S4\}  
> P=\{S -> 1S1 | 0S  
> S1 \-> 0S2 | 1S1  
> S2 \-> 1S3 | 0S  
> S3 \-> 1S4 | 0S2  
> S4 \-> 0S4 | 1S4 | ε \}

我们需要得到包含1011的串，所以我们一个一个字符地去匹配。首先需要匹配一个1，然后需要是一个0，然后再一个1，最后再一个1。如果中途有一步匹配失败，那么需要返回到前面的状态再继续匹配。所以我们可以抽象出这样几个状态：

*  S：无匹配，期待下一个字符是1
 *  S1：匹配到了1011中的1，期待下一个字符是0
 *  S2：匹配到了1011中的10，期待下一个字符是1
 *  S3：匹配到了1011中的101，期待下一个字符是1
 *  S4：匹配到了1011中的1011

所以说**正则文法其实是从状态的角度去考虑问题**。比如S1期待得到一个0，从而转换为S2，那么如果得到一个1，就会回到状态S1。S3已经匹配了101，期待得到一个1，从而转换为S4，那么如果得到一个0，其实就会得到1010，所以10是成功匹配的，因此回到状态S2。

感兴趣的读者可以自行画一下上述文法的DFA。