how do I regex_syntax crate for translating two posix descendant regexes syntaxes?

[kaiuri]

Say I wanted to reuse the regex_syntax crate for implementing a translator from one regex syntax to another. Since some strategically important types are private and many, how can I make use of those without using a wrapper if no traits are available that make those type's functionalities available?
Would I be better off working with Nondeterministic Finite Automata as a bridge between the two regexes syntaxes instead?

[BurntSushi]

Sorry but I don't think there are enough details in your question for me to understand it enough to give an answer. Can you maybe be a bit more concrete? Showing some code tgat you would like to write would be helpful too.

[kaiuri]

hey, i solved it. thank you for your time, @BurntSushi . Sorry for wasting your time. I'm very new to programming

[BurntSushi]

Note that when you ask a question, if you end up figuring it out on your own, it is generally polite to share the solution you found. That way, others who stumble across this question can get something out of it.

[BurntSushi]

Also, I noticed that you deleted a comment you made here? Again, why? It contained useful information! This is what I see in my inbox:

I'm looking for a way to convert this crate's regular expressions into vim's regex implementation. Initially i thought about writing a compatible parser for vim's regex and from there implementing this crate's Visitor, which is private. Maybe a wrapper would do, but it came to me, since I'm still kind of a noob in Rust and programming, that there must sure be an easier way and i just couldn't find it.

PS: On the subject of NFA, that is a backup plan in storage if the above doesn't pan out or gets to big for me to complete.

So the first thing to note here is that Visitor for the HIR is not private. It's right here: https://docs.rs/regex-syntax/latest/regex_syntax/hir/trait.Visitor.html

There is even a Visitor for the AST as well, although you probably want the HIR visitor: https://docs.rs/regex-syntax/latest/regex_syntax/ast/trait.Visitor.html

It's possible you might want the AST visitor though. It will be more complicated, but it will give you a bit more control on how things are translated to another syntax. With the HIR, I suspect it should work just fine, but you might wind up with regexes that do not look like a human wrote them.

Now, with all that said, you don't need to use a Visitor. A Visitor is a complicated piece of infrastructure that is really only motivated by one thing: to use constant stack space. If you don't need or care or even know what that means, then you probably don't want to use a Visitor. Especially for a first draft or a proof of concept. Instead, you can just do structural recursion on the HIR (or AST) types. Kind of like how src/compiler.rs in this repo looks. It is much much much simpler.

As for what you said on reddit:

I might do that, i guess I was afraid of feeling dumb

I get that too myself. But there are no stupid questions. The answers might be staring you right in the face in the docs, and indeed, I might give a terse response pointing to the docs. But that doesn't mean you're dumb or I think your dumb. The number of times I've missed something plainly stated in the docs over the years is uncountable. Sometimes you just miss stuff. And other times, the docs aren't as good as they could be.

[kaiuri]

It occurred to me to try implementing just an alternative Printer using generics and the available traits, I actually even started on that, therefore I figured deleting it before wasting anyone's time - which I know now it wouldn't be so.

Thanks a lot for answering, despite my shortsightedness, because now I know there's actually a confirmed, feasible and easier way, exemplified in src/compiler.rs, as you helpfully mentioned 🙏.

I'll try not forgetting that

(...) there are no stupid questions (...)

for the future. In retrospect, it was a little bit of a burnout on my part. Anyways, answers, like you said, right in front of me but missed, somehow, and heck ...sometimes you just miss stuff..., right?

Thank you so much @BurntSushi , this discussion's been helpful in more ways than I hoped for.

[BurntSushi]

Glad I could help. Good luck!

[kaiuri]

@BurntSushi , man! I actually solved it through math, here me out:

1. Theorem: If an NFA recognizes A then A is a regular language.

2. Theorem: If R is a regular expression and A=L(R) then A is regular. Simply put, Every language describable with regular expressions is regular.

Proof: R being a regular expression, it can be so either by being [atomic] or [composite].

* Case: R is atomic ::= if R is a single symbol then an NFA will reject anything other than it.
                        if R = an empty string or empty language, that's solved.

* Case R is composite ::= Closure construction thru concatenation,
                          union and Klene's star, solves it.

Then, after hacking the source code of Neovim and Vim, I've studied the algorithm for their new NFA engine which then occurred to me must be mathematically compatible through Nondeterministic Finite Automata as they're both formal languages. Therefore, after researching Kleene's algorithm and Glushkov's construction algorithm, both are compatible at high-level intermediate representations, aka NFA.

Concluding, transforming a Rust's (BurntSushi) regex syntax into HIR and printing it back out as a regular expression bridges the gap between the two syntaxes and that output should be accepted by both machines. I then ran some tests and it is indeed so, even more, Vim would automatically switch engines to accommodate the expression derived from the HIR, explicitly.

