文件名称：分析算法分析过程-java动态添加外部jar包到classpath的实例详解
文件大小：2.75MB
文件格式：PDF
更新时间：2024-07-11 17:53:27
计算语言学 自然语言处理
表 6-16 LR(1)分析算法分析过程 步骤 栈 其余输入部分 树 0 ±0 ™N V A N ＄ 1 ±0 N 3 KV A N ＄ 2 ±0 NP 2 ƒV A N ＄ T1 = NP( N ) 3 ±0 NP 2 V 6 5A N ＄ 4 ±0 NP 2 V 6 A 10 �N ＄ 5 ±0 NP 2 V 6 A 10 N 11 õ＄ 6 ±0 NP 2 V 6 NP 8 �＄ T2 = NP( A N ) 7 ±0 NP 2 VP 5 ＄ T2 = VP( V NP) 8 ±0 S 1 7＄ T1 = S( NP VP ) 9 ±成功 注 : ( 1) 若分析成功 ,则输出一个完整的树。否则输出多个树。 (2 ) 若存在一个树的子结点是其他树 ( T k , Tm ⋯ )的父结点 ,且这些树中 , k 是最小的 标号 ,则记新建立的树为 T k 。 LR( 1) 算法的核心数据结构是分析表。事先根据文法构造分析表 , 如果文法不变 , 分 图 6-12 “小华有好书”的分析树 析表就不需要重复创建。所以分析不同的多个句子时只 需创建一次分析表。这样对每个句子的分析基本上变成 了查表和按照表上的动作机械执行的过程。对于 LR ( 1) 文法 , LR (1 ) 分析算法可以达到同输入字符串的长度呈 线性关系的速度。所以 , 总体来说 , LR ( 1 ) 的分析速度较 快。但是 ,如果文法是非 LR (1 )文法时 , 动作表容易产生 “移进/ 规约”冲突或者“规约/ 规约”冲突 , 这样 LR ( 1 ) 分 析算法就很难执行。实际的自然语言中 ,比如英语的介词短语附着歧义 , 所使用的上下文 无关文法就是非 LR ( 1) 文法。而 LR ( 1 ) 文法不能生成的语言 LR ( k ) 文法也不能生成。 因此 LR ( k ) 文法无法处理介词短语附着歧义现象。因此 , 富田胜在 1985 年提出了 Generalized LR( GL R)分析算法来处理 LR (1 )分析表中的动作冲突现象 , 从而使得 GLR 分析算法能用来分析自然语言。 ·801·