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
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

Files in This Item:
File Description SizeFormat 
toplas-typeinfer-patmatch.pdfPostprint360.26 kBAdobe PDFView/Open
Show full item record

Google ScholarTM

Check


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