Blogs (1) >>
POPL 2019
Sun 13 - Sat 19 January 2019 Cascais, Portugal
Mon 14 Jan 2019 15:00 - 15:30 at Sala X - Session 2 Chair(s): Thomas P. Jensen

Regular expressions are used for a wide variety of purposes from web-page input validation to log file crawling. Very often, they are used not only to match strings, but also to extract data from them. Unfortunately, most regular expression engines only return a list of the substrings captured by the regular expression. The data has to be extracted from the matched substrings to be validated and transformed manually into a more structured format.

For richer classes of grammars like CFGs, such issues can be solved using type-indexed combinators. Most combinator libraries provide a monadic API to track the type returned by the parser through easy-to-use combinators. This allows users to transform the input into a custom data-structure and go through complex validations as they describe their grammar.

In this paper, we present the Tyre library which provides type-indexed combinators for regular languages. Our combinators provide type-safe extraction while delegating the task of substring matching to a preexisting regular expression engine. To do this, we use a two layer approach where the typed layer sits on top of an untyped layer. This technique is also amenable to several extensions, such as
routing, unparsing and static generation of the extraction code. We also provide a syntax extension, which recovers
the familiar and compact syntax of regular expressions. We implemented this technique in a very concise
manner and evaluated its usefulness on two practical examples.

Slides (talk_pepm.pdf)211KiB

Mon 14 Jan

pepm-2019-papers
14:00 - 15:30: PEPM 2019 - Session 2 at Sala X
Chair(s): Thomas P. JensenINRIA Rennes
pepm-2019-papers14:00 - 14:30
Talk
Sihan XuNankai University, China, Sen ZhangNankai University, China, Weijing WangNankai University, China, Xinya CaoNankai University, China, Chenkai GuoNankai University, China, Jing XuNankai University, China
DOI
pepm-2019-papers14:30 - 15:00
Talk
Keiichi WatanabeUniversity of Tokyo, Japan, Takeshi TsukadaUniversity of Tokyo, Japan, Hiroki OshikawaUniversity of Tokyo, Japan, Naoki KobayashiUniversity of Tokyo, Japan
DOI
pepm-2019-papers15:00 - 15:30
Talk
Gabriel RadanneUniversity of Freiburg, Germany
DOI Pre-print File Attached