1.综述
.1.1. 绪论
.1.1.1. 背景,目标
.1.1.1.1. 研究自然语言的动力
1． 语言是思维的裁体，是人际交流的重要工具。在人类历史上以语言文字形式记载和流传的知识占到知识总量的80％以上。就计算机的应用而言，据统计用于数学计算的仅占10％，用于过程控制的不到5％，其余85％左右都是用于语言文字的信息处理。在这样的社会需求下，自然语言理解作为语言信息处理技术的一个高层次的重要方向，一直是人工智能界所关注的核心课题之一。
2． 由于创造和使用自然语言是人类高度智能的表现，因此对自然语言理解的研究也有助于揭开人类智能的奥秘，深化我们对语言能力和思维本质的认识。
.1.1.1.2. 什么是计算语言学
计算语言学（Computational Linguistics）指的是这样一门学科，它通过建立形式化的数学模型，来分析、处理自然语言，并在计算机上用程序来实现分析和处理的过程，从而达到以机器来模拟人的部分乃至全部语言能力的目的。
计算语言学（Computational Linguistics）有时也叫计量语言学（Quantitative Linguistics）, 数理语言学（Mathematical Linguistics）, 自然语言理解（Natural Language Understanding）, 自然语言处理（Natural Language Processing）, 人类语言技术（Human Language Technology）。
.1.1.1.3. 图灵测验
在人工智能界，或者语言信息处理领域中，人们普遍认为可以采用著名的1950年描述的图灵试验(Turing Test )来判断计算机是否“理解”了某种自然语言。
.1.1.1.3.1. Turing模仿游戏 (Imitation Game)
l 场景：男性被试、女性被试、观察者，
3者在3个不同的房间，房间号分别为X, Y, O
l 规则：观察者用电传打字机与被试们通信，
男性被试欺骗观察者、女性被试帮助观察者。
l 目标：观察者要判断出X房间里被试的性别。
.1.1.1.3.2. Turing测试 (Turing Test)
l 场景：被试人、计算机、观察者
3者在3个不同的房间，房间号分别为X, Y, O
l 规则：观察者用“某种方式”与被试人和计算机通信
计算机欺骗观察者、被试人帮助观察者
l 目标：观察者要判断出被试人在那个房间
.1.1.1.3.3. 全Turing测试 (Total Turing Test)
l 场景：被试对象（人或计算机）、观察者，
观察者可以看到被试对象
l 规则：观察者可以任意与被试对象通信
l 目标：观察者要判断出被试对象是人还是计算机
.1.1.1.3.4. 参考文献
1． A. M. Turing，COMPUTING MACHINERY AND INTELLIGENCE，http://cogsci.ucsd.edu/~asaygin/tt/ttest.html连接的http://www.oxy.edu/departments/cog-sci/courses/1998/cs101/texts/Computing-machinery.html
2． 曹存根，《AI历史和问题》讲义，中科院计算所
3． Roland Hausser,Foundations of Computational Linguistics,Springer,1999
.1.1.2. 研究历史
.1.1.2.1. 20世纪50年代
NLP于20世纪50年代早期开始于美国，当时美国害怕在空间竞赛中落败，需要翻译大量俄文科技文献，于是开发机器翻译系统，特别是俄英机器翻译系统，做法是采用词到词的翻译。由于成本高而效率低，渐渐撤去了资金支持。
.1.1.2.2. 20世纪60年代
60年代开发的自然语言理解系统，大都没有真正意义上的语法分析，而主要依靠关键词匹配技术来识别输入句子的意义。在这些系统中设计者事先存放了大量包含某些关键词的模式，每个模式都与一个或多个解释(又叫响应式)相对应。系统将当前输入句子同这些模式逐个进行匹配，一旦匹配成功便立即得到了这个句子的解释，而不再考虑句子中那些不属于关键词的成分对句子意义会有什么影响。
SIR
SIR(Semantic Information Retrieval)是1968年B．Raphael完成的，这是他在美国麻省理工学院的博士论文研究工作的一部分。系统用LISP语言编程。这是一个理解机器的原型，因为它能把用户通过英语告诉它的事实记住，然后通过对这些事实的演绎来回答用户提出的问题。
SIR有能力接受英语的一个受限子集，它把输入句子同如下类型的24种关键词模式进行匹配：
* is *
* is part of *
Is * * ?
How many * does * have ?
What is the * of * ?
当符号“*”同输入句子中的一个名词相匹配时，该名词前面允许带有像a，the，every，each等冠词、量词或数词的修饰语。每当匹配到一种模式，便会在程序中触发相应的动作。
STUDENT
1968年美国麻省理工学院的博士研究生D．Bobrow完成了另一个基于模式匹配的自然语言理解系统STUDEN丁。系统能理解和求解中学代数题。
ELIZA
1968年，J．Weizenbaum在美国麻省理工学院设计的ELIZA系统，或许是这些基于“模式匹配”的自然语言系统中最有名一个。系统模拟一位心理治疗医生(机器)同一位患者(用户)的谈话。
TG
Noam Chomsky 创建了generative transformational grammar。机器翻译中开始使用句法分析。
.1.1.2.3. 20世纪70年代
进入70年代以后，一批采用句法—语义分析技术的自然语言理解系统脱颖而出，在语言分析的深度和难度方面都比早期系统有了长足的进步。这个时期的代表作是LUNAR，SHRDLU和MARGIE系统。
LUNAR
LUNAR是第一个允许用普通英语同计算机数据库对话的人---机接口，是1972年美国BBN公司的W．Woods负责设计的。系统用来协助地质学家查找、比较和评价阿波罗—11飞船带回的月球岩石和土壤标本的化学分析数据。
SHRDLU
SHRDLU系统是1972年Terry Winograd设计的，这是他在美国麻省理工学院的博士学位研究工作。SHRDLU是一个在“积木世界”中进行英语对话的自然语言理解系统。系统模拟一个能操纵桌子上一些玩具积木的机器人手臂，用户通过人—机对话方式命令机器人捏弄那些积木块，系统则通过屏幕来给出回答并显示现场的相应情景。
这个系统是想说明让计算机理解语言是可以做到的；
MARGIE
MARGIE(Meaning Analysis，Response Generation，and lnference on Eng1ish)是由R．Schank及其学生们在美国斯坦福大学的人工智能实验室里建立的一个系统，目的是提供一种自然语言理解过程的直觉模型。
.1.1.2.4. 20世纪80年代
实用化和工程化系统
进入80年代以来自然语言理解系统的最大特点就是实用化和工程化。其重要标志就是一批商品化的自然语言人----机接口和机器翻译系统出现在国际市场上。著名的有美国人工智能公司(AIC)生产的英语人—机接口系统Intellect，美国弗雷公司生产的Themis人----机接口，美国加里福尼亚工学院研制的ASK接口；欧洲共同体在美国乔治敦大学开发的机译系统SYSTRAN的基础上成功地进行了英、法、德、西、意、葡等多语对的机器翻译，加拿大蒙特利尔大学开发的服务于天气预报领域的英法机译系统TAUM—METE0，日本富士通公司开发的ATLAS英日、日英机译系统，日本日立公司开发的HICATS英日、日英机译系统等等。国内“七五”期间由中国软件总公司开发的商品化英汉机译系统“译星”(TRANSTAR)，也是这方面的一个范例。
语料库语言学(Corpus Linguistics)
“语料库语言学(Corpus Linguistics)是80年代才崭露头角的一门计算语言学的新的分支学科。它研究机器可读的自然语言文本的采集、存储、检索、统计、语法标注、句法语义分析，以及具有上述功能的语料库在语言定量分析、词典编纂、作品风格分析、自然语言理解和机器翻译等领域中的应用”。
语料库语言学(Corpus Linguistics)开始崛起。首先它顺应大规模真实文本处理的需求，提出了以计算机语料库为基础的语言学研究及自然语言处理的新思想。这个学派坚持认为语言学知识的真正源泉是大规模活生生的语料，计算语言学工作者的任务是使计算机能自动或半自动地从大规模语料库中获取理解语言所需的各种知识，他们必须客观地而不是主观地对库存的语言事实作出描述。
.1.1.2.5. 20世纪90年代
1990年8月，在赫尔辛基召开的第13届国际计算语言学大会上，大会组织者首次提出了处理大规模真实文本的战略目标，并在会前组织了“大型语料库在建造自然语言系统中的作用”、“词典知识的获取与表示”和“电子词典”等专题讲座，预告了语言信息处理的一个新的历史阶段即将到来。
.1.1.2.6. 21世纪初
.1.1.2.7. 21世纪20年代
.1.1.2.8. 参考文献
1） 石纯一、黄昌宁、王家钦，《人工智能原理》，清华大学出版社
2） Chris Manning and Hinrich Schutze，Foundations of Statistical Natural Language Processing，http://www-nlp.stanford.edu/fsnlp/
3） 周 强，《基于语料库和面向统计学的自然语言处理技术介绍》，http://www.icl.pku.edu.cn/research/papers/chinese/collection-2/zqlw6.htm
.1.1.3. 研究内容
.1.1.3.1. 从计算的角度来研究语言的性质
所谓从计算的角度来看语言的性质，就是要求将人们对语言的结构规律的认识以精确的、形式化的、可计算的方式呈现出来，而不是像其他语言学研究那样，在表述语言的结构规律时一般采用非形式化的表达形式。
.1.1.3.2. 将语言作为计算对象来研究相应的算法
所谓将语言作为计算对象来研究相应的算法，是研究如何以机械的、规定了严格操作步骤的程序来处理语言对象（主要是自然语言对象，当然也可以是形式语言对象），包括一个语言片断（比如词组、句子或篇章）中大小语言单位的识别，该语言片断的结构和意义的分析（自然语言理解），以及如何生成一个语言片断来表达确定的意思（自然语言生成），等等
.1.1.4. 语言分析的不同层次
.1.1.4.1. 基于语言构成划分层次
.1.1.4.1.1. 词汇
.1.1.4.1.2. 短语
.1.1.4.1.3. 句子
.1.1.4.1.4. 段落
.1.1.4.1.5. 篇章
.1.1.4.2. 基于语言特征划分层次
.1.1.4.2.1. 音韵
词与其发音的关系。
.1.1.4.2.2. 词法
如何用音节形成词，如friend-ly。
.1.1.4.2.3. 句法
.1.1.4.2.4. 语义
.1.1.4.2.5. 语用
.1.1.5. 应用领域
.1.1.5.1. 机器翻译（Machine Translation）和机助翻译
.1.1.5.2. 语音识别（Speech Recognition）
.1.1.5.3. 语音合成（Speech Synthesis）
.1.1.5.4. 文本分类（Text Classification）
.1.1.5.5. 信息检索（Information Retrieval）
.1.1.5.6. 信息提取（Information Extraction）与自动文摘（automatic summarizing）
.1.1.5.7. 人机接口（Human-Machine Interface）
.1.1.5.8. 故事理解与问答系统
.1.1.6. 相关学科
.1.1.6.1. 各学科的交叉
.1.1.6.2. 哲学
一个词和一个句子怎么会有意义，如何用词指定世界中的物体。信念、目标、和意图是什么东西，与语言有什么关系。通过反例的直觉来扩展自然语言；
.1.1.6.3. 数学
.1.1.6.3.1. 数理逻辑
.1.1.6.3.2. 图论
.1.1.6.3.3. 概率论
.1.1.6.4. 语言学
研究语言的结构，词如何形成短语、短语如何形成句子，什么东西限制一个句子可能的意义等。研究的工具：人类对合适的语法和意义形式的直觉，以及一些数学工具如形式语言理论、模型理论语义学等。
.1.1.6.5. 心理学
研究人类语言产生和理解的过程，人类如何识别句子的正确结构，何时决定一个词的正确含义，理解过程何时发生等。研究的方法是：测量人类对象执行情况的实验技术，以及对观察结果的统计分析。
.1.1.6.6. 计算机科学
.1.1.6.6.1. 人工智能
.1.1.6.6.2. 机器学习
.1.1.6.6.3. 模式识别
.1.1.6.7. 信息科学
.1.1.6.7.1. 数据库
.1.1.6.7.2. 数据挖掘
.1.1.6.7.3. 数据仓库
.1.1.6.7.4. 信息提取
.1.1.6.7.5. 自动文摘
.1.1.6.7.6. 信息分类
.1.1.6.7.7. 信息检索
.1.1.6.7.8. 信息过滤
.1.2. 英语的特点
.1.3. 汉语的特点
2.音韵
3.词法
4.句法
.4.1. 总论
词如何形成短语，词和短语如何形成正确的句子，每一个词在句中在机构方面起什么样作用。
.4.1.1. 句法分析的任务
对于自然语言的分析来说，句法分析有以下两个主要任务：
1．识别一个语言的句子和确定输入句子的结构
给定文法G和该文法描述的语言L,
(1)给定一个字符串S,判定S是否属于L;
(2) 给定一个字符串S,如果S属于L，给出S对应的树结构;
3．句法结构的规范化
如果我们能把大量可能的输入结构映射为数量较少的结构，那么后继的处理(例如语义分析)就得以简化。下面是几个结构规范化的例子：
(1) 句子中时常有些成分可以被省略或“零化”；
(2) 各种转换可以把表层结构不同的句子联系起来，如主动语气和被动语气；
(3) 正常词序和所谓分裂结构：
That I like wine is evident.
It is evident that I like wine.
(4) 名词性结构和动词性结构：
the barbarians’destruction of Rome
the barbarians destroyed Rome
等等。这样一类的转换使得后继的处理只需考虑数量少得多的结构。
.4.1.2. 句法分析的不同类型
1． 传统的非概率分析方法
概率方法（PCFG）
2． 完全句法分析
部分句法分析（partial parsing / shallow parsing）
3． Top-down句法分析predicative parser
Bottom-up句法分析shift-reduce parser
4． 确定性句法分析deterministic parser
非确定性句法分析non-deterministic parser
.4.1.3. 形式语法阵营
1）TG，GB，MP，……
2）LFG，GPSG，HPSG，……
3）PATR-II，DCG，FUG，……
4）树邻接语法（TAG）
5）链语法（Link Grammar）
6）范畴语法（CategorialGrammar）
7）依存语法（Dependency Grammar）
8）词语法（Word Grammar）
……
.4.1.4. 当代形式语法理论体系的分类
.4.1.5. 形式语法理论体系的演变历史
.4.2. 理论
.4.2.1. 形式语言与自动机
.4.2.1.1. 基本概念
.4.2.1.1.1. 基础概念
.4.2.1.1.1.1. 字母表
由元素组成的非空有限集。我们把字母表中的元素称为符号，因此字母表也称为符号集。
.4.2.1.1.1.2. 字（也叫字符串，符号串）与空字(也叫空串)
由字母表中的元素所构成的一个有穷序列。在符号串中，符号的顺序是很重要的。如果某符号串x中有m个符号，则称其长度为m．表示为|x|＝m。
不包含任何字符的序列，记为ε。|ε|=0。
字母表Σ上的所有字的全体记为Σ*。Σ*称为字母表Σ上的符号串集合。
.4.2.1.1.1.3. 空集
不含任何元素的集合，记为Φ。
.4.2.1.1.1.4. 积/闭包/正则闭包
Σ*的子集U和V的（连接）积定义为
UV={αβ|α∈U & β∈V}
V自身的n次连接（也称V的n次方幂）记为
Vn=VV……V,V的数目为n
规定V0={ε}。令
V*= V0∪V1∪V2∪V3∪…
称V*是V的闭包。记V+=V V*,称V+是V的正（则）闭包。
显然，εX=Xε=X,X为符号串；或{ε}X=X{ε}=X ，X为符号串集合。
.4.2.1.1.2. 正规式与正规集
下面是的正规式与正规集递归定义：
1． ε和Φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和Φ；
2． 任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；
3． 假定U和V都是Σ上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么，（U|V）,(U.V)和(U)*也都是正规式，它们所表示的正规集分别为L(U) ∪L(V),L(U)L(V)（连接集）和(L(U))*（闭包）。
仅由有限次使用上述步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。
若两个正规式U和V所表示的正规集相同，则认为U和V等价，记为U=V。
.4.2.1.2. 自动机
.4.2.1.2.1. 状态转换图
状态转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连接。箭弧上的标记（符号或符号串）代表在射出结（即箭弧始结）状态下可能出现的输入符号或符号串。一张状态转换图只包含有限个状态,其中一些被称为初态，又有一些被称为终态（用双圈表示）。
用状态转换图可以构造词法和语法分析程序。但为了分析程序的自动生成，需要对状态转换图加以形式化。这就产生了自动机理论。
.4.2.1.2.2. ε-闭包与a弧转换
1） 状态集合I的ε-闭包，表示为ε-closure(I)，它是一个状态集：
a)若s∈I,则s∈ε-closure(I)；
b) 若s∈I，则从s出发经任意条连续的ε弧而能到达的状态s’ ∈ε-closure(I)。
2） 状态集合I的a弧转换，表示为move(I，a) ，它是一个状态集：
令J= move(I，a)，则J是所有那些可从I中的某一状态结经过一条a弧而到达的状态结的全体。
对于状态集I和弧a,我们定义
Ia=ε-closure(J)，其中J= move(I，a)
即Ia是状态集I的a弧转换的ε-闭包。
.4.2.1.2.3. 确定有限自动机（DFA）
一个确定有限自动机（DFA）M是一个五元式
M=(S, Σ,f,s0,Z)
其中，
1．S是一个有限集，它的每个元素称为一个状态；
2．Σ是一个有穷字母表，它的每个元素称为一个输入字符。所以也称Σ为输入符号字母表；
3．f 是一个从S*Σ到S的(单值)部分映射。f(s,a)=s’意味着：当前状态为s，输入字符为a时，将转换到下一状态s’。我们把s’称作s的一个后继状态；
4．s0是S中的一个元素，是唯一的一个初态，也称为开始状态。
4． Z是S的子集，是一个终态集（可空）。终态也称可接受状态或结束状态。
确定有限自动机（DFA）可以表示成一张（确定的）状态转换图。
.4.2.1.2.4. 非确定有限自动机（NFA）
一个非确定有限自动机（NFA）M是一个五元式
M=(S, Σ,f,S0,Z)
其中，
1．S是一个有限集，它的每个元素称为一个状态；
2．Σ是一个有穷字母表，它的每个元素称为一个输入字符。所以也称Σ为输入符号字母表；
3．f 是一个从S*Σ*到S的子集的映射。即
f: S*Σ*à2S
4．S0是S中的一个子集，是非空初态集。
5． Z是S的子集，是一个终态集（可空）。
非确定有限自动机（DFA）可以表示成一张（非确定的）状态转换图。
DFA是NFA的特例。但是，对于每个NFA M存在一个DFA M’，使L(M)=L(M’)。
.4.2.1.2.5. 确定有限自动机的化简
所谓一个确定的有限自动机M的化简是指：寻找一个状态数比M少的DFA M’，使得L(M)=L(M’)。
我们说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。
所谓有穷自动机的多余状态，是指这样的状态：从该自动机的开始状态出发，任何输入串也不能到达的那个状态。
假定s和t是DFA M的两个不同的状态，我们称s和t是等价的：如果从状态s出发能读出某个字α而停于终态，那么同样，从t出发也能读出同一个字α而停于终态；反之，如果从状态t出发能读出某个字α而停于终态，那么同样，从s出发也能读出同一个字α而停于终态。如果DFA M的两个状态s和t不等价，则称这两个状态是可区别的。
我们介绍一个方法，叫做“分割法”，来把一个DFA M(不含多余状态)的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。
对DFA M的状态集S进行分划的步骤：
1） 把S的终态和非终态分开，分成两个子集，形成基本分化Π。
2） 假定到某个时候Π已含m个子集，记Π={I(1),I(2),…,I(m)},并且属于不同子集的状态是可区别的。然后检查Π中的每个I看能否进一步分划。对于某个I(i),令I(i)={s1,s2,…,sk},若存在一个输入字符a使得Ia(i)不全包含在现行Π的某一子集I(j)中，就将I(i)一分为二：I(i1)和I(i2)，使得I(i1)中的状态和I(i2)中的状态是可区别的，这样就形成了新的分划Π。
3） 重复2），直到Π所含的子集数不再增长为止，得到最后的分划Π，对于这个Π中的每一个子集，我们选取子集中的一个状态代表其他状态，这样得到的DFA M’和原来的DFA M是等价的。
.4.2.1.2.6. NFAàDFA的转换
定理：设L为一个由不确定的有穷自动机接受的集合．则存在一个接受L的确定的有穷自动机。
子集法：一种将NFA转换成接受同样的语言的DFA的算法。下面详细介绍：
基本思想：该DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。也就是说，在读入输入符号串a1a2…an之后，该DFA处在这样一个状态，该状态表示这个NFA的状态的一个子集T，T是从NFA的开始状态沿着某个标记为a1a2…an的路径可以到达的那些状态。
算法：
对于一个NFA Mn=(Sn, Σn,fn,S0n,Zn),我们按下面的方法构造一个Md=(Sd, Σd,fd,S0d,Zd)，使得L(Mn)=L(Md)：
1) Md的状态集Sd由Sn的一些子集组成 (构造Sn的这些子集的算法将在后面给出) 。
我们用[Sd1，Sd2，…，Sdj]表示Sd的任意一个元素，其中Sd1，Sd2，…，Sdj是Sn的状态。并且约定，状态Sd1，Sd2，…，Sdj是按某种规则排列的，即对于子集{ Sd2，Sd1}来说，Sd的状态就是{ Sd1，Sd2}；
2) Md和Mn的输入字母表是相同的，即是Σd =Σn；
3) 转换函数fd是这样定义的：
fd ([Sd1，Sd2，…，Sdj]，a)＝ε-closure(move（[Sd1，Sd2，…，Sdj]，a))；
4) S0d=ε-closure(S0n)；
5) Zd ={[Sdp，Sdq，…，Sdr]| [Sdp，Sdq，…，Sdr] ∈Sd & { Sdp，Sdq，…，Sdr }∩Zn != Φ}
下面给出构造NPA Mn的状态Sn的子集的算法。
假定所构造的子集族为C,即C=(T1,T2,…,Ti),其中T1,T2,…,Ti为状态Sn的子集：
1．开始，令ε-closure(S0n)为C中唯一成员，并且它是未被标记的；
2． while(C中存在尚未被标记的子集T)do
{ 标记T，
for每个输入字母a （a != ε） do
{ U:= ε-closure (Move(T，a));
if U不在C中 tken
将U做为未被标记的子集加在C中;
}
}
例如：把下图表示的NFA转换成DFA。
.4.2.1.3. 文法
.4.2.1.3.1. 规则
也称重写规则（rewriting rule）、产生式规则（production rule）或生成式，是形如αàβ或α：：＝β的(α,β)有序对。其中α是某字母表V的正闭包V+中的一个符号，β是V*中的一个符号。α称为规则的左部，β称为规则的右部。
.4.2.1.3.2. 文法
一个文法G定义为四元组(VT,VN,S,R),其中，
VT为终结符号集，是个非空有限集；终结符是组成语言的基本符号。
VN为非终结符号(或语法实体，或变量)集，是个非空有限集；非终结符是用来代表语法范畴的；VT∩VN =Φ。
S称作识别符号或开始符号．它是一个非终结符号，至少要在一条规则中作为左部出现；
R为产生式(也称规则)的集合, 每一个产生式为αàβ, α，β∈（VT∪VN）*，且α必须至少包含一个非终结符，并且不能是空字符；R 中至少有一个产生式中的α得由S 来充当。
通常用V表示VT∪VN,V称为文法G的字母表或字汇表。
例如：G=( VT ={0，1}, VN ={S},S,R={Sà0S1,Sà01})
文法的三个作用：
1）生成：产生语言L中所有的句子；
2）判定：一个字符串（String）是否属于语言L；
3）分析：得到L中句子的结构树；
.4.2.1.4. 语言
.4.2.1.4.1. 直接推导/推导/可推导出
对于文法G＝(VT,VN,S,R)，我们称αAβ直接推导αγβ，即
αAβ==>αγβ
仅当Aàγ是R中的一产生式，且α，β∈（VT∪VN）*。如果α1==〉α2==〉…==>αn，则称这个序列是从α1到αn的一个推导。若存在一个从α1到αn的推导，则称α1可推导出αn。
用α1=+=>αn表示：从α1出发，经一步或若干步，可推导出αn；
用α1=*=>αn表示：从α1出发，经0步或若干步，可推导出αn；
.4.2.1.4.2. 最左推导/最右推导
最左推导：任何一步α==>β都是对α中的最左非终结符进行替换的。
最右推导：任何一步α==>β都是对α中的最右非终结符进行替换的。
在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。
.4.2.1.4.3. 句型/句子/语言
对于文法G＝(VT,VN,S,R)，如果S=*=>α，则称α是一个句型。仅含终结符好的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。
L(G)={ α|S=+=>α &α∈VT*}
对于文法G1，G2，若L(G1)＝L(G2)，则称文法G1和G2是等价的。
.4.2.1.4.4. 递归语言和可递归枚举的语言
递归语言(Recursive langag)
如果能编写一部程序，它在读入一个符号串后能最终判断这个串是或不是某种语言的一个句子，就说这种语言是递归的。
可递归枚举的语言(recursively enumerable language)
如果能编写—部程序，使之能以某种顺序逐个地输出(即枚举)一种语言的句子，就说这种语言是可递归枚举的。
.4.2.1.5. 形式语言
乔姆斯基(Chomsky)于1956年建立形式语言的描述。
乔姆斯基把文法分成四种类型，即o型、1型、2型和3型。这几类文法的差别在于对
产生式施加不同的限制。
对于文法G＝(VT,VN,S,R)，
0）如果G的每个产生式αàβ均满足：α∈（VT∪VN）*且至少含有一个非终结符，而β∈（VT∪VN）*，则G是一个0型文法（PSG）。
0型文法也称短语(结构)文法（Phrase Structure Grammars）。一个非常重要的理论结果是，0型文法的能力相当于图灵机(Turning)。或者说,任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。但某些语言不是递归的。
1）设G为0型文法，若G的每一个产生式αàβ均满足|α|<=|β|，仅仅sàε除外，但S不得出现在产生式的右部，则文法G是1型文法或上下文有关文法(CSG)。
一个等价的定义：
设G为0型文法，若G的每一个产生式都为为αAβ==>αγβ，A∈VN，且γ不是ε，α，β，γ∈（VT∪VN）*，则文法G是1型文法或上下文有关文法。
这一定义表明：只有A出现在α和β的上下文中，才允许用γ取代A。
2）设G为0型文法，若G的每一个产生式为Aàβ,A∈VN，β∈（VT∪VN）*，则文法G是2型文法或上下文无关文法(CFG)，也称为BNF范式（Backus-Naur Form或Backus Normal Form）。
这一定义表明：非终结符的替换可以不必考虑上下文。
上下文无关文法对应非确定的下推自动机。
3）设G为0型文法，若G的每一个产生式为AàαB或Aàα, α∈VT*， A，B∈VN，则文法G是3型文法或正规文法(RG)或右线性文法。
3型文法或正规文法(RG)另一种定义是：设G为0型文法，若G的每一个产生式为Aà Bα或Aàα, α∈VT*， A，B∈VN，则文法G是3型文法或正规文法(RG)或左线性文法。
很显然，对任何一个3型文法G，可以设计一个NFA，它能够且只能够识别G的语言。
四个文法类的定义是逐渐增加限制的，因此每一种正规文法部是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言相正规语言。
各型文法的判定难度：
1）PSG：半可判定
对于一个属于Gtype0的句子L，总可以在确定步内判断出“是”；但对于一个不属于Gtype0的句子L’，不存在一个算法，可以在确定步内判断出“否”。
2）CSG：可判定，复杂度：NP完全 。
3）CFG：可判定，复杂度：多项式 。
4）RG：可判定，复杂度：线性 。
.4.2.1.6. 正规式和有限自动机的等价性
正规式和有穷自动机的等价性由以下两点说明：
1．对于Σ上的NFA M，可以构造一个Σ上的正规式R，使得L(R)＝L(M)；
2．对于Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)＝L(R)。
证明：
1） 为Σ上的NFA M构造相应的正规式R。
我们把状态转换图的概念拓广，令每条弧可用一个正规式作标记。
第一步，在M的状态转换图上加进两个结，一个为x结点，一个为y结点。用ε弧连接到M的所有初态结点，从M的所有终态结点用ε弧连接到y结点。形成一个与M等价的M’，M’只有一个初态x和一个终态y。
第二步，逐步消去M’中的所有结点，直至只剩下x和y结点。在消结过程中，逐步用正规式来标记弧。其消结的规则如下：
最后x和y结点间的孤上的标记则为所求的正规式R。
2） 从Σ上的任一个正规式R构造Σ上的一个NFA M．使得L(M)＝L(R)的方法。
a)把正规式R表示成下图的拓广转换图：
R 或当R=Φ时为:
b) 通过对R进行分裂和加新结的办法，逐步把这个图转变成：每条弧标记为Σ的一个字符或ε。其转换规则是反向利用1）中的消结规则。
例如：为R＝(a|b)*abb构造NFA N，使得L(N)＝L(R)。
.4.2.1.7. 正规文法等价于正规式，正规语言等价于正规集
.4.2.1.7.1. 正规文法等价于正规式
对任意一个正规文法，存在一个定义同一个语言的正规式：反之，对每个正规式，存在一个生成同一语言的正规文法。
证明：
1） 将Σ上的一个正规式转换成文法G＝(VT,VN,S,R)。
令其中的VT＝Σ，确定产生式和VN的元素用如下办法：
a)对任何正规式r，选择一个非终结符S生成产生式Sàr，并将S定为G的识别符号。
b)若x和y都是正规式，对形如Aàxy的产生式，重写成：A—xB，Bày两产生式，其中B是新选择的非终结符，即B∈VN。
c)对已转换的文法中的形如Aàx*y的产生式，置写为
AàxB
Aày
BàxB
Bày，其中B为一新非终结符。
d)对形如Aàx|y的产生式，重写为：
Aàx，Aày
不断利用上述规则做变换，直到每个产生式最多含有一个终结符为止。
2） 将正规文法转换成正规式。
基本上是上述过程的逆过程。最后只剩下一个开始符号定义的产生式，并且该产生式的右部不含非终结符。正规文法到正规式的转换规则列于下表：
文法产生式 正规式
规则1规则2规则3 AàxB，BàyAàxA|yAàx，Aày A=xyA=x*yA=x|y
例如：
1） 将R＝a(a|d)*转换成相应的正规文法；
2） 将文法G=(VT={a,d},VN={S,A}, S,R={SàaA,Sàa,AàaA,AàdA,Aàa,Aàd})转换成相应的正规文法；
.4.2.1.7.2. 正规语言等价于正规集
.4.2.1.8. 正规文法与有限自动机的转换
.4.2.1.8.1. 正规文法到有限自动机的转换
从正规文法G直接构造一个有穷自动机NFA M，使得L(M)＝L(G)：
a) 字母表与的终结符集相同；
b) 为G中的每个非终结符生成M的一个状态，(不妨取成相同的名字)。G的开始符号S是开始状态S。
c) 增加一个新状态Z，做为NFA的终态；
d) 对G中的形如AàtB（其中t为终结符或ε，A和B为非终结符）的产生式，构造M的一个转换函数f(A，t)＝B；
对G中形如Aàt的产生式．构造M的一个转换函数f(A，t)＝Z。
.4.2.1.8.2. 有限自动机到正规文法的转换
从有穷自动机NFA M直接构造一个正规文法G，使得L(G)＝L(M)：
a) 有穷自动机的字母表为文法的终结符号集；
b) 有穷自动机的初态对应文法开始符号；
c) 有穷自动机的转换规则非常简单：
对转换函数f(A，t)＝B，可写一产生式：
A—tB
对可接受状态Z，增加一产生式：
Zàε
.4.2.1.9. 词法
词法分析的主要任务是从左至有逐个字符地对输入字符串进行扫描，产生一个个单词序列，用以语法分析。
正规式用于说明(描述)单词的结构十分简洁方便。而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA，这个NPA或DPA正是识别该正规式所表示的语言的句子的识别器。
.4.2.1.10. 上下文无关文法的语法分析
上下文无关文法有足够的能力描述现今程序设计语言的语法结构。目前广泛使用上下文无关文法作为程序设计语言语法的描述工具。
.4.2.1.10.1. 语法树
语法树也称推导树，它是一种描述上下文无关文法的句型推导的直观方法。
对于上下文无关文法G＝(VT,VN,S,R)的任何句型都能构造与之关联的语法树,这棵树满足下列4个条件：
1．每个结点都有一个标记，此标记是（VT∪VN）*的一个符号；
2．根的标记是S；
3．若一结点n至少有一个它自己除外的子孙，并且有标记A,则A肯定在VN中；
4．如果结点n(标记为A)的直接子孙，从左到右的次序是结点n1,n2,n3,…,nk，其标记为A1,A2,A3,…,Ak，那么AàA1,A2,A3,…,Ak一定是R中的一个产生式。
例：对于文法G＝({S，A}，{ a，b},S,R)，其中R为
(1)SàaAS
(2)AàSbA
(3)AàSS
(4)Sàa
(5)Aàba
构造句子aabbaa的语法树。
.4.2.1.10.2. 文法的二义性
如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。或者说，若一个文法中存在某个句子，它有两个不同的最左(或者最右)推导、则这个文法是二义的。
定理：二义性问题是不可判定的。即，不存在一个算法，它能在有限步骤内，确切的判定一个文法是否是二义的。
.4.2.1.10.3. 语法分析方法
从左到右分析法：即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而识别右边的一个符号。
从右向左分折法：即总是从右到左地识别输入符号串，首先识别符号串中的最右符号，进而识别左边的一个符号。
自上而下分析法：也称自顶向下分析法，面向目标的分析方法。从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。
自下而上分析法：从输入符号串开始．逐步进行“归约”，直至归约到文法的开始符
从语法树建立的方式可以很好理解这两类方法的区别。自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串；自下而上方法则是从输入符号串开始，以它做为语法树的末端结点符号串，自底向上地构造语法树。
下面讨论的都是从左到右分析法。
.4.2.1.10.4. 自上而下分析法
.4.2.1.10.4.1. 问题
在自上而下分析方法中，假定要被代换的最左非终结符号是V，且有n条规则：
Vàα1|α2|…|αn
那么如何确定用哪个右部去替代V呢?有一种解决办法是从各种可能的选择中随机挑选一种，并希望它是正确的。如果以后发现它是错误的，我们必须退回去，再试另外的选择，这种方示称为回溯。显然这样做代价极高，效率很低，这是我们需要解决的问题。
.4.2.1.10.4.2. 递归下降分析法
.4.2.1.10.5. 自下而上分析法
.4.2.1.10.5.1. 基本概念
.4.2.1.10.5.1.1. 短语/直接短语/句柄
令G是一文法，S是文法的开始特号，αβδ是文法G的一个句型。如果有：
S=*=>αAδ且A=+=>β
则称β是句型αβδ相对于非终结符A的短语。特别，如有
A==〉β
则称β是句型αβδ相对于规则Aàβ的直接短语(也称简单短语)。一个句型的最左直接短语称为该句型的句柄。
.4.2.1.10.5.1.2. 规范规约
.4.2.1.10.5.2. 问题
在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，我们暂且把这个子串称为“可归约串”。问题是，每一步如何确定这个“可归约串”，也就是说，在每一步如何选择一个串，使得它是可归约的，而不是不可归约的。
.4.2.1.10.5.3. 算符优先分析法
.4.2.1.10.5.4. LR分析器
.4.2.1.11. 参考文献
1）陈火旺等，《程序设计语言 编译原理》，国防工业出版社
2）《编译原理》，清华大学计算机系列教材
.4.2.2. 状态转移网络
.4.2.2.1. 有限状态转移网络（FSTN）
一个有限状态转移网络(Finite State Transition Network)由一组状态(即结点)和一组弧(用来把一种状态连向另一种状态)所组成：
1） 其中的一个状态被指定为起始状态；
2） 在每条弧上都标注着该语法的终结符(包括词或词类等等)。它表明必须在输入句子中找到这样一个词，才可以进行这条弧所规定的转移；
3） 状态集中有一个名为结束状态的子集。如果输入句子(或短语)的头从起始状态开始，经过一系列的转移，句尾恰好达到结束状态，我们就说这个句子(或短语)被这个转移网络所接受(或识别)。
说明：有限状态转移网络只能用来生成或识别正规(即3型)语言。
例如：下图可以识别“董永喜欢七仙女”的FSTN。
.4.2.2.2. 状态转换表(state transition table)
状态 转移 弧 N V ε
q0 q1
q1 q1 q2
q2 q2 q1
.4.2.2.3. 递归转移网络(RTN)
递归转移网络(recursive transition networks，简称RTN)是对有限状态转移网络的一种扩展，在RTN中每条弧的标注不仅可以是一个终结符(词或词类等)，而且可以是一个用来指明另一个网络名字的非终结符。
说明：
（1） RTN中任何一个子网络都可以调用包括它自己在内的任何其他于网络。
（2） 从生成能力来看，递归转移网络等价于上下文无关语法。
例如：
.4.2.2.3.1. RTN算法（top-down）
.4.2.2.3.1.1. 算法描述----基本概念
子网名称：S, NP, VP等
状态节点：q0, q1, q2；
出边：从当前状态向下一个状态转移的弧；
待分析字符串：w1w2w3…（主意是董永想出来的）；
递归栈：记录来自哪个子网，以及回到上层子网时应处的状态；
当前状态： <当前子网，当前状态节点>
<当前出边，后续状态节点>
.4.2.2.3.1.2. 算法
1． 初始化：当前状态为<S,q0>，字符串指针指向待分析字符串第一个字符，递归栈空。
2． 2．1． 如果当前状态节点不是终止状态：把当前状态节点出边指针指向第一个出边，
2．1．1．如果当前出边的标记为终结符，比较该标记与当前字符串移动指针所指字符
2．1．1．1．如果相等，预测得到验证，构造子树，将当前状态节点设为当前出边的后续状态节点，同时修改当前出边；
2．1．1．2．如果不相等，出边指针指向下一个出边。如果不存在下一个出边并且存在回溯点，则回溯，否则分析失败。
2．1．2．如果当前出边的标记为非终结符，把当前子网名称及当前节点出边的后续状态压栈，并把当前状态节点设为当前子网的开始状态，同时修改当前出边及后续状态。
2．1．3如果当前出边有多重选择，需要设置恢复断点，保存递归栈、待分析字符串、当前ATN状态以及出边列表状态的全部内容，以便回溯时使用。
2．2． 如果当前状态节点是终止状态但不是子网S的终止状态：将递归栈退栈，并将当前状态设置为当前栈顶的状态，转入步骤2继续执行。
2．3． 如果当前状态节点是终止状态并且是子网S的终止状态：
2．3．1．若递归栈已空且待分析字符串已空，则分析成功，结束；
2．3．2．否则，若存在回溯点，回溯。
2．3．3．若不存在回溯点，分析失败。
.4.2.2.3.1.3. 例子
分析“我是县长派来的”：
.4.2.2.4. 扩充状态转移网络（Augmented Transition Network,ATN）
扩充转移网络(augmented transition networks，简称ATN)这种形式体系是1970年W．Woods提出来的，并曾成功地应用于他的著名的LUNAR系统中。
.4.2.2.4.1. 基本思想
ATN语法属于一种增强的上下文无关语法，它的基本思想是继续采用上下文无关语法来描写句子的成分结构；但对语法中的个别产生式增添了某些功能，主要是描写某些必要的语法限制和建立句子的深层结构。
.4.2.2.4.2. ATN对RTN的扩充
ATN在以下三方面对RTN作了扩展和增强：
（1） 添置了一组寄存器(registers)，用来存储分析过程中得到的中间结果(如局部句法树)和有关信息(如名词短语的人称和数，某些成分的语义特征等)。但设置哪些寄存器完全取决于句法分析的需要，并没有硬性的规定；
（2） 每条弧上除了用句法范畴(如词类和短语标记)来标注以外，可以附加任意的测试(test)，只有当弧上的这种测试成功之后才能通过这条弧；
（3） 每条弧上还可以附加某些动作(actions)，当通过一条弧时，相应的动作便被依次执行，这些动作主要用来设置或修改寄存器的内容。
.4.2.2.4.3. ATN形式体系
下面是用BNF定义的ATN形式体系：
<transition—network>::=(<arc-set><arc-set>*)
<arc-set>::=(<state><arc>*)
<arc>::= (CAT<category><test><action>*(TO<next-state>))
|(TST<1abel><test><action>* (TO<next-state>))
|(PUSH<state><test><pre-action>*<action>* (TO<next-state>))
|(POP<form><test><pre-action>*)
|(JUMP<next-state><test><action>*)
<action>:=(SETR<register><form>)
|(SENDR<register><form>)
|(LIFTR<register><form>)
|(ADDL<register><form>)
|(ADDR<register><form>)
<form>::=(GETR<register>)
|(GETF<feature><word>)
|(BUILDQ<template><form>*)
|LEX
|*
|<1isp-function>
<test>::=(x-AGREE<form1><form2>)
|(x-START)|…
说明：
1．终结符/非终结符/*
在BNF的定义中，尖括号及其内部的英文小写字母串表示非终结符；定义式右侧的圆括号和英文大写字母串都是终结符。
在BNF的定义中，“*”号有两种用法：
1) 当它出现在非终结符后面，表示这个非终结符可以出现零次或有限多次；
2) 当它单独出现时，表示输入串中的当前词，
21)在JUMP或POP弧上，它同LEX的值一样，其词形同输入串一致；
22)在一条CAT弧上，它取该词的词根形式，因此，如果LEX＝“stopped”，*＝“stop”；
23)在—条PUSH弧上，对于测试<test>和准备动作<pre-action>来说，*等于当前词，但在该弧后继的动作<action>中，它又代表被这条PUSH弧启动的那个子网络(即下一层)的回送值。
2．五种基本弧型
它们分别是：判类弧CAT，测试弧TST，下推运算弧PUSH，下推返回弧POP和跳弧JUMP。
（1） CAT弧要求当前词必须具有该弧第二个元素<category>所指定的句法范畴，并满足第三个元素<test>所规定的条件，否则不能通过；当一条CAT弧被通过时，输入串中相应的当前词被“消耗”，即导致输入指针前移到下一个词。
（2） JUMP弧不同于CAT弧，它不消耗输入串中的当前词，因此伴随着JUMP弧的转移可以在不对输入串进行任何处理的情况下发生。
（3） 一条PUSH弧意味着一次网络的逆归调用，它的第二个元素＜state＞指明了转向的新网络的名字，后者也是当前分析所要寻找的一个指定成分。发生这种网络转移的情况时，原网络的状态及其计算结果(它们被分别储存在这个网络的许多寄存器中)必须保存在一个堆栈中，以便在新网络的处理结束后(体现在这个新网络的一条POP弧上)能返回原来的状态，并恢复原寄存器的内容。
3．五种基本动作
它们分别是：LIFTR,SETR,ADDL,ADDR,SENDR。它们分别用来对不同层次上的寄存器进行存取操作。如下图所示：
在ATN中，每一个子网络都有自己的一张寄存器表。
SETR把本层寄存器表中一个指定寄存器的内容设置为＜form＞的值。对本层寄存器进行操作的其他两个动作是ADDL和ADDR，前者把＜form＞的值添加到指定寄存器的头上(即表左)，后者把同样的内容附加到指定寄存器的尾端(即表右)。
SENDR是一个仅用于PUSH弧的准备动作，它使得被这条PUSH弧所启动的下一层寄存器表中指定寄存器的内容被设置为＜form＞的值。如果把被PUSH弧所启动的新网络看作是一个子程序的话，那么SENDR的作用就如同是向这个子程序传递参数。
LIFTR是SENDR的逆操作，它把＜form＞的值赋与上一层寄存器表中某个指定的寄存器。
4．form
在每个动作中可以使用许多不同的＜form＞，其中最基本的是变量*和LEX，以及函数GETR，GETF，BUILDQ和其他LISP函数。
变量LEX的值总是等于输入串中的当前词，其词形保持和输入串中一样，也即维持词法分析以前的原始形式。变量*是指输入的当前项，它的值已在前面介绍过了。
函数GETR回送的是本层寄存器表中指定寄存器的当前内容，如果该寄存器未曾赋值，其回送值为NIL。
GETF检查指定词＜word＞的词典条目，并回送该条目中指定特征＜feature＞的值。如果＜word＞省缺，就默认是输入串中的当前词。因此，(GETF NUMBER)回送的是当前词的“数”特征——SG (单数)或PL(复数)。
BUILDQ是一个用来建造局部结构的函数，它的第一个变元是一个由常量和特殊标记组成的任意样板，第二个变元是 (form)。它通过用＜form＞的值去依次取代样板中那些特殊标记，然后把所得结果作为局部结构回送出来。在样板＜template＝中用到的特殊标记有如下几种：
+ 它预期相应的＜form＞是一个寄存器的名字，并要求用该寄存器的内容去取代这个特殊标记。
# 它预期相应的＜form＝是一个LISP表达式，要求对这个表达式求值，然后用这个值去取代标记#。
* 要求用变量*的值来取代它，它不需要有相应的＜form＞。
@ 出现在表达式(＠x1 x2 … xn)中，它利用LISP的APPEND函数把子表x1…xn拼接成一张大表，它也不需要有相应的(form)出现。
5．测试谓词
用于弧上测试的谓词很多，例如x-AGREE代表着DET-N-AGREE，SUBJ-V-AGREE等一组用来检查两个表达式之间某种一致关系的谓词。x-START是另一组所谓“向前看谓词”，通常用于JUMP和PUSH弧。例如，IMP-START用在起始状态为S的一条外射的JUMP弧上，以便测试输入句子的开头有没有一个无时态动词；Q-START用来检查句子是否以一个疑问词作为开头。PP-START用在一条(PUSH PP／…)的弧上，以便测试下一个词是否为介词。
.4.2.2.5. 弧上带输出的FSTN：Transducer
.4.2.2.6. 参考文献
1） 石纯一、黄昌宁、王家钦，《人工智能原理》，清华大学出版社
2） 詹卫东，《计算语言学概论》讲义，北京大学中文系
.4.2.3. 特征结构与合一运算
.4.2.3.1. 特征结构与复杂特征结构
1） 一个特征结构（Feature Structure，Fs）是一个特征描述二元组<Attribute : Value>，其中前一项称作“特征名”（或“属性”），后一项称作“特征值”（或“属性值”）。“特征名”是一个字符串；“特征值”可以是一个字符串值或数值等原子值类型(atom)，也可以是另一个特征结构，这就是所谓的特征结构的“嵌套”；两个特征可以共享一个值，这是所谓的特征值的“共享”。“嵌套”与“共享”（也有人称为“重入”）是“特征结构”的两个主要性质。
2） 一个复杂特征结构（Complex Feature Structure ，CFs，也称复杂特征集）是由一个以上的特征结构组成的特征结构列表（list）。
3） 复杂特征集的形式定义：
α为一复杂待征集，当且仅当α可用
的形式来表示，n＞=1；而且特征名fi为原子，特征值vi为原子或复杂特征集。式
α(fi)＝vi
读作：集α中特征fi的值等于vi。
4） 在句法结构的表示中对每个结点附加上复杂标记，而不象原先的短语结构语法那样只标注句法范畴一类的单一标记，不仅有效地解决了原先只能通过转换才能解决的某些语言现象，而且为句法和语义分析的有机结合创造了条件。
5） 特征结构示例（框式表示法）
特征结构的表表示法
((主语: (词语:董永)(词性:名词)(数:单数))
(谓语: (述语:(词语:喜欢)(词性:动词))
(宾语:(词语:七仙女)(词性:名词)(数:单数))))
.4.2.3.2. 合一运算（Unification）
指对两个特征结构进行类似于但不同于集合求并的一种运算，从而可以在“小”的特征结构基础上形成“大”的特征结构，这种运算非常适于刻划“小”的语言单位发展为“大”的语言单位的过程。
1．合一（Unification）的形式定义：
我们如果用符号“?”表示合一。
定义：合一（?）
1． 若a与b均为原子，则a ? b＝a，当且仅当a＝b；否则a ? b＝ф；
2． 若α与β均为复杂特征集，则
(1) 若α(f)＝v，而β(f)的值未定义，则f＝v属于α?β；
(2) 若β(f)＝v，而α(f)的值未定义，则f＝v属于α?β；
(3) 若α(f)＝v，β(f)＝v’，则f＝(v ?v’)属于α?β；否则α?β＝ф。
说明：
1． 从以上定义来看，这是一个递归定义。由于f的值v和v’本身又可以是复杂特征集，因此仅当v和v’可以合一时，α与β才能合一。
2． 如果把自然语言看作是一个信息传递系统，并且承认自然语言的合成性(composMonality)假设，即无论是句法成分还是语义成分都是按由小到大的方式逐步组合出来的，那么采用合一作为句法和语义分析的基本运算是非常理想的。
.4.2.4. *FUG
功能合一语法（Functional Unification Grammar）是M.Kay于1979年提出的，他最早把合一运算引入语法理论。
.4.2.4.1. 基本特点
a) 最大的特点就是词条定义、句法规则、语义信息以及句子的结构功能表示全部都可以用复杂特征集来表示，复杂特征集在FUG中被称作功能描述(FD)。
b) 弱化线性序结构关系；
c) 强调功能结构；
d) 对所有语言单位统一采用FD形式描述；
e) 适合于生成（Generation）。
.4.2.4.2. 一个基于合一的应用型形式语法系统
1）产生式规则：一个语言的基本范畴及其组合类型
2）合一等式：基本范畴之间发生组合关系的条件；
3）树结构+特征结构：描述句子的结构关系，语义关系信息。
.4.2.4.3. 从一个简单的例子说起
S=“一件衣服”
S的内部组成情况：
mp + np , 定中结构, mp是定语,np是中心语；“一件”跟“衣服”可以组合成定中结构；
S的外部功能情况：
S作为一个整体是一个名词短语（np），可以充任主谓结构的主语，述宾结构的宾语，定中结构的中心语；不能充任述补结构的补语，定中结构的定语，状中结构的状语和中心语。
.4.2.4.4. 规则
&& {R1}np-> mp !np ::
$.内部结构=定中,$.定语=%mp,$.中心语=%np,$.dingyu=否,…, ①
%np.数量名=是,…, ②
IF %mp.量词子类=个体THEN %np.个体量词=%mp.原形ENDIF,…③
&& {R2} mp -> m !q ::
$.内部结构=定中,$.定语=%m,$.中心语=%q,$.dingyu=是,…,
&& {R3}np-> !n ::
$.内部结构=单词
注：
①说明np的内部结构，定语，中心语，以及功能特征等；
②说明对中心语np的约束条件（独立条件）；
③说明对定语mp与中心语np之间的相互约束条件（组配条件）。
.4.2.4.5. 词典
一 [词性:m,数词子类:基数]
件 [词性:q,量词子类:个体,表数:数]
衣服 [词性:n,名词子类:na,数量名:是,个体量词:件|套,…]
心胸 [词性:n,名词子类:ne,数量名:否,…]
.4.2.4.6. “一件衣服”的分析结果
衣服词语内部结构件词语单词短语类型中心语词语单词内部结构短语类型定语定中内部结构短语类型内部结构短语类型
.4.2.4.7. 参考文献
f) Martin Kay, 1979, Functional Grammar, In Proceedings of the 4thAnnual Meeting of the Berkeley Linguistics Society.
g) Martin Kay, 1985, Parsing in Functional Grammar, In D.Dowty, L.Karttunen, and A.Zwicky eds, Natural Language Parsing, Cambridge University Press, Cambridge, 1985.
.4.2.5. *LFG
词汇功能语法（Lexical Functional Grammar）是J．Bresnan和R．M．Kaplan于1982年提出的。
.4.2.5.1. 基本特点
基本思想：
依托短语结构语法已有的树结构，通过自底向上（bottom-up）层层传递的方式把词汇所负载的各种信息传播、汇集到上层节点中去，最终形成关于一个句子的完整的结构信息和功能信息描述。
分析结果：
C-结构（constituent structure）：对句子的句法结构树描述 ；
F-结构（functional structure）：对句中各成分的功能描述；
.4.2.5.2. 带“修饰”的Rewriting Rule
Sà NP VP
(↑SUBJ)=↓↑=↓
VPà V NP
↑=↓ (↑OBJ)= ↓
VPà V
↑=↓
NPà N
↑=↓
注：↑表示父亲节点；↓表示当前节点；↑SUBJ 表示父亲节点的SUBJ特征；＝表示合一。
.4.2.5.3. 词汇信息描述（特征结构）
董永 N (↑LEX)=’董永’
(↑SEM)=HUMAN
(↑PERS)=3
七仙女 N 同上
喜欢 V(↑PRED)=’喜欢<(↑SUBJ), (↑OBJ)>’
(↑SUBJ SEM)=HUMAN
(↑OBJ SEM)=HUMAN
.4.2.5.4. C－结构
.4.2.5.5. 从C－结构到F－结构
.4.2.5.6. 从成分结构导出功能方程
1. x1.SUBJ = x2
2. x1= x3
3. x3.OBJ = x4
4. x2.LEX = “董永”
5. x2.SEM = HUMAN
6. x2.PERS = 3
7. x3.PRED = “喜欢<( x3 SUBJ),( x3 OBJ)>”
8. x3.SUBJ.SEM = HUMAN
9. x3.OBJ.SEM = HUMAN
10. x4.LEX = “七仙女”
11. x4.SEM = HUMAN
12. x4.PERS = 3
注：”.” 相当于“的”
.4.2.5.7. 从功能方程求解功能结构
x1= x3=
x2= x4=
“董永喜欢七仙女”的功能结构：
FS(x1)=
.4.2.5.8. LFG检查句子合法性的标准
1)一个属性只允许有一个值（唯一性）；
2)每个属性都应该有值（完备性）；
3)不该有的属性不应该有值（一致性）。
.4.2.5.9. 参考文献
1）Kaplan, R. and J.Bresnan, 1982, Lexical-Functional Grammar : A Formal System for Grammatical Representation, In J.Bresnaned. The Mental Representation of Grammatical Relations, MIT Press 1982.
2）http://www-lfg.stanford.edu/lfg/bresnan/
3）http://www.parc.xerox.com/istl/members/kaplan/
.4.2.6. GPSG
广义短语结构语法(Generalized Phrase Structure Grammar)是Gazdar等人于1985年提出的。
.4.2.6.1. 基本特点
语法模型：
基本规则-> 合格性检查-> 树结构
基本规则：
直接支配规则（Immediate Dominance Rule）
元规则（Meta Rule）
合格性检查：
特征共现限制（Feature Co-occurrence Restriction）
线性顺序描述（Linear Precedence Statements）
……
.4.2.6.2. 参考文献
1） erald Gazdar, EwanKlein, GeofferyK. Pullum, Ivan A. Sag, 1985, Generalized Phrase Structure Grammar, Oxford, England, Blackwell Publishing and Cambridge, 1985.
2） http://www.cogs.susx.ac.uk/lab/nlp/gazdar/gazdar.html
.4.2.7. HPSG
中心词驱动的短语结构语法（Head-Driven Phrase Structure Grammar，也称核驱动的短语结构语法）。
.4.2.7.1. 基本特点
1） 强调中心词在短语结构规则中的作用
中心语—补足语规则（Head -Complement Rule）
中心语—指示语规则（Head -SpecifierRule）
中心语—修饰语规则（Head -Modifier Rule）
2） 产生式规则＋特征结构＋合一运算
3） 基于中心词的属性特征传递（Head Feature Principle, …）
4） 以同样的形式化方式表达句法知识和语义知识
.4.2.7.2. 参考文献
1）Pollard, Carl andIvagA. Sag. 1987. Information Based Syntax and Semantics. CSLI Lecture Notes, No.13, The University of Chicago Press,Chicago.
2） Pollard, Carl andIvagA. Sag. 1994. Head-Driven Phrase Structure Grammar. The University of Chicago Press,Chicago.
3）Sag, Ivan A. & ThomasWasow, 1999, Syntactic Theory: A Formal Introduction, CSLI Publications, Stanford, California.
4）http://ling.ohio-state.edu/research/hpsg/
5）http://hpsg.stanford.edu/
.4.2.8. PATR-Ⅱ
.4.2.8.1. 基本特点
在独立的CFG基础上增加特征结构与合一运算
在规则中引入附加范畴（比如通配符*. %）
在合一式中引入函数（比如morph_gen()）
引入逻辑表达符号增强规则表达能力（比如多个合一式之间可以有析取关系）
.4.2.8.2. 参考文献
1）Shieber, Stuart M., 1984, The Design of a Computer Language for Linguistic Information, In Proceedings of Coling84(10th), Stanford University, Stanford, California.
2）Shieber, Stuart M., 1985, Using Restriction to Extend Parsing Algorithms for Complex-feature-based Formalisms, In Proceedings of the 22ndAnnual Meeting of the ACL, University of Chicago, Chicago, Illinois.
3）Shieber, Stuart M., 1986, An Introduction to Unification Based Approaches to Grammar, CSLI Lecture Notes Series, No.4, Stanford University.
4）http://www.eecs.harvard.edu/~shieber/
.4.2.9. LSP和LST
语言串分析器(Linguistic String Parser，简称LSP)是由美国纽约州立大学N．Sager所领导的研究小组设计的，系统的设计目标是处理为情报检索服务的大量科技文献，所以强调它所建立的英语语法系统应当有广泛的覆盖面。这部以美国语言学家Z.Harris(N.Chomsky的老师)的语言串理论为基础的英语语法包括了大约250条上下文无关规则和200条限制。系统的词典收入9500词条。这个系统已经被用来分析医院的病历和医学、生理学方面的文献。
.4.2.9.1. 语言串理论(LST)
（2） 语言串理论利用特定的句法范畴(名词、时态动词等)、一组基本串和规则来把某些基本串结合成为句串；
（3） 通过对句子中某基本串的一个元素的左边或右边插入一个附加串(adjunct string)，任何句串都可以形成一个更复杂的句串；
（4） 句子还可以通过插入连接串(conjunct string)来得到扩充；
（5） 串理论允许串中的一个元素被一个置换串(replacement string)所取代；
（6） 语言中的每个词都根据其语法特性注上一个或多个词类。据此每个词序将伴随着一个或多个同类序。语言串理论认为语言的每个句子至少有一个词类序是一个句串，即它是由一个中心串通过附加、连接和置换建立起来的。但是，并不是选自正确词类的词的任何一种组合被插入到一个句串便一定能形成一个合法的句子。
例如：
中心串(noun tensed—verb noun)：programmers write code.
è添加附加串：Programmers at our installation write lengthy code.
è插入连接串：Programmers at our installation wrtte and debug lengthy code.
è使用置换串：中心串中后一个noun置换成noun that tensed—verb adj,变成
programmers write code that proves excellent.
.4.2.9.2. 参考文献
1） 石纯一、黄昌宁、王家钦，《人工智能原理》，清华大学出版社
.4.2.10. *TG
转换生成语法（Transformational-generative Grammar），20世纪50年代后期由Chomsky创建。
Z．Harris提出了语言转换理论。Chomsky作为Harris的学生后来大大发展了转换语法的思想，并创立了转换生成学派。
.4.2.10.1. 参考文献
1) 石纯一、黄昌宁、王家钦，《人工智能原理》，清华大学出版社
2)
.4.2.11. *GB
.4.2.11.1. 参考文献
.4.2.12. MP
.4.2.12.1. 参考文献
.4.2.13. DCG
定子句语法（Definite Clause Grammar）。1980年英国爱丁堡大学Pereira和Wanen发表了第一篇定子句语法(Definite C1ause Grammar，简称DCG)的论文。论文证明DCG是一种增强的上下文无关语法(Augmented Context—Free Grammar，简称ACFG)，它的效能至少不低于著名的ATN语法，尤其重要的是用定子句表达的语法规则本身就是逻辑程序设计语言Pro1og的可执行程序，换句话说Pro1og系统可以直接解释用DCG形式书写的语法规则，而无需象ATN那样另外再设计一个句法分析器(或规则解释程序)来完成这个任务。
.4.2.13.1. 参考文献
1）Pereira, F.C.N., and D.H.D. Warren, 1980, Definite Clause Grammars for Language Analysis -A Survey of the Formalism and a Comparison with Augmented Transition Networks, In Artificial Intelligence, Vol.13, pp231-278, 1980.
.4.2.14. Lingware
.4.2.14.1. 参考文献
.4.2.15. TAG
Tree Adjunct Grammar，树邻接语法。
.4.2.15.1. 参考文献
1）A. Joshi, L. Levy, & M. Takahashi, 1975, Tree Adjunct Grammar, Journal of Computer & System Science, 1975, 10(1): pp136-163.
2）AnneAbeillé, OwenRambow, 2000, Tree Adjoining Grammars : Formalisms, Linguistic Analysis and Processing, CSLI Publications.
3）http://www.cis.upenn.edu/~xtag/
.4.2.16. *LG
Link Grammar，链语法。
.4.2.16.1. 基本特点
2) 链语法（Link Grammar）不是建立在树结构的基础上，而是将语言知识完全落实到词汇基础上，通过词语的链接（Link）属性，来对句子进行分析。
3) 链语法对句子的分析结果表现为句中词汇之间的链接关系，即不是“树”结构，而是“图”结构。
4) 跟其他形式语法系统相比，链语法是持强词汇主义观点的形式语法系统。它并不强调语言成分的层次组合关系，而是从词汇的局部着眼，力图揭示:一个句子中任意两个词之间是否有联系，以及是什么联系。
.4.2.16.2. 以链语法的眼光看句子的构成
词典中带链接的词：
由词链接而成的句子：
.4.2.16.3. 基本概念
一个语言的一部链语法就是该语言中的单词的集合，并且对每个单词都定义了它的链接要求（linking requirement）。单词的链接要求可以通过一个或若干个链接表达式（formula of connector）指定。
.4.2.16.4. 一个链语法实例
单词 链接表达式 说明
a D+ D是链接冠词（Determiner）和名词的链
the D+ +表示向右链接
cat D-& (O-or S+) O是链接动词和宾语（Object）的链
snake D-& (O-or S+) S是链接动词和主语（Subject）的链
chased S-& O+ & 表示逻辑上的“并且”关系
ran S- -表示向左链接
Mary O-or S+ or 表示逻辑上的“或”关系
dog {@A} & D- @A表示该单词可以有多个A链接
.4.2.16.5. 链接表达式的定义
（1）一个链接表达式由链接子（connector）、二元操作符（&，or）以及圆括号（规定了组合符合的优先顺序）组成。只含一个链接子的链接表达式有时简称为链接子；
（2）一个链接子由链名（name）和链接方向（direction）两部分组成；
（3）链名是个符号串，用于标记两个单词之间的关系；
（4）链接方向有两个，向左（-）和向右（+）；
e.g. Cat : D-& (O-or S+)
.4.2.16.6. 链接表达式的内部顺序
如果一个链接表达式由多个链接子组合而成，其中有并列关系的链接子之间是有顺序要求的，比如：“cat”的链接表达式是：
D-& (O-or S+)
就不能写成：(O-or S+) & D-。
如果写成后者，就会出现先有O链，再有D链的情形。
.4.2.16.7. 链接子的满足
单词串中某个单词如果有一个向右的链接子，例如X+，而另一个单词有一个向左的链接子X-，那么这两个链接子相互匹配(match)，在这两个单词之间就可以画一条X链。这时，我们说链接子X+或X-得到了满足(Satisfication)或说存在一个链接，满足了链接子X+或X-。
.4.2.16.8. 链接表达式的满足
链接表达式X & Y要被满足，则链接必须同时满足链接子X和Y。
链接表达式X or Y要被满足，则链接必须至少满足链接子X和Y中的一个。
.4.2.16.9. 用链语法来检查句子合法性
对于一个由单词组成的串（S），如果根据一部链语法（LG），S中所有单词的链接要求都得到满足且每个链接要求都只被满足一次，并且所有的链接符合下面4条元规则（Meta Rule）的要求：
平面性（Planarity），链与链之间互相不交叉；
连通性（Connectivity），所有的单词应该链在一起，形成连通图。
顺序性（Ordering），链接表达式中靠前的链接子跟距离该单词较近的单词链接，链接表达式中靠后的链接子跟距离该单词较远的单词链接。
排它性（Exclusion），一对单词之间不能同时有两个链接。
就说S是LG所定义的语言中的句子。使得S合法的全部链接称为一个链接集（Linkage），链接集就是链语法分析句子的结果，如同一般的CFG分析结果为句法树那样。
.4.2.16.10. 应用示例
(1)
(2)
(1)合法；（2）非法
.4.2.16.11. 参考文献
1） 链语法由美国CMU（卡耐基梅隆大学）计算机学院的DanielSleator和美国Columbia University（哥伦比亚大学）音乐系的DavyTemperley共同提出，最早的文章是1991年的一个技术报告，题目是“Parsing English with a Link Grammar”（CMU-CS-91-196, October 1991）
见：http://citeseer.nj.nec.com/sleator91parsing.html
2） http://www.link.cs.cmu.edu/link/
.4.2.17. *CG
Categorial Grammar，范畴语法。
.4.2.17.1. 基本思想
把语言中的各种成分对应为某种“类型”/“范畴”，把语言结构的构造过程对应为“类型”/“范畴”之间的演算过程。
.4.2.17.2. 基本概念
1) 范畴语法里面有两种基本范畴：S和N。粗略地理解，S相当于"句子"，N相当于"名词"。
2) 一个语言成分的范畴（类型）由基本范畴S,N加上范畴表达式构造符“/”，“/”，括号“（”，和“）”构成。
3) 范畴构造符“/”表示“左缺”；“/”表示“右缺”，直观上，可以把它们设想为除号，相应地，范畴的构造就可以看成是带有方向的除法运算。括号表示结合顺序。
4) 当两个语言成分之间发生结合关系时，它们相应的范畴则发生对应的“乘法”运算。运算中最关键的操作就是“约分”。
.4.2.17.3. 英语词类的范畴表示法
词类 范畴标注 说明
句子 S 基本范畴
名词 N 基本范畴
不及物动词 N/S 左方缺少主语
及物动词 (N/S)/N或者N/(S/N) 左方少主语，右方少宾语
形容词（做定语） N/N 右方少中心语
形容词（做表语） (S/N)/S 左方少“缺宾语句子”
副词（做前置状语） (N/S)/(N/S) 右方少中心语
副词（做后置状语） (N/S)/(N/S) 左方少中心语
介词（做后置状语） ((N/S)/(N/S))/N 右方少介词宾语
介词（做后置定语） (N/N)/N 右方少介词宾语
冠词 N/N 右方少名词
代词（主格） S/(N/S) 右方少不及物动词
代词（宾格） (S/N)/S 左方少“缺宾语句子”
.4.2.17.4. 范畴演算
1) 句子的构造过程就是语言成分所对应的范畴的演算过程。
2) 一个单词串的演算的结果或者是S，或者不是S，前者即为合法的句子，后者则是不合法的句子。
3) 演算的具体操作分为两种：一种叫做“应用"(Application)，简记为A；一种叫做"合成"(Composition)，简记为C。 应用就是完整的约分，即分母被约掉，只剩下分子作为结果；比如：S/NN-> S NN/S -> S合成就是约分后范畴表达式仍然带着分母。比如：S/(N/S)(N/S)/N -> S/N
.4.2.17.5. 范畴演算示例
He is a clever boy.
1）范畴词典
he S/(N/S)
is (N/S)/N
a N/N
clever N/N
boy N
2）步骤
He is a clever boy.
S/(N/S) (N/S)/N N/N N/N N
-------------------->C
S/N
------------------>C
S/N
--------------------->C
S/N
-------------------------->A
S
.4.2.17.6. 范畴演算的语言学假设
1） 假设了所有结构都是由词汇负载的，这样才能从词汇的范畴标记推导出各个上级结构成分的范畴标记；
2） 假设了所有结合必定是邻接成分的结合，而不可能有跨越邻接成分的超距结合，这样才能依托邻接关系实现范畴标记的约分计算；
3） 假设了严格的语序关系，这样才能从确定方向上找到约分的对象；
4） 假设了每个结构必须填项完备，这样才能在最后获得一个分母约干净了的S标记。
.4.2.17.7. 范畴语法存在的问题
1） 范畴标记和词类不是一一对应的，要在具体的语流中确定具体词的范畴标记有相当的难度，甚至无异于先要理解。
2） 不负载在词上面的结构（如汉语中的联合结构、连谓结构等）就很难纳入范畴语法的框架中去表达。
3） 超距相关的成分（如"王冕死了父亲"中的"王冕"和"父亲"）在范畴语法的框架中无法建立约分关系。
4） 象汉语这样语序灵活、填项经常不完备（省略）的语言，用范畴语法去描述会遇到许多麻烦问题。
.4.2.17.8. 参考文献
1）Lesniewski, 1929,Ajdukiewicz,1935Bar-Hillel,1950, Lambek,1958,1961,Montague,1970,邹崇理,1995,蒋严&潘海华,1998,白硕,1998
2）http://www.cs.man.ac.uk/ai/CG/
.4.2.18. *DG
Dependency Grammar，依存语法。配价语法和词语法是依存语法的两个发展。
.4.2.18.1. Tesniere依存语法的基本框架
关联（Connexion）：句子成分之间的从属关系 。
组合（Jonction）：句子的并列扩展 。
转位（Translation）：词语功能的转移 。
动词是句子的中心，动词支配其他成分，它本身不受支配； 直接受动词支配的有名词词组和副词词组； 名词词组是动词的行动元（actant）； 副词词组是动词的状态元（circonstant）； 行动元的数目就是动词的价数（valence）；
.4.2.18.2. 动词的行动元——配价
零价动词：不支配任何行动元, “例如”
一价动词：支配一个行动元, “游泳”
二价动词：支配两个行动元, “购买”
三价动词：支配三个行动元, “送给”
.4.2.18.3. Robinson提出的依存关系四大公理
2） 一个句子中只有一个成分是独立的；
3） 除独立成分外，句子中其他成分都必须依存于某成分；
4） 句中任何一个成分都不能依存两个以上的其他成分；
5） 如果A成分从属于B成分，而C成分在句中处于A和B之间，则C成分或者从属于A，或者从属于B，或者从属于A,B之间的某个成分。
很显然，跟链语法一样，依存语法描述的是句子中词与词之间的直接关系，而且这种关系是有方向的（支配－从属，一般把支配词称为“主词”，把从属词称为“从词”）。
.4.2.18.4. 依存树与短语结构树
Dependency Relation Tree Phrase Structure Tree
.4.2.18.5. 分析示例
北京 是 我 国 的 首都。
.4.2.18.6. 参考文献
1）依存语法也称从属关系语法，最早是法国语言学家特尼埃尔（L. Tesniere）提出的，其主要思想反映在他去世后于1959年出版的《结构句法基础》（Element de SyntaxeStructruale）一书中。但他在发表于1934年的《怎样建立一种句法》（Comment Construire Une Syntaxe）这篇论文中就已经提出了这一语法思想。
2）Haim Gaifman, 1965, Dependency systems and phrase-structure systems. Information and Control, Vol.8, No.3, pp304-337.
3） Jane J. Robinson, 1970, Dependency structures and transformational rules. Language, 46:259-285.
4） Geert-Jan M. Kruijff，Dependency Grammar，http://www.coli.uni-sb.de/~gj/Lectures/DG.ESSLLI/esslli-heads+dependents.pdf
5） http://www.cs.bham.ac.uk/research/conferences/esslli/notes/hudson/
6） http://ufal.mff.cuni.cz/dg.html
7） 冯志伟，1983，《特思尼耶尔从属关系语法》，载《国外语言学》1983年第1期
8） Peter Hellwig,1986, Dependency Unification Grammar, Proceedings of Coling’86, Bonn.
9） 吴升（1992），周明、黄昌宁（1994）
10） Michael A. Covington，A Dependency Parser for Variable-Word-Order Languages (1990)，http://citeseer.nj.nec.com/covington90dependency.html
11） Dependency Grammar and the Parsing of Chinese Sentences，http://arxiv.org/PS_cache/cmp-lg/pdf/9412/9412001.pdf
12） Converting Dependency Structures to Phrase Structures，http://hlt2001.org/papers/hlt2001-14.pdf
13） Towards a competitive dependency grammar formalism，http://www.coli.uni-sb.de/egk/talks/RD_Sem_SS02.pdf
14） Functional Constraints in Dependency Grammar，http://titus.uni-frankfurt.de/curric/gldv99/paper/lai/laix.pdf
15） Dependency Grammars and Context-Free Grammars，http://www.vinartus.com/spa/94g.pdf
16） A Fundamental Algorithm for Dependency Parsing，http://webster.cs.uga.edu/~jam/acm-se/review/referee/mc.pdf
17） Dependency Parsing with an Extended Finite State Approach，http://acl.ldc.upenn.edu/P/P99/P99-1033.pdf
.4.2.19. *VG
Valency Grammar， 配价语法。
.4.2.19.1. 参考文献
.4.2.20. WG
Word Grammar，词语法。
.4.2.20.1. 参考文献
1） Richard Hudson, 1984, 1990, Blackwell
2） http://www.phon.ucl.ac.uk/home/dick/wg.htm
3）
.4.2.21. SLM
Statistical Language Modeling,统计语言模型。
.4.2.22. Others
5.语义
.5.1. 总论
每个词的意义是什么，词的意义如何结合成句子的意义，主要指独立于语境的意义。
.5.1.1. 语义研究的发展和现状
.5.1.1.1. 语文学（philology）时期
语文学时期的语义研究，最早的工作是注释古书。语言的研究被当成了了解古代的典籍以及风俗、习惯、制度等的工具。
在欧洲，公元前3世纪，在希腊的亚历山大里亚（Alexandria）和贝尔加木斯(Pergamus)分别聚集了一批学者，专门从事校订、评注等整理古籍的工作，特别是整理荷马（Homer）的史诗伊里亚特（Iliad）和奥德赛（Odyssey）。他们的注意力集中在典籍的语法问题上，同时考订词语的意义。
我国语文学时期的语义研究叫做训诂学。春秋战国时期从义理辞章方面注释《春秋》的《公羊传》和《谷梁传》。汉代训诂学兴起，郑玄注的《诗经》、《周礼》、《仪礼》、《礼记》，倍受推崇。为了解释古书的字义，汉代编成了几部重要的工具书：《尔雅》、《方言》和《释名》。东汉许慎的《说文解字》保存了大量的古义古训和古字字形。晋朝以后我国语文学的重点由训诂学转向音韵学。清代把古音的研究和字义的研究结合起来，打破了文字通假的蒙蔽。
古希腊、罗马、古印度语文学的重点是语法，对语音也很重视。语义不是他们的重点。而我国的训诂学则重点在于字形和字义的关系。
.5.1.1.2. 传统语义学时期
就世界的范围来看，从语文学进入语言学（linguistics）是19世纪初的事。语言学开始成为一门独立的、有自己理论和方法的科学。这个时期语义的研究成了词汇学的重要内容，主要研究词汇学中的语义部分。
传统语义学在理论上对一系列问题作了研究和阐明：
（1）词义、语音、客观事物三者的关系；
（2）词义和概念的关系；
（3）词义的色彩；
（4）多义词、同音词、同义词、反义词；
（5）词义的演变，特别是演变中的扩大、缩小和转移等等。
19世纪以后（含19世纪）语言教学（本族语和外语）、词典编撰、翻译等都有了长足的进步。
传统的语义研究有3个弱点：
（1）它把词义当作一个整体进行研究，没有再把它分解成更小的因素；
（2）没有把词义当作一个系统来研究，而只单纯的就词而研究词义；
（3）它也没有往更大的语义单位（比如句子）去研究，而一直囿于词义。
.5.1.1.3. 现代语义学时期
现代语义学个别流派的破土而出是20世纪二三十年代的事，60年代以后逐步展开。
下面介绍现代语义学的主要流派：
.5.1.1.3.1. 指称论
语义学的一大任务是阐明词语与世界上事物之间的联系。当我们说话的时候，总要用词语来指事物。词语与事物之间的这种联系称为指称(reference)关系。词语叫做指称语(referring expression，又称referential expression，有些语言学著作中简记为R—expression或r—expression)。词语所指的事物叫做所指对象(referent)。
.5.1.1.3.2. 结构语义学
最重要的贡献是语义场理论。
.5.1.1.3.3. 解释语义学
在标准理论中，语义部分的语义规则对句子的深层结构作出语义解释。
.5.1.1.3.4. 生成语义学
语义也有生成性。
.5.1.1.3.5. 菲尔墨的语义理论
格语法。
.5.1.1.3.6. 切夫的语义理论
动词中心论。
.5.1.1.3.7. 数理语义学
.5.1.1.3.8. 情景语义学
.5.1.1.3.9. 概念依存理论
.5.1.1.3.10. 优选语义学
.5.1.1.4. 参考文献
1． 贾彦德，《汉语语义学》，北京大学出版社；
2． 靳光谨，《现代汉语动词语义计算理论》，北京大学出版社；
3． 徐列炯，《语义学》
.5.1.2. “意义”的各种意义
.5.1.3. 意义的分类
.5.1.4. 语义知识的性质和作用
.5.1.5. 语义知识的内容（类型）及其形式化表示
.5.2. 逻辑语义学（形式语义学）
.5.2.1. LFL
逻辑式语言LFL(Logical Form Language)是由美国IBM沃森研究中心M．McCord提出的，它采用谓词----变元的方式表示句子的意思。沃森研究中心已将这种语义表示形式应用于一个大学文档数据库的问答系统和一个英德机器翻译系统。
LFL表达式可以用Prolog语言的项来表示，并由Prolog程序生成。在象数据库查询这样的应用中，LFL表达式可以看作是Prolog的目标而被Prolog系统直接执行，从而产生用户所需的响应。
.5.2.1.1. 逻辑式(即LFL表达式)
逻辑式(即LFL表达式)的形成规则：
1． 如果p是LFL的一个n目谓词，且变元x1，…，xn是常量、变量或逻辑式，则p(x1，…，xn)是一个逻辑式；
2． 如果P和Q分别是逻辑式，则P&Q也是逻辑式；
3． 如果P是逻辑式，E是变量，则P：E(读作“通过E索引的P”)也是逻辑式。
说明：
1） 在规则3中，“：”叫做索引算子。如果P：E是逻辑式Q的一部分，且E在Q中到处被引用，则E可以看作是P及其“语景”的代表。这里的语景包括在自然语言中通常不予明确说明的有关时间和处所的指称。举例来说，假设P代表事件see(john，mary)，那么通过P：E就可以在整个逻辑式中用E来指称该事件。
2） LFL的谓词有两种：一种是以自然语言的词义为基础的，另一种是用来表达句子的时态和语气等信息的非词义谓词。
例如：
John believes that each man knows Bill．
èbelieve1(john，each(man1(x)，know2(x，bill)))．à词义谓词
其中，believe1是动词“believe”的一个义项，manl是名词“man”的一个义项，等等。
John saw Bill．
èpast(See(john，Bill))．à非词义谓词
3） 每个LFL谓词都具有固定数目的变元，这些变元可以是常量、变量或其他逻辑式。
4） 如果在一个谓词中至少有一个变元是逻辑式，我们就称这个谓词是内涵的(intensional)。
下面给出一个代表性的例子：
John only buys books at Smith’s．
èonly((book(x)&buy(john，x))：E，at(smith，E))
.5.2.1.2. 参考文献
1．石纯一、黄昌宁、王家钦，《人工智能原理》，清华大学出版社
.5.2.2. Montague
.5.2.2.1. 发展历史
.5.2.2.2. 参考文献
1．Course note1,Montague Grammar, http://odur.let.rug.nl/~sjaak/semantiek3/coursenotes/3-1.pdf
.5.3. 读书笔记
.5.3.1. 《知网》
董振东，董强，http://www.keenage.com/zhiwang/c_zhiwang_r.html
知网（英文名称为HowNet）是一个以汉语和英语的词语所代表的概念为描述对象，以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库。
常识性知识库è专业性知识库：知识库的框架
知网哲学的根本点是：世界上一切事物（物质的和精神的）都在特定的时间和空间内不停地运动和变化。它们通常是从一种状态变化到另一种状态， 并通常由其属性值的改变来体现。
知网运算和描述基本单位：万物(物质+精神)，部件，属性（数量类，单位类，…），属性值以及事件，时间，空间。
知网遵循这样一种认识：事物的部件在它整体中的部位和功能的描述大体上比照人体。
属性和它的宿主之间的关系是固定的。
概念的共性和个性。
概念间的16种关系：
1） 上下位，同义，反义，对义，相关
2） 实体—值，整体—部件，成品—材料，宿主—属性，属性—值
3） 事件—角色
事件—时间
事件—场所
事件—工具
事件—施事/经验者/关系主体
事件—受事/内容/领属物等
汉字和单纯词à<分析归纳> à （有限的）义原集à<组合>（无限的）概念集。
义原的考核与确定：
1） 当我们发现一个具有多个概念的词语，例如八个，而我们以有的义原不能够把这八个概念区别开来时，我们就必须对我们的标注集加以调整；
2） 如果一个义原在同类别的许多概念中出现或者不同类别的概念中出现，那么这样的义原就是稳定的义原，是一个必须确定的义原。
.5.3.2. 《HNC(概念层次网络)理论》
黄曾阳
清华大学出版社，
http://www.hackchi.com/hnc/menu.asp
http://www.hncnlp.com/hzy.html
认知行为：
(1)局部联想（词汇层面）è概念表述体系
局部联想脉络的出发点是试图形成一种预期及判断能力，以便计算机能够实行一种“自下而上”（bottom-up）与“由上而下”（top-down）相结合的理解处理模式。
(11)抽象概念
(111)五元组（抽象概念的外在表现）：
动态v、静态g、属性u、值z和效应r
任何一个概念都有需要从不同侧面予以表达，这种现象叫做概念的多元性表现。抽象概念需要从动态、静态、属性、值和效应五个侧面加以表达。
(112)概念语义网络（抽象概念的内涵）
对概念关联性的表达是语义网络的首要目标。语义网络是树状的分层结构，每一层的若干节点分别用数字来表示，网络中的任一个节点都可以通过从最高层开始、到该节点结束的一串数字唯一地确定，这个数字串叫做层次符号。
(1121)基元(Φ):两大类
(11211)主体基元概念(6个一级节点)
作用、过程、转移、较应、关系、状态，
它们构成作用效用链。
(11212)复合基元概念（8个一级概念节点）：人类活动
生理本能活动、一般理智活动和社会性活动
(1122)基本(j)：9个一级节点
序与广义空间、时间、空间、数、量与范围、质与类、度、客观的基本属性、含主观评价的基本属性
(1123)逻辑（l）：两大类
(11231)语言逻辑概念（11个一级概念节点）
相当于汉语的虚词。
语义块区分标志符、语义块组合标志符、语义块及句间关系说明符
(11232)基本逻辑概念（jl）：2个一级概念节点
比较、基本判断
(12)具体概念（挂靠展开近似表达方法）
分为物、人、物性三类（分另用符号 w，p，x 表示）。
基本物（７个一级节点）：
热、光、声、电磁、微观基本物、宏观基本物和生命体。
挂靠展开近似表达方法：对一个具体概念，挂靠一个抽象概念，再外加一些对具体概念的描述
(13)概念的表示
三大语义网络为表达抽象概念的内涵而设计，最终将用它来描写自然语言词汇的语义，但网络本身却不是直接面向语言词汇的，而是面向构成词汇语义的概念基元的。网络上的任何节点本身都是概念，它们是概念基元。它们通过不同方式的组合而构成复合概念。
(131)
概念->((类别符号串)(层次符号串)(组合结构符号)(类别符号串)(层次符号串))
类别符号串->(类别符号)*
层次符号串->(高层)((中层)(底层))*|(本体层)(挂靠层)
组合结构符号->(#|$|&|||--0…|*|+|/||||,|;|!|^|()|(,lm,))
类别符号->(v|g|u|z|r|j|Φ|l|s|f|q|h|w|p|x)
中层->(cnk|dnk|k|emk|-|-0|-00…)
层次符号->(0|1|2|3|4|5|6|7|8|9|a|b|c|d)
(132)符号说明：
(1321)类别符号集
(13211)五元组符号：v，g，u，z，r
(13212)抽象概念的类别符号：j ，Φ，l
(13213)具有三大类抽象概念综合特征的抽象概念：s
(13214)“语法”概念符号：f，q，h
(13215)具体概念物和人的符号：w，p
(13216)兼有抽象具体双重特征的物性概念：x
注：这15个类别符号专门用于表达概念的类别特征，不能用于层次符号的变量表示。它们是概念类别的基元表示，其中的基元概念符号Φ在具体表达时可以省去。
(1322)层次符号
高层层次符号的定义见j表，Φ表，l与jl表，jw表
中层层次符号主要用于表达概念局部联想脉络的三类特征:概念的对比性,概念的对偶性，概念的包含性。
对比性概念： cnk 或 dnk k=（1，n）
对偶性概念： k 或 emk k=0，1，2，3或k=4，5，6，7
包含性概念： -，-0，-00…
式中的数字“c，d”是对比性的标志，“e”是对偶性标志（但对常用的对偶性概念基元省略这一标志）。对比性概念用了两个标志是为了区分排序的属性，数字c表示正序，d表示反序。n表示总级数，k表示排序中的值。正序定义为自然顺序，或值的排列从小到大，反序定义为值的排列从大到小。
(1322) 概念组合结构符号集
作用：#
效应：$
对象：&
内容：|
包含：--0…
挂靠结束：*
展开：+
偏正：/
主谓：||
逻辑并：，
逻辑选：;
逻辑非：!
逻辑反：^
括号：()
一般逻辑组合：(,lm,)
(2)全局联想（句子，篇章层面）è语义块和句类
(21)语义块（句子的语义构成单位）：核心部分（也叫语句要素）+说明部分
(211)语义块的构成
(212)主语义块（“不可缺少”）：特征E、作用者A、对象B 和内容C。
E语义块的命名与作用效应链６个环节的名称相一致，即作用X、过程P(process)、转移T(transfer)、效应Y、关系R(relation)、状态S(state)。
作用效应链：
作用存在于一切事物的内部和相互之间，作用必然产生某种效应，在达到最终效应之前，必然伴随着某种过程或转移，在达到最终效应之后，必然出现新的关系或状态。新的效应又会引发新的作用，如此循环往复，以至无穷。
自然语言的主要内容就是对这六个环节进行局部和总体的具体表述，句类划分以此为标准的。作用效应链既是局部联想脉络的基础，又是全局联想脉络的基础，两个联想脉络通过它联系起来，所以，在一定意义上可以说作用效应链是HNC的理论基础。
广义对象语义块是A,B,C语义块的合称。
(213)辅助语义块（“可有可无”）：条件Cn(Condition)、手段Ms(Means)、工具In(Instrument)、途径Wy(Way)、参照Re(Refer)、因Pr(Premise)、果Rt(Result)
(214)语义块的表示
语义块字母定义
类别字母 E，A，B，C；Ms，In，Wy，Re，Cn，Pr，Rt
函数字母 X，P，T，Y，R，S，D
语义块数字定义
类别字母之后 相同类别语义块的各方
函数字母之后 基本句类的子类，通常与 主体基元概念节点的二级甚至三级层次符号对应
例如：张先生怕李小姐发脾气。 X2B+X2+XAC
(22)句类（句子的语义类别）
只表达作用效应链的一个环节的句类称为基本句类，表达两个或多个环节的句类称为混合句类。所谓混合句类，是指两个以上的基本句类在一个句子中共现，诸如作用效应句、过程转移句、状态判断句等。
由E语义块构成的句子，分别命名为作用句、过程句、转移句、效应句、关系句和状态句。根据作用效应链定义的６个句类加上判断句，构成HNC的７个基本句类。
句类分析的知识基础包括概念层面、词汇层面、语句层面、语境层面的知识。这四个层面的知识应以语句层面为中心，并命名为句类知识。
(221)基本句类：七种，分别命名为：作用句，效应句，过程句，转移句，关系句，状态句，判断句。相应的符号为：X，Y，P，T，R，S，D。
(222)混合句类：是指两基本句类的混合。
(223)复合句类：指一个句子存在两个甚至多个E块，而且它们分别含有作用效应链不同环节的信息。
(224) 句类格式:主语义块的排序。
j表：基本概念一、二级概念节点表
节点 含义 说明
J0 序及广义空间
J00 序（一般）
J01 广义空间（广义位置及广义方向）
J02 广义距离
J1 时间
J10 时间
J11 时间的序
J12 时间的间隔
J2 空间
J20 空间
J21 空间的序
J22 空间的距离
J3 数
J30 基本数
J31 数的空间
J32 数的变换
J4 量与范围
J40 全体、局部、个体（包含性）
J41 量（单、双、半；少与多）
J42 范围（界、内、外；跨、起、止）
J5 质与类
J50 内容与形式
J51 质（对比、对偶）
J52 类（包含）
J6 度
J60 度（一般）
J61 量变的度
J62 质变的度
J7 基本属性（客观的）
J70 对比性
J71 对偶性，对仗性
J72 主要与次要
J73 特殊、一般；宝贵、普通
J74 本质、表象
J75 相对与绝对
J76 常规与异常
J77 简单与复杂；纯与杂
J78 新与旧
J8 基本属性（含主观评价） 大体上相应于伦理学
J80 正与邪
J81 真与假；实与虚
J82 善与恶
J83 美与丑
J84 对与错
J85 是与非
J86 积极与消极
φ表：基元概念一、二级概念节点表（表中已省φ）
主体基元概念 作用效应链
0 作用
00 作用
008 物理作用
009 化学作用
01 作用的承受
02 作用的反应
03 作用的免除 反映的一种特殊形式
04 约束 作用的一种特殊形式
1 过程
10 一般过程
100 过程的基本特征
1008 过程的持续
1009 过程的进展
100a 过程的重复
109 运动过程
10a 演变过程
10b 生命过程
11 过程的序
12 过程和因果及源、汇、流
13 过程的趋向及转化
14 过程的新陈代谢
2 转移
20 一般转移
200 转移的入出（基本特征之一）
204 转移的起止（基本特征之二）
209 定向转移
20a 传输
20b 自身转移
21 接收
219 针对性接收
21a 物的接收
21b 信息的接收
22 物的转移
23 信息转移
24 交换、替代及变换
3 效应
30 一般效应
300 效应的基本特征
309 变化
30a 实现及完成
31 产生与消除
32 利与害
33 显露与隐蔽
34 扩展与缩小
35 立与破
36 推动与抑制
37 连断及通阻
38 选、存、弃
39 合分及聚散
3a 获得与付出
3b 积累与消耗
4 关系
40 一般关系
400 关系的基本构成（方面）
401 我方
402 你方
403 他方
404 双方
405 此方
406 彼方
408 关系的相互性
409 关系的紧密性（距离）
40a 关系的传递性
41 结合与分离
42 依存与排斥
43 支持与反对
44 主宰与从属
45 使用与舍弃
46 拥有与失去
47 适应与干扰
5 状态
50 一般状态
500 状态的基本特征
508 自然状态
509 生命状态
50a 人的状态
51 形态
52 动态
53 势态
54 结构
55 层次
56 等级
复合基元概念 主要针对人类活动的表述
6 生理及本能活动
7 心理活动及精神状态
70 心理与精神活动
71 心理反应
710 一般心理状态
711 态度
7110 以理性为主要依托的态度
7111 感情色彩较浓的态度
7112 涉及自身素质或利益的态度
7113 对事业的态度
7114 对利害关系的态度
7115 对人际交往的态度
7116 对一般事物包括公益活动的态度
7117 对亲近关系者的态度
712 愿望
7120 一般愿望
7121 待实现的愿望
7122 已实现的愿望及其效应
7123 要争取实现的愿望
713 情感
7130 一般情感
7131 喜
7132 忧
7133 惧
7134 外触发为主的情绪表现
7135 爱
7136 恶
7137 恨
7138 内因为主的心理反应
7139 悔愧咎
713a 憾
713b 窘
714 情感与精神状态
72 精神状态
720 一般精神状态
7201 意志
7202 注意
721 能动性
7211 先天能动性
7212 后天能动性
722 气质
7221 性格
7222 秉性
8 思维活动
80 一般思维活动
81 认识与理解
810 一般认识与理解
811 分析与综合
812 演绎
813 判断
82 探索与发现
821 探索
822 发现
83 策划与设计
831 策划与计划
832 设计与规划
84 评价与决策
841 评价
842 决策
843 规定
844 约定
845 认定与承认
9 理智活动
A 专业活动
A0 一般专业活动
A00 常规专业活动
A01 一般组织活动
A02 实施
A1 政治
A10 制度
A11 组织
A12 治理与管理
A13 政治斗争
A14 外交活动
A15 征服与反征服
A2 经济
A20 一般经济活动
A21 工业
A22 商业
A23 服务
A24 金融
A25 国家经济
A26 技术经济
A27 自然经济
A3 文化
A30 一般文化活动
A31 文学
A32 艺术
A33 技艺
A34 信息文化
A35 大众综合文化
A4 军事
A40 一般军事活动
A41 组织
A42 战争
A43 战争效应
A44 军事行动
A45 军事技术
A5 法律
A50 一般法律
A51 立法
A52 法律界用法
A53 法律与道德
A54 一般执法
A55 检察
A56 判决
A57 施行
A58 人与法
A59 违法
A5a 关系人用法
A5b 关系人反应
A6 科技
A60 哲理探索
A61 科研活动
A62 技术活动
A63 自然科学
A64 人文科学
A65 理论科学
A66 实验科学
A67 科技与生产力
A68 学科
A7 教育
A70 一般教育
A71 教
A72 学
A73 考
A74 学校教育
A8 卫生
A80 生命卫生
A81 查
A82 治
A83 养
A84 环境卫生
A85 全局性卫生
A86 局域性卫生
A87 局部及个人卫生
B 追求活动
B0 追求
B00 理性追求
B01 行动追求
B02 伴随追求的战斗
B03 对命运的抗争
B1 改革
B10 一般改革
B11 整体或根本改革
B12 局部改革
B2 继承
B20 一般继承
B21 发展继承
B22 消极继承
B23 局部继承
B3 竞争
B30 一般竞争
B31 攻
B32 守
B33 挑战与应战
B4 协同
B40 一般协同
B41 战略协同
B42 战术协同
B43 积极协同
C 社会性活动
D 规约性活动（行为）
D0 行为
D00 一般行为
D01 行为与理智
D02 大公行为
D03 自私行为
D04 对他人的行为
D1 观念
D10 一般观念
D11 根本及全局观念
D12 观点
D2 准则
D20 一般行为准则
D21 社会性准则
D22 交往准则
D23 束已准则
D24 对他人的准则
L与jl表：逻辑概念一、二级概念节点表
语言逻辑概念 大体上相应于汉语的虚词
L0-3 语义块区分标志符 主要相应于传统语言学里的介词, 但包括按传统概念难以注明词性的义项以及在不同语种里词性标记不同但语言逻辑意义相同的词
L0 主语义块单一标志符
L00 特征
L01 作用者
L02 对象
L03 内容
L1 辅语义块单一标志符
L11 方式
L12 工具
L13 途径
L14 比照
L15 条件
L16 动因
L17 目的
L2 主语义块搭配标志符
L20 特征
L21 作用
L22 对象
L23 内容
L3 辅语义块搭配标志符
L31 方式
L32 工具
L33 途径
L34 比照
L35 条件
L36 动因
L37 目的
L4-5 语义块组合标志符 相应于多种词性的虚词，包括关系代词和部分连词、介词以及按传统概念难以注明词性的词
L4 语义块组合标志
L41 偏正
L42 反偏正
L43 并
L44 或
L5 语义块组合说明
L6-a 语义块说明符
L6 时态说明
L7 暂空即目前暂缺
L8 辅要素说明
L9 指代逻辑
La E要素逻辑说明
Lb 语句间逻辑说明
基本逻辑概念 大体上相应于西语的系词和情态动词
Jl0 比较
jl00 两相比较
jl01 集合内相互比较
jl02 与一个标准比较
Jl1 判断
jl11 判断内容
jl111 是，肯定
jl112 否，否定，不
jl115 有，存在
jl116 无
jl12 判断的势态（纯客观）
jl12c31 可能
jl12c32 能够
jl12c33 必然
jl13 判断的势态（含主观）
jl13c21 应该，应
jl13c22 必须，必
jw表：基本物概念一、二级概念节点表
Jw0 热
Jw1 光
Jw2 声
Jw3 电磁
Jw4 微观基本物质
Jw5 宏观基本物
Jw51 气态物
jw518 大气
Jw52 液态物
Jw528 水
Jw53 固态物
Jw538 土
Jw6 生命体
Jw61 植物
Jw62 动物
Jw63 人体
Jw61- 植物部件及组织
Jw62- 动物部件及组织
Jw63- 人体部件及组织
s表：s概念一、二级概念节点表
S1 途径
S11 具体途径
S12 策略
S2 手段
S21 方式
S22 方法
S3 条件
S31 时间条件
S32 空间条件
S33 社会条件
S34 一般物质条件
S35 前提条件
S4 工具
S41 具体工具
S42 材料
S43 原料
S44 能源
.5.3.3. 《汉语语法的意合网络》
鲁川
商务印书馆
.5.4. 参考文献
6.语用
.6.1. 总论
句子如何用于不同的场合，不同的用法如何影响它的解释。
.6.1.1. 谈话的知识
前一句如何影响下一句的解释，对于代词的解释和时态的解释特别重要。
.6.1.2. 世界知识
语言的使用者为执行对话所必须具有的世界的一般知识，包括语言使用者对别的使用者的信念和目标要了解些什么。
.6.2.
7.应用
.7.1. 语义理解在信息处理中的应用
.7.1.1. 系统模型
问题：
1． 概念体系（或者说概念框架）是什么样的，怎样组织的，是否有效？
2． 文章怎样映射成概念体系？
3． 用户兴趣怎样描述为概念体系？
4． 概念体系间怎样运算？
8.原型系统
构造自动采集与语料库生成系统
构造自增式英汉词典（词号与词的对应关系）
构造词性词典（词号与词的对应关系）
构造人名、地名、历史事件词典
构造词的学科词典（一个词属于哪个学科）
构造词的语义词典
构造词的范例词典
基于语料库构造词间统计关系词典
金山词霸
知网
WordNet
9.专题
.9.1. 让机器理解自然语言的哲学思考
要让机器理解人的语言，首先必须回答这样一个问题：什么是语言？也就是说，人的语言的机制是什么？
我们要说，语言是一种符号表示。这一点可以从下面几个现象中得到证实：口语，书面语，体态语都是语言，可见语言可以是声音符号的，也可以是图像符号的，甚至还可以是行为符号的。另外早期的埃及文字，巴比伦文字，以及中国文字，都是象形文字，这也从一个方面反映了语言是一种符号表示系统。而现在的语言则更是一套抽象的符号系统了，连最初的象形意义都不再需要。
那么，这种符号系统要表示什么？又是如何表示的呢？
作者认为，语言这种符号系统，它要表示的是现实的客观世界以及人对这个客观世界的认识。这一点要从以下几个方面理解：
第一，客观世界是语言要描述的本体；但语言描述的世界不等同于客观世界，它是站在人的角度，是人所认识到的那个世界；
第二，人对客观世界的认识，既有人对这个世界的感知，又有人对这个世界的思考，另外还加入了人的情感。
于是问题就变为经典的哲学问题了。但作者不想去讨论物质和意识，思维和存在的关系问题。作者感兴趣的是客观世界à人的感知à人的思维这样的一个链。也就是说，既然语言是对现实的客观世界以及人对这个客观世界的认识的符号表示，那么，人眼中的客观世界是什么样的呢？人又是如何认识客观世界的呢？语言又是如何对现实的客观世界以及人对这个客观世界的认识进行表示的呢？
让我们把人类的历史和人的成长史浓缩到一起，就可以得到一种启发：
我哇哇着地，脑子里一片空白。我能看到，能听到，能触摸到，能闻到，能尝到，一句话，我能感知到。而我的视觉，本能的感受到光线有强弱（亮度），颜色有深浅，距离有远近，方位有不同。而这些都是本能的感受到的，也就是客观世界对我的刺激。但我并不知道光线，颜色，距离，方位这些概念。同样，我能听到声音，而且声音有强弱，以及有声音产生的距离感；我触摸到，让我有了温度和光滑的感受，有疼痛感；我闻到气味；我尝到滋味。
另外，还有两件东西也是与生俱来的。一种是先后感。这种感觉就产生了时间的概念，这是后话；另一种就是利害感，或者说好恶感。这种感觉，似乎达尔文的生物进化论可以予以佐证。而利害感就衍生出人类的复杂感情，这也是后话。
上面的这些就构成了人类的感知能力。
仍然想像我的脑子里一片空白，除了本能的有上面的那些感受之外，没有任何概念。我看到人，看到房子（当然，我是原始人的话，我看不到房子，但我看得到天空，树林，或者山洞什么的），我听到人们的声音，鸟的声音，我闻到奶香，我感受到亲人对我的抚摸等等等等。很显然，我是能感受到这些之间是有区别的，不至于把山洞跟鸟叫混为一体。所以说，区别和细分是人的思维的特点之一。再想像一下，我还是一个婴儿，我每次看到我母亲这样的一个视觉形象的时候，别人都发出“妈妈”这个音，于是我也就发“妈妈”这个音。以后我就把母亲这个视觉形象跟“妈妈”联系在了一起。也就是说，以后每当一个人过来的时候，我首先把她跟脑海中的母亲对照一下，如果一致，我就认定母亲这个视觉形象就是“妈妈”了。我这么说，显然是假定我有记忆能力。
然后又有别的女人Ａ来了，人们让我叫她“阿姨”。于是每次Ａ来了，我都叫她“阿姨”。虽然我并不知道“阿姨”是什么意思，或者说“阿姨”有什么特征。反正我见到她就认定为“阿姨”。
以后又有别的女人B和Ｃ来了，人们也叫让我叫她们“阿姨”，我也就这么叫着，没有感觉什么不对劲的地方。直到有一天又来了一个女人D， 却没有人告诉我该叫她什么。这时候我就在想：我叫她“妈妈”呢还是叫她“阿姨”呢？也许你们会问为什么不叫“姐姐”呢？对不起，我的脑子里没有姐姐这个概念。
也许我会叫她“妈妈”，也许我会叫她“阿姨”。当我叫她妈妈的时候，别人就告诉我：“不对，叫她阿姨”。
“为什么呢？”
“因为生你养你的才是你妈妈。”
于是“妈妈”和“阿姨”就被细分而有了区别。然而后来，“阿姨”在与“奶奶”“姐姐”“姑姑”等等概念的对比中又因为有共同的特征而统称为“阿姨”这一类，或者说因为有共同特征而聚为一类，这就是聚类。
这么说，记忆，认定(或者说符号表示)，模式匹配，细分，分类，聚类就构成了人类思维的特征。首先，人类认定每一个个体，新来的个体总是跟记忆中的个体进行模式匹配，直到为了区别的需要，我们对一个个个体进行细分，因为差异而有了分类，因为有共同点而有了聚类，因为新的分类和聚类而有了重新认定接受，从而又有新的模式匹配。
这样，在人类感知客观世界的基础上，不断的对客观世界和人的感知进行认定，模式匹配，细分，分类和聚类，就形成了人眼中的客观世界。作者认为哲学中的矛盾论是分类和聚类的另一种描述。
上面说的，是构成人的感知能力和思维能力的基础部件。下面我就几个具体的例子来阐述这些部件如何构成较大的单位的。
首先，我来说说感知能力如何构成人的空间和运动的概念。由于人的视觉能够感知光线、颜色、距离和方位，有距离和方位，产生长度的概念，由光线、颜色和长度，产生形状的概念，方位和形状，就构成了空间。而运动呢？运动可以说是光线和颜色的变化，或者是物体空间的变化。时空，运动和静止，这些经典哲学中的概念，就是这样的一个道理。沿着时间轴的一类特殊运动那就是生死存亡。
再说说序这个重要的概念。时间和空间的方位就构成了序。
再说说思维中一种很有名的思维方法：归纳法。由个别为真的实例，按照生长条件（在分类的基础上有共同的属性），所有由这些个别实例生长出来的实例都为真（从而实现了聚类）。
作者认为，人类所有的思维能力，最终都可化为集合上的细分，模式匹配，分类，聚类来处理。
到此为止，似乎我们已经回答了人们是如何感知世界，又是如何思考世界的。而语言就是记载这些并使之条理化的符号。下面引用利奇在《语义学》中的两段话进一步说明语言与客观世界以及人的认知的关系：
“语言是一个单一的概念体系，还是有多少种语言就有多少个概念体系呢？虽然当前许多人的看法倾向于要假设存在一个所有人类语言共有的普遍的概念体系，但是大多数观察表明，各种语言为经验分类的方式是不同的。”
如果不承认人类语言共有一个概念体系而强调各种语言为经验分类的方式是不同的话，那么“各种语言都把自己的‘条条框框’强加于经验，或者换一个比喻来说，就是语言提供了一套‘分类格’，我们根据这些‘分类格’把对世界的认识条理化。”真是这样的话，“一个人使用的语言，在很大程度上影响了他的思维过程和认识客观世界的方式。”
很显然，按我们的看法，各种语言是共有一个概念体系的，之所以各种语言为经验分类的方式不同，是因为各种语言中人们认定，细分，分类，聚类的方式不同而已。
说了这么多，让机器理解语言，到底该怎么做呢？
首先，我们要确定，我们已经认定了多少概念，我们最终要形成一个概念体系；
其次，我们要形成一个新概念的产生体系，这样才能满足我们的知识体系是个开放体系的需求；而这新概念的形成如果是个认定的过程的话，新概念的界定则是模式匹配，细分，分类，聚类的过程。
第三，在前面两条的基础上，我们把语言映射到我们的概念体系上。对语言的理解和处理就化为概念体系上的模式匹配，细分，分类和聚类。
.9.1.1. 参考文献
5． 罗素，《西方哲学史》
6． 冯友兰，《中国哲学简史》
7． 《马克思主义原理》，高等教育出版社
8． 史忠植，《高级人工智能》
9． 石纯一、黄昌宁、王家钦，《人工智能原理》，清华大学出版社
10． 弗里.N.利奇，《语义学》，上海外语教育出版社；
11． 于江生，《语言的哲学问题》，http://icl.pku.edu.cn/yujs/papers/html/what's%20linguistics.htm
12． 杨雄里，《脑研究改变对世界的看法》，http://www.people.com.cn/GB/guandian/183/8778/8779/20020812/798217.html
.9.2. 自然语言理解与人工智能
.9.2.1. AI知识表示方法及推理（19991211）
谓词归约与产生式系统是建立在规则系统的抽象的形式化的描述之上的，表达了人类思维能进行严格推理的一面。他们适合于有限空间的严格推理，加上启发式搜索函数能使搜索空间减小。而人类的思维在计算速度上虽比不上计算机快，却能在求解同样的问题时直接找到最佳或次佳推理路径。
è1）人类具有若干并行处理单元，每个单元的性能并不是很好，但总体上性能却非常好；2）各种求解方法在脑子中的关联程度以及各自的存储程度是不同的。
当人们提到爸爸时，最可能想到的是妈妈，子女，爷爷等等，一般不会想到老虎。
è在逻辑上关联性强的，在人脑的物理存储上关联性也是强的。因此，人脑存在某种连接机制。
语义网络，框架，脚本反映了人类思维的联想能力，分类能力，继承能力和面向对象能力，但联想能力有限，只记述了部分事物的相关性。
人类思维还有记忆能力，且记忆能力有机械记忆和意义记忆，机械记忆儿童擅长，意义记忆成人擅长。记忆时间有长短，这涉及记忆的强度问题。
è记忆时间长短：记忆强度+记忆容量
人们学习某门课程后，过了两三年，全忘了。可是重新温习时，很容易上手且很容易恢复。
è记忆是强度而非容量。记忆有强者生存性。
è人脑具有存放“抛弃知识”的“遗忘角落”。
附：人类还拥有以下认识能力：注意力和观察力；另一方面，人类还具有实践能力，包括自学能力、表达力、交际能力、竞争能力、自控力、创造力、操作能力、适应力。
人类能学习知识，并能从许多知识中提取核心知识，进行组织和表达。
è联想：
1） 事物的相关程度；
2） 事物的可推理性；
3） 相关性>=a，则存储相关性，否则如果在n步内不可推导，则存储相关性，否则不存相关性。
.9.2.2. 从各学科角度考察AI（20000307）
1．各学科
1） 数学à逻辑、命题，<=归纳法、反正法、顺证（直觉）=>正向推理，反向推理，双向推理
人类的推理在更多时候是双向推理。
2） 数据结构à应用
3） 英语
单词：词义辨析，同义词，近义词，反义词
语法
语境
练习
4） 物理、化学：实验事实à（归纳）à猜测à实证、论证
5） 历史：历史事实à（总体感受）à历史规律
6） 哲学、经济学：对现实生活中某些特征的认同
è A)大胆猜测，小心求证
è B)在人的思维中，逻辑并未占据全部，而只是小部分。归纳和对归纳结果的认同，对猜测结果的认同，倒是占据大多数。
è 逻辑<-- (确定性|不确定性)-->目前研究最多的是形式逻辑，而非语义逻辑
2． 人类的智能是随历史而发展的
3． AI对知识的依赖主要表现在对知识的利用，即利用已有的知识进行分析、猜测、判断、预测等。
4． 灵感、潜意识问题。
.9.2.3. 逻辑
思维是培养出来的考虑问题的一种习惯方式。
限定逻辑：从某些事实出发能推出具有某一性质p的对象，就是满足性质p的全部对象。
默认逻辑：正常情况下或典型情况下，断言A成立，则默认在所有情况下，A成立。在出现反例时再纠正。
基于范例学习推理：原范例?(回忆，推导)à目标范例
提出问题à分析问题（==>特征）à解决问题(==>猜测论证)
归纳、类比à猜测à论证
.9.2.4. 现阶段AI研究特点（20000317）
谓词、产生式：过程 默认推理
语义网络、框架：结构（逻辑） 模仿人的思维
神经网络：结构（物理） 归纳学习
意识：人脑对客观事物的反映-->？本身能出发智能性活动
“只可意会不可言传”
人脑的特点：
1． 平时思维并非逻辑的，而是跳跃性的、火化性的
缺点：1）计算速度慢；2）深度浅、广度低
2． 记忆；
3． 想象力、形象思维能力；
4． 时空；
5． 人的思维可培养、可训练（下棋）
目前AI一直在模仿人的思维的个别属性。
人的智能具有其局限性，目前的研究有的超出了人的智能的范围。
预测+统计分析==>结论
who,when,where,what,how,why
.9.2.5. 自然语言理解的几个原则思考（20000307）
1． NLP是项庞大的工程；
2． NLP的学习机制
（20000407）知识学习是一个循序渐进的过程
3． (20000407)NLP、语音识别、MT、ML（归纳、类比、解释等）、DW&DM,CBR
4． 人类无论听说，都极其自然
讲的话要熟，要是人们讲过的话，否则，人们一般都听不懂，要给予解释。
.9.2.6. 我的自然语言理解观（20000317）
1． 以名词为中心，引入对象模型（继承、发展、覆盖等）；
2． 以语义为研究重点，引入元语义、同义词、近义词、反义词；
3． 以语义网络为语义表示形式，引入语义生成规则；
4． 具有学习机制，具有开放性、容错性和智能性；
5． 记忆模型和联想模型；
6． 真正做到语法分析为辅、语义分析为主，形式为内容服务；
7． 对象方法
1） 主体对象（特征描述）：属性+行为；
2） 事件对象（who,when,where,what,how,why）。
8． (20000505)语义理解—从虚词（助词，连词）入手，从“人”入手。
.9.2.7. 人类的语言机制：命名与认同机制（20000421）
1． 对实体的命名与认同机制
对“人”这个实体命名为“人”，但“人”是什么？自古至今，谁也难用文字表达出来。
2． 命名的模糊性、不确定性与细分性
对“计算机”，我高中时想到的是一台机器，仅此而已；可是现在认识大不一样了；
见到“人”这个概念，想到的有“外星人”，男人，女人；
哭-->啜泣、抽泣、大苦、号哭、痛哭
3． 语言的约定性
例如：“国脚”
4． 形式为内容服务，语法为语义服务
汉语早期语法研究很少。
语言本无词性，语法学加强佳的。
从某种程度上，语法就是语义的一个方面规律的总结。
.9.2.8. 人眼中的世界
1． 构成；
2． 是否有用；
3． 有利还是有害
.9.2.8.1.
10.相关资源
11.参考文献
4） 白硕，《计算语言学》讲义，中国科学院计算技术研究所
5） 詹卫东，《计算语言学概论》讲义，北京大学中文系
6） 李堂秋，《自然语言处理》讲义，厦门大学计算机科学系
7） 石纯一、黄昌宁、王家钦，《人工智能原理》，清华大学出版社
8） Chris Manning and Hinrich Schutze，Foundations of Statistical Natural Language Processing，http://www-nlp.stanford.edu/fsnlp/
9） Dr Ted Briscoe,Nature language processing Course handout, http://www.cl.cam.ac.uk/Teaching/2000/NatLangProc/handout.ps
12.读书笔记
.12.1. 心得
2) 问题与背景,研究历史，研究现状，最新研究进展，应用；
3) 解决的方法，思路，理论依据；
4) 有什么优点，新意，缺点，局限性；
.12.2. 文章
.12.3. 总结
零星的也看了不少文章，大多因耐心不够，而没看得进去，所以也谈不上一点儿，但总算自己有个印象吧。
如果以信息过滤为中心的话，机器学习，模式识别，知识挖掘这些都是底层基础理论，而信息分类，信息检索，信息过滤，信息提取则相对是高层的理论，而且这四者又是相辅相成的。
转载自原文链接, 如需删除请联系管理员。
原文链接：自然语言处理讲义，转载请注明来源！