第三章：基于短语结构语法的形式模型

语法的 Chomsky 层级

• W. Wundt 1990 年《大众心理学》提出把句子为成层次的思想；与此同时，传统的欧洲语法研究单词之间的关系，而不是单词所表示的成分之间的关系。
• Leonard Bloomfield 1914 年在《语言研究导论》中将关于组成性的思想引入语言学。
• 1933 年《语言论》时，“直接成分分析法” 已经成为完善的方法。欧洲的句法学家仍然强调以词为基础的语法（依存语法）。
• Z. Harris 使用 “可替换性” 试验检验单独的单位 “分布相似性”：如果一个简单形式可以替换一个复杂结构，这个复杂结构就可能是一个成分。
• 1956 年 N. Chomsky 定义短语结构语法，最早地形式化描述这种层次成分思想。

短语结构语法是形式语言理论的主要内容，是自然语言处理中最重要的形式模型。

• Chomsky 的形式语法：G = (Vn, Vt, S, P)
  • Vn 非终极符号
  • Vt 终极符号
  • S 是 Vn 的初始符号
  • P 是重写规则
• 根据重写规则的形式，形式语法分四类：
  • 0 型语法：φ→ψ，并且要求 φ 不是空符号串
  • 1 型语法（上下文有关语法）：φ1Aφ2→φ1ωφ2
  • 2 型语法（上下文无关语法）：A→ω，A 重写为 ω，应用于自然语言的形式分析中： “短语结构语法”。
  • 3 型语法（有限状态语法）：A→aQ 或 A→a，A 和 Q 是非终极符号，a 是终极符号。

每一个有限状态语法都是上下文无关的，每一个上下文无关语法都是上下文有关的，而每一个上下文有关语法都是 0 型的。

一个人的语言知识是以某种方式体现在人脑这个有限的机体之中，语言知识就是一个由某种规则和原则构成的有限系统，但人却能讲出并理解他从未听到过的句子以及听到的不十分相似的句子，而且这种能力是无限的。——Chomsky

语言是有限手段的无限运用。——W. V. Humboldt

有限状态语法和它的局限性

• 有限状态 Markov 过程

  • 给出一个状态图，能从初始状态出发，按着状态图中的路，始终顺着箭头所指的方向来生成语言。
  • 当达到图中某个状态时，可以沿着从这一状态引出的任何一条路前进，无论之前的生成过程是否走过。
  • 从一个状态到另一个状态，可以允许若干种走法。
  • 状态图中还可以允许任意有限长度的、任意有限数目的圈。

• 由于真实的自然语言常有套叠、递归等结构，有限状态语法对这些结构处理能力不强，所以一般用来进行黏着语和屈折语的形态分析。

• 可以采用状态图清晰地描述屈折语单词的形态分析过程。

  

  有以下缺陷：

  • 不能生成一些由非常简单的符号串构成的形式语言。如：$L_1={a^nb^n}, L_2={\alpha\alpha^*}, L_3={\alpha\alpha}$
  • 不能生成存在相依关系的句子（与具有镜像结构的 L2 相似）
  • 不适合刻画句法结构
  • 只能说明语言中各个符号的前后排列顺序，不能说明语言符号的层次，因此不能解释歧义现象。

短语结构语法

“上下文无关” 指语法中重写规则的形式，而不是指它所生成的语言。

推导树与树形图

通过推导树描述上下文无关语法的推导过程：

• 每个结点有一个标记，这个标记就是 Vn U Vt 中的符号
• 根节点是 S
• 如果结点 n 至少有一个异于其本身的后裔，并由标记 A，那么 A 必定是非终极符号集 V 中的符号
• 如果结点 n1,…nk 是结点 n 的直接后裔，从左到右分别标记为：A1,…Ak，那么 A→A1A2…Ak 必定是 P 中的重写规则

树形图由结点和连接结点的枝组成，标记表示结点上的有关信息。各个结点间有两种关系要注意：支配关系和前于关系。

• 从结点 X 到 Y 有一系列枝连接，X 支配 Y，Y 叫 X 的后裔
• X 与 Y 之间没有另一个相异的结点，叫直接支配
• 不被任何其他结点支配的结点叫根
• 被其他结点支配而不支配任何其他结点的结点叫叶
• 两个结点没有支配关系时，才能从左到右排序，这两个结点之间就存在前于关系，左边结点前于右边结点
• 支配关系和前于关系互斥

树形图可为语言自动分析提供的语言信息：

• 句子中的词序
• 句子的层次
• 词类信息、词组类型信息、句法功能信息、词与词或词组与词组之间的语义关系信息和逻辑关系信息

Chomsky 证明：任何由上下文无关语法生成的语言，均可由重写规则为 A→BC 或 A→a 的语法生成，其中 ABC 是非终极符号，a 是终极符号。具有这样重写规则的上下文无关语法的推导树均可简化为二元形式。这样就可以用二分法来分析自然语言，用二叉树来表示自然语言的句子结构。 A→BC 或 A→a 便叫做 Chomsky 范式。

上下文无关语法采用二分的层次分析法来揭示句子内部的句法结构规律。

上下文无关语法与有限状态语法的关系

• 每一个有限状态语法生成的语言都可以由上下文无关语法来生成
• 在上下文无关语法中，存在一个非终极符号 A 具有性质：A=>φAψ，φψ 是非空字符串，这个语法叫 “自嵌入语法”。如果 G 是非自嵌入的上下文无关语法，那么由 G 生成的语言 L(G) 就是有限状态语言。如果 L(G) 是上下文无关语言，当且仅当 G 是具有自嵌入性质的上下文无关语法。所以 L1 L2 不能由有限状态语法生成。

