简单模式的一种匹配方法  

A Matching Method for Simple Pattern

作　　者：张强[1] 陈海明[1] 

机构地区：[1]中国科学院软件研究所计算机科学开放实验室,北京100080

出　　处：《计算机工程与应用》2001年第17期63-66,163,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(编号:69873042);国家"九五"攻关计划(编号:96-729-06-02)的资助

摘　　要：模式匹配是包括LFC在内的大多数函数式语言都具有的特点。文章在LFC语言现有的模式匹配实现方法的基础上，结合常用的模式匹配树的构造思想，设计了一种模式匹配方法。这种模式匹配方法通过计算给定模式集合的扩展集合来构造模式匹配树。虽然在最坏情况下，该方法与LFC现有实现的空间复杂度一样，但当函数定义是部分构造式，而定义中的非项模式覆盖了较多项时，这种模式匹配方法可以避免LFC语言现有实现中较大的编码空间。这个方法略作修改即可用于复杂的嵌套模式，是一种通用的模式匹配方法。： Pattern matching is a feature of lots of functional languages including LFC．This article introduces a method of pattern matching，which is based on the implementation of LFC and the construction of pattern matching tree．Though the worst－case space complexity is comparable to that of the implementation of LFC，this method can decrease the large code space of the implementation of LFC when the definition of the function is good－natured．This method can be also used for nested pattern with little modification and is a general method for pattern matching．

关 键 词：函数式语言 模式匹配 简单模式 LFC语言 形式规约语言 

分 类 号：TP301.2[自动化与计算机技术—计算机系统结构]