计算语言学讲义(14)句法分析ii

《计算语言学讲义(14)句法分析ii》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算语言学第14讲句法分析II刘群中国科学院计算技术研究所liuqun@ict.ac.cn中国科学院研究生院2002~2003学年第二学期课程讲义内容提要•上下文无关语法的分析算法–富田算法（Tomita算法）–线图分析算法（Chart算法）•概率上下文无关语法•组块分析与部分分析中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学句法分析II第2页线图（Chart）分析算法•线图分析算法ChartParsingAlgorithm•线图分析法的核心是线图（Chart）表示法，线图表示法具有简单、直观的特点；•通过修改线图分析法

2、的分析策略，可以方便地模拟很多种分析算法，如自顶向下的分析方法、自底向上的分析方法、左角分析方法等等。中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学句法分析II第3页线图表示法1•线图是一个无环有向图（DAG），其中：–结点：输入句子中词与词之间的每一个间隔为一个结点；结点的标记往往用一个序号来表示；–边（弧）：对应于句子中的一个短语，边两端的结点给定了短语的边界，边的方向总是从左到右。边上面不仅要标记短语的类型，还需要标记产生该短语的规则。–说明：在汉语分析中，为了兼容词语切分的歧义，常常将汉字之间的间隔作为一个结点中

3、国科学院研究生院课程讲义（2003.2～2003.6）计算语言学句法分析II第4页线图表示法2SÆNPVPVPÆVNPNPÆSφ的SÆNPVPSφÆNPVPφVPÆVNPNPÆRNPÆNVPφÆVRVNVV我是县长派来的0123456中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学句法分析II第5页活跃边与非活跃边1•上述记录分析成功的短语的边称为非活跃边。•在线图中，还有另一种形式的边，用于记录一条规则不完全分析的结果，称为活跃边，如下所示：记录方式边状态匹配程度起点终点对应词串<0,0,SÆ·NPVP>活跃SÆ·NPV

4、P00<0,1,SÆNP·VP>活跃SÆNP·VP01我<0,3,SÆNPVP·>非活跃SÆNPVP·03我是县长•活跃边的引入，可以减少规则匹配中的冗余操作，提高句法分析的效率。中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学句法分析II第6页活跃边与非活跃边2SÆ·NPVPSÆNP·VPSÆNPVP·VPÆVNP·NPÆR·NPÆN·RVN我是县长派来的0123456中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学句法分析II第7页日程表(Agenda)•在线图分析算法中，除了“线图(Chart)”以

5、外还有一个重要的数据结构，称为“日程表(Agenda)”•Chart分析的过程就是一个不断产生新的边的过程。但是每一条新产生的边并不能立即加入到Chart中，而是要放到日程表(Agenda)中•日程表(Agenda)实际上是一个边的集合，用于存放已经产生，但是还没有加入到Chart中的边。•日程表(Agenda)中边的排序和存取方式，是Chart算法执行策略的一个重要方面中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学句法分析II第8页线图分析算法的基本流程Chart算法就是一个由日程表驱动的不断循环的过程：1.按照初始化

6、策略初始化Agenda2.如果Agenda为空，那么分析失败3.每次按照日程表组织策略从Agenda中取出一条边4.如果取出的边是一条非活跃边，而且覆盖整个句子，那么返回成功5.将取出的边加入到Chart中，执行规则匹配策略和规则调用策略，将产生的新边又加入到Agenda中6.返回第(2)步中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学句法分析II第9页线图分析算法：初始化策略•Chart分析算法开始执行以前，要先将Agenda初始化•对于不同的句法分析策略，初始化策略也不相同自底向上分析的规则调用策略–将所有单词（含词

7、性）边加入到Agenda中。自顶向下分析的规则调用策略–将所有单词（含词性）边加入到Agenda中；–对于所有形式为SÆW的规则，产生一条形式为<0,0,SÆ·W>的边，并加入到Agenda中；中国科学院研究生院课程讲义（2003.2～2003.6）计算语言学句法分析II第10页线图分析算法：规则匹配策略•在Chart算法中，边是逐条从Agenda中加入到Chart中的•将每一条边从Agenda中取出并加入到Chart中时，都要执行以下规则匹配策略：–如果新加入一条活跃边形式为：，那么对于Chart中所有形式为：

8、的非活跃边，生成一条形式为的新边，并加入到Agenda中；–如果新加入一条非活跃边形式为：，那么对于Chart