上下文无关语法和上下文有关语法的关系

上下文有关语法：重写规则 P 的形式：φ→ψ，φψ 是符号串，且 ψ 的长度不小于 φ 的长度

• 每一个上下文无关语法都包含在上下文有关语法之中
• 存在不是上下文无关语言的上下文有关语言，如 L3

0 型语法

φ→ψ，φ≠ψ

Chomsky 证明：每一个 0 型语言都是符号串的 “递归可枚举集”；并且任何一个上下文有关语言同时又是 0 型语言，而且存在不是上下文有关语言的 0 型语言。

0 型语言几乎没有限制，用于描述自然语言比较困难，生成能力太强，会有很多不合格句子；有限状态语法生成能力太弱；上下文有关语法比上下文无关语法生成能力强，但由于上下文无关语法可以采用 Chomsky 范式来实现层次分析，所以在自然语言计算机处理中，人们一般乐于采用上下文无关语法。

四种类型语法分别与图灵机、线性有界自动机、后进先出自动机和有限自动机联系：若一语言能被某种自动机识别，就能用对应语法生成，反之亦然。

递归转移网络和扩充转移网络

• 基于有限状态语法

• 1970 年，美国 W. Woods 在《自然语言分析的转移网络语法》中提出扩充转移网络（Augmented Transition Network，ATN）

• 有限状态转移图（Finite State Transition Diagram，FSTD）：用状态图形象地表示一个句子的分析过程。由于有限状态语法的局限性，难以识别复杂句子，需要扩充：加入一个递归机制，使其具备处理上下文无关语言的能力。
• 递归转移网络（Recursive Transition Networks，RTN）：经过扩充的 FSTD。
  • 弧的标记不仅仅是终极符号或词类符号，还可以是表示词组类型的非终极符号（如 NP，VP 等），每种类型的词组都可以单独用一个 FSTD 表示。
  • 如果同时存在一条以上路径，RTN 无法分析，因此需要 “并行处理” 或先试探一条路，失败时可以 “回溯” 到另一条路。
• 扩充转移网络（Augmented Transition Network，ATN）：对 RTN 进行改进扩充
  • 增加一组寄存器存储信息（因为回溯需要先前背景信息作为依据）
  • 弧的标记除了终极符号和非终极符号，还可以附加一些条件判断
  • 弧上附加一些动作，经过该弧要执行规定操作，通常是重新安排分析句子所生成的数据结构
  • ATN 改进
    • 识别功能可以提高到图灵机
    • 过分依赖句法分析，处理有明显语义但不完全符合语法的话语时存在局限
    • 过程性的，修改可能引发很大副作用

自顶向下分析和自底向上分析

• 基于上下文无关语法
• 自顶向下：根据重写规则，从初始符号开始，自顶向下进行搜索，构造推导树，直到句子结尾为止。
• 自底向上：从输入句子的句首开始顺次取词向前 “移进” 并根据语法的重写规则逐级向上 “归约”，直到构造出表示句子结构的整个推导树为止。
  • 移进：把一个尚未处理过的符号移入栈顶，并等待更多的信息到来之后再做决定；
  • 归约：把栈顶部分的一些符号，由语法的某个重写规则的左边的符号来替代。
  • 接受：输入的符号串处理完毕且栈内仅剩下初始符号 S
  • 拒绝：无法移进，无法归约，且栈并非只有 S 或输入符号串还有符号未处理完毕
• 移进-归约算法本质上是一种自左向右的 LR 算法，难以处理自然语言中的歧义问题。

通用句法处理器和线图分析法

1973 年，R. M. Kaplan 提出了通用句法处理器（General Syntacic Processor，GSP）

• 元系统，不仅是一种处理方法，也是一个能形式地描写各种方法的系统

• 基本数据结构是 “线图”（把树形图加以修改而形成的一种图）

• 修改树形图以便直观地表示前于关系，修改后的图叫 “线图”

  • 可以表示不相连的子树
  • 可以有多个解释的词

• 线图的控制机构

  • 寄存器
  • 层次栈：有递归功能先把线图及一些语法信息存在栈中，以供递归调用
  • 非确定表：选择语法的指示表，方便回溯处理
  • 过程栈：暂停处理表，有暂停和重新开始功能

1968 年，J. Earley 发表的博士论文《一种高效的上下文无关分析算法》提出了 Earley 算法和点规则的概念，为线图分析法奠定理论基础。1980 年，Martin Key 在《句法处理中的算法图和数据结构》中，提出了 “线图分析法”。

• 线图边上的项

  • 有空所（空所是需要证实的部分）：活性边
  • 没有空所：非活性边

• 线图分析过程

  • 自顶向下
  • 自底向上

• Martin Key 提出了 “点规则” 更加直观地表示 “活性边” 和 “非活性边”，修改如下：

  • 容许从某个结点出发，中间不经过其他结点又返回到这个结点的圈出现
  • 线图的边上的标记，不仅可以是简单的范畴，还可以是语法规则。在这样规则的右边符号串中可以加圆点，叫 “点规则”。点规则中圆点后面的部分相当于 “项” 的空所。
    • 圆点后面不空，说明项中有空所，这样的项所在的边为活性边。
    • 圆点后面为空，项中没有空所，这样的边必定是非活性边。

