PDF《Masaru Tomita, 1987, An efficient》

GLR 分析算法 詹卫东 http://ccl.

pku.edu.cn/doubtfire Masaru Tomita, 1987, An efficient augmented context-free parsing algorithm. Computational Linguistics, vol. 13, No. 1, pp.31-46. 提纲1. 标准LR分析算法 1.1 从语法规则到状态转移 1.2 从状态集到分析表 1.3 标准LR分析算法示例 1.4 标准LR分析算法处理自然语言句子的不足 2. GLR分析算法:针对自然语言句法分析做的改进 ・ 分析表允许多重入口 ・ 分析栈由线性栈(单顶部)结构改为多重顶部栈结构 ・ 共享子树 ・ 局部歧义压缩

3 标准LR分析算法 (Left-to-right Reduce) LR分析器 分析表 ACTION GOTO 分析栈输入符号串 分析结果 语法规则集 状态集 分析表 语言模型(知识)的数据表示

4 LR分析算法的基本思想和基本概念 根据规则集中规则之 间的相互制约关系, 来判断当前规则的使 用是否合理.比如: 根据示例规则(5), CS后面一定是 "的";

根据规则(1)(2) (5),NP后面要么是 V,要么是$(结束符) ? 利用预读字符(Lookahead)和当前状态来决定下一步分析动作 ? 状态由若干个二元组(项目)构成: ? 分析动作: C 移进(shift) C 归约(reduce) C 成功(accept) C 报错(error) (1) S ? NP VP (2) NP ? N (3) NP ? CS 的(4) VP ? V NP (5) CS ? NP V ' (6) V ' ? V V

5 First(x)函数 ―― 实现Lookahead First(x) = {? | x ? ? ? , ??VT , ? ? VN VT } First(x) = {x} 若x?VT * (1) S ? NP VP (2) NP ? N (3) NP ? CS 的(4) VP ? V NP (5) CS ? NP V ' (6) V ' ? V V X ? ? X A ? ? 示例: First(S) ={N} First(NP) = {N} First(N) = {N} First(CS) = {N} First(VP)={V} First(V ') = {V} 终结符的first集是它自身 ?

6 LR分析算法 之[状态构造算法 ] 1) 首先在规则集中添加一条新规则S'? S,S'为新的文法开始符号;

2) 定义0为起始状态,项目也属于状态 i ,其中,若?不为空,t'?first(?), 若?为空,则t'= t;

4) 从当前状态 i 转移到新的状态 j : 状态 j 是状态 i 遇到字符 y (终结符或非终结符)时的后继状态, 状态 i 中每个形如 < x? ? ・ y ?, t > 的项目,变换为 状态 j 中的项目 < x? ? y ・ ?, t >(如j已存在同形形式 k,则j不加入 状态集,而是把 k 作为 i 的后继状态) 5) 重复上面

3、4两步,直至最终状态中项目均形如 < x? ? y ? ・, t > 注[1]: 状态 i 的后继状态 j 有0到多个,具体数量为 i 中项目 y的不同字符类型数 [1]

7 NP可能是"N",也可能是"CS 的",但NP后面必是"V",CS 后面必是"的",S后面必是"$" 状态构造算法示例-1 (0) S'? S (1) S ? NP VP (2) NP ? N (3) NP ? CS 的(4) VP ? V NP (5) CS ? NP V ' (6) V ' ? V V 规则集 0:

2 {0遇见NP} : 状态是分析 过程中的一个个"格局", 状态编号0,1,2,...等并无顺序 含义 如果预读到$,则可以 调用0号规则进行归约 如果预读到V,则可以 调用2号规则进行归约 "遇见"仅意味着"状态转移"的条件(对分析格局的预测), 比如1{0遇见N},表示状态0如果遇到N,则转移到状态1

3 {0遇见S} : < S' ? S ・ , $>

1 {0遇见N} :

8 状态构造算法示例-2

4 {0遇见CS} :

5 {2遇见VP} :

6 {2遇见V} :

7 {2遇见V '} : First(V ') = {V} 说明:状态6中,从

14 {11遇见V ' } : = 状态7 = 状态9 相同的状态,即相同的 "格局"(两个状态中所有项目都 相同),没有必要重新命名, 所以应该合并. 状态构造算法示例-3

10 0:

1 {0遇见N} :

2 {0遇见NP} :

3 {0遇见S} : < S' ? S ・ , $>

4 {0遇见CS} :

5 {2遇见VP} :