摘要
通过对关联文法语法推导树的详细分析,提出了具有共享子树的语法推导树算法。该算法实现了不仅叶子节点可以共享,其中任意相同子树均可以共享,有效节省了存储空间。针对共享子树的特点,提出了并行构造共享子树的算法,并通过实例详细描述了算法并行处理过程,验证了算法的可行性和正确性。
Syntax derivation trees of conjunctive grammar are detailly analyzed.Condensed derivation trees are adopted.It needs less stored space.Condensed derivation trees of conjunctive grammar have not only identical terminal descendants,but also any identical subtrees which have the same set of terminal descendants.So the subtrees that can derivate the same termination can be constructed simultaneously.The algorithm of parallel constructing condensed derivation trees and the implementing process of the algorithm are also described in this paper.The parallel process is described by instance and the validity of the algorithm is verified.
作者
李玉萍
李科
孙玉强
LI Yuping;LI Ke;SUN Yuqiang(School of Information Technology,Shangqiu Normal University,476000,Shangqiu,Henan,PRC;School of Mathematics,Changzhou University,213016,Changzhou,Jiangsu,PRC)
出处
《江西科学》
2019年第1期121-124,共4页
Jiangxi Science
基金
国家自然科学基金项目(61640211)
河南省高等学校重点科研项目(19B520023)
关键词
语法推导树
压缩推导树
并行处理
syntax derivation trees
condensed derivation trees
parallel processing
