查看“︁前缀文法”︁的源代码

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

==形式定义==

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

==例子==

一个简单的例子前缀文法可以定义为
*&Sigma; = {0, 1}
*''S'' = {01, 10}
*''P'' = {0 &rarr; 010, 10 &rarr; 100}
它描述如下[[正则表达式]]所定义的语言
:<math> 01(01)^* \cup 100^* </math>

==性质==
前缀文法生成[[字符串运算#前缀|前缀闭合]]的语言。

==参见==
* [[正则文法]]

[[Category:形式语言|Q]]