Reference. Technical Report: Match-reference regular expressions and lenses
A lens is a single program that specifies two data transformations at once: one transformation converts data from source format to target format and a second transformation inverts the process. Over the past decade, researchers have developed many different kinds of lenses with different properties. One class of such languages operate over regular languages. In other words, these lenses convert strings drawn from one regular language to strings drawn from another regular language (and back again). In this paper, we define a more powerful language of lenses, which we call match-reference lenses, that is capable of translating between non-regular formats that contain repeated substrings, which is a primitive form of dependency. To define the non-regular formats themselves, we develop a new language, match-reference regular expressions, which are regular expressions that can bind variables to substrings and use those substrings repeatedly. These match-reference regular expressions are closely related to the familiar “back-references“ that can be found in traditional regular expression packages, but are redesigned to adhere to conventional programming language lexical scoping conventions and to interact smoothly with lens language infrastructure. We define the semantics of match-reference regular expressions and match-reference lenses. We also define a new kind of automaton, the match-reference regex automaton system (MRRAS), for deciding string membership in the language match-reference regular expressions. We illustrate our definitions with a variety of examples.
Cite
Cites 13 works (0 here)
External (13)
- Match-Reference Regexes and Bijective Lenses (2023)
- Regular Expressions with Backreferences: Polynomial-Time Matching Techniques (2019)
- Deterministic regular expressions with back-references (2019)
- Inside the Class of REGEX Languages (2012)
- On the intersection of regex languages with regular languages (2009)
- On the closure of pattern expressions languages under intersection with regular languages (2009)
- Bidirectional programming languages (2009)
- Boomerang: resourceful lenses for string data (2008)
- Combinators for bidirectional tree transformations (2007)
- Pattern expressions and pattern automata (2004)
- A Formal Study Of Practical Regular Expressions (2003)
- pcre2pattern man page
- Catalogs and Feeds