[HN Gopher] Show HN: Transductive regular expressions for text e...
___________________________________________________________________
Show HN: Transductive regular expressions for text editing
An extension of regular expressions for text editing, with a grep-
like command-line tool. If you, like me, struggle with group logic
in regular expressions, you might find it useful. I wanted to do
this for a very long time. It is more of a sketch or prototype. I'd
really appreciate your feedback!
Author : c0nstantine
Score : 186 points
Date : 2025-02-07 16:18 UTC (6 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| the_arun wrote:
| > $ echo 'xor' | '(x:)or' 'xor'
|
| > cat
|
| I got lost here.
| c0nstantine wrote:
| Typo. Fixed. Thanks. Too many cats in examples.
| trashburger wrote:
| Also too many dogs it seems, as the infinite and finite loop
| examples also produce "dog".
| i3oi3 wrote:
| Are the examples all actual outputs of the program? It's entirely
| possible that my understanding of the grammar is off, but it
| looks like these examples are wrong:
|
| $ echo 'cat dog' | trre 'c:bat|d:hog' bat hog
|
| $ echo '' | trre ':a*' # <- do NOT do this dog
|
| $ echo '' | trre ':(repeat-10-times){10}' dog
| c0nstantine wrote:
| The second line actually is an output. I've modified the
| README. The last example is a typo. Fixed. Thanks!
| meonkeys wrote:
| And the first one? Wouldn't the output be
|
| batat hogog
| c0nstantine wrote:
| Can't reproduce.
|
| I have the following:
|
| > echo 'cat dog' | ./trre 'c:bat|d:hog'
|
| bat hog
| mordechai9000 wrote:
| I would probably use this in a text editor if it was available. I
| don't struggle with group logic, but I often forget which tools
| use \ to reference capture groups, and which use $. (If it's
| Microsoft or Microsoft-adjacent, it's probably $.)
| rjh29 wrote:
| and of course Perl supports both!
| crazygringo wrote:
| > _Regular expressions is a great tool for searching patterns in
| text. But I always found it unnatural for text editing._
|
| The entire purpose of this project seems to hinge on this
| assertion, but there isn't a single example.
|
| I don't understand what makes regex unnatural for editing? What
| is meant by editing? Why do people struggle with groups?
|
| There are lots of examples of the syntax for this project, but
| why is it better than regular regex?
|
| If there were a few examples showing "here's the vanilla regex
| version, here's my version, here's why my version makes this
| easier" I might be able to understand this project.
| everdimension wrote:
| Come on, it's about replacements. They're easier to express
| (meaning literally easier to type out) with the author's syntax
|
| Great project
| c0nstantine wrote:
| 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.
| crazygringo wrote:
| Thanks!
|
| I guess I'm still struggling to see how it's simpler overall.
|
| Most of the examples on your page don't involve groups at
| all, e.g.: $ echo 'catcatcat' | trre
| '((cat):(dog))*' dogdogdog
|
| That already seems a lot more complicated than just:
| re.sub('cat', 'dog', 'catcatcat')
|
| I don't need to use groups that often in regex replacements,
| and when I do I'm already trying to do something complicated,
| and it's not clear to me why the colon syntax is easier to
| write, easier to understand, or if it's as flexible.
|
| Not trying to criticize the project, just genuinely trying to
| understand the specific strengths and limitations of the
| proposed syntax. E.g. what if I want to turn xyz into zYx?
| c0nstantine wrote:
| >> E.g. what if I want to turn xyz into zYx?
|
| echo 'zyx' | ./trre 'xy:Yz|zy:Yx'
|
| It is still a regular language. I do not introduce
| references.
|
| You are right in sense the `sed` is far superior editor.
| But here I see some advantages: - the current
| implementation is super small; it is direct translation to
| an automaton - the complex patterns may be compiled in a
| more efficient way using deterministic transducer. I can't
| defend this claim now but I have some evidences - there are
| some tricks you can do using 'generative' part of it, e.g.
| and you even can find levenshtein distance of 1 between two
| strings just by generating
| substitutions/insertions/deletions and implement a simple
| spell checker.
|
| Overall, I think you have a good point. Maybe it is just
| marginal improvement (if any). It was more comfortable to
| write in this style instead of group usage. I used it for
| some time and found it handy (especially as extended `tr`).
| rendaw wrote:
| I think it's an interesting project, but is this a functional
| replacement for regex substitutions? It seems like you can
| only replace text with something else at the same location.
| Separating the replacement from the matching can be unweildy,
| but you can reorder, repeat, and insert text between things
| too.
|
| IIUC
| Etheryte wrote:
| 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.
| psychoslave wrote:
| Sure, though you can do commented regexp in Perl and Ruby and
| probably others, using x flag if my memory serve well, though
| in practice for maintenability you'll probably better avoid
| this kind of "clever" tricks.
|
| Just skimming through the readme, I'm also in doubt that the
| paradigm shift would really be any better than folk regexp.
|
| That doesn't make the existence of the project any less
| cooler, of course. Congratulation to the author, and don't
| let such a comment narrow down your motivation, as it's
| really not the point. If you enjoy do it, great. If you learn
| something in the process, awesome. If it can lead to
| something that I can't envision, how marvelous. But it
| doesn't, that was still a great epic and you can be proud.
| zokier wrote:
| 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.
| andrewla wrote:
| I feel like this is very underspecified, The very first example:
| $ echo 'cat' | trre 'c:da:ot:g' dog
|
| Feels strange. What is happening here; the grammar says
| TRRE <- TRRE* TRRE|TRRE TRRE.TRRE TRRE <- REGEX
| REGEX:REGEX
|
| What is the parse tree here? Why is "c" not being replaced with
| "da"? Or why isn't c being removed and "da" being replaced by
| "ot"?
|
| I do like the idea of having a search/replace semantic that is
| more intuitive than grouping operators; back in MS-DOS days you
| could do "ren _.log_.txt " and this would work which feels
| bananas to my modern bash-minded way of thinking, but it's very
| obvious looking at this what it is supposed to do.
| Imustaskforhelp wrote:
| 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
| ...
| danielparks wrote:
| 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
|
| With unnecessary parentheses: $ echo 'cat' |
| trre '(c:d)~(a:o)~(t:g)' dog
| kccqzy wrote:
| 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.
| danielparks wrote:
| Cool, I'm interested to see where you go with this.
|
| I found the operator precedence unnatural, and it looks like a
| lot of other folks in this thread did too. I would naturally
| assume `cat:dog` would be equivalent to `(cat):(dog)` rather than
| `ca(t:d)og`.
| twiss wrote:
| 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.
| kazinator wrote:
| I would suggest simply [a-z]:[A-Z], inspired by _tr_.
|
| Then there is no syntactic special case. This is just
| EXPR:EXPR; the special case is that both EXPR are character
| class syntax, and so the _tr_ -like range mapping applies.
| c0nstantine wrote:
| 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.
| froh wrote:
| sweet, I did my "Diplom" CS thesis around 1997 on finite state
| transducers. was mich less trivial than I'd thought. the ask was
| to implement composition and DFAs where possible. also for
| composed transducers. "algebra of finite state transducers". use
| case was morphology. the topic was heavily underestimated and I
| had to finish half way through. so: chapeau :-)
|
| anyhow
|
| wrt syntax, are you sure you want ':' to bind stronger than
| concatenation 'ab' ?
| Etheryte wrote:
| I have to say, incredibly bold of you to essentially hinge your
| graduation on whether you can regex hard enough or not.
| c0nstantine wrote:
| 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.
| froh wrote:
| hm maybe juxtapose a number of examples in one precedence and
| then the other? and share them to gather feedback?
|
| also,
|
| * colon as member of a character class (and dash and how they
| interact)
|
| * posix character classes (and the colon in the syntax)
|
| * word boundaries are really useful in practice
|
| * think of unicode early and look at what russ cox did there
|
| boundaries, what do you decide to exclude? for example back
| references and grouping have fun with DFAs (again see russ
| cox and re2)
|
| composition is fantastic, and a shortcut to exponential land
| because grammars (as in Chomsky hierarchy) can easily be
| expressed with transducers, yay.
|
| boundaries will also clarify use cases and allow to state:
| "if you want to do xyz please use re2 and a bit of code
| instead"
|
| and one "technicality" that hit me once with re2 was a static
| buffer for resumable iteration. I'd _loved_ to reallocate the
| buffer and drop it 's beginning and extend it at the end but
| alas, the state of re2 has hard pointers into the buffer, not
| relative ones. I think this was when re2 hit the end of the
| buffer mid-expression during incremental parse. so you can't
| reallocate and instead you have to drop the hard earned state
| and resume.
|
| anyhow, it's been quite a while so I'm no longer in the
| thicket of this :-D
|
| what's your driver? curiosity? or some itch?
|
| but I really enjoy seeing your project :-)
| username223 wrote:
| 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
| sabellito wrote:
| I love the idea, wanna se where it goes. Gives me the same vibe
| as when jq came out all those years ago.
| zoogeny wrote:
| > Avoid using * or + in the right part, as it can cause infinite
| loops
|
| Why not just disallow this? I understand it would make the
| grammar more difficult to specify - but I don't see any good
| reason to keep it.
| c0nstantine wrote:
| 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.
| shawnz wrote:
| Another question about this issue: in the case of `:a*` for
| example, why doesn't it just pick empty string as the
| replacement text and immediately exit? Why would it be an
| infinite loop if `-g` isn't specified?
|
| And then if `-g` were specified, you could use this to create
| infinite generators, which could be a useful construct in
| some cases -- like `yes` but more powerful.
|
| EDIT: Another interesting use case, if I am understanding
| correctly: if this worked, then you could use `:(<regex>)` to
| have it output an example of a string that matches any given
| regex. `-g :(<regex>)` produces a generator of every string
| in the language matched by that regex. `-g :(<regex>) | head
| -n 100` would give you 100 examples.
| wfn wrote:
| What a pleasure your C code is :) very nice (currently reading
| it)
|
| My only quick comment is - the link to `theory.pdf` in README is
| broken (your pdf is in docs/ dir, so just need to change the url
| to include docs/).
| c0nstantine wrote:
| Thank you! For the feedback and pointing to the typo. Fixed.
| Actually my C is very rusty and I am bit uncomfortable about
| this.
| BFPQVZ wrote:
| Another alternative that is similar would be Carmel
| (https://github.com/isi-nlp/Carmel-Repository)
| teknopaul wrote:
| My two penneth: I find the replacement part the easiest and
| escping all the characters which mean something in regexp to be
| the most annoying part.
|
| Adding a new char to be escaped seems like another annoyance.
|
| I try to avoid tools that make the hard bit harder, and the easy
| bit easier
| metadat wrote:
| When I saw this headline, I got excited about the prospect of a
| new innovation in the application of Regular Expressions. After
| reading, I was scratching my head because trre doesn't provide
| any new capabilities and is essentially just yet another flavor
| of regex. Additional complexity without a significant upside.
|
| Trre seems like an arbitrarily different version of `sed -e /a/b/
| ..`. This method of search and replace is essentially ported
| everywhere else, from awk to vim to IntelliJ, and has always
| gotten the job done adequately and feels as natural as anything
| else I've learned.
|
| Am I missing something?
|
| p.s I just realized I've been regex'ing heavily for 21 (!) years
| now, time flies.
| c0nstantine wrote:
| 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).
| metadat wrote:
| Thanks for the clarification, totally on me to set
| expectations inappropriately based on only a headline. Take
| care.
| simlevesque wrote:
| I ran the installation lines and got this error:
| make && sh test.sh cc -std=c99 -Wall -Wextra -Wpedantic
| -o2 trre_nft.c -o trre cc -std=c99 -Wall -Wextra
| -Wpedantic -o2 trre_dft.c -o trre_dft test.sh: 14: Syntax
| error: "(" unexpected
|
| Using bash fixed it.
|
| Then I ran one of the generator examples: echo
| '' | trre -g ':(0|1){,3}?'
|
| And I got this error: ./trre: invalid option --
| 'g' Usage: ./trre [-d] [-m] expr [file]
| c0nstantine wrote:
| 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}?'
| larodi wrote:
| In place replacing the text while parsing is very powerful
| approach. Fingers crosses this flies.
|
| This, combined with probabilistic approach can be even more
| interesting. Probabilistic approaches regexes exist since 70s if
| memory serves right.
| kazinator wrote:
| This is nifty --- and small.
|
| You could port this to like V7 Unix from 1979 or earlier; why
| didn't they get this idea? :)
|
| Tools like sed build a transducer around the whole automaton:
| s/this/that/g.
| layer8 wrote:
| I would give the colon operator lower precedence than
| concatenation and repetition.
| pmarreck wrote:
| so basically just `sed -e`?
| layer8 wrote:
| This doesn't seem sufficient as soon as you want to perform some
| kind of structural substitution, for example doing the equivalent
| of s/"([^"]*)"/'$1'/. If it could do that _and also_ somehow be
| able to replace any of the [^ "] that match ['] by \', that would
| seem more useful.
|
| More generally speaking, since regular expressions effectively
| define a parse tree on their matches, being able to perform more
| general transformations of those trees would be useful.
| johnnymellor wrote:
| If I understand correctly the following ttre expression does
| what you're asking for: ":'(':(\\')|[^"'])*":'
| Lanzaa wrote:
| If you are looking for an alternative to standard regex,
| especially if you have trouble with group logic and are looking
| for something maintainable, you might like the Rosie Pattern
| Language.
|
| https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
|
| https://rosie-lang.org/about/
| groby_b wrote:
| It's a cool exploration, but I'm missing examples of why it's
| actually better. (Which, TBF, might just be an indicator I spent
| too much time with regexps :)
|
| I.e - why is trre "(cat):(dog)" an improvement over s/cat/dog?
| What's the improvement of "(x:)or" over s/xor/or? And so on.
| Pretty much all the examples match (at least in my head) to
| relatively easy regexps.
|
| I think the core advantage, if there is one, would be in group
| logic, so maybe the examples should lean into that - even before
| explaining the basics. I'd explain why it's actually a better
| choice before explaining the full syntax, or hello-world use
| cases.
|
| For the caesar cipher example, it screams for a "apply this in
| reverse" - it's a pretty common request for a lot of text
| replacements, but it's super clear with this one. (Because
| programmer brain immediately screams "why express logic twice")
|
| I don't know if it's useful (yet), but I think it's great you're
| trying to explore alternatives to a long-established status quo.
| (Caveat: That usually means there's a good chance it won't land.
| But it's still great to see an exploration)
| agumonkey wrote:
| very inspiring idea, makes me wanna start projects I had in mind
| related to that. thanks and good luck
| languagehacker wrote:
| For folks interested in finite-state transducers and other kinds
| of tooling available, check out XFST (Xerox Finite-State
| Transducer), which has been used in computational linguistics
| applications for a good 20 years now.
|
| I remember a Finnish researcher from PARC coming to one of my
| classes at UT to show how you can use FSTs for handling Finnish
| morphology, which is, on its face, quite a feat.
| kreyenborgi wrote:
| 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.
| ChuckMcM wrote:
| 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.
| jll29 wrote:
| Check out Xerox XFST and its open source clone FOMA for finite
| state transducers as described by extended regular expresssions,
| both of which describe the language of regular relations:
|
| The Xerox FST book
| https://press.uchicago.edu/ucp/books/book/distributed/F/bo36...
| (Xerox XRCE's finite-state-tools comprising the compilers lexc,
| xfst and twolc, the languages they compile and the formal
| language finite state transducers describe including linguistic
| applications)
|
| The XFST book
| https://press.uchicago.edu/ucp/books/book/distributed/F/bo36...
|
| FOMA: the open source clone https://fomafst.github.io/
|
| FOMA: the paper (Holden, M. (2009) Proc. EACL)
| https://aclanthology.org/E09-2008.pdf
|
| FOMA: the open source clone https://fomafst.github.io/
|
| FOMA: the paper (Holden, M. (2009) Proc. EACL)
| https://aclanthology.org/E09-2008.pdf
| MathMonkeyMan wrote:
| From the readme: $ echo 'cat' | trre
| 'c:da:ot:g' dog
|
| Why?
|
| Elsewhere, the readme says that ":" is "non-associative", and I
| had a look at the language grammar but haven't figured out how to
| parse a sequence of ":".
| synthc wrote:
| Interesting! I did an internship where I tried to use transducers
| for fast information extraction. In theory, you can use FST's for
| fast approximate parsing. I didn't really work out, but I had
| lots of fun implementing a libary to compose FST's and explore
| cool algorithms to compose them. Not much business value was
| delivered, but I learned a lot.
___________________________________________________________________
(page generated 2025-02-07 23:00 UTC)