| 摘要: |
| 平行最外策略是归约系统中适用范围非常广的策略，平行最外模式匹配研究适用于该策略的高效模式匹配方法．本文在生成自适应模式匹配自动机APMA的基础上，充分利用匹配失败状态的部分匹配信息，构造了平行最外模式匹配自动机POPMA．利用POPMA进行模式匹配，在维持空间开销不大的前提下，降低了朴素思想的2大时间开销．并将模式匹配和归约策略结台起来，几乎一遗扫描即可找出所有平行最外匹配子项，具有很高的时空效率．借助于POP-
MA,还可以对平行最外策略进行改进． |
| 关键词: 模式匹配，归约策略，自动机，项． |
| DOI： |
| 分类号: |
| 基金项目: |
|
| PARALLEL—OUTERMOST PATTERN MATCHING |
|
Shen Li,Lin Kai,Sun Yongqiang
|
| 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． |
| Key words: Pattern matching,reduction strategy,automaton,term． |