• 经过修改的线图比原来的线图功能更强，叫 “活性线图”。活性边和非活性边分别表示尚未证实的假设和已经证实的假设。活性线图的定义：

  • 由具有如下属性的边构成的图

    • 起点：<START>，整数
    • 终点：<FINISH>，整数
    • 标记：<LABEL>，范畴
    • 已证实部分：<FOUND>，范畴系列
    • 尚待证实的：<TOFIND>，范畴系列

  • 一个边可用五元组记录：(<START>, <FINISH>, <LABEL>→<FOUND>.<TOFIND>)

  • 力求找到能满足活性边条件的非活性边，以便推动分析进程。线图分析的基本规则：

    • 如果一条活性边遇到了一条非活性边，而且这条非活性边的标记上的范畴满足活性边的要求，那么可以在线图上加一条新的边，这条边横跨在活性边和非活性边上。

    • 如果在线图中含有活性边 (i,j,A->W1.BW2) 和非活性边 (j,k,B->W3.)，其中，A 和 B 是范畴，W1，W2，W3（可能为空）是范畴序列或词，那么在线图中加一条新的边 (i,k,A->W1B.W2)。

      

  • 线图的另一个重要问题是启动问题：至少要有一条活性边和一条非活性边（详见书中例子 P.124）。

    • 查字典的方法，把单词在词典中的有关范畴记录到线图边上构造出非活性边
    • 根据规则造出活性边
    • 根据活性边和非活性边造出新的边

Earley 算法

美国学者 J. Earley 于 1968 年在博士论文中提出的算法，在左角分析法的基础上把自顶向下和自底向上结合起来，分析过程中交替使用。规则表示方法体现了点规则的基本精神，实质与线图分析法规则一致。表示方法是把点规则写成：“A→α·β,[i,j]” 的形式，该算法的核心是线图。对于句子中的单词，线图包含一个状态来表示在此之前已经生成的部分；在句子终点，线图提供出该句子所有可能的分析结果。

线图的状态包含三种信息：

• 关于与语法的一个规则相对应的的子树的信息；
• 关于完成这个子树已经通过的进程的信息；
• 关于这个子树相对于输入的位置的信息。

Earley 算法中的三种基本操作（详见书中例子）：

• Predictor（预示）：生成新的状态，预示下一步可以做什么；
• Scanner（扫描）：判断将要分析的单词的词类是否与这个词类的范畴相匹配，如果匹配，就把点向右移动一个位置，并把新的状态加入到线图中；
• Completer（完成）：当状态中的点的右边是非终极符号，而在输入句子中，这个非终极符号所跨越的输入符号串已经分析结束时，就把该状态中的点的位置向右移动到这个非终极符号的右边，并把新的状态加入到线图中。

Earley 算法的分析过程没有回溯（通过遍历 predictor），改进了自顶向下分析的效果。

左角分析法

左角分析法（left-corner parsing method）是一种自顶向下分析法和自底向上分析法结合起来的分析法。所谓 “左角” 是指表示句子句法结构的树形图的任何子树中左下角的那个符号。

• 自顶向下分析过程是先上后下，从左往右
• 自底向上分析过程是从左往右，先下后上
• 左角分析法过程是先自下而上，然后再自顶向下

左角分析法使用了回溯，M. Marcus 1980 年提出用人工方法对规约的条件加以控制，从而避免了回溯，这就是 “Marcus 确定性分析算法”。分为两部分：

• 模式部分
• 行为部分

CYK 算法

Cocke-Younger-Kasami 算法，一种并行的、以 Chomsky 范式为描述对象的句法分析算法。

CYK 步骤：

• 第一步：从 i=1 开始，对长度为 n 的输入句子中的每一个单词 Wi，显然都有重写规则：A→Wi，因此，顺次把 Wi 相应的非终极符号 A 记入 bi1（第 i 列 第 1 行）中。

• 第二步：对于 1≤h<j 以及所有的 i，造出 bih，这时，包含 bij 的非终极符号的集合定义如下：

  bij = { A|对于 1≤k<j，B 包含在 bik 中，C 包含在b(i+k,j-k) 中，并且存在语法规则 A→BC }

CYK 算法由小型分析树逐渐扩大，同样的分析树不会重复计算，不需要进行回溯，规则都采用 Chomsky 范式。

Tomita 算法

1985 年，卡内基-梅隆大学计算语言学家 M. Tomita 提出，是一种扩充的 LR 算法。引入了图结构栈、子树共享和局部歧义紧缩等技术，提高了算法效率。

• LR 分析方法：把分析状态和分析动作对应关系组织在一张分析表中
  • 动作表（ACTION）：描述某个状态下遇到某个展望符号时分析器所应该采取的分析动作；
  • 转移表（GOTO）：描述当归约动作发生以后，分析状态应该怎样转移。
• LR 不适用于所有的上下文无关语法
  • LR 是一个由分析表驱动的自底向上的分析算法，它的确定性表现在 LR 分析表的确定性上。每个单元格最多只有一个分析动作或状态。
  • LR 分析只能处理可以构造出确定分析表的上下文无关语法（LR 语法）。另外，如果语法有歧义，那肯定不是 LR 语法。所以 LR 不适合分析自然语言（分析表的某些单元格会出现一个以上的分析动作，分析表会出现多重入口，无法只按照一种路径分析）。
• 因此，Tomita 引入图结构栈技术以对付多重的分析动作（LR 分析表的多重入口），图结构栈由栈表技术和树结构栈发展而来。
  • 栈表技术：每个进程对应一个栈，每个进程动作与标准 LR 分析一样。缺点：进程之间没有关系，出现歧义时栈表数目指数增长。
  • 树结构栈：将进程处于相同状态的进程合并为栈顶顶点，当栈顶被弹出时又会分解为原来的几个栈。枝干数依然会随歧义的增加指数增长。
  • 图结构栈：改变了树结构栈在分裂时复制若干个的做法，只将栈的某些部分分裂，表示为一棵树。利用栈合并技术可将其表示为 DAG（有向无环图）。不会对句子的任何部分以同样的方式做两次或两次以上的分析。
