|
|
| 描述语言语法结构的形式规则称为文法。文法G是一个四元组，可表示为G=(VN,VT,P,S)，其中VT是一个非空有限集，其中的每个元素称为一个终结符；VN是一个非空有限集，其每个元素称为非终结符。VN∩VT=?。P是产生式的有限集合，每个产生式是形如α→β的规则，其中α称为产生式的左部，β称为产生式的右部。S∈VN，称为开始符号，它至少要在一条产生式中作为左部出现。
|
|
|
|
|
| 乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。
|
|
|
|
|
| （1）1型文法也称为上下文有关文法，这种文法意味着对非终结符的替换必须考虑上下文，并且一般不允许替换成ε串，此文法对应于线性有界自动机。
|
|
|
| （2）2型文法是上下文无关文法，对非终结符的替换无须考虑上下文，它对应于下推自动机。
|
|
|
| （3）3型文法等价于正规式，因此也称为正规文法或线性文法，它对应于有限状态自动机。
|
|
|
|
|
|
|
| （1）推导和直接推导。从文法的开始符号S出发，反复使用产生式，将产生式左部的非终结符替换为右部的文法符号序列，直至产生一个终结符的序列时为止。若有产生式α→β∈P，γ，δ∈V*，则γαδ?γβδ称为文法G中的一个直接推导。
|
|
|
（2）直接归约和归约。若文法G中有一个直接推导α?β，则称α是β的一个直接归约；若文法G中有一个推导 ，则称γ是δ的一个归约。
|
|
|
（3）句型和句子。若文法G的开始符号为S，那么，从开始符号S能推导出的符号串称为文法的一个句型，即α是文法G的一个句型，当且仅当有以下推导 ，α∈V*，若X是文法G的一个句型，且X∈V*T，则称X是文法G的一个句子。
|
|
|
| （4）语言。从文法G的开始符号出发，所能推导出的句子的全体称为文法G产生的语言，记为L(G)。
|
|
|
| （5）文法的等价。若文法G，与文法G2产生的语言相同，即L(G1)=L(G2)，则称这两个文法是等价的。
|
|
|
