句法分析装置及句法分析方法

摘要

本发明公开了一种句法分析装置和句法分析方法。根据本发明的使用正则表达式规则的句法分析装置包括训练树库、规则获取模块、规则应用模块、句法树生成模块和规则集。规则获取模块通过统计学习的方法从已经标注好的训练树库学习句法分析规则，生成在对输入句子进行分析时使用的规则集。对于产生式规则的后项中的重复部分，规则获取模块应用正则表达式来表示。规则获取模块所学习的句法分析规则还可以包含上下文信息。规则应用模块使用规则获取模块学习获得的句法分析规则集分析输入句子，识别出输入句子的语法成份及成份间的关系。句法树生成模块根据规则应用模块输出的分析结果，按照用户的需求生成输入句子的依存句法关系图或者短语结构型句法分析树。

说明书

技术领域

本发明涉及句法分析技术，用于从输入的自然语言句子中识别出句子的语法成份及成份之间的关系。更具体地说，本发明涉及一种使用正则表达式的句法分析装置及句法分析方法，其应用正则表达式形式的句法分析规则和句法分析算法去分析输入句子的语法成份并输出句法分析树。

背景技术

识别自然语言的语法成份及成份间的关系是处理自然语言的难点和重要任务。关于这方面的研究已经公开了多篇论文和相关专利，例如，美国专利US5,386,556A公开了一种自然语言分析装置和方法(Natural language analyzing apparatus and method)，而美国专利US 5,930,746A则公开了一种自动解析和翻译自然语言的装置和方法(Parsing and translating natural language sentences automatically)。

在对自然语言的处理过程中，进行句法分析时需要使用句法分析规则库，句法分析规则库的质量和能力是影响句法分析结果的最关键原因。但是，在现有的自然语言分析装置和方法中，由于句法分析规则的表达能力有限，因此不能灵活高效地应用句法规则描述自然语言的语法特征，相应地也不能有效准确地识别出输入句子的句法成份。

发明内容

鉴于上述情况，本发明提出一种使用正则表达式描述句法分析规则的句法分析装置及句法分析方法，用以对输入的自然语言进行句法成份及成份间关系的识别。根据本发明的句法分析装置及句法分析方法，能够应用正则表达式形式的句法分析规则和句法分析算法去分析输入句子的语法成份并输出句法分析树，从而增强描述自然语言规律的能力。

根据本发明的一个方面，提供一种句法分析装置，包括：规则获取模块，配置为从已经标注好的训练树库学习句法分析规则以生成包含正则表达式形式的产生式规则集，其中对于产生式规则的后项中的重复部分用正则表达式来表示；规则应用模块，配置为使用规则获取模块获得的产生式规则集对输入句子进行分析，识别出输入句子的成份及成份间的关系；以及句法树生成模块，配置为根据规则应用模块输出的输入句子的语法成份及成份间的关系，生成输入句子的依存句法关系图或者短语结构型句法分析树。

根据本发明的一个实施例的句法分析装置，规则获取模块包括：树片段分解部，配置为将训练树库中的每棵句法树分解为作为产生式规则的树片段，以形成树片段集；重复片段检测部，配置为检测树片段分解部分解得到的树片段集中的产生式规则的后项中是否有重复的结点序列，并将具有重复的结点序列的产生式规则表示为正则表达式形式的产生式规则；以及重复规则合并部，配置为将重复片段检测部生成的形式相同的产生式规则合并为一个产生式规则，以形成产生式规则集。

优选地，规则获取模块还包括规则选择部，配置为根据选择策略对重复规则合并部所生成的产生式规则进行选择，以生成缩减的产生式规则集。

根据本发明的一个实施例，树片段分解部分解得到的树片段表示为<freq:xx>{<f₁>...<f_n>}P→Y₁ Y₂...Y_n，n为大于等于1的正整数，其中<freq:xx>为频度信息，表示该树片段在训练树库中的出现次数；<f_i>为属性特征，用于描述使用该产生式规则时的上下文信息、词汇或语义特点，i为从1至n的任一整数；P表示该树片段的上位结点，为一个短语标记；Y_i表示P结点的子结点，为一个短语标记或一个词汇标记；“{<f₁>...<f_n>}P→Y₁ Y₂...Y_n”表示在出现了<f₁>...<f_n>属性的情况下，短语P可以由Y₁ Y₂...Y_n构成。重复规则合并部在将重复片段检测部生成的形式相同的产生式规则合并为一个产生式规则时，将产生式规则的频度进行相应合并。另外，在产生式规则中属性特征<f_i>为可选。

优选地，产生式规则包括：单结点重复型规则，为产生式规则的后项中的某一成份重复二次以上的产生式规则；多结点重复型规则，为产生式规则的后项中的某一片段重复二次以上的产生式规则；混合重复型规则，为产生式规则的后项中既包含单结点重复部分也包含多结点重复部分的产生式规则；以及无重复型规则，为产生式规则的后项中没有重复部分的产生式规则。