• 歧义句子总数（形成 “森林”）可能随句子长度增加而指数增长，Tomita 提出了 “子树共享” 和 “局部歧义紧缩” 技术保证分析森林的大小不至于过快增加。
  • 子树共享：如果几棵树存在一个共同子树，则子树只表达一次，构成 “共享森林”。
  • 局部歧义紧缩：当两个或两个以上的子树具有相同的叶节点，且这几棵子树的根具有相同的非终极符号（即句子某一部分能用两种或两种以上的方式归约为一个非终极符号时），这若干个子树就构成一个 “局部歧义”；因为局部歧义太多会导致总的歧义数量指数增长，需要把具有局部歧义的子树的若干个顶点结合为一体，进行 “局部歧义紧缩”。
    • 当出现局部歧义时，把表达局部歧义的子树的根合并为一个结点，该结点为 “紧缩结点”；
    • 在图结构栈中，如果两个或两个以上的符号具有相同的状态顶点在紧缩结点左边，又有相同的状态在右边，就表示这几个符号具有 “局部歧义”。

管辖-约束理论与最简方案

普遍语法属于人类语言的共性。凡是能够用普遍语法原则说明的语言现象，就不必在个别语言的语法中分别做出具体的规定了。

我们所希望发现的是建立在几个基本原则上的高度结构化的普遍语法理论——这些原则严格限制可以获取的那些语法的种类，大力约束它们的形式，但是又具有必须用经验来确定的诸多参数。

——Chomsky

Chomsky 基于那样的认识提出了 “管约论”，其核心是一系列普遍性的原则，称为 “原则子系统”。

X 阶标理论（X-bar theory）

1970 年提出，认为：

• 短语范畴应该分析为词汇范畴的阶标投射，阶标可以分为若干层次，最低层次的词 X 就是中心语，中心语带有若干个补足语，中心语管辖着补足语。
• 词汇范畴应该分析为一组特征。
  • 动词短语、名词短语、形容词短语和介词短语的重写规则都可以归纳为：XP → X Comp。
  • 重写为：X' → X Comp，X' 表示比 X 更高一个层次的语类。
  • 最高层写作 XP，中间需要加几层就加几个 '，XP 下面的整个树形就是 XP 所属的 “最大投射”。
  • X 阶标语法比短语结构语法表达能力更强。短语结构语法只有单词型语类和短语型语类，缺乏中间层次。
  • X 阶标语法比短语结构语法更为严谨（层次严格）。

题元理论（θ-theory）

Chomsky 把逻辑学的命题中的谓词和个体词的关系用 θ（题元）来表示，称为 “题元关系”。充当题元的词语称为 “主目”，不充当或不能充当的称为 “非主目”。

• 每个主目必须，而且只许充当一个题元；
• 每个题元必须，而且只许由一个主目充当。

如果在题元位置缺少有形词，就必须用无形词填充，叫 “空语类”，用 PRO 表示。

格理论（Case theory）

“格” 是一个抽象的概念，只要名词处于一定的句法关系，不论有没有形态上的变化，就都有格。

动词和介词后面可以直接接一个名词短语做补语，而名词和形容词后面不可以直接跟补语，必须在中间插入一个介词。因为：动词和介词的补语有格，而名词和形容词的没有。所以，动词和介词能够指定格，名词和形容词不能。根据格理论可以解释语类的不同性质。

管辖理论（government theory）

所谓 “管辖” 就是成分之间的支配关系，它要说明短语中的各个成分是否在同一管辖区域之内，以及在管辖区域之内，什么是主管成分，什么是受管成分。

从 X 阶标理论角度看，主管成分就是 X 阶标结构中的最低一个层次 X，受管成分就是 X 的补语 Comp。

约束理论（binding theory）

所谓 “约束” 就是语义解释的照应关系。“约束” 要说明在管辖区域内的成分，在什么样的情况下是自由的，在什么样的情况下是受约束的。

三条约束原则：

• 照应词（类似反身代词如 himself 这样的词）在管辖区域内受约束
• 代词（类似 him 这样的词）在管辖区域内是自由的
• 指称词（类似 John 这样的词）总是自由的

所谓某个名词短语受到 “约束”，是指它与先于它的另外一个名词短语指同一客体；所谓某个名词短语 “自由”，是指它与先于它的名词短语不指同一客体；所谓 “管辖区域” 是指最底层的 S 和 NP。

界限理论（bounding theory）

研究对转换范围的限制，重点讨论 wh-移位应该在什么样的区域范围内进行。

在英语中，S 和 NP 都是界点，领属条件规定，wh-移位时，不能一步越过两个界点。

控制理论（control theory）

主要研究如何解释语音上是零的空语类 PRO。

控制理论的基本原则是 “最小距离原则”，也就是说，如果控制带有宾语，则定宾语为控制成分；如果不带宾语，则定主语为控制成分。大部分动词都已宾语为控制成分。

Chomsky 语言哲学

20 世纪 90 年代，Chomsky 又提出了参数方法和最简方案，把生成语法的研究提高到一个新阶段。赋予生成语法以生命的是生成语法的语言哲学理论，其中最为重要的是关于人类知识的本质、来源和使用问题。

