文档介绍：句法分析I张宇哈尔滨工业大学计算机科学与技术学院******@(续)上下文无关语法的分析算法移进-归约算法Marcus确定性分析算法CYK算法Earley算法Tomita算法Chart算法概率上下文无关语法组块分析与部分分析精品什么是句法分析句法分析(Parsing)和句法分析器(Parser)句法分析是从单词串得到句法结构的过程;不同的语法形式,对应的句法分析算法也不尽相同;由于短语结构语法(特别是上下文无关语法)应用得最为广泛,因此以短语结构树为目标的句法分析器研究得最为彻底;很多其他形式语法对应的句法分析器都可以通过对短语结构语法的句法分析器进行简单的改造得到。本讲义将主要介绍上下文无关语法的句法分析器。精品与形式语言句法分析的比较形式语言一般是人工构造的语言,是一种确定性的语言,即对于语言中的任何一个句子,只有唯一的一种句法结构是合理的,即使语法本身存在歧义,也往往通过人为的方式规定一种合理的解释。如程序语言中的if…thenif…then…else…结构,往往都人为规定else子句与最接近的if子句配对;而在自然语言中,歧义现象是天然地大量存在着的,而且这些歧义的解释往往都有可能是合理的,因此,对歧义现象的处理是自然语言句法分析器最本质的要求。由于要处理大量的歧义现象,导致自然语言句法分析器的复杂程度远高于形式语言的句法分析器。精品句法结构歧义的消解人们正常交流中所使用的语言,放在特定的环境下看,一般是没有歧义的,否则人们将无法交流(某些特殊情况如幽默或双关语除外)如果不考虑语言所处的环境和语言单位的上下文,将会发现语言的歧义现象无所不在;结论:一般来说,语言单位的歧义现象在引入更大的上下文范围或者语言环境时总是可以被被消解的。句法分析的核心任务就是消解一个句子在句法结构上的歧义。精品句法结构的歧义消解(续)我是县长。我是县长派来的。咬死了猎人的狗跑了。就是这条狼咬死了猎人的狗。小王和小李的妹妹结婚了。小王和小李的妹妹都结婚了。精品例子-语法小王和小李的妹妹结婚了精品例子-分析结果之一精品例子-分析结果之二精品