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

形式定义

前缀文法G是3-元组

，这里的

• Σ 是有限字母表

• S是在 Σ 上的基础字符串的有限集合

• P是形如

的产生规则的集合，u和v是 Σ 上的字符串

每个产生式

只可以应用于形如

的字符串。

例子

一个简单的例子前缀文法可以定义为

•

• 

• 

它描述如下正则表达式所定义的语言

性质

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

正则语言

正则语言

又称 正规语言是满足下述相互等价的一组条件的一类形式语言：

• 可以被确定有限状态自动机识别；

• 可以被非确定有限状态自动机识别；

• 可以被只读图灵机识别；

• 可以用正则表达式描述；

• 可以用正则文法生成。

• 可以用前缀文法生成。