• 语言知识的本质

  Chomsky 把语言知识的本质问题叫做 “Humboldt（洪堡特）问题”。德国学者 W. Humboldt 提出 “语言绝不是产品，而是一种创造性活动”，语言实际是心智不断重复的活动，它使音节得以成为思想的表达。人类语言知识的本质就是语言知识如何构成的问题，其核心是 Humboldt 指出的 “有限手段的无限使用”。语言知识的本质在于人类成员的心智/大脑中，存在着一套语言认知系统，这样的认知系统表现为某种数量有限原则和规则体系。高度抽象的语法规则构成了语言应用所需要的语言知识，由于人们不能自觉地意识到这些抽象的语法规则，Chomsky 主张，这些语言知识是一些不言而喻的或者无意识的知识。我们应当把语言知识和语言的使用能力区分开，语言能力可以改进，而语言知识则保持不变；语言能力可以损伤或消失，但并不至于失去语言知识。所以，语言知识是内在于心智的特征和表现，语言能力是外在行为的表现。生成语法研究的是语言的心智知识，而不是语言的行为能力。语言知识体现为存在于心智/大脑中的认知系统。

• 语言知识的来源

  语言知识的来源在西方哲学中是 “Plato 问题”，与此相应，人类语言知识的来源问题是：为什么儿童在较少直接语言经验的情况下，能够快速一致地学会语言？

  这让我们想到了 MIT Launches Initiative To Develop Artificial Intelligence That Learns Like Children | Edify 中 Josh Tenenbaum 教授在 MIT 发布 的Intelligence Quest 项目后的采访中说过的话：“Imagine if we could build a machine that grows into intelligence the way a human being does, that starts off like a baby and that learns like a child. This is really the oldest dream of artificial intelligence”，他认为人类的孩子是宇宙中唯一真正已知的通往智能的捷径。

  Chomsky 对此的解释是：在人类成员的心智/大脑中，存在着由生物遗传而天赋决定的认知机制系统。这些认知系统叫做 “心智器官”，决定构成人类语言知识的是心智器官中的 “语言机能”，这个语言机能在经验环境引发下的生长和成熟，决定这人类语言知识的获得。语言机能有初始状态和获得状态。初始状态是人类共同的、普遍一致的；获得状态是具体的、个别的；初始状态叫做 “普遍语法”，获得状态叫做 “具体语法”。对普遍语法的本质特征及其与具体语法的关系的研究和确定，是解决语言知识 “柏拉图问题” 的关键。

• 生成语法的本质
  Chomsky 坚持认为语言机能内在于心智/大脑，对语言的研究是对心智的研究，最终是在抽象的水平上对大脑结构的研究。因此，生成语法研究在学科上属于 “认知心理学”，最终属于 “人类生物学”。实际应当叫做 “生物语言学”。这是与其他传统语言研究的根本区别。生成语法追求的目标是在理想化和抽象化的条件下，构建关于语言和心智的理论，它期待与主体自然科学的统一。这就是生成语法 “方法论的自然主义”，Chomsky 力图把对于语言、心智的研究以及对于大脑的研究统一在一个共同的理论原则之下，最后把它纳入自然科学的总体研究之中。

• 生成语法的运算系统

  Chomsky 主张，语言是语言机能或者语言机器所呈现的状态，某人具有语言 L，就是说他的语言机能处于状态 L。这个状态是一个生成系统或运算系统（能够生成无限多的语言表达式），Chomsky 把这样的运算系统叫做 “I 语言”（大写的 i）。

  • 内在的：心智的组成部分，最终表现在大脑的神经机制之中
  • 个体的：直接与个体有关，与语言社团存在间接联系，后者的存在取决于其成员具有相似的 I 语言
  • 内涵的：是一个函数或生成程序，生成一系列内在的表现于心智/大脑中的结构描写

• 生成语法与结构主义语法的区别

  • 结构主义语法的方法是：在广泛搜集语言材料的基础上，通过切分、归类、替换等程序，概括出有关语言的语法规则。
  • 结构主义语法是经验主义的方法，其基础是外在主义的语言观。

• 生成语法的最简单主义

  • 生成语法的一个重要原则，可以分为 “方法论最简单主义” 和 “实体性最简单主义”。

  • 方法论最简单主义：在科学研究中使用最小数量的理论原则和理论构件；最大限度地减少复杂性，消除冗余性，增加理论原则的抽象性和概括性；构建最简单的理论模式和最具有解释性的理论；寻求理论的对称性和完美性。

    这里提到的方法很容易让人产生联想，比如《最省力原则》中的哲学思考，比如梯度下降的实用方法，比如关于美感的计算。

  • 实体性最简单主义：要求科学研究对象本身在设计和结构方面具有简单性、优化性和完美性。

  • 原因和动机

    • 什么是人类语言机能应该被期望去满足的一般条件？
      • 语言机能自身在心智/大脑认知系统序列中的位置是什么？Chomsky：是心智/大脑中其他认知系统对于语言机能所施加的界面条件。
      • 那些具有某些独立性的一般概念自然性的考虑，即简单性、经济性、对称性、非冗余性等等，对于语言机能施加的是一些什么样的条件？Chomsky：科学研究对于客体对象所施加的一般性条件，属于方法论的 “最简单主义” 的范畴。
    • 在哪种程度上，语言机能是由这些条件所决定的，而不存在超出它们的特殊结构？Chomsky：语言机能可以很好地满足这些外界性条件，从这个意义上说，语言是一个 “完美的系统”。

