第3章 语法与语法剖析.ppt

第三章 语法与语法剖析 厦门大学计算机科学系李堂秋 第一节 语法与句子结构 表示句子结构的最常用的表示法是语法树： Jone ate the cat. 表结构表示：(S (NP (NAME Jone)) (VP (V ate) (NP (ART the) (N cat)))) 简单的上下文无关规则： 可以用语法推导出合法的句子（所以又叫做生成语法）： 有两个过程是基于推导的：生成 与 剖析 第二节 什么是好的语法 好语法应具有如下的性质： 普遍性 选择性 易理解性 判断文法的正确性，有几种方法： 如果决定有一类词可以形成句子的某一成分，试试看这类成分的并列词组是否可以做同样的成分，如果不行可能就有问题。 如果认为某一类词可以做句子的某一类成分，看一看是否可以出现在句子需要同一类成分的其它地方： 当提出一条规则的时候，要考虑它对其它规则的相互影响。 第三节 自上而下的语法剖析 语法分析是一种AI中有哪些信誉好的足球投注网站过程，下面判断句子是否被语法所接受为例 下面是使用一个简单的自顶向下的语法剖析算法分析结果： 算法：从初始状态((s) 1)开始，重复以下过程： 1。选择当前状态：从可能状态表中取出第一个状态，叫它为C。如果可能表为空，算法失败（不可能得到正确的剖析） 2。如果C包含一个空符号，且词的位置是处于句子的结尾，算法成功 3。否则，生成下一个状态：3。1 如果C符号表中的第一个符号是词类符，而当前位置上的词可以作为这种词类，则形成一个新的状态，办法是：去掉符号表中的第一个符号，并把词的位置加一。把新状态放入可能状态表3。2 否则，如果当前状态符号表中的第一个符号是一个非终结状态，把语法规则表中所有可以重写这个符号的规则重写这个符号，形成新的状态。把形成的所有可能的状态加入到可能状态表中。 对比一下语法分析和Ai的有哪些信誉好的足球投注网站过程： 重复如下过程直到成果或失败： 从可能状态表中取出第一个状态 从这个选择的状态生成所有可能的后续状态（可能一个也没有） 把生成的状态加入到可能状态表中 如果把生成的后续状态放在可能状态表的前面，执行的是深度优先有哪些信誉好的足球投注网站。 如果把生成的后续状态放在可能状态表的后面，执行的是广度优先有哪些信誉好的足球投注网站。 可以看出语法分析的过程就是有哪些信誉好的足球投注网站的过程。 注意： 对于深度优先有哪些信誉好的足球投注网站，遇到左递归的规则可能引起无限循环：NP -- NP’s N 对于广度优先有哪些信誉好的足球投注网站，在有左递归规则的语法，如果句子是合法的，不会陷入无限循环，但是如果句子是不合文法时，也会引起无限循环。 上述过程实际上是一个深度优先有哪些信誉好的足球投注网站的过程： 广度优先有哪些信誉好的足球投注网站的过程： 第四节 自底向上的图剖析器 自顶向下和自底向上语法分析不同的地方在于： 前这使用规则在句子中找规则描述的成分 后者是使用规则把句子中已经归结出来的成分归结成更大的成分 最简单的自底向上的语法分析可用下述简单步骤： 把单词重写成它可能的词类 把与任何一条规则右部相匹配的符号序列重写成匹配规则的坐部 但是这样的过程太低效，实际上无法使用。主要原因是在分析的过程中会对同一个成分进行多次重复的分析，现在研究使用一种称为图的数据结构以避免重复的工作 图剖析器的工作的原理为： 有一个记事表 记录遇到的词的类符或已经分析完成的成分，称它们为关键成分，取出一个关键成分 在语法中找出右部以这个关键成分打头的语法规则，将之激活 或找出已经由别的关键成分开始并刚好需要这个关键成分接续下去，以便扩展规则的匹配。 这样一直进行下去或一个完整的句子剖析已得到，或记事表空（失败） 下面是使用一个简单的自上而下的语法剖析算法分析结果： 算法：从((s) 1)，重复以下过程： 1。选择当前状态：从可能状态表中取出第一个状态，叫它为C。如果可能表为空，算法失败（不可能得到正确的剖析） 2。如果C包含一个空符号，且词的位置是处于句子的结尾，算法成功 3。否则，生成下一个状态：3。1 如果C符号表中的第一个符号是词类符，而当前位置上的词可以作为这种词类，则形成一个新的状态，办法是：去掉符号表中的第一个符号，并把词的位置加一。把新状态放入可能状态表3。2 否则，如果当前状态符号表中的第一个符号是一个非终结状态，把语法规则表中所有可以重写这个符号的规则重写这个符号，形成新的状态。把形成的所有可能的状态加入到可能状态表中。 例如：有如右的语法规则，并且正在分析句子（第一个词是ART 第二个词是ADJ…） 用ART 在规则集合中找出规则2、3，并将结构记成：NP - ART。ADJ NNP - ART。Ｎ　　　这两个弧成活动弧 用ADJ在规则集合中找出规则４并写成NP-ADJ。N 以激活的弧也得到扩