根据本发明的一个实施例的句法分析装置，规则应用模块包括：规则编译部，配置为将规则获取模块生成的产生式规则集编译成句法分析规则的规则查询表；规则查询部，配置为查询规则编译部编译的规则查询表；以及句法分析部，配置为通过规则查询部在规则查询表中查询能够应用于输入句子的句法分析规则，根据句法分析规则识别输入句子的语法成份及成份间的关系。

优选地，规则应用模块还包括歧义消解部，配置为从句法分析部生成的局部分析候选中选择最优的局部分析结果；以及句法分析部对歧义消解部选择的局部分析结果进行进一步的句法分析，以输出满足要求的最终分析结果。

根据本发明的一个实施例，规则编译部为产生式规则集中包含正则表达式的部分增加中间生成标记和中间生成规则，并用中间生成标记替换产生式规则中正则表达式表示的部分，中间生成标记并入句法分析规则集的短语标记集，中间生成规则并入句法分析规则集；以及句法分析部按照与识别短语标记相同的方式识别中间生成标记，通过规则查询部查询所有适合当前输入句子的包括中间生成规则的句法分析规则，以识别输入句子的语法成份及成份间的关系。

优选地，歧义消解部按照下式通过计算句法分析树的概率P(S，t)来确定使用的最优产生式规则，以选择最优的局部分析结果：

$P(s,t)=\underset{r\in D\left(T\right)}{\Pi }p\left(r\right)$

其中S为输入句子，t为句法分析树，r为句法分析过程中使用的一条句法分析规则，D(T)为生成句法分析树t使用的全部句法分析规则，而p(r)为针对句法分析规则r的规则概率。

根据本发明的一个优选实施例，中间生成标记的规则概率的计算与句法分析中存在的短语符号的规则概率的计算相同，中间生成规则的规则概率的计算与非中间生成规则的规则概率的计算相同；以及对于含有正则表达式的产生式规则用公式计算规则概率，其中r_i为转化该含有正则表达式的规则时用到的一条中间生成规则，而p(r_i)为针对该中间生成规则r_i的规则概率，n为大于等于1的正整数，i为从1至n的任一整数。

根据本发明的一个实施例的句法分析装置，句法树生成模块包括：中间标记清理部，配置为清除在句法分析过程中使用的中间生成标记；以及短语结构生成部，配置为根据中间标记清理部输出的清除中间生成标记之后的输入句子的语法成份及成份间的关系，生成短语结构型句法分析树。

根据本发明的另一个实施例的句法分析装置，句法树生成模块也可以包括：中间标记清理部，配置为清除在句法分析过程中使用的中间生成标记；核心结点标注部，配置为根据中间标记清理部输出的清除中间生成标记之后的输入句子的语法成份及成份间的关系进行核心结点标注；以及依存结构生成部，配置为根据核心结点标注部标注的核心结点生成输入句子的依存句法关系图。

根据本发明的另一个方面，提供一种句法分析方法，包括：规则获取步骤，从已经标注好的训练树库学习句法分析规则以生成包含正则表达式形式的产生式规则集，其中对于产生式规则的后项中的重复部分用正则表达式来表示；规则应用步骤，使用规则获取步骤获得的产生式规则集对输入句子进行分析，识别出输入句子的成份及成份间的关系；以及句法树生成步骤，根据规则应用步骤输出的输入句子的语法成份及成份间的关系，生成输入句子的依存句法关系图或者短语结构型句法分析树。

根据本方明提出的句法分析装置和句法分析方法，可以使用正则表达式形式的句法分析规则，增加了句法分析规则的描述能力，克服了现有方法中存在的规则表达不灵活，表达能力不强的缺点。本发明提出的句法规则获取方法及句法分析算法，可以形成一个支持正则表达式规则的句法分析器，从而实现高效正确的句法分析。

另外，本发明还提供用于实现上述字符识别方法的计算机程序。

此外，本发明也提供至少计算机可读介质形式的计算机程序产品，其上记录有用于实现上述字符识别方法的计算机程序代码。

附图说明

参照下面结合附图对本发明实施例的说明，会更加容易地理解本发明的以上和其它目的、特点和优点。在附图中，相同的或对应的技术特征或部件将采用相同或对应的附图标记来表示。附图中：

图1示出根据本发明实施例的使用正则表达式规则的句法分析装置的结构示意图；

图2示出根据本发明实施例的图1所示的规则获取模块的结构方框图；

图3示出根据本发明实施例的图1所示的规则应用模块的结构方框图；

图4示出根据本发明实施例的图1所示的句法树生成模块的结构方框图；

图5是用于说明上位结点和下位结点的示意图；

图6是用于说明规则获取模块获取句法规则时所使用的示例句法树S1；

图7是用于说明规则获取模块获取句法规则时所使用的另一示例句法树S2；

