前缀文法

在计算机科学中，前缀文法是类似形式文法的一种文法，这里的字符串是从基础字符串通过不断的替代前缀建造出来的。前缀文法精确的描述了所有正则语言。

形式定义
前缀文法 G 是3-元组 (Σ, S, P)，这里的
*Σ 是有限字母表
*S 是在 Σ 上的基础字符串的有限集合
*P 是形如 u → v 的产生规则的集合，u 和 v 是 Σ 上的字符串
每个产生式 u → v 只可以应用于形如 uw 的字符串。

例子
一个简单的例子前缀文法可以定义为
*Σ = {0, 1}
*S = {01, 10}
*P = {0 → 010, 10 → 100}
它描述如下正则表达式所定义的语言
: 01(01)^ \cup 100^

性质
前缀文法生成前缀闭合的语言。

参见

• 正则文法