This is a very interesting idea for a few reasons.

> I would naturally assume `cat:dog` would be equivalent to `(cat):(dog)` rather than `ca(t:d)og`

It was confusing to me too until I remembered that we all kind of use regexes sort of wrong. They're "really" supposed to be considered as generators and not matchers. So IIR cat|dog as a "regular expression" (not a regex) is supposed to formaly expand to

{catog,cadog}

For matching, this set of strings can then be substring matched against some larger text.

The problem is that almost no regex matching engine actually does this, and so now they'll do all kinds of strange things either to meet our expectations, or for efficiency or something.

If you go and try a bunch of different regex tools you'll get variations that either service (cat)|(dog) or (cat)|(dog)|(ca[td]og) or something else.

So from a more formal conceptualization I think cat:dog should produce ca(t:d)og not (cat):(dog). But our experience with "regex" tools has subverted that formalization and now everybody just puts parens around expressions they want to alternate.

My real minor issue with this proposal, as interesting and well thought out as it is, is that it feels like it's just trying to get back at regular expressions as generators, which they actually are and it's coming from a place on the other side of a few decades of how we've been abusing them as regexes for user expectations. In other words, the problem is the tooling, not the syntax.

source: I've worked adjacent to this space in the past and if you've never thought of regexes as string set generators you can toy with the idea here

https://onlinestringtools.com/generate-string-from-regex

but again, how these generator tools works is also very specific. The ones I used to work with had a variety of ways to specify constraints on closures and such to restrict the generators.

Thank you for the feedback. Yes, the precedence is a question for me. Maybe I will change this.

If I shift it behind concatenation there could be another problem. E.g. with non-associative : should be illegal. And I am not sure how to treat this:

cat:dog:mouse

In the current version I inject the epsilon (empty string). It looks natural E.g. to remove every second letter I could run '..:' which is technically '.(.:eps)':

echo 'abcde' | ./trre '..:'

result: 'ace'

actually ':' association could have a meaning as a composition of regular relations; but I found it too complicated for now.

Yeah. Similarly, for the range transformations, instead of `[a:A-z:Z]`, I would suggest `[a-z:A-Z]`; and instead of `[a:b-y:zz:a]`, something like `[a-y:b-z;z:a]`, perhaps.

I was going to mention this as well. This is a link to Kaplan's paper : https://aclanthology.org/J94-3001.pdf which describes the work PARC did.

http://hfst.github.io/ is the modern open source version of XFST; it subsumes foma and openfst, pretty sure it does all of what trre does and more.

People may also be interested in Pynini [1], a python wrapper (+ a lot of additional ease-of-use functionality) of OpenFst [2] (a really great library for transducers).

There are some good tutorials in the form of homework assignments (from like Johns Hopkins and some others) that go through Pynini use cases.

[1] https://www.openfst.org/twiki/bin/view/GRM/Pynini

[2] https://www.openfst.org/

I used OpenFST for bioinformatics back in the early 2000s. They were fun to play with, but never ended up being useful for the things I was working on. It's cool to see that the project is still going 20 years later: https://www.openfst.org/twiki/bin/view/FST/WebHome

I have to say, incredibly bold of you to essentially hinge your graduation on whether you can regex hard enough or not.

yeah. Transducers are very old topic. For some reason they were not connected to a specific language like regex.

> wrt syntax, are you sure you want ':' to bind stronger than concatenation 'ab' ?

That's something I am still not sure about. I took a hundred examples and it looked more natural this way (: lower then .). But I can change it with the change of one digit in the code, literally. That's why I'm posting here. I need some real feedback.

If I understand correctly the following ttre expression does what you're asking for:

  ":'(':(\\')|[^"'])*":'

Hi,

If I understand it correctly you want to change something inside the "..." block and change the quotas to single '.

It can be done by this expression:

echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"

'-' '-'

So I substitute the text inside "" by symbol - using this expression ".+?:-" and simultaneously changing the surrounding quota.

Question mark means non-greedy mode.

I would say regex is usually pretty write once edit never. Building a prototype that tries to look beyond that is a great way to see what a better future might look like in this regard.

