mirror 说：

”括号可以用几重？立委作为计算机的半拉专家，应该知道是有限的。问题是限在几重上。…… 比如｛［最（伟光正的）党］领导的｝是一个深度的例子。 没有抽象化，也就没有学问了。问题不在于可不可以。问题是出自一个什么样的考虑、取舍，定下的如此规矩。”

由镜子所说引申去：自然语言是递归的么？ (92201)
Posted by: liwei999
Date: June 17, 2007 05:17PM

很多句法学家认为，自然语言的结构具有递归性 (recursion)。递归的表现是结构的嵌套，这就好像我们数学表达式中使用括号一样，理论上是括号的嵌套使用是无限的（无法预先规定嵌套的层数）。可是，语言的制约不仅仅是句法，还有语用上的限制。

自然语言中，括号的有限使用是语用学（pragmatics）的常识和可以观察到的语言现实。因为中间嵌套太深，不利于交流，也会超出人的短期记忆的承受范围。

中间嵌套的例子有主句套从句：主句的主语（S）和做谓语的动词短语(VP)中间又插入一个定语从句，修饰主句的主语：

A guy who knows a girl also knows another girl.

其结构是：[S [S VP] VP]

然而，右嵌套可以很深，在英语，这种例子屡见不鲜。

［…[…[…[…[…[…]]]]]]

例如：

I know a guy, who knows a girl, who knows another guy, who knows ……

其结构是：[S VP [S VP [S VP [S VP […]]]]]

再如：有一类英语动词（a verb subcategy），其动词短语要求嵌套另一个动词短语作为其宾语补足语，如果被嵌套的动词短语恰好也是同类动词，这种嵌套就可以循环下去。

这类动词有：expect, tell, ask, force, … VP 的句型是：VP –> [V + NP + VP] （V是这类动词，NP 是名词短语做宾语）
譬如：

I expected John to finish the homework.
I expected John to tell Mary to finish the homework.
I expected John to tell Mary to ask her students to finish the homework.
……

其结构是：[S VP[V NP VP[V NP VP[V NP VP[…]]]]]

由于语言结构的recursive nature, 受到”乔木司机“的形式语言理论的不良影响，很长一段时间，计算语言学界推崇能够反映recursion的上下文无关语法（CFG, Context Free Grammar），排斥有限状态语法（FSG, Finite State Grammar），认为后者不适合自然语言parsing。可是，研制实用系统的人对简单而高效的FSG情有独衷。

FSG 比起 CFG 不够 powerful，为什么也可以成功运用在自然语言的parsing上呢？

诀窍就在，可以把很多个FSG叠加起来用（cascaded finite state device），一层一层地由里往外退括号。由于语用学的制约，人类实际的语言现象，表达中间recursion的括号数量是很有限的（很少超过三层，形象地说，只要大中小三种括号就够用了），而边缘嵌套难不住FSG (其实实际语料中边缘嵌套也很少超过五层)，所以线性叠加完全可行。

【置顶：立委科学网博客NLP博文一览（定期更新版）】