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
