Please use this identifier to cite or link to this item:
|Title:||Type inference for unique pattern matching||Authors:||VANSUMMEREN, Stijn||Issue Date:||2006||Source:||ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 28(3). p. 389-428||Abstract:||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.||Keywords:||pattern matching; disambiguation policies; programming languages; XML; XML||Document URI:||http://hdl.handle.net/1942/1425||Link to publication:||http://doi.acm.org/10.1145/1133651.1133652||ISSN:||0164-0925||e-ISSN:||1558-4593||ISI #:||000238273200001||Category:||A1||Type:||Journal Contribution||Validations:||ecoom 2007|
|Appears in Collections:||Research publications|
Show full item record
Files in This Item:
|toplas-typeinfer-patmatch.pdf||Postprint||360.26 kB||Adobe PDF||View/Open|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.