• 生成语法的理论构建

  • 逐步抽象化、概括化和最简单化的过程。
  • Chomsky：
    • 早期的短语结构语法：生成能力过强，经常生成不符合语法的句子
    • 转换的方法（转换规则系统）：规则系统越来越复杂
    • 限制规则的条件理论：限制和减少规则数量
    • 原则和参数方式：从语言本身的设计特征以及它与其他认知系统的相互关系出发，消除了一切只是服务于语言机能内部的理论构件，使得生成语法的整体模式达到了空前的简单性和完美性
  • 原则和参数阶段
    • 提出语法规则系统：由词库、句法和语音式、逻辑式构成
    • 提出普遍语法的原则子系统：X 阶标理论、题元理论、格理论、管辖理论、约束理论、界限理论和控制理论
    • 一般性原则：投射原则、准许原则和完全解释原则

• 生成语法的 Y 模式图式

  • 用来说明语法规则和运算的表现形式
  • 
  • I 表示语法基础部分的短语结构规则，II 表示转移规则移动，III 是音位规则，IV 是逻辑规则
  • I 生成 D-结构，II 把 D-结构转化为 S-结构，III 把 S-结构转化为语音表现形式 PF，IV 把 S-结构转化为逻辑表现形式 LF。
  • D 和 S 完全属于语言机能内部，D 结构与词库发生内在性界面关系，S 起着中心枢纽作用；PF 和 LF 分别与心智中的其他认知系统和信念系统形成界面关系。D 和 S 不存在先后顺序问题。
  • Σ = (D, S, P, L)

• 最简方案的总体性考虑

  • 与内在语言有关的应用系统总体上可以分为两个：一个是发生感知系统（A-P）；一个是概念意向系统（C-I）。语言与他们形成的界面一般认为就是语音表现形式和逻辑式。
  • 语言包括词库（描写词汇项目特征）和运算系统（使用这些词汇成分生成推导式和结构描写）两个组成部分。推导式是运算的规程，结构描写是运算的结果。最简方案的设想：除了语音形式的选择和词汇的任意性之外，语言变体只限于词库中那些非实体性的部分（功能成分）和词汇项目（词库）的一般性特征。
  • 原则参数方法的题元理论、格理论、约束理论等，只能在界面上起作用，并通过界面获得它们存在的原因和动机。
  • 由普遍语法的运算推导可产生 “收敛” 和 “破裂” 两个结果。如果一个推导式同时收敛于 PF 层面和 LF 层面，才可以算是真正的收敛。

Joshi 的树邻接语法

1975 年，A. K. Joshi, L. S. Levy, M. Takahashi 等提出 ”树邻接语法“（TAG, Tree Adjoining Grammar），可以识别和生成 ”树邻接语言“（Tree Adjoining Language, TAL）。以句法结构树作为核心操作对象，在树的基础上组织语言知识，产生规则对应着树结构，以线性的一维形式来表达二维的树结构。与短语结构语法的不同之处在于，树邻接语法的规则比短语结构语法的规则更加细致。前者是一个基于符号串的生成系统，后者是基于树的生成系统（当然，树邻接语言仍然是符号串语言）。基本构成要素和操作模式：

• 一个五元组（Σ, NT, I, A, S）
  • Σ 是终极符号的有限集合
  • NT 是非终极符号的有限集合
  • S 是初始符号，特殊的非终极符号
  • I 是初始树的有限集合，两个特征
    • 所有的非叶节点都用非终极符号标记
    • 所有的叶节点，或者用终极符号标记，或者用带有下箭头的非终极符号标记；下箭头是初始树的标志，它的含义是 ”替换“，表示该节点可以被其他的树结构替换。
    • 如果一个初始树的根节点为 X，则这个初始树在 TAG 系统中叫作 X 类型的初始树。
  • A 是辅助树的有限集合，两个特征：
    • 所有的非叶节点都用非终极符号标记
    • 辅助树叶上的结点用终极符号或非终极符号标记
    • A 树叶上的非终极符号结点带有插接符号，用星号标注将被插接的结点，这个结点叫做 ”落脚结点“，该节点标记的非终极符号（短语类符号）要跟它所在的树结构的根节点相同。
  • I U A 中的所有树叫做基础树，TAG 是树生成系统，但生成的树可以分析和解释目标语言的串语言。

• 如果一棵树由集合 I U A 中的任意两课树组合而成，这棵树叫做 ”推导树“。得到推导树的两个操作：插接和替换。

  • 插接：把辅助树插到任意树中而建立一棵新树的过程
    • 选择插接：辅助树可以插接到指定结点上，但这种辅助树上的插接不是强制的
    • 空插接：在指定结点上不允许有任何邻接成分
    • 强制插接：辅助树一定要插接在指定结点
  • 替换：用推导树替换初始树而建立一棵新树的过程
    • 标记了替换的结点（下箭头）不允许出anren现任何插接操作

• 推导关系树：确定推导树构成过程的树。

  • 一个父节点的所有子结点的地址都不相同
• TAG 生成的树集合
  • 从某个以 S 为根的初始树推导出的绝对初始树的集合。
  • 绝对初始树：叶子上没有替换节点的初始树
    • 可识别树集合严格包含在树邻接语法的树集合中
    • 在给定 TAG 树集合中，所有树的路径集合都是上下文无关语法
    • 对于 TAG 中的每个语法 G，G 的树集合都可以多次被识别

