平行最外模式匹配*
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:


PARALLEL—OUTERMOST PATTERN MATCHING
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    平行最外策略是归约系统中适用范围非常广的策略,平行最外模式匹配研究适用于该策略的高效模式匹配方法.本文在生成自适应模式匹配自动机APMA的基础上,充分利用匹配失败状态的部分匹配信息,构造了平行最外模式匹配自动机POPMA.利用POPMA进行模式匹配,在维持空间开销不大的前提下,降低了朴素思想的2大时间开销.并将模式匹配和归约策略结台起来,几乎一遗扫描即可找出所有平行最外匹配子项,具有很高的时空效率.借助于POP- MA,还可以对平行最外策略进行改进.

    Abstract:

    Parallel—outermost strategy is widely used in reduction systems.Parallel—outermost pattern matching studies the pattern matching method adapted to the strate-gy.By preproeessing the patterns into an adaptive pattern matching automaton APMA,this paper takes advantages of local matching information of unsuccessful matching states to build parallel—outermost pattern matching automaton POPMA.By use of POPMA,all of parallel—outermost pattern matching subterms can be gotten through a single scan.The method limits the size of the automaton,avoids the overheads in the naive algorithm and makes the good relation between the pattern matching and the reduction strategy.POPMA also can be used to improve parallel—outermost strategy.

    参考文献
    相似文献
    引证文献
引用本文

沈理,林凯,孙永强.平行最外模式匹配*.软件学报,1996,7(zk):329-337

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:1995-09-22
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号