基于最小序句子的上下文无关语言句子枚举

Enumerating Sentences of Context Free Language Based on First One in Order

形式规约获取系统SAQ和一些形式化验证系统中常常需要枚举上下文无关语言的句子 ,现有的枚举方法较少且效率较低 以上下文无关语言L(G)的最小序句子和最大序句子为基础 ,从最小序句子开始按照一定的顺序扫描字符串 ,直至扫描到最大序句子为止 ,对被扫描的字符串进行判断取舍 在扫描的过程中采用削减和前瞻策略 ,很大程度上减少了被扫描的字符串个数 ,可以取得较好的时空性能 实验数据表明 。

Enumerating sentences for CFL is often needed in SAQ(specification acquisition system) and some formal proof systems. The current methods are not very efficient and enough. Some of them are limited to deal with specific CFL like regular CFL. First and last sentences of the same length in order can be found by parsing the productions. Then scanning those strings from first sentence to last sentence in order covers all the sentences of the same length. The scanned strings are determined to be outputted or skipped by Earley algorithm. Earley algorithm is modified to judge whether a string is the left subword of some sentences of CFL. Two control strategies, reduction and look-ahead, are adopted in the scanning process. So the number of those scanned strings are decreased greatly. And good time and space efficiencies can be acquired in practice. Compared with other methods, the method shows some advantages by test data.