www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/1425

Title: Type inference for unique pattern matching
Authors: VANSUMMEREN, Stijn
Issue Date: 2006
Citation: 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.
URI: http://hdl.handle.net/1942/1425
Link to publication: http://doi.acm.org/10.1145/1133651.1133652
ISI #: 000238273200001
ISSN: 0164-0925
Category: A1
Type: Journal Contribution
Validation: ecoom, 2007
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Postprint360.26 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.