正则文法

在计算机科学中，正则文法是产生式规则取下述形式的一种形式文法（N, Σ, P, S）：
 A -> a  ，此处的A是N中的非终结符号，a是Σ中的终结符号；
 A -> aB，此处的A和B是N中的非终结符号，a是Σ中的终结符号；
 C -> ε，此处的C是N中的非终结符号。

下面给出一个正则文法的例子：
文法G = (N, Σ, P, S)，其中N = {S, A}，Σ = {a, b, c}，S是起始符号，P包含下述规则：
S -> aS
S -> bA
A -> ε
A -> cA

这个文法描述的语言也可以用正则表达式a*bc* 来表达。

正则文法描述的语言构成了正则语言类，正则语言类中的语言也可以由有限状态自动机或正则表达式来表达。

相关条目
 乔姆斯基谱系
 正则语言
 正则表达式
 有限状态自动机

Category:编译原理
Z