软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2000年
8期
1030-1034
,共5页
上下文无关文法%产生式集合%产生式集合划分%句子生成%句子生成策略
上下文無關文法%產生式集閤%產生式集閤劃分%句子生成%句子生成策略
상하문무관문법%산생식집합%산생식집합화분%구자생성%구자생성책략
给出了上下文无关文法(context-free grammar,简称CFG)产生式集的一种划分方法,可将产生式分为两类.使用一类产生式进行推导时,推导过程将无限进行下去;使用另一类进行推导时,推导过程将迅速结束.证明了CFG句子生成过程一定是先使用一类产生式使生成的句型不断变长、变复杂,再使用另一类产生式使句型变成句子.据此,提出了一种可控制的通用句子生成方法.其生成一条句子的时间和空间复杂度是O(r+n),其中n是生成句子的长度或深度限制,r是给定上下文无关文法中产生式的数目.同时,给出了适应不同需要的句子生成策略.
給齣瞭上下文無關文法(context-free grammar,簡稱CFG)產生式集的一種劃分方法,可將產生式分為兩類.使用一類產生式進行推導時,推導過程將無限進行下去;使用另一類進行推導時,推導過程將迅速結束.證明瞭CFG句子生成過程一定是先使用一類產生式使生成的句型不斷變長、變複雜,再使用另一類產生式使句型變成句子.據此,提齣瞭一種可控製的通用句子生成方法.其生成一條句子的時間和空間複雜度是O(r+n),其中n是生成句子的長度或深度限製,r是給定上下文無關文法中產生式的數目.同時,給齣瞭適應不同需要的句子生成策略.
급출료상하문무관문법(context-free grammar,간칭CFG)산생식집적일충화분방법,가장산생식분위량류.사용일류산생식진행추도시,추도과정장무한진행하거;사용령일류진행추도시,추도과정장신속결속.증명료CFG구자생성과정일정시선사용일류산생식사생성적구형불단변장、변복잡,재사용령일류산생식사구형변성구자.거차,제출료일충가공제적통용구자생성방법.기생성일조구자적시간화공간복잡도시O(r+n),기중n시생성구자적장도혹심도한제,r시급정상하문무관문법중산생식적수목.동시,급출료괄응불동수요적구자생성책략.
