CoDE Publications CoDE Publications
IRIDIA Publications IRIDIA Publications
SMG Publications
WIT Publications
WIT Publications
SMG Publications
Home People Research Activities Publications Teaching Resources
By Class By Topic By Year Technical Reports
By Class By Topic By Year Technical Reports
login
S. Vansummeren. Type Inference for Unique Pattern Matching. ACM Transactions on Programming Languages and Systems, 28(3):389-428, 2006.

Abstract

Regular expression patterns provide a natural, declarative way to express constraints on semi-structured 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.


Updated: 2017-03-27