Regex Library in Rust from Scratch (Finite-State Machines)

Рет қаралды 47,317

Tsoding Daily

Күн бұрын

Пікірлер: 35

@titaniumtomato7247 2 жыл бұрын

This "recreational coding" is exactly what I want to spend my life doing

@ilovepeaceandplaying8917 Жыл бұрын

me too

@SoftBreadSoft 10 ай бұрын

@@travaaa8432God's plan

@TedMan55 9 ай бұрын

go for it

@anoh2689 4 ай бұрын

Me too

@omarmagdy1075 2 жыл бұрын

Just found this channel and it's an absolute gem mine. your content is just precious and very educational too.

@nilstrieb 3 жыл бұрын

You can use Enums for indexing, you just have to set the values for the enum like enum A { B = 0, C = 1} and then cast it arr[A::B as usize]

@zaneoblaneo7624 2 жыл бұрын

I might be dumb for asking, but can't you also repr(C) the enums now-a-days? While it's less readable and less "rust"y, it looks like it would do the right thing. ¯\_(ツ)_/¯

@relacibo 2 жыл бұрын

you could also do #[repr(usize)] enum A { B, C }

@user-uf4lf2bp8t 3 ай бұрын

@@relaciboexplicit repr in rust is generally bad practise in rust

@fr3fou 3 жыл бұрын

this seemed really interesting, hope you finish working on the groups next time!

@erenmetesar8427 2 жыл бұрын

seeing this, even though i am great at understanding and writing code, i suck at algorithms and all the other mathematical shit so i don't have what it takes to be a full blown developer. i now understand why entrance exams require mathematical knowledge now

@legion_prex3650 2 жыл бұрын

if you like coding, its just a little jump over to math and algorithms. a really good course for algorithms is by princeton professor Rob Sedgewick (by hisself student of the great donald knuth, look them up, if you dont know those guys): kzbin.info/www/bejne/Z4K9dZhobdWYkM0

@JMCe6a 3 жыл бұрын

Seems like this kind of engine does not work properly with regex like ".*bc", doesn't it? It will stuck on FsmColumn of *, which will never propagate to latter columns. I guess we need some kind of lookahead for it.

@TsodingDaily 3 жыл бұрын

Oh yeah! That is true! Thank you so much for noticing! I'll think what we can do about it.

@iuppiterzeus9663 Жыл бұрын

@@TsodingDailycompile your regex to an NFA (non-deterministic finite automaton) which is equivalent to a DFA (deterministic finite automaton, what you called "finite state machine" thoughout the video). The operations that compose the parts of regexes are concatenation, branching/option and repeating (Kleene-closure). All other regex features (like +) are syntactic sugar for the basic operations. These operations are fairly easy to implement over NFAs. Therefore, compile the parts of your regex to separate NFAs and apply the corresponding operations. Then convert your NFA to a DFA (there are fairly stright-forward algorithms for that) and you have it. That's how I wrote a regex library myself, also using rust and for recreational purposes. quick note on your finite state machine terminology: turing machines, push-down-automatons, NFAs and DFAs are all finite state machines. NFAs and DFAs are equivalent and can accept regular languages (regexes define a regular language). push-down-automatons are basically NFAs with a stack, the top of which is an argument to the transition function, and can accept regular and context-free languages (all programming languages are context-free languages). turing machines can compute anything computable (*the* famous paper by Alan Turing) and, as you mentioned, modify some memory which is also their input and output.

@boboxxrbt Жыл бұрын

Great content here! But does it work with the regex "a.*bc"? I guess that the .* will consume all remaining characters and fail on valid inputs as "adfgbc"... Am I wrong? BTW, I would love to see a follow up video where you tackle this problem and the nested regexps you were mentioning at the end.

@kyuantym Жыл бұрын

This is an absolute masterpiece.

@andresalejandrogarciahurta5856 3 жыл бұрын

you could also match the combinations of all the dimensions of the state machine inside a tuple, so that you get flat arms (rather than nested) and the code is "cleaner" and more manageable, like: `match (state, event, other_dim)`. For a few number of dimensions I think this approach is more idiomatic and less "hacky". Thanks for the video anyways, really enjoy it thoroughly.

@erenmetesar8427 2 жыл бұрын

You could've done something like: ('a'..='z').map(|a| a as u8 ).collect::() range is mappable, you just need to call collect method on it

@martinfrances107 2 жыл бұрын

For array initialization, the lazy_static module is a good option.

@yapayzeka 2 жыл бұрын

16:20 thank you but you didn't inform user what to write?! also enum means already const.

@MACAYCZ 2 жыл бұрын

1:35:55 You should rename your channel to T-rex Daily

@DMWatchesYoutube 3 жыл бұрын

I saw a good video on command pattern for a more complex state machine

@GPandzik 2 жыл бұрын

Unexpectedly excited to see another emacs user writing Rust! 😀 It seems everybody is using (or at least demoing) VSCode, which I don't use for a lot of reasons.

@legion_prex3650 2 жыл бұрын

i really wonder, why so many people use VSCode these days. It is by far not an good editor (as far as i know, i just tried it out once). I don't use emacs either, i am only a little vim user and quite happy with it (and cannot even program properly in common lisp).

@JohnDoe-sp3dc 2 жыл бұрын

@@legion_prex3650 so you can't program yet you're complaining what code editor other people use? Cognitive dissonance in action here folks.

@belaolson8172 2 жыл бұрын

@@JohnDoe-sp3dc as someone who can program reasonably alright, I agree with the sentiment that VSC is a pain simply because ease of access. You install Vim, all you gotta do is read the docs and you know what you're doing. For VSC you have to download 15 packages to do one task, then you need internet to update those packages just to get them to work properly, it's all a big fuss. I probably would have less to complain about if it wasn't so finnicky with everything, but as it serves now it's just not nice to use unlike something like Vim or emacs

@syth-1 Жыл бұрын

@@belaolson8172download everything? I mean usually when it's a new language sure, and you get a pop up asking you to download all major packages for that language, Once it's set up, that's it - you never need to worry about that sort of thing again, updating is done automatically when you get internet connection, your not forced to do so nor does it render your editor useless by not updating said packages (dunno how you got that issue - never had any thing of that sort) I'm not saying Vs code is great, but the points mentioned seemed trivial and not highlighting actual problems with Vs code - and painting a worst picture than it rlly is (yes downloading extensions for new languages suck, I get that point, but it's not as* bad as you made it sound to be where it's problem ridden etc - it's a automated process the way I see it) Vs code has a slow start up that's for sure - I've not used many other editors, but Vs code is for my purpose, very usable - sure it's ease of access for things may not be the same - where using vim will be faster cause kB shortcut (n powerful commands that can come with that) vs navigating a UI, plus mem intensive compared to running in a terminal etc etc

@lainiwakura3741 Жыл бұрын

@@JohnDoe-sp3dc If you want to insult people you should at least try to properly understand what they're saying.. They specified that he cannot program in lisp, which is the language you use to configure Emacs, which is why they stick to vim. There was absolutely no cognitive dissonance in that sentence. I guess you can still be angry with them for having an opinion on vscode, but that seems silly imo.