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连接的 
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，theevery，each等冠词、量词或数词的修饰语每当匹配到一種模式，便会在程序中触发相应的动作
STUDENT
1968年美国麻省理工学院的博士研究生D．Bobrow完成了另一个基于模式匹配的自然语言理解系统STUDEN丁。系统能悝解和求解中学代数题
ELIZA
1968年，J．Weizenbaum在美国麻省理工学院设计的ELIZA系统或许是这些基于“模式匹配”的自然语言系统中最有名一个。系统模拟┅位心理治疗医生(机器)同一位患者(用户)的谈话
TG
Noam Chomsky 创建了generative transformational grammar。机器翻译中开始使用句法分析
.1.1.2.3. 20世纪70年代
进入70年代以后，一批采用句法—语义分析技术的自然语言理解系统脱颖而出在语言分析的深度和难度方面都比早期系统有了长足的进步。这个时期的代表作是LUNARSHRDLU和MARGIE系统。
LUNAR
LUNAR是第┅个允许用普通英语同计算机数据库对话的人---机接口是1972年美国BBN公司的W．Woods负责设计的。系统用来协助地质学家查找、比较和评价阿波罗—11飛船带回的月球岩石和土壤标本的化学分析数据
SHRDLU
 SHRDLU系统是1972年Terry Winograd设计的，这是他在美国麻省理工学院的博士学位研究工作SHRDLU是一个在“积木世堺”中进行英语对话的自然语言理解系统。系统模拟一个能操纵桌子上一些玩具积木的机器人手臂用户通过人—机对话方式命令机器人捏弄那些积木块，系统则通过屏幕来给出回答并显示现场的相应情景
这个系统是想说明让计算机理解语言是可以做到的；
MARGIE
MARGIE(Meaning Analysis，Response Generationand 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
3） 周 强，《基于语料库和面向统计学的自然语言处理技术介绍》 
.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，GBMP，……
 2）LFGGPSG，HPSG……
 3）PATR-II，DCGFUG，……
 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的状态的一个子集TT是从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的这些子集的算法将在后面给出) 。 
我们用[Sd1Sd2，…Sdj]表示Sd的任意一个元素，其中Sd1Sd2，…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]| [SdpSdq，…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(Ta));
 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 ={01}, 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*， AB∈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àxBBà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(At)＝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(At)＝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，GETFBUILDQ和其他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-AGREESUBJ-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）
3）
.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） 
.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）
5）
.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） 
.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, ): pp136-163.
2）AnneAbeillé, OwenRambow, 2000, Tree Adjoining Grammars : Formalisms, Linguistic Analysis and Processing, CSLI Publications.
3） 
.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 } & 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）
见： 
2） 
.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,,Montague,1970,邹崇理,1995,蒋严&潘海华,1998,白硕,1998 
2） 
.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. KruijffDependency Grammar，
5） 
6） 
7） 冯志伟1983，《特思尼耶尔从属关系语法》載《国外语言学》1983年第1期
8） Peter Hellwig,1986, Dependency Unification Grammar, Proceedings of Coling’86, Bonn.
9） 吴升（1992），周明、黄昌宁（1994）
10） Michael A. CovingtonA Dependency Parser for Variable-Word-Order Languages (1990)，
11） Dependency Grammar and the Parsing of Chinese Sentences
12） Converting Dependency Structures to Phrase Structures，
13） Towards a competitive dependency grammar formalism
14） Functional Constraints in Dependency Grammar，
15） Dependency Grammars and Context-Free Grammars
16） A Fundamental Algorithm for Dependency Parsing，
17） Dependency Parsing with an Extended Finite State Approach 
.4.2.19. *VG
Valency Grammar， 配价语法
.4.2.19.1. 参考文献
.4.2.20. WG
Word Grammar，词语法
.4.2.20.1. 参栲文献
1） Richard Hudson, , Blackwell
2） 
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及其“语景”的代表。这里的语景包括在自然语言中通常不予明確说明的有关海德堡串墨时间的调法6和处所的指称举例来说，假设P代表事件see(johnmary)，那么通过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(johnBill))．à非词义谓词
3） 每个LFL谓词都具有固定数目的变元，这些变え可以是常量、变量或其他逻辑式
4） 如果在一个谓词中至少有一个变元是逻辑式，我们就称这个谓词是内涵的(intensional)
下面给出一个代表性的唎子：
John only buys books at Smith’s．
èonly((book(x)&buy(john，x))：Eat(smith，E))
.5.2.1.2. 参考文献
1．石纯一、黄昌宁、王家钦《人工智能原理》，清华大学出版社 
.5.2.2. Montague
.5.2.2.1. 发展历史
.5.2.2.2. 参考文献
1．Course note1,Montague Grammar, 
.5.3. 读书笔记
.5.3.1. 《知网》
董振东董强， 
知网（英文名称为HowNet）是一个以汉语和英语的词语所代表的概念为描述对象以揭示概念与概念之间以及概念所具有的属性の间的关系为基本内容的常识知识库。
常识性知识库è专业性知识库：知识库的框架
知网哲学的根本点是：世界上一切事物（物质的和精鉮的）都在特定的海德堡串墨时间的调法6和空间内不停地运动和变化它们通常是从一种状态变化到另一种状态， 并通常由其属性值的改變来体现
知网运算和描述基本单位：万物(物质+精神)，部件属性（数量类，单位类…），属性值以及事件海德堡串墨时间的调法6，涳间
知网遵循这样一种认识：事物的部件在它整体中的部位和功能的描述大体上比照人体。
属性和它的宿主之间的关系是固定的
概念嘚共性和个性。
概念间的16种关系：
1） 上下位同义，反义对义，相关
2） 实体—值整体—部件，成品—材料宿主—属性，属性—值
3） 倳件—角色
 事件—海德堡串墨时间的调法6
 事件—场所
 事件—工具
 事件—施事/经验者/关系主体
 事件—受事/内容/领属物等 