• TAG 中的串语言

  • 树邻接语法可以识别和最终生成的语言是树邻接语言，树邻接语言不再包含任何形式的树，是一种串语言。树邻接语言生成的树最终还是为了识别和生成这样的串语言。
  • T_G = { t | t 是从某个以 S 为根的初始树的推导结果}，假设 L(G) 是 TAG 的串语言，则 L(G) 是树集合中所有树的生成结果的集合：L(G) = {w | w 是 T_G 中某个树 t 的生成结果}
  • 属性：
    • 树邻接语言完全包括上下文无关语言；
    • 树邻接语言是半线性的；
    • 树邻接语言是语言的完整抽象集合；
    • TAG 的自动机是嵌入式下推自动机；
    • 树邻接语言都有一个启动词条；
    • 树邻接语言可以被多次分析。

• 总的来说，一个 TAG 语法包括一组有限的初始树和辅助树，用一个 TAG 语法生成自然语言中的句子，就是从 S 类型的初始树开始，不断地进行替换和插接操作，直到所有带替换标记的结点已经被替换了；所有带插接标记的结点都已经被插接了，最后把所得到的树的叶节点按顺序列出，就可以得到该 TAG 语法所生成的句子集合。在自然语言句子分析时，从包含树中词语的树结构开始，通过替换和插接操作，形成一个以 S 为根节点的树结构。

• LTAG：把词汇信息引入 TAG 的规则中。
  • 把每一个初始树和辅助树都与某一个或某一些具体的单词关联起来，带有词的结点叫做这个树的 ”抛锚点“。
  • 进一步限制了短语结构语法过强的生成能力，提高了自然语言处理的精确度和效率。

汉字结构的形式描述

• 汉字分为独体字和合体字。独体字只能分离出笔画，合体字由两个或以上的部件组成。合体字的三个层次：合体字、部件、笔画。部件是枢纽，是汉字形体结构的核心。
• 如果一个部件继续分解就成为笔画，这种部件叫做 ”末级部件“。独体字可看作由一个末级部件组成，所有的汉字均有部件组成。汉字：648 个末级部件，其中 327 个是独体字。
• 汉字结构的上下文无关语法：
  • G = (Vn, Vt, S, P)
  • Vn = \{A, B, C, D, E, F, G, H, I, J, K\}，表示汉字的 11 种基本结构：上下、上中下、左右、左中右、左上包围、右上包围、左下包围、左上右包围、上左下包围、左下右包围、全包围
  • Vt = \{O\}，O 可以为各种终极符号，就是 648 个末级部件
  • S：初始符号，要分析其结构的汉字本身，只能取 Vn 中唯一的一个值，这是上下文无关语法描述汉字和句法结构时的差别
• 括号表达式：树形图可以转写为等价的括号形式，如 ”霜“：A(O, C(O, O))
  • 三部件：15 个小类
  • 四部件：19 个小类
  • 五部件：19 个小类
  • 六部件：10 个小类
  • 七部件：4 个小类
  • 八部件：1 个小类
  • 九部件：1 个小类

Hausser 的左结合语法

德国埃尔朗根-纽伦堡大学计算语言学教授 Roland Hausser 创立，他还提出了 “数据库语义学” 和完整的 “语表组合线性内部匹配” 理论。

2006 年，Hausser 出版的《自然语言交流的计算机模型：数据库语义学下的语言理解、推理和生成》中，他系统分析了自然语言的主要结构，分析了听话人模式和说话人模式下的示意推导。

Hausser 提出的 “语表组合线性内部匹配（SLIM）” 理论以人作为人机交流的主体，而不是以语言符号为主体，要求通过完全显化的机械步骤，使用逻辑和电子的方式来解释自然语言理解和自然语言的生成过程。

• 表层成分（surface）：以语表组合性作为它的方法论原则；
• 线性（linearity）：以时间线性作为它的实证原则；
• 内部因素（internality）：以语言的内部因素作为它的本体论原则；
• 匹配（matching）：以语言和语境信息之间的匹配作为它的功能原则。

SLIM 的技术实现手段叫做 “数据库语义学（DBS）”：把自然语言理解和生成重新建构为 “角色转换” 的规则体系，即 “说话人模式” 和 “听话人模式” 的互相转换。

• Step1：DBS 输入，要求计算机具备外部界面。听话人模式中的自然主体从另一个主体或语境获得信息。
• Step2：左结合语法模拟，处于听话人模式，叫做 LA-hear。自然主体在自己的认知当中分析信息。
• Step3：左结合语法的第二个变体负责在内存词库中搜索合适的内容，叫做 LA-think。自然主体思考如何做出反应。
• Step4：左结合语法的第三个变体的任务是语言生成，叫做 LA-speak。自然主体用语言或行动作出反馈。

DBS 的结果用 DBS 图表示，一种树结构，与短语结构语法和依存语法的树结构不同：

• 短语结构语法：句子的层次和单词之间的前后线性关系很清楚，但句子中各个成分的中心不突出（没有说明哪个是中心词）。
• 依存语法：没有范畴结点，单词间依存关系很清楚，依存关系是二元关系，支配者是中心词，被支配者是从属词。但单词之间前后线性顺序不如短语结构语法明确。
• DBS 图：着重分析语言内容，结点单词都用原型词表示，没有定冠词等结点。节点之间的连线有明确含义：
  • 竖线 “|” 表示修饰-被修饰关系
  • 左斜线 “/” 表示主语-动词关系
  • 右斜线 “\” 表示宾语-动词关系
  • 水平线 “—” 表示并列关系