Fair point. The most explicit example if you need to change something in context. For example if we need to change 'y' to 'Y' only if it occurs between x and y you would do something like this in python.

pattern = r'(x)y(z)'

replacement = r'\1Y\2'

result = re.sub(pattern, replacement, text)

I would like to replace it with 'xy:Yz' pattern:

result = re.trre('xy:Yz', text)

If you need your x, z to be more complicated patterns or even regex themselves it can be more handy using this approach.

Well, I think it is fair to say that regexes alone do not provide any facilities for editing. You have groups, but you have to use some other language (like sed) to compose those groups.

Come on, it's about replacements. They're easier to express (meaning literally easier to type out) with the author's syntax

Great project

[flagged]

Thank you! For the feedback and pointing to the typo. Fixed. Actually my C is very rusty and I am bit uncomfortable about this.

Fair point. I agree. Now it is better to disable it.

The rationale was to implement a fun operation called transducer composition. It is possible to do simple operation on strings and compose trre's like filters. But I haven't finished it yet. So again, a fair point.

This is a matter of operator precedence and tokenization. Tokens are single characters in this language, and there is an invisible operator between them.

If the operator were explicit (let’s call it ~), the example would look like this:

    $ echo 'cat' | trre 'c:d~a:o~t:g'
    dog

    $ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'
    dog

The grammar is underspecified. The full grammar is more complex. I guess I need just remove the current version from docs. Now it is confusing indeed.

> Why is "c" not being replaced with "da"?

It is all about precedence. According to the discussion I think I've chosen a wrong one and it raises confusion. Current version of precedence table is this:

| 1 | Escaped characters | \<special character> | | 2 | Bracket expression | [] | | 3 | Grouping | () | | 4 | Single-character-ERE duplication | * + ? {m,n} | | 5 | Transduction | : | | 6 | Concatenation | . (implicit) | | 8 | Alternation | | |

So the ':' is stronger then '.' (implicit concatenation).

Yes it is underspecified. The deletion example shows that an empty string is possibly a REGEX. So you can essentially treat any position as containing as many empty string regexes as you want. So there are indeed infinite number of parses.

If we instead require regex to be non-empty (breaking the deletion examples), then the ambiguity becomes that of concatenation: whether it's '(((c:d)(a:o))(t:g))' or '((c:d)((a:o)(d:g)))'. Assuming associativity, this would not matter.

From what it feels as to how it works, it seems that c:d and a: (nothing) and ot:g

but yes now that I read it , it also makes confusion , theoretically your point makes valid , I also believe that c should be replaced by da after I read the repo , I am not sure ...

The second line actually is an output. I've modified the README. The last example is a typo. Fixed. Thanks!

Thank you for your feedback. There is a bunch of deterministic methods to infer regex from samples (positive and negative). There are ml-based as well. But it is a different story.

Hi. Missed your message initially. Helix is a great project. Let me know if/how I can help. The trre is a bit raw. But hope I can polish it within a month or two.

Thank you! Still a lot of work to do. I really like the jq style.

Let me know if you need any help. Not it is still raw but I hope I'll polish it soon.

and of course Perl supports both!

This doesn't seem to have anything to do with regular expressions.

I guess folks generally more interested in searching for the pattern then modifying it.

> Tools like sed build a transducer around the whole automaton: s/this/that/g.

That sounds reasonable. Could you provide any links on sed internals? Thanks.

Typo. Fixed. Thanks. Too many cats in examples.

Are you using MAC? For tests please try:

$ make && bash test.sh

with 'bash' instead.

For the second part it is a bug in the README. Thank you for pointing this out! I had to be more careful before the publication. Fixed. Try '-ma' flags instead.

$echo '' | trre -ma ':(0|1){,3}?'

Hey, I didn't claim it is something groundbreaking. The idea is quite old, indeed. You don not need AI or LLMs here.

The sed is superior, actually. I do not cover all the functions sed provides. I think of it more like 'tr' + regexp. But it has different underlying engine and might be faster and more expressive for some use cases (e.g. tokenization, morphology).

Thank you for the link. I think I came across it some years ago. They implement weighted transducers. Nice tool for things like morphology from the era before the LLMs. I've implemented something similar 8 years ago: https://github.com/c0stya/fslib