句法分析算法

/ NLP / 没有评论 / 520浏览

自然语言句法分析算法大多是基于上下文无关文法进行的, 即采用基于上下文无关文法的句法分析算法。

自顶向下的句法分析

始于开始符号 S
利用重写规则进行推导
直到推导出待分析的句子

自底向上的句法分析

始于待分析的句子
逆向利用规则进行归约
直到归约出开始符号 S

算法的确定性和非确定性

算法的非确定性

对于自顶向下的分析方法而言,当有多个重写规则可用时,如何避免选择导致分析失败的规则?
对于自底而上的分析方法而言,如果有多种可能的归约,如何避免导致分析失败的归约?

回溯和(伪)并行

回溯导致效率低下
回溯也会导致重复计算

对于自然语言而言,彻底消除非确定性是困难的

句法分析算法

面向自然语言,已经提出了多种句法分析算法,这些算法都可以相对有效地完成句法分析

Earley分析算法
广义LR分析算法
基于chart的分析算法
CYK分析算法

Earley算法

1970年,由Earley提出,所以称为Earley算法
属于一种自顶向下的分析算法,时间复杂度是$O(N^{3})$,其中N是待分析句子中的词数

线图(chart)

Earley算法主要数据结构是线图(chart)

由N+1个状态表组成, N是句中的词数
每一个状态表对应句中的一个位置
每一个状态包含下述信息
一个子树(对应一个重写规则)
该子树的完成状态
子树与输入句子的对应关系

点规则(dotted rule)

一种右部加点标记的重写规则。

如: $NP \rightarrow$ Det ·Nominal

三种基本操作

PREDICTOR() : 作用于一个点号后是非终结符号(不包括词类标记)的状态,并产生新的状态
SCANNER() : 作用于一个点号后是词类标记的状态,并产生新状态
COMPLETER() : 作用于一个点号位于规则右部最右端的状态,并产生新状态

初始化,在 chart[0] 加入一个初始状态$\gamma \rightarrow$ ·S, [0,0]
终止条件,若在 chart[N] 出现状态 $S \rightarrow \alpha$ ·,[0,N],分析成功

ENQUEUE()保证不会反复分析某些子树
算法是非确定性的,需要尝试各种可能

标准LR算法

标准LR分析算法是确定性分析算法

标准LR分析算法是为分析程序设计语言等人工语言而提出的,由Knuth于1965提出
标准LR分析算法,是一种自底向上的分析算法
标准LR分析算法效率高且应用广泛,在许多程序设计语言的编译器中得到应用
并非所有语言都可以使用标准LR分析算法进行分析,只有LR文法所定义的语言可以使用LR分析算法进行分析
对于LR文法所定义的语言, LR分析算法,完全消除了回溯, 可以确定性的方式进行分析

利用标准LR分析算法进行分析,首先要构造LR分析表
构造LR分析表首先要构造所有的分析状态和状态转移图
一个LR分析表由两个部分组成,一部分为动作表(ACTION),另一部分为转移表(GOTO)
LR分析算法通过查分析表来完成分析过程
LR分析算法主要使用两个数据结构,分析栈以及输入缓冲区
分析栈用来记录分析过程的中间状态,输入缓冲区用来保存待分析的句子

两种分析动作

移入动作(s):把输入缓冲区中输入指针指向的词移入分析栈 归约动作(r):运用重写规则,把分析栈顶的符号串替换成一个非终结符号

对于LR分析器而言,除了进行分析动作外,还要考虑分析状态的转移,通常用sn表示移入动作,其中n表示移入动作发生后,分析器所处的状态。用$r_{j}$表示归约,表示用第j条重写规则进行归约,归约后分析器所处的状态可以查询转移表(GOTO)获得

初始化

分析栈中首先放一个状态0,输入缓冲区中放待分析的句子,输入指针指向待分析句子中第一个词

LR算法

未完待续

标准LR算法的缺点

标准LR文法不能有二义性(歧义), 因此标准LR分析算法不能用来分析自然语言

对于描述自然语言的上下文无关文法可以使用同样的方法构造LR分析表,但构造出的分析表不是确定性的分析表。也就是说,动作表的一个单元格内可能包含多个分析动作,或者说分析表具有多重入口

当分析表的单元格中出现多个动作时,标准LR分析器不知道应该执行哪个分析动作

广义LR算法(GLR)

1987年,日本学者富田胜(Tomita)对标准LR算法进行了改进,使之可以用来分析自然语言,即广义LR算法,又称富田胜算法Tomita算法

对于LR分析表中的多重入口,由于相应的分析动作是多重的,分析动作应同时沿着多条分析路径进行。富 田胜为此引入了图结构栈技术。在分析过程中,每当分析进程遇到有多个动作同时可以进行,分析进程就 分裂成相应的几个子进程。栈顶亦分裂为多个栈顶,分别依据分析表中规定的不同动作进行分析。如果两 个进程处理同一状态,则栈顶合并为一个栈顶,两个进程则合并为一个进程,这样就形成一种图结构的分 析栈

树的构造

当分析器移进一个词时,就用该词和相应的词类标记创立叶子结点
当分析器归约时,利用归约的规则创建相应的分支结点

子树共享

如果两棵或两棵以上的树具有共同的子树,那么这棵子树就只应该表示(构造)一次
为了构造共享子树,分析过程不再把语法符号入栈,而是将指向子树的指针入栈
创建树结点时,使用这些指向子树的指针创建新结点

局部歧义

如果两棵或两棵以上子树的所有叶结点都相同,并且所有子树的根结点被标有同一非终结符号,也 就是说句子的某一部分能用两种或两种以上方式归约为同一非终结符,这时称句子中出现了局部歧义

局部歧义压缩

如果句子中有许多局部歧义,总的歧义数将会指数增长。为避免这种增长,可采用了局部歧义压缩技术。 这种技术是把有局部歧义的子树的结点结合为一体,这样的结点叫收集结点

在图结构栈中,如果两个或多个符号顶点左边具有一个共同的状态顶点,并且右边有一个共同的状态顶点,则表示这几个符号顶点具有局部歧义

压缩共享森林

采用了子树共享技术和局部歧义压缩技术后,得到的分析结果被称为压缩共享森林

压缩共享森林是一个句子的多个句法树的压缩表示法

算法总结

广义LR分析算法是非确定性算法
广义LR分析算法通过构造分析表消除了部分回溯和子树的重复分析
通过子树共享和局部歧义压缩实现了分析结果的高效存储---压缩共享森林