• 词性关系图：DBS 图结点的词替换为词性，语义关系图就变成了 “词性关系图”。
• 编号弧图：表示激活语义关系图的时间线性顺序。所有表示推导的编号弧的方向是自底向上的。
• 语表实现图：表示如何按照遍历顺序生成语言的表层形式。
• 数据库语义学的两个基础：
  • 左结合语法。
    • 按照自然语言的时间线性顺序自左向右结合进行分析与计算的方法。
    • 与短语结构语法是同质的，不同之处在于后者依据的是 “替换原则”，前者是 “可持续性原则”。
    • 推导时，总是从左向右，自底向上，沿着树结构的左侧一步一步把单词逐一结合起来。
    • 一种基于短语结构语法的形式模型，同时吸取了依存语法和数据库语义学的优点。
  • 单词数据库。存储单词的内容的存储形式是一种非递归的特征结构，叫做 “命题因子”，一个命题因子是 “属性-值偶对” 的集合。每个单词或句子元素的句法语义信息都体现为相应的属性-值矩阵。

小结

本章介绍了各种各样基于短语结构（“上下文无关” 指语法中重写规则的形式，而不是指它所生成的语言）的语法分析方法，不过无论哪种方法，最终的表现形式基本都是树（或类树）结构。

• 递归转移网络和扩充转移网络：1970 年，美国 W. Woods 在《自然语言分析的转移网络语法》中提出扩充转移网络（Augmented Transition Network，ATN）。前者是基于有限状态语法、经过扩充的有限状态转移图。后者是基于前者的进一步扩充。
• 自顶向下和自底向上分析：基于上下文无关语法。
• 通用句法处理器和线图分析法：
  • 1973 年，R. M. Kaplan 提出了通用句法处理器（General Syntacic Processor，GSP），其基本数据结构是 “线图”（把树形图加以修改而形成的一种图，便于更直观地表示前于关系）。不仅是一种处理方法，也是一个能形式地描写各种方法的系统。
  • 1968 年，J. Earley 发表的博士论文《一种高效的上下文无关分析算法》提出了 Earley 算法和点规则的概念，为线图分析法奠定理论基础。
  • 1980 年，Martin Key 在《句法处理中的算法图和数据结构》中，提出了 “线图分析法”。Martin Key 提出的 “点规则” 更加直观地表示 “活性边” 和 “非活性边”，经过修改的线图比原来的线图功能更强，叫 “活性线图”。活性边和非活性边分别表示尚未证实的假设和已经证实的假设。
• Earley 算法：
  • 美国学者 J. Earley 于 1968 年在博士论文中提出的算法，在左角分析法的基础上把自顶向下和自底向上结合起来，分析过程中交替使用。
  • 规则表示方法体现了点规则的基本精神，实质与线图分析法规则一致。表示方法是把点规则写成：“A→α·β,[i,j]” 的形式，该算法的核心是线图。对于句子中的单词，线图包含一个状态来表示在此之前已经生成的部分；在句子终点，线图提供出该句子所有可能的分析结果。
  • Earley 算法的分析过程没有回溯（通过遍历 predictor），改进了自顶向下分析的效果。
• 左角分析法：
  • 左角分析法（left-corner parsing method）是一种自顶向下分析法和自底向上分析法结合起来的分析法。所谓 “左角” 是指表示句子句法结构的树形图的任何子树中左下角的那个符号。
  • 左角分析法使用了回溯，M. Marcus 1980 年提出用人工方法对规约的条件加以控制，从而避免了回溯，这就是 “Marcus 确定性分析算法”。
• CYK 算法：
  • 一种并行的、以 Chomsky 范式为描述对象的句法分析算法。
  • CYK 算法由小型分析树逐渐扩大，同样的分析树不会重复计算，不需要进行回溯，规则都采用 Chomsky 范式。

• Tomita 算法：

  • 1985 年，卡内基-梅隆大学计算语言学家 M. Tomita 提出，是一种扩充的 LR 算法（LR 分析方法：把分析状态和分析动作对应关系组织在一张分析表中）。
  • 引入了图结构栈、子树共享和局部歧义紧缩等技术，提高了算法效率。

• 树邻接语法：

  • 1975 年，A. K. Joshi, L. S. Levy, M. Takahashi 等提出 ”树邻接语法“（TAG, Tree Adjoining Grammar），可以识别和生成 ”树邻接语言“（Tree Adjoining Language, TAL）。
  • 以句法结构树作为核心操作对象，在树的基础上组织语言知识，产生规则对应着树结构，以线性的一维形式来表达二维的树结构。与短语结构语法的不同之处在于，树邻接语法的规则比短语结构语法的规则更加细致。前者是一个基于符号串的生成系统，后者是基于树的生成系统（当然，树邻接语言仍然是符号串语言）。
• 左结合语法：
  • 德国埃尔朗根-纽伦堡大学计算语言学教授 Roland Hausser 创立，他还提出了 “数据库语义学” 和完整的 “语表组合线性内部匹配” 理论。
  • 按照自然语言的时间线性顺序自左向右结合进行分析与计算的方法。与短语结构语法是同质的，不同之处在于后者依据的是 “替换原则”，前者是 “可持续性原则”。推导时，总是从左向右，自底向上，沿着树结构的左侧一步一步把单词逐一结合起来。

除此之外，还有两个特别值得一提的：

• Chomsky 的管辖-约束理论与最简方案，内容涉及 Chomsky 的语言哲学，其关于语言的本质思考及生成语法理论的分析和深入探讨引人深思。
• 作者关于汉字结构的形式描述，以部件为核心，构建了汉字结构的上下文无关语法，无疑是一种创新的方法。

本章内容乍看非常复杂繁琐，但其实并不难，每块内容都有例子配套，很容易理解（虽然可能会有些耗时）。