PDF《第八章 句法分析（二）》

第八章 句法分析

(二) 詹卫东 http://ccl.

pku.edu.cn/doubtfire

2 提纲 ?

1 线图分析算法(Chart parsing) ?

2 标准LR分析算法 ?

3 GLR分析算法(Tomita/富田胜算法)

3 1 线图分析算法 (1) S ? NP VP (2) NP ? N (3) NP ? CS 的(4) VP ? V NP (5) CS ? NP V '

(6) V '

? V V 张三是县长派来的 苍蝇是瞎子打死的 主意是董永想出来的 …… N V N V V 的4线图结构图示-1

1 2

3 4

5 6

0 N N V V V 的 张三 是 县长 派来的苍蝇 是 瞎子 打死的主意 是 董永 想 出来 的…… V'

CS NP VP S 线图 Chart NP NP

5 线图结构图示-2

1 2

3 4

5 0 V N U de N …… 咬死 了 猎人 的狗发现 了 敌人 的 哨兵 批评 过 张三 的 老师 NP VP VP VP NP

6 基本概念:线图/chart 线图是一组节点(node)和边(edge)的集合 节点:对应着输入字符串中的字符间隔 边: 其中标记为非终结符或终结符 问题: 如何从输入串开始,一步步形成chart,使得存在 一条边可以覆盖全部节点,并且边上标记为S?

7 Chart的另一种表示形式 边 的起始位置 边的终止位置 边 上的标记

6 S VP NP 的5CS V'

V

4 V

3 N, NP

2 V

1 N, NP

0 0

1 2

3 4

5 6

8 Chart算法的基本数据结构 1) chart(线图) {edge[i]} i=1,2,… edge := 2) agenda(议程表) 存放等待加入到chart中的边(edge) 可以栈(stack)结构,或队列(queue)结构实现 3) active arc(活动弧) 存放分析过程的中间状态, 状态由三部分组成

9 Chart算法的过程描述 扫描 吃进 归约 预测 agenda中的这条边将为下面的分析指出方向:吃进所有右部以A开头的规则(步骤b,c) 1) 将待分析字符串w置入输入缓冲区,agenda清为空栈;

2) 循环,反复执行下面步骤,直至输入缓冲区和agenda均为空 a) 若agenda为空,则从输入缓冲区取一个字符,并把该字符及其起止位置 (P1, P2)推入agenda栈;

b) 若agenda不为空,则从agenda中弹出栈顶的边,该边的起止位置为(P1, P2), 边上标记为L;

c) 检查规则集中的规则,对所有形如A?L β这样的规则,在active arc集合中增 加一条起止位置为P1, P2,弧上为A?L ・ β这样的点规则;

d) 把从agenda中弹出的标记为L的边,加入到chart中的P1, P2之间;

e) 检查所有active arc,如果存在起止位置为P0, P1,且弧上点规则为A? α ・ L β 的active arc,就增加一条新的active arc,起止位置为P0, P2,弧上点规则为 A? α L ・ β f) 如果一条active arc(起止位置为P0, P2)上点规则形如A? α L ・ (点号在规 则最右端),就将起止位置为P0, P2,边上标记为A的边压入agenda栈.

10 Chart算法分析示例-1

1 2

3 4

5 6

0 agenda 输入缓冲区 N V N V V 的chartactivearc 线图 用于存放已经确定的分析结果 活动弧 用于存放分析的中间结果 (包括尚未确定的,和已经确定的分析结果) 议程 表 用于 中转当 前正在 处理的 边(1) S ? NP VP (2) NP ? N (3) NP ? CS 的(4) VP ? V NP (5) CS ? NP V '

(6) V '

? V V

11 Chart算法分析示例-2

1 2

3 4

5 6

0 输入缓冲区 N V N V V 的(0,1) N N NP ? N ・ c h a r t a c t i v e a r c CS?NP ・ V '

S ? NP ・ VP NP (0,1) NP agenda (1) S ? NP VP (2) NP ? N (3) NP ? CS 的(4) VP ? V NP (5) CS ? NP V '

(6) V '

? V V

12 Chart算法分析示例-3

1 2

3 4

5 6

0 输入缓冲区 N V N V V 的(1,2) V N NP ? N ・ CS?NP ・ V '

NP V VP ? V ・ NP V '

? V ・ V S ? NP ・ VP agenda (1) S ? NP VP (2) NP ? N (3) NP ? CS 的(4) VP ? V NP (5) CS ? NP V '