PDF《WOODS,燱.燗.？,1970,烛ransition?》

WOODS,?W.

?A.?,1970,?Transition?network?grammars?for?natural?language?analysis.?In?Computational?linguistics,?vol.13,?No.10.? ATN分析算法 ATN分析算法 詹卫东 詹东http://ccl.pku.edu.cn/doubtfire

1 ATN分析方法 ATN分析方法 张三是县长派来的 苍蝇是瞎子打死的 (1) S ? NP VP (2) NP ? N 苍蝇是瞎子打死的 主意是董永想出来的 (2) NP ? N (3) NP ? CS 的(4) CS ? NP V ' …… N??V??N??V??V??的(5) VP ? V NP (6) V ' ? V V ATN : Augmented Transition Network RTN :Recursive Transition Network

2 RTN :Recursive Transition Network 从CFG到递归转移网络(RTN) 从CFG到递归转移网络(RTN) S NP VP (1) S ? NP VP q0 q1 q2 S NP q2 N (2) NP ? N (3) NP ? CS 的(4) CS ? NP V ' q0 q1 q2 CS 的()(5) VP ? V NP (6) V ' ? V V VP q0 q1 q2 V NP CS q0 q1 q2 NP V ' V V V ' q0 q1 q2 V V

3 RTN算法描述 基本概念 RTN算法描述 ―― 基本概念 状态节点 子网名称 S, NP, VP, CS, V' (S是个特殊的子网) q0, q1, q2(其中q0是开始状态, q2是结束状态) 出边 从当前状态向下一个状态转移的弧(NP, VP, V, …) 待分析字符串 递归栈 w1w2w3…(主意是董永想出来的,张三是县长派来的) 记录来自哪个子网 以及回到上层子网时应处的状态 递归栈 当前状态 记录来自哪个子网,以及回到上层子网时应处的状态 对过去加以保留 对将来进行预测

4 RTN算法描述(top\down) 1. 初始化:当前状态为,字符串指针指向待分析字符串第一个字符, 递归栈清空. 2. 2.1 如果当前状态节点不是终止状态: 把当前状态节点出边指针指向第 个出边 把当前状态节点出边指针指向第一个出边, 2.1.1 如果当前出边的标记为终结符, 比较该标记与当前字符串移动指针所指字符

2 1

1 1 如果相等 预测得到验证 构造子树 将当前状态节点设为当前 2.1.1.1 如果相等,预测得到验证,构造子树,将当前状态节点设为当前 出边的后续状态节点,同时修改当前出边;

2.1.1.2 如果不相等,出边指针指向下一个出边.如果不存在下一个出边 并且存在回溯点 则回溯 否则分析失败 并且存在回溯点,则回溯,否则分析失败. 2.1.2 如果当前出边的标记为非终结符,把当前子网名称及当前节点出边的后 续状态压栈,并把当前状态节点设为当前子网的开始状态,同时修改 当前出边及后续状态. 当前出边及后续状态. 2.1.3 如果当前出边有多重选择,需要设置恢复断点,保存递归栈、待分析字 符串、当前ATN状态以及出边列表状态的全部内容,以便回溯时使用. 2.2. 如果当前状态节点是终止状态但不是子网S的终止状态: 如果当前状态节点是终止状态但不是子网 的终止状态: 将递归栈退栈,并将当前状态设置为当前栈顶的状态,转入步骤2继续执行. 2.3. 如果当前状态节点是终止状态并且是子网S的终止状态: 2.3.1?若递归栈已空且待分析字符串已空,则分析成功,结束;

2.3.2?否则,若存在回溯点,回溯. 2.3.3?若不存在回溯点,分析失败. RTN算法过程示例\1 RTN算法过程示例\1 记录回溯点,即当 前选择的出边序 号,回溯时+1? S NP N N S NP N VP V N V

6 RTN算法过程示例\2 RTN算法过程示例

2 S NP NP N VP V NP N S S NP VP N V NP CS NP N

7 RTN算法过程示例

3 S RTN算法过程示例\3 S NP VP N V NP CS NP N S NP N VP NP V CS NP V '

8 N V RTN算法过程示例

4 S RTN算法过程示例\4 NP VP N NP CS V NP N V ' V V S NP NP N VP NP V CS NP V ' 的9NVV从RTN到ATN 从RTN到ATN ? 寄存器(register) ? 条件测试(condition) 条件测试 ? 动作(action) 件小孩的衣服 一件衣服 ―― * 一件小孩 张三打李四 ―― 李四被张三打了 一件小孩的衣服 施事:张三 受事:李四