1
常宝宝，1999年4月25日
1. 形式语法系统的分类
(1)关于category-based Grammar
在Catrgory-based 类的语法系统中都使用(1)类(Category)；和(2)成分(Constituent)两个概念描述语言现象。
从TG 到Unification-based 语法系统，带来了两个特别是对计算语言学颇有吸引力的好处。(1)取消了转换规则；(2)引入了复杂特征集和合一运算。
这些形式语法系统的基础都是上下文无关语法，从这些形式语法系统的发展可以看出，人们尽力在力图
设法避免这个不稳定的根基带来的局限性，而使得形式语法系统能够处理上下文敏感(context-sensitive)的语言现象。
(2) 关于Word-based Grammar
反映了语法理论的词汇主义倾向，在词汇主义理论中，关于语言的所有知识都记录在词典中。在这些体系中，没有明显的语法规则，而代之以元规则(Meta-rule)。
2. 链语法的提出
由CMU 计算机学院的Daniel Sleator 、Columbia University 音乐系的Davy Temperley 共同提出，最早的文章发表于1991年，题目是“Parsing English with a Link Grammar ”。
Formal grammatical system
(Grammar Formalism)
Category-based
TG GB
Unification-based Word-based Word Grammar Dependency Grammar
Categorial Grammar
Link Grammar
TAG GPSG HPSG FUG LFG ……
目前基于Link Grammar研究并不很常见。
2.链语法的形式定义和基本概念
(1)形式语法系统G必须回答的问题
G所定义的语言是什么？什么样的符号串是G所定义的语言L(G)中的合法句子?形式语法系统怎样生成自然语言中合法的句子？怎样排除掉不合法的句子。链语法对这些问题同样要做出回答。
(2)一部链语法(Link Grammar)就是一个单词的集合，其中的每个单词后面记录 着各自的链接要求(Linking requirement)。下面我们会进一步谈到，这些链接要求可以通过一系列链接子表达式(formula of connectors)指定。 (3)怎样判定一个单词串是否链语法所定义的语言中的句子？
一个由单词组成的串(word sequence)，如果在单词之间存在满足下列条件的链(link)的话，(或者说，能够在单词之间画出一些链，并且这些链满足下面的条件)，就说，这个单词串是链语法所定义的语言中的句子(sentence)。 首先这些链满足了其中所有单词的链接要求，其次满足下面4条元规则。
平面性(Planarity)，这些链之间互相不交叉(do not cross)。
何小伟连通性(Connectivity)，这些链足以把所有的单词链在一起。
顺序性(Ordering)，公式中较左边的链接子必须和距离单词较近的单词链接，反之，公式中较右边的链接子必须和距离单词较远的单词链接。
排它性(Exclusion)，一对单词之间同时不能有两条链链接。
下面给出一部含有7个单词的链语法，对上面的一些概念进行解释。
简单的链接表达式由链接子(connector)、二元操作符&和or以及圆括号组成。
每个链接子(connector)由名字(name)和后缀(suffix)两部分组成。后缀有两个，分别是+和-。+和-表示链接的方向，+表示向右面链接，-表示向左面链接。
2
单词串中某个单词如果有一个向右的链接子，例如X+，而另一个单词有一个向左的链接子X-，那么这两个链接子相互匹配(match)，(这里暂把匹配的含义定义为两个链接子的名字相同，)这两个单词之间可以画一条X链。同时我们可以说，链接子X+或X-得到了满足(Satisfication)或说链接满足了链接子X+或X-。
在链接子被满足的基础上，可以定义公式的满足。
公式X & Y要被满足，则链接必须同时满足链接子X和Y。
公式X or Y要被满足，则链接必须满足链接子X和Y中的一个。
接下来我们看看下面两个单词串是否为上述语法定义的语言中的合法句子。
(1) the cat chased a snake.
(2) *the Mary chased cat.
首先看单词the 的链接表达式，其中只有一个向右的链接子D+，再看单词cat的链接表达式D- & ( O- or S+)，其中有一个D-，可以和单词the的D-匹配，在它们之间可以画一条D链，单词the 的链接要求得到满足。但单词cat的链接表达式尚未完全得到满足，要使cat的链接表达式完全得到满足，链接子O-和S+必须有一个得到满足。再看chased的链接表达式S- & O+。可以在cat 和chased 之间画一条S链，同样的道理，在chased和snake之间也可以画一条O 链，在单词a和snake 之间画一条D链，到此为止，词串中所有单词的链接要求都得到了满足，并且得到下面的一个图。
进而检查这这种链接方法是否满足4条元规则，首先满足平面性，4条链互不交叉。连通性也满足，四条链把词串中所有5个单词都链在一起。顺序性，可以看单词snake，在snake的链接表达式中，D-靠左，所以链接和它距离较近的单词a，O-链靠右，链接和它距离较远的单词chased。最后，排它性也得到满足，所有的单词对之间都只有一条链链接。所以，现在可以说，单词串(1)是语法所定义的语言中的合法句子。
链语法把这样一组可以证明一个单词串是链语法所定义语言中的合法句子
3
4 的链的集合叫做一个链接集(Linkage)，链接集是用链语法分析句子所得到的结果，正如一般句法分析中所得到的句法树一样。
钼粉按照同样的原则，对于词串(2)，我们可以画出下面的链接图。
the
Mary chased cat
同样所有单词的链接要求都得到了满足。仔细检查，顺序性未得到满足，单词cat 的链接表达式D- & ( O- or S+)，D-链靠左面，却链接了一个较远的单词the 。因此，词串(2)不是上面的链语法定义的句子。
现在，再来看一下这些链的具体含义：
除用链接子的表达式表示外，链接要求还可以用disjunct 范式(disjunct form)来表示。用表达式描述链接要求对于建立自然语言语法很方便，但对于分析链语法和描述分析算法则显得很不方便。
如果用disjunct 范式来描述链接要求，每个单词后面的链接要求是由一系列disjunct 组成。一个disjunc
t 由两个有序表组成，左表(left list)和右表(right list)。左表由所有向左的链接子组成(即那些后缀是-的链接子)，右表由所有向右的链接子组成(即那些后缀是+的链接子)，这样，一个disjunct 可以写成下面的形式：
( (L 1,L 2,……,L m ) (R n ,R n-1,……,R 1) ) 这里，L 1,L 2,……,L m 是所有向左的链接子。R n ,R n-1,……,R 1是所有向右的链接子。左表和右表都可以为空，后缀+或-可以省略不写，因为已经隐含在
disjunct 中。
要满足某个单词的链接要求，那么它所有disjunct 中必须有一个disjunct 被满足。一个disjunct 被满足当且仅当它两个表中的所有链接子同时被满足。disjunct
的两个表中的链接子是有序的，左表中L1,L2,……,L m链接的单词距离当前单词越来越远，右表中R n,R n-1,……,R1链接的单词距离当前单词越来越近。
链接表达式和disjunct范式互相转换很容易，例如，下面的链接表达式(A-or ()) & D- & (B+ or ()) & (O- or S+)
对应下面8个disjunct范式：
科技进步奖((A,D) (S,B))
((A,D,O) (B))
((A,D) (S))
((A,D,O) ())
((D) (S,B))
((D,O) (B))
((D) (S))
((D,O) ())
3.链语法的主要特点
(1)链语法是词汇主义(lexicalism)的语法系统，对于任何一个单词，词典中
都详尽地描述了这个单词在句子中如何使用。
(2)所有词汇主义的语法系统所带来的优点：构造大型语法系统很容易，一
个单词的描述只对包含这个单词的句子的分析产生影响。同时，允许我
们逐步地建立一个大型语法系统(incrementally)。进而对于特殊的不规则咸阳师范学院学报
住家创业的词语描述很方便，它们在词典中单独占据一个条目。实际经验告诉我
们，语言中任何现象都可以分为典型的和非典型的，描述典型规律的规
则很容易，而描述非典型的规则则要麻烦得多。
(3)链语法用单词间得关系描述代替了成分描述。
(4)一般认为，词汇主义得语法系统易于用来构造统计模型，单词间得关系
描述也使我们收集词汇之间得统计信息变得容易。
(5) D.Sleator等已经论证了链语法系统得生成能力等价于上下文无关语法。
是否可以考虑把复杂特征集和合一运算加进去，限制其生成能力。
5.分析算法
D.Sleator和D.Temperley提出了一个基于动态规划(Dynamic programming)
5
>温纳
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议