图8示出根据本发明的一个实施例由句法分析模块对输入句子进行分析后输出的最终句法分析结果；

图9示出根据本发明的一个实施例由句法树生成模块的中间标记清理部对图8所示的最终句法分析结果进行中间结点清除后的结果；

图10示出根据本发明一个实施例的句法分析方法的流程图；

图11示出根据本发明一个实施例在图10所示的规则获取步骤中执行的处理方法的详细流程图；

图12示出根据本发明一个实施例在图10所示的规则应用步骤中执行的处理方法的详细流程图；

图13示出根据本发明一个实施例图10所示的句法树生成步骤中执行的处理方法的详细流程图；以及

图14示出用于实施根据本发明的句法分析方法的信息处理设备的结构方块图。

具体实施方式

下面参照附图来说明本发明的实施例。应当注意，为了清楚的目的，附图和说明中省略了与本发明无关的、本领域普通技术人员已知的部件和处理的表示和描述。

这里，首先给出在本发明中应用到的单结点重复型规则、多结点重复型规则、混合重复型规则和无重复型规则的定义、以及上位结点和下位结点的定义，以便更好地对本发明的原理进行阐述。

定义1：单结点重复型规则，产生式规则的后项的某一成份重复二次以上的规则定义为单结点重复型规则。

定义2：多结点重复型规则，产生式规则的后项的某一片段重复二次以上的规则定义为多结点重复型规则。

定义3：混合重复型规则，产生式规则的后项中既包含单结点重复部分也包含多结点重复部分的规则定义为混合重复型规则。

定义4：无重复型规则，产生式规则的后项中没有重复部分的规则定义为无重复型规则。

下面给出各种类型的产生式规则的一些实例，以进一步说明上面定义的单结点重复型规则、多结点重复型规则、混合重复型规则和无重复型规则。

(1)单结点重复型规则

例如，RL1：P→AAABC，其中“AAA”部分为单结点重复部分，则用本发明的正则表达式规则表示方法表示为P→A＊BC。

再例如，RL2：P→ABBCCD，其中包含有两组单结点重复部分“BB”和“CC”，则用本发明的正则表达式规则表示方法表示为P→AB＊C＊D。

(2)多结点重复型规则

例如，RL3：P→ABABC，其中“AB”部分为多结点重复部分，则用本发明的正则表达式规则表示法表示为P→[AB]⁺C。

再例如，RL4：P→ABCBCDEFDEFG，其中“BCBC”和“DEFDEF”为多结点重复部分，则用本发明的正则表达式规则表示法表示为P→A[BC]⁺[DEF]⁺G。

(3)混合重复型规则

例如，RL5：P→AAABCDBCDE，包含单结点重复型和多结点重复型，其中“AAA”部分为单结点重复部分，“BCDBCD”部分为多结点重复部分，则用本发明的正则表达式规则表示法表示为P→A＊[BCD]⁺E。

(4)无重复型规则

例如，RL6：P→ABCDEABC，既不包含单结点重复型，也不包含多结点重复型，因此为无重复型规则。

接着定义上位结点和下位结点。

定义5：上位结点，在树结构中包含子结点的结点定义为上位结点。

定义6：下位结点，在树结构中有父结点的结点定义为下位结点。

上位结点和下位结点相对于所关注的树的不同部分而变化，同一棵树的同一个结点，既可以做上位结点，有时也可以做下位结点。例如，如图5所示的句法树中A2、B3、C1这三个结点，其中C1是B3、A2的下位结点，A2是B3、C1的上位结点，B3是C1的上位结点并且是A2的下位结点。

接下来将参考附图，特别是图1至图4，描述根据本发明实施例的句法分析装置的一般工作原理。如图1所示，根据本发明实施例的使用正则表达式规则的句法分析装置包括训练树库101、规则获取模块102、规则应用模块103、句法树生成模块104、以及规则集105。

规则获取模块102通过例如统计学习的方法从已经标注好的训练树库101学习句法分析规则，生成在对输入句子进行分析时使用的规则集105。对于产生式规则的后项中的重复部分，规则获取模块102应用在上文中所定义的正则表达式形式来进行相应的表述。因此，规则集105为包含正则表达式形式的产生式规则的集合。另外，规则获取模块102所学习的句法分析规则还可以包含上下文信息。

规则应用模块103使用规则获取模块102学习获得的句法分析规则集105分析输入句子，识别出输入句子的成份及成份间的关系。

句法树生成模块104根据规则应用模块103输出的分析结果，按照用户的需求生成输入句子的依存句法关系图或者短语结构型句法分析树。

下面对本发明的句法分析装置的三个主要模块规则获取模块102、规则应用模块103和句法树生成模块104进行具体说明。

图2示出根据本发明实施例的图1所示的规则获取模块102的结构方框图。如图2所示，根据该实施例的规则获取模块102包括句法分析树库201、树片段分解部202、分解参数输入单元203、树片段集204、重复片段检测部205、无重复型规则单元206、单结点重复型规则单元207、多结点重复型规则单元208、混合重复型规则单元209、重复规则合并部211、以及产生式规则集213。

