3 ms·
Maybe I'm taking this a step too far but doesn't Gödel's Incompleteness Theorems (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://e
by proverbialbunny 7y ago
Maybe I'm taking this a step too far but doesn't Gödel's Incompleteness Theorems (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...) state that a language can not define itself? You need a meta language to be able to define and specify a language in its entirety.
In other words, regex can not parse regex in its entirety. It's impossible.
- wool_gather 7y agoNo, not really. This is probably closer to Chomsky's area than Gödel's. Gödel's theorem is about semantics, not syntax. As a nice counter-example to what you said, you can define the Backus-Naur notation using Backus-Naur notation: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form#Further_examples https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form#Furth...
- wahern 7y agoCan a C program parse C source code? A Java program parse Java source code? Yes, they can, so such a general limitation couldn't be the reason regular expressions can't parse themselves. Perhaps you had in mind the Halting Problem: https://en.wikipedia.org/wiki/Halting_problem#G%C3%B6del's_incompleteness_theorems https://en.wikipedia.org/wiki/Halting_problem#G%C3%B6del's_i...