短语结构文法

短语结构文法 phrase structure grammar 以结构语言学的直接成分分析法为基础对语言进行定义,从而给予语言中的句子以有用结构的数学系统,又称∑，F文法或乔姆斯基文法，是1957年美国语言学家N.乔姆斯基创立的语言转换生成理论的一部分。

集合

两种符号

分类

程序文法

集合

为了从数学上进行分析，可以把一种语言看成是由有限个字母按照一定的文法规则从左到右线性排列组成的链的集合。这有限个字母组成字母表∑。由∑中的符号（字母）可能形成的所有的链的集合(包括长度为0的链)用∑*表示。既然一种语言是由一定的文法所产生,它只能是∑*的一个子集。考察英文句子“The girl walksgracefully“，从句法上分析,可以看成由下列步骤所形成：

〈句子〉─→〈名词短语〉〈动词短语〉─→〈冠词〉〈名词〉〈动词短语〉─→ The〈名词〉〈动词短语〉─→The girl〈动词短语〉─→The girl〈动词〉<副词>─→The girl walks<副词>─→The girl walksgracefully 其中“─→”的意思是“能够重写”，即用“─→”右边的符号代替“─→”左边的符号。从符号〈句子〉出发，使用一系列重写规则可得到所需要的句子。对于上面的例子，重写规则是

〈句子〉─→〈名词短语〉〈动词短语〉

〈名词短语〉─→〈冠词〉〈名词〉

〈动词短语〉─→〈动词〉〈副词〉

〈冠词〉─→The

〈名词〉─→girl

〈动词〉─→walks

〈副词〉─→gracefully

两种符号

这里用了两种不同性质的符号，带有〈〉的符号在最后的句子中并不出现，因此它们所组成的集合称为非终止符集N，N＝｛〈句子〉,〈名词短语〉,〈冠词〉,〈名词〉，〈动词〉，〈副词〉｝，而在最后句子中出现的符号组成的集合称为终止符集,亦即字母表∑，∑={The,girl,walks,gracefully}。非终止符集中的〈句子〉在导出整个句子的过程中有特殊的意义,称为起始符S。因此产生一种语言的文法G可以用四元组表示，即G={∑，N，P，S}，其中P 是形式为α ─→β的重写规则或称产生式规则的集合。产生式规则中的α 和β是由非终止符和终止符所组成的链，但α 中至少包含N 中的一个符号。

分类

按照产生式α─→β的不同形式,可把文法分成四种类型。产生式的两端无任何限制的为0型文法，产生0型语言或称递归可数语言。在产生式两端加上一些限制，又可分为三类文法：①上下文敏感文法(1型)α1Aα2─→α1βα2，只有当非终止符A的前后为α1、α2的条件下,A才可以改写成β。②上下文无关文法（2型）,产生式的形式是 A─→β,左端为一个非终止符,右端没有限制。前面所述七条产生式规则就是这种文法的例子。上下文无关文法通过导出树产生句子。产生“The　girl walks gracefully”的导出树（见图）。③有限状态文法或正则文法（3型）,产生式规则为A─→ɑB和A─→a两种形式。其中A,B为非终止符,a是终止符。从0型文法到3型文法，在产生式规则上的限制形式是逐步增加的，所以它们所对应的语言有包含关系,即0型文法所产生的递归可数集真包含上下文敏感语言，上下文敏感语言真包含除了空链以外的上下文无关语言,上下文无关语言真包含3型文法产生的正则集。这四种类型的文法所产生的语言可被相应的自动机所接受（见语言识别器）。

程序文法

此外为了增加上下文无关文法的描述能力而又避免在用上下文敏感文法时所存在的分析上的困难，又提出上下文无关文法的改型文法──上下文无关程序文法和上下文无关附标文法。程序文法的特点是在导出过程中对中间链用了一个产生式后，下一次再用哪一条产生式要受到限制，因此每个产生式都有一个标号，一个作为核心的重写规则以及称为成功区和失败区的两个标号集合。假使在导出过程中使用某条产生式成功，就要从该产生式的成功区中去找使用下一条产生式的标号，如果该产生式不能用于该链，就要从它的失败区中去找下一个产生式的标号。这种上下文无关程序语言是上下文敏感语言的真子集，且真包含上下文无关语言。附标文法是通过引入附标产生式的有限集来扩大上下文无关文法的描述能力的。附标文法所对应的语言真包含上下文无关语言而且是上下文敏感语言的一个真子集。

把模式的产生和描述与语言的产生和描述加以比较，借鉴语言的句法结构对模式进行处理和识别，从而在短语结构文法的基础上，便发展形成模式识别的一个重要分支──句法模式识别（见结构模式识别）。