句法分析树库201为用于学习的句法分析树库，即图1中所示的训练树库101，其中标示了用于训练的句子的语法成份及成份间的嵌套关系。本发明分别在两个树库英文PennTreebank和中文PennTreebank上进行了实际应用，但是应该指出的是本发明所提出的句法分析装置和句法分析方法与语言无关，任何语言只要标注了句子的语法成份和成份间的嵌套关系，就可以用本发明的技术方案获取句法分析规则，并随后对输入句子进行句法分析。

树片段分解部202根据分解参数输入单元203输入的分解参数，将句法分析树库201即训练树库101中的每棵句法树分解为若干较小的子树或树片段。树片段的表示格式如下。

<freq:xx>{<f₁>...<f_n>}P→Y₁ Y₂...Y_n

其中，<freq:xx>为频度信息，表示该树片段在训练树库中的出现次数。<f_i>为属性特征，主要用来描述使用该规则时的上下文信息、词汇或语义特点。属性特征根据分解参数输入单元203所输入的分解参数确定，规则可以包含属性特征，也可以不包含。

P表示该树片段的上位结点，为一个短语标记。Y_i表示P结点的子结点，为一个短语标记或一个词汇标记。“{<f₁>...<f_n>}P→Y₁ Y₂...Y_n”表示在出现了<f₁>...<f_n>属性的情况下，短语P可以由Y₁ Y₂...Y_n构成。

由树片段的表示格式可知，一个树片段即为一个产生式形式的规则。句法分析树库201中的每棵句法树可以分解为若干树片段，所有分解结果均存入树片段集204中，形成产生式形式的规则集。

然后，树片段集(即，产生式规则集)输入重复片段检测部205。重复片段检测部205检测所输入的树片段中的“Y₁ Y₂...Y_n”部分是否有重复的结点序列。根据结点重复的形式，树片段集被分为如上定义的单结点重复型规则单元207、多结点重复型规则单元208、混合重复型规则单元209和无重复型规则单元206。包含重复结点序列的规则，将用正则表达式符号“＊”或“+”来表示。

在引入正则表达式之后，将转化出一些形式相同的规则。例如，“规则R₁：P→ABBBC”和“规则R₂：P→ABBC”用正则表达式形式表示时均表达为P→AB^＊C。

因此，将所有规则转化为正则表达式形式后，需要对重复的形式相同的规则进行去除。基于此，重复规则合并部211将形式相同的规则合并为一个规则，同时将规则的频度进行相应合并。由此，可以直接生成用于对输入句子进行句法分析的产生式规则集213。

另外，为了提高句法分析的效率，根据本发明一个实施例的规则获取模块102还可以包括选择策略单元210和规则选择部212。规则选择部212根据选择策略单元212提供的选择策略，对重复规则合并部211所生成的产生式规则进行选择，从而生成缩减的高效产生式规则集213，以便提高句法分析的效率。

以下通过具体实例说明规则获取模块102的操作过程。图6和图7是用于说明规则获取模块102在获取句法规则时所使用的两个示例句法树S1和S2。规则获取模块102从句法树S1和S2中获取句法分析规则的过程如下。

首先，树片段分解部202根据分解参数输入单元203提供的分解参数对句法树S1和S2进行分解。在本实例中假设分解参数为将树分解为上下文无关的短语，则将图6和图7所示的句法树S1和S2分解后所形成的树片段集如下表1所示。

表1树片段集

然后，将表1所示的分解片段集进入重复片段检测部205，在此检测是否有重复结点。在该示例中片段集中包含有重复结点。重复部分采用正则表达式形式表示后，根据重复的类型分别送入单元206至单元209。上面表1所示的片段集用正则表达式表示后的结果如下表2所示。

表2正则表达式表示的规则集

用正则表达式表示后的片段将作为句法分析规则候选输入到重复规则合并部211，在此进行重复规则的合并。上面表2所示的规则经过重复规则合并部211合并后形成的规则集共包含9条规则，其中对规则“X→a^＊”进行了重复合并。重复规则合并部211的输出结果如下表3所示。

表3重复规则合并后的规则集

之后，重复规则合并部211的输出结果进入规则选择部212，按照选择策略进行选择，最终形成规则应用模块103进行句法分析所需要的句法分析规则集，并作为产生式规则集213输入规则应用模块103。

图3示出根据本发明实施例的图1所示的规则应用模块103的结构方框图。规则应用模块103应用图2所示的规则获取模块102形成的句法分析规则集，即产生式规则集对输入句子进行句法分析，输出输入句子的语法成份及成份间的关系。如图3所示，根据该实施例的规则应用模块103包括产生式规则集302、规则编译部303、规则查询表304、规则查询部305、句法分析部306、歧义消解部308等。

