| 上下文无关语言句子的反向自然枚举 |
| |
| 引用本文： | 戴晓君.上下文无关语言句子的反向自然枚举[J].计算机工程与设计,2008,29(8):1874-1877. |
| |
| 作者姓名： | 戴晓君 |
| |
| 作者单位： | 中国科学院软件研究所,计算机科学国家重点实验室,北京,100080 |
| |
| 摘 要： | 在测试基于复杂数据结构的程序时,需要用到上下文无关语言句子的枚举.基于上下文无关语言按推导树高度的分层构造,提出了句子的反向自然枚举算法.通过堆、层、簇和长方体将句子划分为有穷集合序列,该算法的时间效率为O(n),n是被枚举句子的长度.实验数据表明,该算法是高效的,且应用更加便利.
|
| 关 键 词： | 上下文无关语言 句子枚举 分层构造 算法 线性时间 |
| 文章编号： | 1000-7024(2008)08-1874-04 |
| 修稿时间： | 2007年6月6日 |
Reverse enumeration of sentences of context-free languages |
| |
| DAI Xiao-jun.Reverse enumeration of sentences of context-free languages[J].Computer Engineering and Design,2008,29(8):1874-1877. |
| |
| Authors: | DAI Xiao-jun |
| |
| Affiliation: | DAI Xiao-jun(State Key Laboratory of Computer Science,Institute of Software,Chinese Academy of Sciences,Beijing 100080,China) |
| |
| Abstract: | Enumerating sentences of CFL are often needed when testing programs involving complex data structures.An algorithm is described that enumerates sentences of CFL reversely according to the height of derivation trees.All sentences of CFL are partitioned into subsets by heaps,hierarchies,clusters and cuboids.It has a time bound proportional to(where is the length of the sentence enumerated).The experiment shows that this algorithm is highly efficient and convenient. |
| |
| Keywords: | context-free language sentence enumeration hierarchy algorithm linear time |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
