system
Given the following post, respond as if you're commenting on Reddit:
human
What is the ELI5 for how RegExp works?

For me, Regexp feels like magic. It's like you can parse anything with a few short keystrokes. Prior to Regexp, I'd be writing extemely complicated for item of string.split loops, to get the things that I would need. 

I'm pretty curious as to how it works under the hood.
gpt
First, that gibberish-looking `[a-zA-Z_][a-zA-Z_0-9]*\s*=\s*\d+\s*;` syntax is just some notation. The regex engine reads this notation and builds its internal representation - a _state machine_.

A state machine is basically a directed graph whose nodes represent questions about the next symbol in the input stream and the edges are the possible answers to these questions _and_ instructions to go to the next question.

For example:
 1. Is the current symbol one of `a-zA-Z_`? If yes, read next character and go to state 2, else _NO MATCH_;
2. Is the current symbol one of `a-zA-Z_0-9`? If yes, read next character and go to state 2, else read next character and go to state 3;
3. Is the current symbol a kind of space (the syntax is `\s`)? If yes, read next character and go to state 3, else read next character and go to state 4;
4. Is the current symbol a literal "equals" sign (`=`)? If yes, read next character and go to state 5, else _NO MATCH_;
5. Is the current symbol a kind of space (the syntax is `\s`)? If yes, read next character and go to state 5, else read next character and go to state 6;
6. Is the current symbol a digit? If yes, read next character and go to state 7, else _NO MATCH_;
7. Is the current symbol a digit? If yes, read next character and go to state 7, else read next character and go to state 8;
8. Is the current symbol a kind of space (the syntax is `\s`)? If yes, read next character and go to state 8, else read next character and go to state 9;
9. Is the current symbol a literal semicolon? If yes, __FOUND A MATCH__! Else, _NO MATCH_!

Say, your string is `"abc = 82;"`. You read the first character and go to state `(1)`.

If you arrive at state `(9)` and get a match, this means that, well, the regular expression above matches the string, or, in other words, that string can be generated by the grammar encoded by the regular expression.

If you arrive at `NO MATCH` _anywhere during the execution of the algorithm_ (not necessarily in state `(9)`), you stop and report an error because the regex doesn't match the string.

As you can see, this can be easily implemented with `goto` statements and labels:

```
azAZ_ = "abcd...xyzABCD...XYZ_";
azAZ_09 = azAZ_ + "0123456789";

START:
 ch = getchar();
 if (ch in azAZ_) goto _2;
 goto ERROR;

_2:
 ch = getchar();
 if (ch in azAZ_09) goto _2;
 goto _3;

_3:
 ch = getchar();
 if (isspace(ch)) goto _3;
 goto _4;

_4:
 ch = getchar();
 if (ch == '=') goto _5;
 goto ERROR;

// and so on...

_9:
 ch = getchar();
 if (ch == ';') goto MATCH;
 goto ERROR;

ERROR:
 printf("ERROR at character '%c'!\n", ch);
MATCH:
 puts("Yeah, everything is OK!");
```

Now, you wouldn't normally generate that code from the regex string above (although you could). Instead, you'd build some kind of graph (like a linked list, but a graph whose node can link to _any_ other node, including itself), whose nodes will execute some functions that can return, for example, a pointer to the node where the algorithm will jump:

```
node *start; // will be filled up by analyzing the regex string

node *current_node = start;
while (1) {
 current_node = current_node.step(string_to_match);
 
 if (current_node.tag == NODE_ERROR) {
  printf("ERROR at character '%c'\n", current_node.character);
  break;
 } else if (current_node.tag == MATCH) {
  puts("Yeah boiiiiiiiiii!");
  break;
 }
}
```