产生式规则集302为规则获取模块102形成的产生式规则集213，首先进入规则编译部303。规则编译部303将产生式规则集302编译形成能被规则查询部305使用的规则查询表304。

输入句子301输入句法分析部306后，由句法分析部306通过规则查询部305在规则查询表304中查询可以应用于该输入句子301的句法分析规则，根据句法分析规则识别输入句子301的语法成份，并输出分析结果。句法分析的过程采用CYK算法从输入句子301的词结点开始，规则查询的过程从1个结点扩展到2个结点，至止覆盖整个句子。

句法分析规则可能给出多个局部分析候选307，歧义消解部308从中选择最优的局部分析结果309。歧义消解部308选择的局部分析结果309进入句法分析部306进行进一步的句法分析，直至句法分析部306输出满意的最终分析结果310。

对于在规则获取模块102中生成的含有正则表达式形式的产生式句法分析规则，根据本发明的实施例，通过对产生式句法分析规则中含有正则表达式的部分增加中间生成结果，由规则编译部303、规则查询部305、句法分析部306解决了在句法分析过程中使用包含正则表达式的句法分析规则的问题。其具体的操作过程如下。

规则编译部303为产生式规则集中包含正则表达式的部分增加中间生成标记和中间生成规则，并用中间生成标记去替换规则中该正则表达式表示的部分。

具体来说，对于x^＊型片段，增加中间生成标记<x>及中间生成规则<x>→xx和<x>→<x>x。对于[x..y]+型片段，增加中间生成标记[x..y]及中间生成规则[x..y]→x..yx...y和[x..y]→[x..y]x...y。

例如，规则“R₂：X→a^＊”中的“a^＊”含有正则表达式，则为“a^＊”增加中间生成标记“<a>”及两条中间生成规则“<a>→aa”和“<a>→<a>a”。用中间生成标记替换规则中的正则表达式部分，将规则R₂转化为X→<a>。

表3所示的重复规则合并部211的输出结果，在增加中间生成标记和中间生成规则后的结果如下表4所示，所使用的中间标记和中间生成规则如表5所示，其中引入6条中间生成规则，分别用R₁₃～R₁₇表示。

表4重复规则合并部211的输出结果增加中间标记后的结果

表5转化重复规则合并部211的输出结果时用到的中间标记和中间生成规则

  中间标记  中间生成规则  <a>  R₁₃：<a>→aa  R₁₄：<a>→<a>a  [ab]  R₁₅：[ab]→abab  R₁₆：[ab]→[ab]ab  <X>  R₁₇：<X>→XX  R₁₇：<X>→<X>X

在规则编译过程中，中间标记并入规则集的短语标记集，中间生成规则并入句法分析规则集，规则编译部303统一组织所有规则和标记，生成便于查询的规则查询表304。

句法分析部306在分析过程中，按照与识别短语相同的方式识别中间标记，采用CYK算法通过规则查询部305查询所有适合当前输入句子301的句法分析规则(包含中间生成规则)，生成句法分析结果。

下面通过使用表4和表5中的规则分析输入句子“aaababababcaa”，举例说明规则应用模块103的操作过程。

表6分析句子使用规则示例

 过程  当前分析状态  使用规则 过程1  aaababababcaa  R₁₃：<a>→aa  R₁₅：[ab]→abab  R₁₃：<a>→aa 过程2  <a>[ab]abc<a>  R₂：X→<a>  R₄：Z→[ab] 过程3  XZabcX  R₅：M→abcX 过程4  XZM  R₇：S→XZM 过程5  S

这里应该指出的是，上述示例仅是作为举例给出了一种使用句法分析规则的方式，并非最优或唯一。该示例的目的在于说明如何通过引入中间符号和中间分析规则，在句法分析的过程中使用含有正则表达式的句法分析规则。

在规则使用的过程中，同一状态可能会出现若干可用的分析规则，即出现分析歧义。规则查询部305查询得到的多种生成规则候选307将输入到歧义消解部308，由歧义消解部308选择最优规则进行应用，从而生成局部分析结果309。

根据本发明的一个实施例，歧义消解部308通过计算句法分析树的概率P(S，t)选择使用的最优规则，进而输出最优句法分析结果309。其基本的计算公式如下：

$P(s,t)=\underset{r\in D\left(T\right)}{\Pi }p\left(r\right)$

其中S为输入句子，t为句法分析树，r为句法分析过程中使用的一条句法分析规则，D(T)为生成句法分析树t使用的全部句法分析规则，而p(r)为针对句法分析规则r的规则概率。

在计算规则概率时，中间符号与句法分析中存在的短语符号等同，中间分析规则与非中间分析规则等同。已有的各种计算句法分析规则的方法均可以用来计算在根据本发明的处理中获取的句法分析规则。其规则的概率估计方法简单总结如下：

1.非正则表达式规则：规则概率估计与已有方法相同。

