%0 Journal Article
%T Generating Sentences of CFL Based on Partition of CFG Production Set<br>基于产生式集划分的上下文无关语言句子生成
%A WANG Hong-hao
%A DONG Yun-mei
%A <br>王泓皓
%A 董韫美
%J 软件学报
%D 2000
%I 
%X In this paper, a method is presented to partition productions of CFG (context-f ree grammar). It divides production set into two parts. The derivation with prod uctions in one part will never terminate, while it must terminate rapidly with p roductions in the other part. It is proved that the procedure of generating sent ences of CFL (context-free language) is using productions in one part to make t he sentential form longer and more complex first, and then using productions in the other part to terminate the procedure. A general controllable method is atta ined for generating sentences of CFL with restricted length or depth. The time a nd space complexity for generating one sentence is O(r+n), where n is th e restricted length or depth of sentences and r is the number of productions in given CFG. The generating strategies for different conditions are also discu ssed.
%K CFG (context-free grammar)
%K production set
%K production set partition
%K sentence generation
%K sentence generating strategy<br>上下文无关文法
%K 产生式集合
%K 产生式集合划分
%K 句子生成
%K 句子生成策略.
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=09CA6E56935BDF94&yid=9806D0D4EAA9BED3&vid=708DD6B15D2464E8&iid=5D311CA918CA9A03&sid=0342E221E01D5238&eid=78996380F3108204&journal_id=1000-9825&journal_name=软件学报&referenced_num=2&reference_num=7