Type inference for unique pattern matching
Type inference for unique pattern matching
复制标题
用于唯一模式匹配的类型推断
DOI：
10.1145/1133651.1133652
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Stijn Vansummeren
中科院分区：
文献类型：
--
作者：
Stijn Vansummeren
正则表达方式提供了一种自然的声明性方式，可以表达对半结构数据的约束并从中提取相关信息。确实，它是编程语言PERL的核心功能，在SED和AWK等各种Unix工具中表面表面，并且最近在XML编程语言Xduce的背景下提出了。由于常规表达式通常可能是模棱两可的，因此已经提出了不同的歧义政策来获得独特的匹配策略。我们正式定义了（1）POSIX和（2）第一和最长的匹配歧义策略下的匹配语义。我们表明，根据第一次匹配和递归来定义最长匹配的普遍接受方法不符合最长匹配的自然概念。我们继续解决两种歧义策略的类型推理问题，该策略包括计算输入值的所有子部分的集合，该子表达在给定的策略下可以匹配。
Regular expression patterns provide a natural, declarative way to express constraints on semistructured data and to extract relevant information from it. Indeed, it is a core feature of the programming language Perl, surfaces in various UNIX tools such as sed and awk, and has recently been proposed in the context of the XML programming language XDuce. Since regular expressions can be ambiguous in general, different disambiguation policies have been proposed to get a unique matching strategy. We formally define the matching semantics under both (1) the POSIX, and (2) the first and longest match disambiguation strategies. We show that the generally accepted method of defining the longest match in terms of the first match and recursion does not conform to the natural notion of longest match. We continue by solving the type inference problem for both disambiguation strategies, which consists of calculating the set of all subparts of input values a subexpression can match under the given policy.