《句法分析i[1]》由会员分享，可在线阅读，更多相关《句法分析i[1]（136页珍藏版）》请在金锄头文库上搜索。
1、句法分析I张宇哈尔滨工业大学计算机科学与技术学院 2011年11月9日10时37分中文信息处理-句法分析2内容提要n什么是句法分析n与形式语言句法分析的比较n上下文无关语法的分析策略n自顶向下分析法n自底向上分析法n左角分析法2011年11月9日10时37分中文信息处理-句法分析3内容提要（续）n上下文无关语法的分析算法n移进归约算法nMarcus确定性分析算法nCYK算法nEarley算法nTomita算法nChart算法n概率上下文无关语法n组块分析与部分分析2011年11月9日10时37分中文信息处理-句法分析4什么是句法分析n句法分析（Parsing）和句法分析器（Parser)n句法
2、分析是从单词串得到句法结构的过程；n不同的语法形式，对应的句法分析算法也不尽相同；n由于短语结构语法（特别是上下文无关语法）应用得 最为广泛，因此以短语结构树为目标的句法分析器研 究得最为彻底；n很多其他形式语法对应的句法分析器都可以通过对短 语结构语法的句法分析器进行简单的改造得到。n本讲义将主要介绍上下文无关语法的句法分析器。2011年11月9日10时37分中文信息处理-句法分析5与形式语言句法分析的比较n形式语言一般是人工构造的语言，是一种确定性的语 言，即对于语言中的任何一个句子，只有唯一的一种 句法结构是合理的，即使语法本身存在歧义，也往往 通过人为的方式规定一种合理的解释。n如程序
3、语言中的ifthenifthenelse结构，往往都人为规 定else 子句与最接近的if 子句配对；n而在自然语言中，歧义现象是天然地大量存在着的， 而且这些歧义的解释往往都有可能是合理的，因此， 对歧义现象的处理是自然语言句法分析器最本质的要 求。n由于要处理大量的歧义现象，导致自然语言句法分析 器的复杂程度远高于形式语言的句法分析器。2011年11月9日10时37分中文信息处理-句法分析6句法结构歧义的消解n人们正常交流中所使用的语言，放在特定的环 境下看，一般是没有歧义的，否则人们将无法 交流（某些特殊情况如幽默或双关语除外）n如果不考虑语言所处的环境和语言单位的上下 文，将会发现语言
4、的歧义现象无所不在；n结论：一般来说，语言单位的歧义现象在引入 更大的上下文范围或者语言环境时总是可以被 被消解的。句法分析的核心任务就是消解一个 句子在句法结构上的歧义。2011年11月9日10时37分中文信息处理-句法分析7句法结构的歧义消解（续）n我是县长。我是县长派来的。n咬死了猎人的狗跑了。就是这条狼咬死了猎人的狗。n小王和小李的妹妹结婚了。小王和小李的妹妹都结婚了。2011年11月9日10时37分中文信息处理-句法分析8例子语法n小王和小李的妹妹结婚了2011年11月9日10时37分中文信息处理-句法分析9例子分析结果之一2011年11月9日10时37分中文信息处理-句法分析10例
5、子分析结果之二2011年11月9日10时37分中文信息处理-句法分析11另一个例子n我是县长派来的2011年11月9日10时37分中文信息处理-句法分析12另一个例子分析结果2011年11月9日10时37分中文信息处理-句法分析13句法分析的基本策略n句法分析通常采用的策略有：n自顶向下分析法；n自底向上分析法；n左角分析法；n其他策略。2011年11月9日10时37分中文信息处理-句法分析14上下文无关语法的分析算法n常见的上下文无关语法的句法分析算法：nCYK算法；n移进归约算法；nMarcus确定性分析算法；nEarley算法；nTomita算法（GLR算法、富田算法）；nChart算法
6、（图分析算法、线图分析算法）；2011年11月9日10时37分中文信息处理-句法分析15自顶向下和自低向上分析法1n句法分析的过程也可以理解为句法树的 构造过程n所谓自顶向下分析法也就是先构造句法 树的根结点，再逐步向下扩展，直到叶 结点；n所谓自底向上分析法也就是先构造句法 树的叶结点，再逐步向上合并，直到根 结点。2011年11月9日10时37分中文信息处理-句法分析16自顶向下和自低向上分析法2n自顶向下的方法又称为基于预测的方法，也就是说，这种方法是 先产生对后面将要出现的成分的预期，然后再通过逐步吃进待分 析的字符串来验证预期。如果预期得到了证明，就说明待分析的 字符串可以被分析为所
7、预期的句法结构。如果某一个环节上预期 出了差错，那就要用另外的预期来替换（即回溯）。如果所有环 节上所有可能的预期都被吃进的待分析字符串所“反驳”，那就说 明待分析的字符串不可能是一个合法的句子，分析失败。n自底向上的方法也叫基于归约的方法。就是说，这种方法是先逐 步吃进待分析字符串，把它们从局部到整体层层归约为可能的成 分。如果整个待分析字符串被归约为开始符号S，那么分析成 功。如果在某个局部证明不可能有任何从这里把整个待分析字符 串归约为句子的方案，那么就需要回溯。2011年11月9日10时37分中文信息处理-句法分析17自顶向下分析法示例12011年11月9日10时37分中文信息处理-句
8、法分析18自顶向下分析法示例22011年11月9日10时37分中文信息处理-句法分析19自顶向下分析法示例32011年11月9日10时37分中文信息处理-句法分析20自顶向下分析法示例42011年11月9日10时37分中文信息处理-句法分析21自顶向下分析法示例52011年11月9日10时37分中文信息处理-句法分析22自顶向下分析法示例62011年11月9日10时37分中文信息处理-句法分析23自顶向下分析法示例72011年11月9日10时37分中文信息处理-句法分析24自顶向下分析法示例82011年11月9日10时37分中文信息处理-句法分析25自顶向下分析法示例92011年11月9日10
9、时37分中文信息处理-句法分析26自顶向下分析法示例102011年11月9日10时37分中文信息处理-句法分析27自顶向下分析法示例112011年11月9日10时37分中文信息处理-句法分析28自顶向下分析法示例122011年11月9日10时37分中文信息处理-句法分析29自顶向下分析法示例132011年11月9日10时37分中文信息处理-句法分析30自顶向下分析法示例142011年11月9日10时37分中文信息处理-句法分析31自顶向下分析法示例152011年11月9日10时37分中文信息处理-句法分析32自顶向下分析法示例162011年11月9日10时37分中文信息处理-句法分析33自顶向
10、下分析法示例172011年11月9日10时37分中文信息处理-句法分析34自顶向下分析法示例182011年11月9日10时37分中文信息处理-句法分析35自顶向下分析法示例192011年11月9日10时37分中文信息处理-句法分析36自顶向下分析法示例202011年11月9日10时37分中文信息处理-句法分析37自底向上分析法示例12011年11月9日10时37分中文信息处理-句法分析38自底向上分析法示例22011年11月9日10时37分中文信息处理-句法分析39自底向上分析法示例32011年11月9日10时37分中文信息处理-句法分析40自底向上分析法示例42011年11月9日10时37分
11、中文信息处理-句法分析41自底向上分析法示例52011年11月9日10时37分中文信息处理-句法分析42自底向上分析法示例62011年11月9日10时37分中文信息处理-句法分析43自底向上分析法示例72011年11月9日10时37分中文信息处理-句法分析44自底向上分析法示例82011年11月9日10时37分中文信息处理-句法分析45自底向上分析法示例92011年11月9日10时37分中文信息处理-句法分析46自底向上分析法示例102011年11月9日10时37分中文信息处理-句法分析47自底向上分析法示例112011年11月9日10时37分中文信息处理-句法分析48自底向上分析法示例122
12、011年11月9日10时37分中文信息处理-句法分析49自底向上分析法示例132011年11月9日10时37分中文信息处理-句法分析50自底向上分析法示例142011年11月9日10时37分中文信息处理-句法分析51自底向上分析法示例152011年11月9日10时37分中文信息处理-句法分析52自底向上分析法示例162011年11月9日10时37分中文信息处理-句法分析53左角分析法概述n左角分析法是一种自顶向下和自底向上 相结合的方法n所谓“左角(Left Corner)”是指任何一个句 法子树中左下角的那个符号n比较：2011年11月9日10时37分中文信息处理-句法分析54左角分析法示例
13、12011年11月9日10时37分中文信息处理-句法分析55左角分析法示例22011年11月9日10时37分中文信息处理-句法分析56左角分析法示例32011年11月9日10时37分中文信息处理-句法分析57左角分析法示例42011年11月9日10时37分中文信息处理-句法分析58左角分析法示例52011年11月9日10时37分中文信息处理-句法分析59左角分析法示例62011年11月9日10时37分中文信息处理-句法分析60左角分析法示例72011年11月9日10时37分中文信息处理-句法分析61左角分析法示例82011年11月9日10时37分中文信息处理-句法分析62左角分析法示例9201
14、1年11月9日10时37分中文信息处理-句法分析63左角分析法示例102011年11月9日10时37分中文信息处理-句法分析64左角分析法示例112011年11月9日10时37分中文信息处理-句法分析65左角分析法示例122011年11月9日10时37分中文信息处理-句法分析66左角分析法示例132011年11月9日10时37分中文信息处理-句法分析67左角分析法示例142011年11月9日10时37分中文信息处理-句法分析68左角分析法示例152011年11月9日10时37分中文信息处理-句法分析69左角分析法示例162011年11月9日10时37分中文信息处理-句法分析70左角分析法示例1
15、72011年11月9日10时37分中文信息处理-句法分析71左角分析法示例182011年11月9日10时37分中文信息处理-句法分析72左角分析法示例192011年11月9日10时37分中文信息处理-句法分析73左角分析法示例202011年11月9日10时37分中文信息处理-句法分析74左角分析法示例212011年11月9日10时37分中文信息处理-句法分析75左角分析法示例222011年11月9日10时37分中文信息处理-句法分析76左角分析法示例232011年11月9日10时37分中文信息处理-句法分析77左角分析法示例242011年11月9日10时37分中文信息处理-句法分析78左角分析
16、法示例252011年11月9日10时37分中文信息处理-句法分析79左角分析法示例262011年11月9日10时37分中文信息处理-句法分析80左角分析法示例272011年11月9日10时37分中文信息处理-句法分析81左角分析法示例282011年11月9日10时37分中文信息处理-句法分析82左角分析法示例292011年11月9日10时37分中文信息处理-句法分析83左角分析法示例302011年11月9日10时37分中文信息处理-句法分析84左角分析法示例312011年11月9日10时37分中文信息处理-句法分析85左角分析法示例322011年11月9日10时37分中文信息处理-句法分析86左角分析法示例332011年