2.中间生成规则：将中间符号做为短语对待，采用已有方法估计规则概率。

3.含有正则表达式的规则：其中r_i为转化该含有正则表达式的规则时用到的一条中间规则，而p(r_i)为针对该中间句法分析规则r_i的规则概率。

在根据本发明该实施例的规则应用模块103中，通过引入中间符号和中间生成规则，解决了如何使用正则表达式规则的问题。通过将中间符号和中间生成规则与短语符号和一般的规则同等对待，解决了计算正则表达式规则的概率估计问题。

通过使用表6的规则，对输入句子“aaababababcaa”进行句法分析后得到的最终输出的句法分析结果如图8所示。

规则应用模块103输出的句法分析结果，例如如图8所示的句法分析结果将输入句法树生成模块104，在此根据用户的需求生成依存句法关系图或短语结构型句法分析树。

图4示出根据本发明实施例的图1所示的句法树生成模块104的结构方框图。如图4所示，根据本发明该实施例的句法树生成模块104包括中间标记清理部402、核心结点标注部403、依存结构生成部404和短语结构生成部405。

图4所示的最终分析结果401既是规则应用模块103输出的句法分析结果310。最终分析结果401首先输入中间标记清理部402，清除在句法分析过程中使用的中间标记。

在清除中间标记之后，如果需要生成短语结构型句法分析树，则由短语结构生成部405生成短语结构树。如果需要生成依存句法关系图，则将清除中间标记之后的分析结果输入核心结点标注部403进行核心结点标注，之后由依存结构生成部404生成依存关系。

根据本发明的一个实施例，中间标记清理部402清理中间结点的步骤用递归函数描述如下所述。

Function CleanTags(n_i)

Begin

   For each s_i，where s_i∈{sons of n_i}

    cleanTags(s_i)

    //如果s_i为中间符号

    If s_i is a semi-finished label

      //si的所有儿子上升作为ni的儿子

      move up all the sons of s_i as the sons of n_i

    Endif

   End for

End

图8所示的句法分析模块103的最终分析结果310通过中间标记清理部402进行中间结点清除后的结果如图9所示。

以上描述了根据本发明实施例的句法分析装置的结构及其工作原理。下面将结合附图10～13描述根据本发明实施例的上述句法分析装置所应用的句法分析方法。

图10示出根据本发明的一个实施例的句法分析方法的流程图。如图10所示，根据该实施例的句法分析方法包括规则获取步骤S1001、规则应用步骤S1003和句法树生成步骤S1005。

首先，在规则获取步骤S1001中，从已经标注好的训练树库，例如图1所示的训练树库101，学习句法分析规则以生成包含正则表达式形式的产生式规则集，其中对于产生式规则的后项中的重复部分用正则表达式来表示。然后，在规则应用步骤S1003中，使用规则获取步骤S1001获得的产生式规则集对输入句子进行分析，识别出输入句子的成份及成份间的关系。最后，在句法树生成步骤S1005中，根据规则应用步骤S1003所输出的输入句子的成份及成份间的关系，生成输入句子的依存句法关系图或者短语结构型句法分析树。

图11示出根据本发明一个实施例在图10所示的规则获取步骤S1001中执行的处理方法的详细流程图。如图10所示，根据该实施例的规则获取方法包括树片段分解步骤S1101、重复片段检测步骤S1103、重复规则合并步骤S1105和规则选择步骤S1107。

首先，在树片段分解步骤S1101中，将训练树库例如图1所示的训练树库101中的每棵句法树分解为作为产生式规则的树片段，以形成树片段集，例如图2中所示的树片段集204。

接着，在重复片段检测步骤S1103中，检测树片段分解步骤S1101得到的树片段集中的产生式规则的后项中是否有重复的结点序列，并将具有重复的结点序列的产生式规则表示为正则表达式形式的产生式规则。然后，在重复规则合并步骤S1105中，将重复片段检测步骤S1103生成的形式相同的产生式规则合并为一个产生式规则，以形成产生式规则集。

优选地，为了提高句法分析的效率，根据本发明一个实施例的规则获取方法还包括规则选择步骤S1107，根据事先设定的选择策略对重复规则合并步骤S1105所生成的产生式规则进行选择，以生成缩减的产生式规则集，比如图2所示的产生式规则集213。

树片段分解步骤分解得到的树片段可以表示为

<freq:xx>{<f₁>...<f_n>}P→Y₁Y₂...Y_n，n为大于等于1的正整数。其中<freq:xx>为频度信息，表示该树片段在训练树库中的出现次数；<f_i>为属性特征，用于描述使用该产生式规则时的上下文信息、词汇或语义特点，i为从1至n的任一整数；P表示该树片段的上位结点，为一个短语标记；Y_i表示P结点的子结点，为一个短语标记或一个词汇标记；“{<f₁>...<f_n>}P→Y₁Y₂...Y_n”表示在出现了<f₁>...<f_n>属性的情况下，短语P可以由Y₁Y₂...Y_n构成。

