短语结构语法的代数定义
作者 : 未知

  《现代语文》(语言研究版)2011年第4期发表的于红和戴卫平的文章《生成语法“生成”研究》一文中有一个原则性的错误,本文的目的在于纠正这个错误。
  为了纠正这个错误,我们有必要追述乔姆斯基对于短语结构语法的代数定义。
  乔姆斯基把短语结构语法(Phrase Structure Grammar,简称PSG)定义为一个四元组(quadruple) ,其中:
  (1)V是符号的有限集合;
  (2)Vt是V真子集合,叫做终结符号(terminal symbols);
  (3)S是V中除去Vt之外的符号集合中的一个特殊符号,叫做初始符号;
  (4)P是重写规则,形式为αβ,其中,α是 V+ 中的一个符号串,β是V*中的一个符号串。
  V+是V的正闭包(不包含空符号),而 V* 是V的Kleene 闭包(包含空符号)。
  短语结构语法的基本成分是V,Vt,P以及初始符号S。
  Vt中的终极符号就是语言中的单词。
  V中除去Vt之外的符号叫做变量,它们是非终极符号,也就是范畴符号,如词类符号、词组类型符号等等。
  我们使用希腊字母来表示V*中的符号序列,用大写拉丁字母来表示单个的变量,用小写的拉丁字母来表示单个的终极符号。
  语言的生成使用短语结构语法从初始符号来进行重写,在使用短语结构语法的规则进行重写时,用规则的右手边(right hand side,简称RHS)的符号序列来替换规则左手边(left hand side,简称LHS)的符号序列。例如,如果αβ是P中的一个重写规则,γ,δ是 V*中的序列,那么,
  γαδ→γβδ
  就意味着用序列γβδ来替换序列γαδ。换言之,如果把规则γαδ γβδ 使用于序列γαδ,那么,我们就可以得到一个新的序列 γβδ。
  乔姆斯基对于短语结构语法的重写规则α β给以程度不同的限制,得到如下不同类型的语法:
  ・0类语法(Type 0 grammar):对于短语结构规则没有任何限制。
  在0类语法中,规则的左手边和右手边可以是由终极符号或终极符号组成的任何的符号串,只要α是非空的符号串即可。例如:
  ABC → AB就是一个0类语法的规则。
  ・1类语法(Type 1 grammar):又叫做上下文有关语法(Context-sensitive grammar)。
  在1类语法中,规则的左手边和右手边可以是由终极符号或终极符号组成的任何的符号串,但是,右手边的符号串长度必须不小于左手边的符号串的长度。例如:
  ABC → ADEC就是一个1类语法的规则。
  ・2类语法(Type 2 grammar):又叫做上下文无关语法(Context-free grammar)。
  在2类语法中,规则的左手边只能包含一个单独的非终极符号,规则的右手边包含的符号串由V+中的符号组成。例如:
  A → BC,A → bBCc都是2类语法的规则。
  ・3类语法(Type 3 grammar):又叫做正则语法(Regular grammar)。
  在3类语法中,规则的左手边只包含一个单独的非终极符号,规则的右手边或者只包含一个终极符号,或者由一个非终极符号后面跟着一个终极符号组成。例如:
  A → b
  A → bC
  可以看出,从0类语法到3类语法,对于规则的限制越来越严格,编号大的语法要服从编号小的语法的一切限制。例如,3类语法规则A → bC,必须服从对于2类语法、1类语法和0类语法的规则的限制。
  另一方面,2类语法的规则A → BC,虽然不服从对于3类语法规则的限制,但是服从对于1类语法和0类语法的规则的限制。
  我们可以把不同类型的短语结构语言和短语结构语法对于规则的限制情况归纳如下:
  对于规则的限制 短语结构语法的类型 语言的类型
  3类 正则短语结构语法 正则语言
  2类 上下文无关语法 上下文无关语言
  1类 上下文有关语法 上下文有关语言
  0类 无限制的短语结构语法 递归可枚举语言
  这样,根据不同程度的规则限制,构成了短语结构语法的层级,这样的层级叫做乔姆斯基层级(Chomsky hierarchy)。
  《现代语文》(语言研究版)2011年第4期发表的于红和戴卫平的文章《生成语法“生成”研究》一文中在介绍0类语法(也就是0型语法)时,认为规则
  ab → ba是0类语法的规则,显然错了。
  实际上,ab→ba是一条典型的1类语法规则,这条规则是上下文有关的。理由如下:
  如果我们在ab中,以b为a的下文,可以把ab重写为cb,得到:
  ab → cb
  在cb中,以c为b的上文,可以把cb重写为cd,得到:
  cb → cd
  在cd中,以d为c的下文,可以把cd重写为bd,得到:
  cd → bd
  在bd中,以b为d的上文,可以把bd重写为ba,得到:
  bd → ba
  可以看出,abba这条规则,是一条上下文有关规则,绝对不是非上下文有关的0类语法的规则。
  所以,作者的这个例子是错误的。笔者建议,如果作者想举出一条0类语法的规则,可以举如下的规则:
  ab → a
  在这条规则中,右手边的符号串a的长度(a是只包含一个符号的符号串)小于左手边的符号串ab的长度,不能满足1类语法“右手边的符号串长度必须不小于左手边的符号串的长度”的要求,因此,这条规则是一条典型的0类语法的规则。
  
  
  
  (冯志伟 北京 教育部语言文字应用研究所 100010)

文秘写作 期刊发表