I'm packaging the solution into an app, furthermore, this all implies, if Neovim devs are interested, they can actually replace(or add an opt out of) the old vimregex engine with Rust's, provided we escape the special symbols or turn the "very magic" option. It's even feasible to replace Vim's "new" NFA engine using the regex_syntax crate and keep the later one as a bridge to keep old plugin from breaking changes.

PS: Please forgive any misspelling, my ADHD makes me switch some words and I can't always spot those mistakes.

[kaiuri]

Oh man, I'm overjoyed here, but yeah, you're very much right. I don't intend on pushing it into Neovim - and suggesting on Bram's Vim would be stretch- but I opened a suggestion for enhancement on neovim's repo and made myself available for working on it. Also tried to make sure not to be misinterpreted: 17333. Which reminds me, you talked about this subject on you blog post about working with FOSS, I think.

They decided against but found it an interesting proposal. Anyhow, I'll be working on it out of pure curiosity as I'm VERY interested on the nitty gritty of computers and programming languages. Not even a year has passed since I started programming and can't stop digging into or imagine my life without it (╯°□°）╯︵ ┻━┻

Also, I would add, if you want more help here, please please please share code.

I created a repository for it today: vrex 🦖 but it's all mostly a proof of concept and loads of scratches.

The theory part is all true, but it's not really the issue. The issue is more of a practical one. Namely, the problem is not whether you're dealing with a regular language or not, but rather, how to translate one syntax into another. For example, is this regex engine's \s class the same as vim's?

That's a great point, for this specific example, yes. But there's sure to be instances when it won't be. I'm still digging through the thousands of C-code lines implementing vim's regex engines.

Also, beware of things that look like their theoretical constructs but actually have more power. For example, the NFA simulation in this crate is actually more powerful than what an NFA can do because it tracks capture group match locations.

I will. That disparity comes from the aho-Corasick algorithm implementation?

The answer may or may not include using Rust.

Very true, I've been researching into Haskell after I started reading through c2rust's transpilation implementation, as the language seems to handle strings and regular languages very well.

On a side note, @BurntSushi , would you be so kind as to give me some pointers or reading suggestions on Systems Programming, Theory of Computation or alike? I lack a lot on formal computer science education, being self-taught and all, but I've been feeling those gaps slowing me down and would accept such suggestions gladly. By the way, if you so choose to suggest any readings, don't refrain because of mathematical complexity as I've got a firm background on the topic.

[BurntSushi]

That disparity comes from the aho-Corasick algorithm implementation?

No. Aho-Corasick is a specific algorithm that implements multi-pattern search, where patterns are just plain literals. It is an entirely optional component and is generally only used for optimization purposes.

The extra power in the NFA simulation is how capturing groups are resolved and is not an optional component of this crate.

I suggest reading at least the first three articles in Russ Cox's series on regexes: https://swtch.com/~rsc/regexp/

On a side note, @BurntSushi , would you be so kind as to give me some pointers or reading suggestions on Systems Programming, Theory of Computation or alike? I lack a lot on formal computer science education, being self-taught and all, but I've been feeling those gaps slowing me down and would accept such suggestions gladly. By the way, if you so choose to suggest any readings, don't refrain because of mathematical complexity as I've got a firm background on the topic.

With respect to systems programming, I might suggest working through the xv6 book/class out of MIT: https://pdos.csail.mit.edu/6.828/2021/xv6.html

For theory of computation, I think Sipser's "Introduction to the Theory of Computation" is standard, and is what I used in school. Although personally, I've found it quite difficult to work through textbooks outside of the structure of a class environment. YMMV. If you're interested in the application of theory with respect to regexes specifically, then you probably already know what you need. The challenging part about working on regex engines is not the theory. The theory is rather simplistic and terribly unhelpful, with a couple notable exceptions. The challenging part is the engineering.

There is no substitute for going out and actually building stuff. That is, in my experience, the best way for me to learn. Focus on a goal, and then learn what you need to achieve it.

[kaiuri]

Thank you so much for the suggestions. I've just now seen that GitHub's
actually deleted my original response, it was much more thorough, I should've
kept a backup. Anyways, I already hit those suggestions and Sipser's
explanation on automata and how it relates to CFG has been a BIG game change on
my productivity, his book and MIT-OCW's course are actually helping me advance
a lot! So is the xv6 code and book, the latter I've turned into an asciidoc, if
you're ever interested. And the first regexp article showing how older regex
engines work and their performance superiority to most contemporaneous regex
engines REALLY changed my view of code and what elegant code really means.
Thanks again, seriously, I'll be saving this conversation as it has lots of
content I'll need not forget, like ever.

Be seeing you, have a nice one, @BurntSushi

PS: Please, Github,do not delete this reply too.

[BurntSushi]

Glad to be of help!

Pro-tip: there is a "Include your own updates" checkbox in your Notification Settings on GitHub. I have it enabled. It creates a little extra noise, but that way, I have a copy of whatever I write in my inbox regardless of what happens to it on GitHub.

[kaiuri]

Pro-tip accepted and implemented!