值得指出的是，重复规则合并步骤S1105在将重复片段检测步骤S1103生成的形式相同的产生式规则合并为一个产生式规则时，还将产生式规则的频度进行相应合并。

图12示出根据本发明一个实施例在图10所示的规则应用步骤S1003中执行的处理方法的详细流程图。

如图12所示，首先在规则编译步骤S1201，将规则获取步骤S1001生成的产生式规则集编译成句法分析规则的规则查询表，例如如图3中所示的规则查询表304。然后，在句法分析步骤S1203中，通过规则查询步骤S1205在规则查询表304中查询能够应用于输入句子的句法分析规则，根据句法分析规则识别输入句子的语法成份及成份间的关系。这里，规则查询步骤S1205用于查询规则编译步骤S1201所编译的规则查询表304。

接下来，在歧义消解步骤S1207中从句法分析步骤S1203和规则查询步骤S1205生成的局部分析候选中选择最优的局部分析结果。然后，在步骤S1209判断所得到的分析结果是否满足要求。如果不满足要求，则返回句法分析步骤S1203，对歧义消解步骤S1207选择的局部分析结果进行进一步的句法分析。

如果在步骤S1209中判断经过歧义消解后得到的分析结果满足要求，则处理流程前进到步骤S1211，输出最终的句法分析结果。

根据本发明的一个优选实施例，在规则编译步骤S1201中，为产生式规则集中包含正则表达式的部分增加中间生成标记和中间生成规则，并用中间生成标记替换产生式规则中正则表达式表示的部分，中间生成标记并入句法分析规则集的短语标记集，中间生成规则并入句法分析规则集。

在句法分析步骤S1203中，按照与识别短语标记相同的方式识别中间生成标记，通过规则查询步骤S1205查询所有适合当前输入句子的包括中间生成规则的句法分析规则以识别输入句子的语法成份及成份间的关系。

在歧义消解步骤S1207中，按照下面的公式通过计算句法分析树的概率P(S，t)来确定使用的最优产生式规则，以选择最优的局部分析结果：

$P(s,t)=\underset{r\in D\left(T\right)}{\Pi }p\left(r\right)$

其中S为输入句子，t为句法分析树，r为句法分析过程中使用的一条句法分析规则，D(T)为生成句法分析树t使用的全部句法分析规则，而p(r)为针对句法分析规则r的规则概率。

中间生成标记的规则概率的计算与句法分析中存在的短语符号的规则概率的计算相同，中间生成规则的规则概率的计算与非中间生成规则的规则概率的计算相同。

对于含有正则表达式的产生式规则用公式计算规则概率，其中r_i为转化该含有正则表达式的规则时用到的一条中间生成规则，而p(r_i)为针对该中间生成规则r_i的规则概率，n为大于等于1的正整数，i为从1至n的任一整数。

图13示出根据本发明一个实施例图10所示的句法树生成步骤S1005中执行的处理方法的详细流程图。

如图13所示，首先在中间标记清理步骤S1301中，清除在句法分析过程中使用的中间生成标记。然后，在步骤S1303中判断是要生成依存句法关系图还是要生成短语结构型句法分析树。

如果在步骤S1303中判断需要生成短语结构型句法分析树，则处理流程前进到短语结构生成步骤S1305，在此根据中间标记清理步骤S1301输出的清除中间生成标记之后的输入句子的成份及成份间的关系，生成短语结构型句法分析树，并将生成的输入句子的短语结构型句法分析树输出。

如果在步骤S1303中判断需要生成输入句子的依存句法关系图，则处理流程前进到核心结点标注步骤S1307，根据中间标记清理步骤S1301输出的清除中间生成标记之后的输入句子的成份及成份间的关系进行核心结点标注。然后在依存结构生成步骤S1309中，根据核心结点标注步骤S1307标注的核心结点生成输入句子的依存句法关系图，并将生成的输入句子的依存句法关系图。

以上结合附图详细描述了本发明的句法分析装置和句法分析方法的具体实施例。从以上描述中可以看出，根据本发明的句法分析装置和句法分析方法，通过使用正则表达式形式的句法分析规则，增加了句法分析规则的描述能力，克服了现有方法中存在的规则表达不灵活，表达能力不强的缺点。本发明提出的句法规则获取方法及句法分析算法，可以形成一个支持正则表达式规则的句法分析器，实现高效、正确的句法分析。

此外，根据本发明的句法分析装置和句法分析方法，在产生式句法分析规则中引入正则表达式时，给出了一种描述文法结构中重复部分的方法，重复片段的重复次数可以不受限制，同一个句法分析规则，可以分析不同长度一类短语。通过本发明提出的句法分析装置和句法分析方法，可以更灵活地描述文法，既可以描述文法中各成份的位置关系，又可以描述语法结构中局部成份可以重复的特性，因此用本发明获得的规则具有更强的通用性，更鲁棒。