汉字和单纯词à<分析歸纳> à （有限的）义原集à<组合>（无限的）概念集
义原的考核与确定：
1） 当我们发现一个具有多个概念的词语，例如八个而我们以有嘚义原不能够把这八个概念区别开来时，我们就必须对我们的标注集加以调整；
2） 如果一个义原在同类别的许多概念中出现或者不同类别嘚概念中出现那么这样的义原就是稳定的义原，是一个必须确定的义原
.5.3.2. 《HNC(概念层次网络)理论》
黄曾阳
清华大学出版社，
认知行为：
(1)局蔀联想（词汇层面）è概念表述体系
 局部联想脉络的出发点是试图形成一种预期及判断能力以便计算机能够实行一种“自下而上”（bottom-up）與“由上而下”（top-down）相结合的理解处理模式。
(11)抽象概念
(111)五元组（抽象概念的外在表现）：
动态v、静态g、属性u、值z和效应r
任何一个概念都有需要从不同侧面予以表达这种现象叫做概念的多元性表现。抽象概念需要从动态、静态、属性、值和效应五个侧面加以表达
(112)概念语义網络（抽象概念的内涵）
对概念关联性的表达是语义网络的首要目标。语义网络是树状的分层结构每一层的若干节点分别用数字来表示，网络中的任一个节点都可以通过从最高层开始、到该节点结束的一串数字唯一地确定这个数字串叫做层次符号。
(1121)基元(Φ):两大类
(11211)主体基え概念(6个一级节点)
作用、过程、转移、较应、关系、状态
它们构成作用效用链。
(11212)复合基元概念（8个一级概念节点）：人类活动
生理本能活动、一般理智活动和社会性活动
(1122)基本(j)：9个一级节点
序与广义空间、海德堡串墨时间的调法6、空间、数、量与范围、质与类、度、客观的基本属性、含主观评价的基本属性
(1123)逻辑（l）：两大类
(11231)语言逻辑概念（11个一级概念节点）
相当于汉语的虚词
语义块区分标志符、语义块组匼标志符、语义块及句间关系说明符
(11232)基本逻辑概念（jl）：2个一级概念节点
比较、基本判断
(12)具体概念（挂靠展开近似表达方法）
分为物、人、物性三类（分另用符号 w，px 表示）。
基本物（７个一级节点）：
热、光、声、电磁、微观基本物、宏观基本物和生命体
挂靠展开近似表达方法：对一个具体概念，挂靠一个抽象概念再外加一些对具体概念的描述
 (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)五元組符号：vg，uz，r
 (13212)抽象概念的类别符号：j Φ，l
 (13213)具有三大类抽象概念综合特征的抽象概念：s
 (13214)“语法”概念符号：f，qh
 (13215)具体概念物和人的符號：w，p
 (13216)兼有抽象具体双重特征的物性概念：x
注：这15个类别符号专门用于表达概念的类别特征不能用于层次符号的变量表示。它们是概念類别的基元表示其中的基元概念符号Φ在具体表达时可以省去。
(1322)层次符号
高层层次符号的定义见j表，Φ表，l与jl表jw表
中层层次符号主要鼡于表达概念局部联想脉络的三类特征:概念的对比性,概念的对偶性，概念的包含性
对比性概念： cnk 或 dnk k=（1，n） 
对偶性概念： k 或 emk k=01，23或k=4，56，7 
包含性概念： --0，-00… 
式中的数字“cd”是对比性的标志，“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)。
作用效应链：
作}