Are there known constructs for two-way string pattern matching?

Question

I've often come across situations where pattern matching in a string is formalized, but the reverse is not.

Say I invent a new string pattern that can be expressed by regex /([0-9a-z])*:([0-9a-z])*@([0-9a-z])/.

Expressing that regex as data to your friendly local programming language, the standard lib will be able to convert "foo:bar@4040404" into ["foo", "bar", "4040404"].

How about converting it the other way? With the same piece of data, the above regex, turning ["bar", "baz", "5050505"] into "bar:baz@5050505".

Based on what I've done so far, I will need to duplicate the pattern—into, for example: "#{m[0]}:#{m[1]}@#{m[2]}".

In other words, can we produce text out of structured data and regex patterns, using the same pattern data for parsing as to the other way?

The other way for which we also have a lot of tools already.—One might call that templating or compiling.—What if the format is the same going both ways? Can we reuse the same pattern?

(That the outputted string doesn't match the pattern is not important to my question. This is about the reversibility of pattern matching without duplicating pattern data.)

Answer 1

At its most high-level view, what you are describing is a compiler that has the same language as source and target. If you split this compiler down the middle, you end up with two compilers, one that compiles from the source language into an intermediate abstract representation, and another that compiles from that representation to the source language again.

The trick, then, is how to specify these two "compilers" in one place.

The reverse process of parsing is called unparsing or sometimes pretty printing. What you are looking for is called reversible parsing and is an active research area both in the context of parsing and in the context of reversible computing (which is the more general idea of being able to run a program "backwards" as well as forwards).

syntax: Reversible parsing and pretty-printing is a Haskell package which implements a reversible parser. It has, however, not been updated since 2014.

Theory, examples of reversible parsers? is a Stack Overflow question with some good answers. Also, some good comments on the question by Dr. Ira Baxter, founder, original CTO and current CEO of Semantic Designs, Inc., probably most well-known for their DMS Software Reengineering Toolkit that was used to mechanically translate the flight software of the B-2 Spirit stealth bomber from JOVIAL to C++.

Answer 2

No it does not exist, or most likely does not, because its purpose would be uncertain.

Taking your example, every elements of your struct would be a match for every of your rules, so in what order would it give the output ? How would the regex understand some parts are "supposed to be there" and others are just delimiters ? ( : @ )

Assuming the following regex :

(a|b)[0-9]+

and the token 100, would the expression

a100 be generated or b100 ?

Like said Mr Rudgers, the job of a regex is telling yes or no, even in ambiguous cases.

In this previous example, both a100 and b100 make the regex say "yes"

But the regex in itself does not keep a memory of everything

For instance, the regex

.*abc$

wich is the same as

abc$

has 3 chars of memory total : the n-2, the n-1, and the n. If the string ends when the last 3 are the good ones in the correct order, then the regex says yes -- without any memory of the .* part.

I guess you could always implement some pcre-compatible tool to do that, thanks to capturing groups to represents variables, but that would not resolve a lot of the other issues, especially those regarding ambiguity ; or you would generate a great amount of possible solution, because of edge cases.

And the complexity of the problem is really high ! So in the end, the easiest is a data structure and a function on it.

Answer 3

Not in the general case, but in some more limited cases.

For example, there are several JSON libraries that can automatically convert back and forth between JSON and a programming-language specific data structure. For example, in circe, you can automatically do two-way conversions to and from a case class.

It can do this because on one side you have the limited JSON syntax, and on the other side, you have a complex data structure that is made of primitive pieces for which the conversion to JSON is known.

You can also do something like take your regex match result and generate possible input strings from it. Libraries like Haskell QuickCheck work on similar principles.

You could also do a two-way conversion if you placed certain restrictions on your regex, like only constants outside of capture groups.

Answer 4

In general no.

The information we seek to extract by using a pattern to recognise interesting parts of a string usually discards much of the string contents.

This is much less apparent in simple patterns like: /abc|def/ as they match a whole string and they are either this or that.

But most interest patterns eg: /\((\d{2})\) (\d{4}) (\d{4})|\+(06\d{2}) (\d{4})(\d{4})/ discard information relevant to the format. Both of these patterns recognise and extract 10 digits but under two different formats: (xx) xxxx xxxx and +06xx xxxxxxxx. When reversing this pattern which output format should be selected?

And we haven't even gotten into contextual formatting. Humans love contextual formats. Have you ever wondered why English sentences start with a Capital? Why a phone number shared between two locals might be 6 or 8 digits long, yet sending that number internationally adds and even changes some of the digits?

But to something more hum drum, where do you put the { after an if statement?

• same line?

if (condition) {
}

• or the next line?

if (condition)
{
}

• tabbed in?

if (condition)
    {
}

• aligned?

if (condition)
   {
}

It still holds the same semantic meaning in most languages, yet this is information the pattern needs to know about in order to generate the correct string.

The reason for this problem is that each Pattern describes a Language. That Language is a subset of all possible strings. To take the /abc|def/ example, it contains two strings: abc and def every other string is not part of the language.

To read this language we ask the very simple question, is this string 'some string' a member of that language? A Boolean answer is the result: yes or no.

To reverse this process and write we have to select one of these strings. In the /abc|def/ example its pretty simple it can only be one of those two strings. Yet we have already hit our first sticking point, which string? The problem is that this pattern was built for recognition, not for generation.

Conversely, what about this pattern: "{0,-30}"? Formatting using this pattern is trivial, take the text from the first input, align it to the left, and ensure that 30 characters are displayed, padding out the rest as necessary. But what string is in this language?

It is possible to merge the two but it is often unweildly, most languages that make the attempt keep the recognition pattern and the formatting pattern separate such as in Sed.