另外，由于在学习的训练树库中，包含较多成分的短语(即结点较多的长短语，本文称为长短语)出现的频度较低，这部分短语用已有的句法分析规则描述时通常将被忽略，这样在句法分析时如果出现长短语将不能分析，会出现规则稀疏的问题。而长短语通常都包含有可重复的部分，使用本发明的句法分析装置和句法分析方法，通过将长短语中重复的部分进行合并，不管短语中重复的部分重复多少次，都可以用同一个句法分析规则表示出来，可以一定程度地解决规则的稀疏问题。

此外，根据本发明的句法分析装置和句法分析方法，在进行句法分析时，通过对规则中含有正则表达式的部分增加中间生成结果，从而解决了在句法分析过程中使用包含正则表达式的句法分析规则的问题。

上文中以从汉语抽象出的句法树作为具体实例阐述了本发明的基本工作原理，但是，使用本发明描述的句法分析装置及其句法分析方法可同样对其他各种语言中的语法或语义成份进行识别。另外，本发明方法也可用于对基因组序列的分析或类似的从输入符号序列中识别某类成份的任务。因此可以理解，凡应用于其它语言或符号系统，不超出本发明的构思要领的变化都应归于本发明的保护范围之中。

以上结合具体实施例描述了本发明的基本原理，但是，需要指出的是，对本领域的普通技术人员而言，能够理解本发明的方法和装置的全部或者任何步骤或者部件，可以在任何计算装置(包括处理器、存储介质等)或者计算装置的网络中，以硬件、固件、软件或者它们的组合加以实现，这是本领域普通技术人员在阅读了本发明的说明的情况下运用他们的基本编程技能就能实现的。

因此，本发明的目的还可以通过在任何计算装置上运行一个程序或者一组程序来实现。所述计算装置可以是公知的通用装置。因此，本发明的目的也可以仅仅通过提供包含实现所述方法或者装置的程序代码的程序产品来实现。也就是说，这样的程序产品也构成本发明，并且存储有这样的程序产品的存储介质也构成本发明。显然，所述存储介质可以是任何公知的存储介质或者将来所开发出来的任何存储介质。

在通过软件和/或固件实现本发明的实施例的情况下，从存储介质或网络向具有专用硬件结构的计算机，例如图14所示的通用个人计算机700安装构成该软件的程序，该计算机在安装有各种程序时，能够执行各种功能等等。

在图14中，中央处理单元(CPU)701根据只读存储器(ROM)702中存储的程序或从存储部分708加载到随机存取存储器(RAM)703的程序执行各种处理。在RAM 703中，也根据需要存储当CPU 701执行各种处理等等时所需的数据。CPU 701、ROM 702和RAM 703经由总线704彼此连接。输入/输出接口705也连接到总线704。

下述部件连接到输入/输出接口705：输入部分706，包括键盘、鼠标等等；输出部分707，包括显示器，比如阴极射线管(CRT)、液晶显示器(LCD)等等，和扬声器等等；存储部分708，包括硬盘等等；和通信部分709，包括网络接口卡比如LAN卡、调制解调器等等。通信部分709经由网络比如因特网执行通信处理。

根据需要，驱动器710也连接到输入/输出接口705。可拆卸介质711比如磁盘、光盘、磁光盘、半导体存储器等等根据需要被安装在驱动器710上，使得从中读出的计算机程序根据需要被安装到存储部分708中。

在通过软件实现上述系列处理的情况下，从网络比如因特网或存储介质比如可拆卸介质711安装构成软件的程序。

本领域的技术人员应当理解，这种存储介质不局限于图14所示的其中存储有程序、与装置相分离地分发以向用户提供程序的可拆卸介质711。可拆卸介质711的例子包含磁盘(包含软盘(注册商标))、光盘(包含光盘只读存储器(CD-ROM)和数字通用盘(DVD))、磁光盘(包含迷你盘(MD)(注册商标))和半导体存储器。或者，存储介质可以是ROM 702、存储部分708中包含的硬盘等等，其中存有程序，并且与包含它们的装置一起被分发给用户。

还需要指出的是，在本发明的装置和方法中，显然，各部件或各步骤是可以分解和/或重新组合的。这些分解和/或重新组合应视为本发明的等效方案。并且，执行上述系列处理的步骤可以自然地按照说明的顺序按时间顺序执行，但是并不需要一定按照时间顺序执行。某些步骤可以并行或彼此独立地执行。

虽然已经详细说明了本发明及其优点，但是应当理解在不脱离由所附的权利要求所限定的本发明的精神和范围的情况下可以进行各种改变、替代和变换。而且，本申请的术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者装置不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者装置所固有的要素。在没有更多限制的情况下，由语句“包括一个......”限定的要素，并不排除在包括所述要素的过程、方法、物品或者装置中还存在另外的相同要素。