9 ms·
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!
- the_arun 2y ago> $ echo 'xor' | '(x:)or' 'xor' > cat I got lost here.
- c0nstantine 2y agoTypo. Fixed. Thanks. Too many cats in examples.
- trashburger 2y agoAlso too many dogs it seems, as the infinite and finite loop examples also produce "dog".
- i3oi3 2y agoAre 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 2y agoThe second line actually is an output. I've modified the README. The last example is a typo. Fixed. Thanks!
- meonkeys 2y agoAnd the first one? Wouldn't the output be batat hogog
- c0nstantine 2y agoCan't reproduce. I have the following: > echo 'cat dog' | ./trre 'c:bat|d:hog' bat hog
- robertlutece 2y agoit reads like '(c:b)at|(d:h)og' and not 'c:(bat)|d:(hog)'
- mordechai9000 2y agoI 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 2y agoand of course Perl supports both!
- c0nstantine 2y agoLet me know if you need any help. Not it is still raw but I hope I'll polish it soon.
- crazygringo 2y ago> 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 2y agoCome on, it's about replacements. They're easier to express (meaning literally easier to type out) with the author's syntax Great project
- bawolff 2y ago[flagged]
- c0nstantine 2y agoFair 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 2y agoThanks! 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?
- andrewla 2y agoI 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 2y agoFrom 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 2y agoThis 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
- deleted 2y ago[deleted]
- c0nstantine 2y agoThat'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).
- deleted 2y ago[deleted]
- ej1 2y ago[flagged]
- danielparks 2y agoCool, 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 2y agoYeah. 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 2y agoI 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 2y ago[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).
- kazinator 2y ago[a-z] is a semantically equivalent regex to a|b|..|z, but the two are not equivalent syntactic forms. Distinct syntactic forms can be given distinct semantics, as long as there is rhyme and reason. Moreover, the right side of the colon is not the normal regex language, it only borrows its syntax. So there, we may be justified in denying that the usual equivalence holds between character class syntax and a disjunction of the symbols denoted by the class.
- 2y ago
- froh 2y agosweet, 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 2y agoI have to say, incredibly bold of you to essentially hinge your graduation on whether you can regex hard enough or not.
- c0nstantine 2y agoyeah. 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 2y agohm 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 ünicøde 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 :-)
- sabellito 2y agoI love the idea, wanna se where it goes. Gives me the same vibe as when jq came out all those years ago.
- c0nstantine 2y agoThank you! Still a lot of work to do. I really like the jq style.
- zoogeny 2y ago> 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 2y agoFair 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 2y agoAnother 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.
- c0nstantine 2y agoThe '-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.
- wfn 2y agoWhat 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 2y agoThank you! For the feedback and pointing to the typo. Fixed. Actually my C is very rusty and I am bit uncomfortable about this.
- pipeline_peak 2y ago[flagged]
- BFPQVZ 2y agoAnother alternative that is similar would be Carmel (https://github.com/isi-nlp/Carmel-Repository https://github.com/isi-nlp/Carmel-Repository)
- deleted 2y ago[deleted]
- c0nstantine 2y agoThank 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 https://github.com/c0stya/fslib
- teknopaul 2y agoMy 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
- deleted 2y ago[deleted]
- metadat 2y agoWhen 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.
- deleted 2y ago[deleted]
- c0nstantine 2y agoHey, 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 2y agoThanks for the clarification, totally on me to set expectations inappropriately based on only a headline. Take care.
- simlevesque 2y agoI 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]
- deleted 2y ago[deleted]
- c0nstantine 2y agoAre 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}?'
- simlevesque 2y agoI'm using Linux.
- c0nstantine 2y agoDid it solve the problem? I guess the issue is the process substitution construction of bash "<()". Not all shells support this.
- 38 2y ago[flagged]
- deleted 2y ago[deleted]
- larodi 2y agoIn 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.
- c0nstantine 2y agoThank 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.
- kazinator 2y agoThis 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.
- c0nstantine 2y agoI 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.
- layer8 2y agoI would give the colon operator lower precedence than concatenation and repetition.
- pmarreck 2y agoso basically just `sed -e`?
- layer8 2y agoThis 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 2y agoIf I understand correctly the following ttre expression does what you're asking for: ":'(':(\\')|[^"'])*":'
- layer8 2y agoGood point, I didn't think of that solution.
- tomashubelbauer 2y agoSo this is how it feels to read a regex when you don't know how to regex.
- c0nstantine 2y agoThank you for doing my work! :)
- c0nstantine 2y agoHi, 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.
- Lanzaa 2y agoIf 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/master/doc/i-know-regex.md https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste... https://rosie-lang.org/about/ https://rosie-lang.org/about/
- groby_b 2y agoIt'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 2y agovery inspiring idea, makes me wanna start projects I had in mind related to that. thanks and good luck
- languagehacker 2y agoFor 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 2y agohttp://hfst.github.io/ 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.
- woodson 2y agoThere’s also k2 (https://github.com/k2-fsa/k2 https://github.com/k2-fsa/k2) which implements a lot of FSA and FST algorithms in CUDA, with PyTorch bindings.
- ChuckMcM 2y agoI was going to mention this as well. This is a link to Kaplan's paper : https://aclanthology.org/J94-3001.pdf https://aclanthology.org/J94-3001.pdf which describes the work PARC did.
- mcyc 2y agoPeople 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 https://www.openfst.org/twiki/bin/view/GRM/Pynini [2] https://www.openfst.org/ https://www.openfst.org/
- jll29 2y agoCheck 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/bo3613750.html 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/bo3613750.html https://press.uchicago.edu/ucp/books/book/distributed/F/bo36... FOMA: the open source clone https://fomafst.github.io/ https://fomafst.github.io/ FOMA: the paper (Holden, M. (2009) Proc. EACL) https://aclanthology.org/E09-2008.pdf https://aclanthology.org/E09-2008.pdf FOMA: the open source clone https://fomafst.github.io/ https://fomafst.github.io/ FOMA: the paper (Holden, M. (2009) Proc. EACL) https://aclanthology.org/E09-2008.pdf https://aclanthology.org/E09-2008.pdf
- MathMonkeyMan 2y agoFrom 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 2y agoInteresting! 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.
- skykooler 2y agoNot sure the range operator is fully specified, this works and seems like it shouldn't: echo "regular expressions" | ./trre "[a:A-z:a]" REGULAR EXPRESSIONS In fact, "[a:A-z:x]" seems to do the same thing as "[a:A-z:Z]" for all x.
- kemiller 2y agoThis feels like it would be interesting in the Helix editor. They don't have a good solution for traditional regexp search-and-replace, but this would fill that niche in a more elegant way.
- c0nstantine 2y agoHi. 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.
- kemiller 2y agoOh, I'm not directly associated with it, and I don't use it mostly because that specific feature is missing. And they're in rust, so I'm not sure how well c bindings work. Still, really cool project.
- ngruhn 2y agoyou should call it `trex` :D
- YeGoblynQueenne 2y agoCool project. Here's my use of Finite State Transducers (det and nondet) for navigation agents: https://github.com/stassa/ijclr_2024_experiments https://github.com/stassa/ijclr_2024_experiments
- CyberDildonics 2y agoThis doesn't seem to have anything to do with regular expressions.
- YeGoblynQueenne 2y agoNot regular expressions but regular automata. The project uses Finite State Transducers to build autonomous agents.
- CyberDildonics 2y agoThis thread is about regular expressions. Finite State Transducers to build autonomous agents That's extremely general and is terminology from the days of tape drives that describes techniques that are considered trivial now, like parsing strings into individual words. https://en.wikipedia.org/wiki/Finite-state_transducer https://en.wikipedia.org/wiki/Finite-state_transducer
- deleted 2y ago[deleted]
- YeGoblynQueenne 2y agoOh, apologies, I didn't realise you were asking for more specific information. You can find that in the link I posted above. There is a copy of a paper in the repo, here's a direct link: https://github.com/stassa/ijclr_2024_experiments/tree/master/paper https://github.com/stassa/ijclr_2024_experiments/tree/master... The paper was accepted for publication but it's still in review and anyway I prefer to point people to the repo with the code so they can reproduce the experiments if they want.
- aqueueaqueue 2y agoAnother alternative is regex and use replace all. Then you cam replace the regex cat with dog (or use a group for wrapping with space) This is a common modus operandi for me in VS Code.