Typed and unambiguous pattern matching on strings using regular expressions

Claus Brabrand; Jakob G. Thomsen

Typed and unambiguous pattern matching on strings using regular expressions

Claus Brabrand
, Jakob G. Thomsen

Aarhus University

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Abstract

We show how to achieve typed and unambiguous declarative
pattern matching on strings using regular expressions
extended with a simple recording operator.

We give a characterization of ambiguity of regular expressions
that leads to a sound and complete static analysis. The
analysis is capable of pinpointing all ambiguities in terms of
the structure of the regular expression and report shortest
ambiguous strings. We also show how pattern matching can
be integrated into statically typed programming languages
for deconstructing strings and reproducing typed and structured
values.

We validate our approach by giving a full implementation
of the approach presented in this paper. The resulting tool,
reg-exp-rec, adds typed and unambiguous pattern matching
to Java in a stand-alone and non-intrusive manner. We
evaluate the approach using several realistic examples.

Original language	English
Title of host publication	Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming
Number of pages	12
Publisher	Association for Computing Machinery
Publication date	2010
Pages	243-254
ISBN (Print)	978-1-4503-0132-9
Publication status	Published - 2010
Event	International Conference on Principles and Practice of Declarative Programming (PPDP 2010) - Hagenberg, Austria Duration: 26 Jul 2010 → 28 Jul 2010 Conference number: 12th http://www.risc.jku.at/conferences/ppdp2010/

Conference

Conference	International Conference on Principles and Practice of Declarative Programming (PPDP 2010)
Number	12th
Country/Territory	Austria
City	Hagenberg
Period	26/07/2010 → 28/07/2010
Internet address	http://www.risc.jku.at/conferences/ppdp2010/

Keywords

Typed pattern matching
Regular expressions
Ambiguity analysis
Static analysis
Statically typed languages

Access to Document

http://tType=Proceedings&title=PPDP&CFID=97063111&CFTOKEN=91659355

Cite this

@inproceedings{12ac7eacd36f46098edf0e80ac28661f,

title = "Typed and unambiguous pattern matching on strings using regular expressions",

abstract = "We show how to achieve typed and unambiguous declarative pattern matching on strings using regular expressions extended with a simple recording operator. We give a characterization of ambiguity of regular expressions that leads to a sound and complete static analysis. The analysis is capable of pinpointing all ambiguities in terms of the structure of the regular expression and report shortest ambiguous strings. We also show how pattern matching can be integrated into statically typed programming languages for deconstructing strings and reproducing typed and structured values. We validate our approach by giving a full implementation of the approach presented in this paper. The resulting tool, reg-exp-rec, adds typed and unambiguous pattern matching to Java in a stand-alone and non-intrusive manner. We evaluate the approach using several realistic examples. ",

keywords = "Typed pattern matching, Regular expressions, Ambiguity analysis, Static analysis, Statically typed languages, Typed pattern matching, Regular expressions, Ambiguity analysis, Static analysis, Statically typed languages",

author = "Claus Brabrand and Thomsen, \{Jakob G.\}",

year = "2010",

language = "English",

isbn = "978-1-4503-0132-9",

pages = "243--254",

booktitle = "Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming",

publisher = "Association for Computing Machinery",

address = "United States",

note = "International Conference on Principles and Practice of Declarative Programming (PPDP 2010), PPDP 2010 ; Conference date: 26-07-2010 Through 28-07-2010",

url = "http://www.risc.jku.at/conferences/ppdp2010/",

}

Brabrand, C & Thomsen, JG 2010, Typed and unambiguous pattern matching on strings using regular expressions. in Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming. Association for Computing Machinery, pp. 243-254, International Conference on Principles and Practice of Declarative Programming (PPDP 2010), Hagenberg, Austria, 26/07/2010. <http://tType=Proceedings&title=PPDP&CFID=97063111&CFTOKEN=91659355>

Typed and unambiguous pattern matching on strings using regular expressions. / Brabrand, Claus; Thomsen, Jakob G.
Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming. Association for Computing Machinery, 2010. p. 243-254.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

TY - GEN

T1 - Typed and unambiguous pattern matching on strings using regular expressions

AU - Brabrand, Claus

AU - Thomsen, Jakob G.

N1 - Conference code: 12th

PY - 2010

Y1 - 2010

N2 - We show how to achieve typed and unambiguous declarative pattern matching on strings using regular expressions extended with a simple recording operator. We give a characterization of ambiguity of regular expressions that leads to a sound and complete static analysis. The analysis is capable of pinpointing all ambiguities in terms of the structure of the regular expression and report shortest ambiguous strings. We also show how pattern matching can be integrated into statically typed programming languages for deconstructing strings and reproducing typed and structured values. We validate our approach by giving a full implementation of the approach presented in this paper. The resulting tool, reg-exp-rec, adds typed and unambiguous pattern matching to Java in a stand-alone and non-intrusive manner. We evaluate the approach using several realistic examples.

AB - We show how to achieve typed and unambiguous declarative pattern matching on strings using regular expressions extended with a simple recording operator. We give a characterization of ambiguity of regular expressions that leads to a sound and complete static analysis. The analysis is capable of pinpointing all ambiguities in terms of the structure of the regular expression and report shortest ambiguous strings. We also show how pattern matching can be integrated into statically typed programming languages for deconstructing strings and reproducing typed and structured values. We validate our approach by giving a full implementation of the approach presented in this paper. The resulting tool, reg-exp-rec, adds typed and unambiguous pattern matching to Java in a stand-alone and non-intrusive manner. We evaluate the approach using several realistic examples.

KW - Typed pattern matching

KW - Regular expressions

KW - Ambiguity analysis

KW - Static analysis

KW - Statically typed languages

KW - Typed pattern matching

KW - Regular expressions

KW - Ambiguity analysis

KW - Static analysis

KW - Statically typed languages

M3 - Article in proceedings

SN - 978-1-4503-0132-9

SP - 243

EP - 254

BT - Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming

PB - Association for Computing Machinery

T2 - International Conference on Principles and Practice of Declarative Programming (PPDP 2010)

Y2 - 26 July 2010 through 28 July 2010

ER -

Typed and unambiguous pattern matching on strings using regular expressions

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this