链语法介绍链语法介绍常宝宝，1999年4月25日1.形式语法系统的分类TGGBCategory-basedFormalgrammaticalsystem(GrammarFormalism)Word-basedTAGUnification-basedGPSGHPSGFUGLFG……WordGrammarDependencyGrammarCategorialGrammarLinkGrammar(1)关于category-basedGrammar在Catrgory-based类的语法系统中都使用(1)类(Category);和(2)成分(Constituent)两个概念描述语言现象。从TG到Unification-based语法系统，带来了两个特别是对计算语言学颇有吸引力的好处。(1)取消了转换规则；(2)引入了复杂特征集和合一运算。这些形式语法系统的基础都是上下文无关语法，从这些形式语法系统的发展可以看出，人们尽力在力图设法避免这个不稳定的根基带来的局限性，而使得形式语法系统能够处理上下文敏感(context-sensitive)的语言现象。(2)关于Word-basedGrammar反映了语法理论的词汇主义倾向，在词汇主义理论中，关于语言的所有知识都记录在词典中。在这些体系中，没有明显的语法规则，而代之以元规则(Meta-rule)。2.链语法的提出由CMU计算机学院的DanielSleator、ColumbiaUniversity音乐系的DavyTemperley共同提出，最早的文章发表于1991年，题目是“ParsingEnglishwithaLinkGrammar”。1链语法介绍目前基于LinkGrammar研究并不很常见。2.链语法的形式定义和基本概念(1)形式语法系统G必须回答的问题G所定义的语言是什么？什么样的符号串是G所定义的语言L(G)中的合法句子?形式语法系统怎样生成自然语言中合法的句子？怎样排除掉不合法的句子。链语法对这些问题同样要做出回答。(2)一部链语法(LinkGrammar)就是一个单词的集合，其中的每个单词后面记录着各自的链接要求(Linkingrequirement)。下面我们会进一步谈到，这些链接要求可以通过一系列链接子表达式(formulaofconnectors)指定。(3)怎样判定一个单词串是否链语法所定义的语言中的句子？一个由单词组成的串(wordsequence)，如果在单词之间存在满足下列条件的链(link)的话，(或者说，能够在单词之间画出一些链，并且这些链满足下面的条件)，就说，这个单词串是链语法所定义的语言中的句子(sentence)。首先这些链满足了其中所有单词的链接要求，其次满足下面4条元规则。?平面性(Planarity)，这些链之间互相不交叉(donotcross)。?连通性(Connectivity)，这些链足以把所有的单词链在一起。?顺序性(Ordering)，公式中较左边的链接子必须和距离单词较近的单词链接，反之，公式中较右边的链接子必须和距离单词较远的单词链接。?排它性(Exclusion)，一对单词之间同时不能有两条链链接。下面给出一部含有7个单词的链语法，对上面的一些概念进行解释。wordsathesnakecatchasedranMaryformulaD+D-&(O-orS+)S-&O+SO-orS+简单的链接表达式由链接子(connector)、二元操作符&和or以及圆括号组成。每个链接子(connector)由名字(name)和后缀(suffix)两部分组成。后缀有两个，分别是+和-。+和-表示链接的方向，+表示向右面链接，-表示向左面链接。2链语法介绍单词串中某个单词如果有一个向右的链接子，例如X+，而另一个单词有一个向左的链接子X-，那么这两个链接子相互匹配(match)，(这里暂把匹配的含义定义为两个链接子的名字相同，)这两个单词之间可以画一条X链。同时我们可以说，链接子X+或X-得到了满足(Satisfication)或说链接满足了链接子X+或X-。在链接子被满足的基础上，可以定义公式的满足。公式X&Y要被满足，则链接必须同时满足链接子X和Y。公式XorY要被满足，则链接必须满足链接子X和Y中的一个。接下来我们看看下面两个单词串是否为上述语法定义的语言中的合法句子。(1)thecatchasedasnake.(2)*theMarychasedcat.首先看单词the的链接表达式，其中只有一个向右的链接子D+，再看单词cat的链接表达式D-&(O-orS+)，其中有一个D-，可以和单词the的D-匹配，在它们之间可以画一条D链，单词the的链接要求得到