HackerTrans
TopNewTrendsCommentsPastAskShowJobs

c0nstantine

no profile record

Submissions

Show HN: Transductive regular expressions for text editing

github.com
263 points·by c0nstantine·anno scorso·102 comments

comments

c0nstantine
·anno scorso·discuss
Working on trre - extension of regex for text editing. I'm redesigning the underlying engine to operate on deterministic automata (transducers) for most expressions. Theoretically, it should outperform AWK in complex text-processing tasks.

https://github.com/c0stya/trre
c0nstantine
·anno scorso·discuss
I have a minimalistic one (7 lines in Python) using convolutions:

https://c0stya.github.io/articles/game_of_life.html

### The code ###

  import numpy as np
  from scipy.signal import convolve2d

  field = np.random.randint(0, 2, size=(100, 100)) # 100x100 field size
  kernel = np.ones((3, 3))
  
  for i in range(1000): # 1000 steps
      new_field = convolve2d(field, kernel, mode="same")
      field = (new_field == 3) + (new_field == 4) * field
c0nstantine
·anno scorso·discuss
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.
c0nstantine
·anno scorso·discuss
Let me know if you need any help. Not it is still raw but I hope I'll polish it soon.
c0nstantine
·anno scorso·discuss
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.
c0nstantine
·anno scorso·discuss
Did it solve the problem? I guess the issue is the process substitution construction of bash "<()". Not all shells support this.
c0nstantine
·anno scorso·discuss
Epsilon injection appears whenever right or left side of ':' has no operand. E.g.

(:a)

(a:)

a:|b

a|b:

etc

I will try to change the precedence and see how it works. Btw what do you think about explicit operators '>' '<' where '<' works as usual regex matcher, and '>' as a generator. For example to change 'cat' to 'dog' there could be something like '<cat>dog' where '<cat' part is a parser and '>dog' is a generator. Thanks.
c0nstantine
·anno scorso·discuss
Thank you for the detailed comment.

So Unicode is something on a top of my TODO list. Boundaries is a very interesting topic. Maybe I'll extend the doc to include the details.

> what's your driver? curiosity? or some itch?

It's an itch :). 8 years ago I explored automata theory and found finite transducers to be a handy and natural way to transform texts. And as regex corresponds to FSA (finite state acceptors) I wanted to create a language that corresponds to FST (finite state transducers). There is a lesser-known algorithm for FST determinization and I want to applied it to make the transformation fast and efficient. It turned out to be not that simple as I expected initially.
c0nstantine
·anno scorso·discuss
I agree with the point that precedence is arbitrary. The current version looks like this:

1 Escaped characters

2 []

3 ()

4 * + ? {m,n}

5 :

6 . (implicit concatenation)

7 |

I have some reasons to put it that way. I want : to be somewhat 'atomic'. If you think about '*' or '+' they can be lower in the table as well. Anyway, I will try to put : lower in the next version and see how it goes.
c0nstantine
·anno scorso·discuss
Thank you for doing my work! :)
c0nstantine
·anno scorso·discuss
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.
c0nstantine
·anno scorso·discuss
Oh, I've learnt a lot. Initially wanted to complete the whole project in two weeks and it took a few months. The hardest part was the DFT determinization algorithm design.

Thanks for your feedback!
c0nstantine
·anno scorso·discuss
The right side is a normal regex language syntactically. Semantically it is a generator instead of a parser (consumer).

But I got your point. Maybe there could be some ways to do it in consistent way. Just straight tr-like syntax won't work, e.g I really want it something like this to be valid:

[a-b]:(x|y) (pairs a:x, b:x, a:y, b:y)

and I prefer not handle these in some ad-hoc way.
c0nstantine
·anno scorso·discuss
Thank you! Still a lot of work to do. I really like the jq style.
c0nstantine
·anno scorso·discuss
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).
c0nstantine
·anno scorso·discuss
The '-g' flag is obsolete. Somehow it got into my new docs. The right way is to use '-ma' flags where '-m' is for matching the whole string and '-a' stands for all the outputs.

You got the idea correctly. E.g. to generate all strings of length 5 over alphabet 10 (and truncate to 10000) you can do:

echo '' | ./trre -am ':[a-c]{5}' | head -n 1000

The docs are fixed now. Thanks for pointing this out.

The infinite generators is something nice to have, I agree. Just didn't wrap my hand around how to do this in 'ergonomically' correct way.
c0nstantine
·anno scorso·discuss
That's true. Thank you for elaborating.

There is a hidden operator of concatenation as for usual regular expressions. In the code I denote it as lower dot '.' (as in the old Thompson's implementation).
c0nstantine
·anno scorso·discuss
[a-z] is equivalent to 'a|b|...|z' in the normal regex language.

So if we do [a-z]:[A-Z] it should be expanded to:

(a|b|...|z):(A|B|...|Z)

which is pretty legal in trre but has different meaning of mapping any a-z to ALL the A-Z (generating A-Z on each occurrence of lowercase letter).
c0nstantine
·anno scorso·discuss
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
c0nstantine
·anno scorso·discuss
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.