Synthesizing Context Free Grammars from Sample Strings Based on Inductive CYK Algorithm
Synthesizing Context Free Grammars from Sample Strings Based on Inductive CYK Algorithm
复制标题
基于归纳CYK算法的样本字符串合成上下文无关文法
DOI：
10.1007/978-3-540-45257-7_15
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
T. Ishiwata
中科院分区：
文献类型：
--
作者：
Katsuhiko Nakamura;T. Ishiwata
本文描述了一种从正负样本串合成上下文无关文法的方法，并在一个语法推理系统Synapse中实现。该方法基于正样本的增量学习和基于“归纳CYK算法”的规则生成方法，生成解析正样本所需的最小产生式规则。Synapse可以生成明确的语法，也可以生成歧义语法。实验表明，Synapseco可以在相当短的时间内合成几个简单的上下文无关文法。
This paper describes a method of synthesizing context free grammars from positive and negative sample strings, which is implemented in a grammatical inference system calledSynapse. The method is based on incremental learning for positive samples and a rule generation method by “inductive CYK algorithm,” which generates minimal production rules required for parsing positive samples. Synapse can generate unambiguous grammars as well as ambiguous grammars. Some experiments showed thatSynapsecan synthesize several simple context free grammars in considerably short time.