正则语法

在理论计算机科学和形式语言理论中，正则语法是一种右正则或左正则的语法。虽然它们的确切定义因教科书而异，但它们都要求所有的生成规则最多只有一个非终端符号；这个符号要么总是在规则的右边的末尾，要么总是在规则的开头。每个规则语法都描述一种规则语言。

右正则语法（也叫右线性语法）是一个形式化的语法（N，Σ，P，S），其中P中的所有生产规则都是以下形式之一。A→aA→aBA→ε其中A、B、S∈N为非终端符号，a∈Σ为终端符号，ε表示空字符串，即长度为0的字符串，S称为起始符号。在左规则语法（也叫左线性语法）中，所有的规则都服从于以下形式A→aA→BaA→ε一个给定的语法所描述的语言是所有字符串的集合，这些字符串只包含终端符号，并且可以通过重复应用生产规则从起始符号衍生出来。这两种规则不能混用，例如，规则集为{S→aT,T→Sb,S→ε}的语法是没有规则的，它描述的语言{aibi:i∈N{displaystyle/mathbb{N}.}}，这也是不规则的。一些教科书和文章不允许空的生产规则，并假定语言中不存在空字符串。

一个扩展的右正则语法是指所有的规则都服从于以下的一个规则A→w，其中A是N中的一个非终端，w在一个（可能是空的）终端字符串中Σ*A→wB，其中A和B在N中，w在Σ*中。一些作者把这种类型的语法称为右规则语法（或右线语法），上面的类型称为严格右规则语法（或严格右线语法）。一个扩展的左规则语法是指所有规则都服从下列规则之一的语法A→w，其中A是N中的一个非终端，w在Σ*中A→Bw，其中A和B在N中，w在Σ*中。例子一个右规则语法G的例子，N={S，A}，Σ={a，b，c}，P由以下规则组成S→aSS→bAA→εA→cA而S是起始符号。这个语法描述了与正则表达式a*bc*相同的语言，即由任意多的as组成的所有字符串的集合，后面是一个b，后面是任意多的cs。对于同一正则表达式，一个稍长但更明确的扩展右正则语法G由N={S,A,B,C},Σ={a,b,c}给出，其中P由以下规则组成。S→AA→aAA→BB→bCC→εC→cC...其中每个大写字母对应于正则表达式中下一个位置开始的短语。作为编程语言领域的一个例子，表示浮点数的所有字符串的集合可以用一个扩展的右规则语法G来描述，N={S,A,B,C,D,E,F},Σ={0,1,2,3,4,5,6,7,8,9,+,-,.,e},其中S是起始符号，P由以下规则组成。表达能力在（严格的）右规则语法的规则和非确定性有限自动机的规则之间有一个直接的一对一的对应关系，这样的语法正好产生自动机接受的语言。因此，右正则语法正好生成所有正则语言。

左规则语法描述了所有这类语言的反面，也就是说，也正好是规则语言。每个严格的右正则语法都是扩展的右正则语法，而每个扩展的右正则语法都可以通过插入新的非端点而变得严格，从而产生相同的语言；因此，扩展的右正则语法也产生常规语言。类似地，扩展的左规则语法也是如此。如果不允许有空的生成，那么只有不包括空字符串的所有规则语言才能被生成。虽然正则语法只能描述正则语言，但反之亦然：正则语言也能被非正则语法所描述。

如果允许混合左规则和右规则，我们仍然有一个线性语法，但不一定是一个规则语法。更重要的是，这样的语法不需要生成规则语言：所有的线性语法都可以很容易地变成这种形式，因此，这种语法正好可以生成所有线性语言，包括非规则语言。例如，语法G有N={S，A}，Σ={a，b}，P有起始符号S和规则{displaystyle{a{i}b{i}:igeq0}}，典型的非规则线性语言。，是典型的非规则线性语言。