# Nikita Popov - The True Power of Regular Expressions (Highlights) ![rw-book-cover|256](https://readwise-assets.s3.amazonaws.com/static/images/article1.be68295a7e40.png) ## Metadata **Review**:: [readwise.io](https://readwise.io/bookreview/49005703) **Source**:: #from/readwise #from/reader **Zettel**:: #zettel/fleeting **Status**:: #x **Authors**:: [[Nikita Popov]] **Full Title**:: The True Power of Regular Expressions **Category**:: #articles #readwise/articles **Category Icon**:: 📰 **URL**:: [www.npopov.com](https://www.npopov.com/2012/06/15/The-true-power-of-regular-expressions.html) **Host**:: [[www.npopov.com]] **Highlighted**:: [[2025-02-21]] **Created**:: [[2025-03-29]] ## Highlights - So what are `B`, `C` and `a`? By convention, uppercase characters denote so called “non-terminals” - symbols which *can* be broken down further - and lowercase characters denote “terminals” - symbols which *cannot* be broken down any further. ([View Highlight](https://read.readwise.io/read/01jmkqacy1ha06ttycfye1zk86)) ^855141495 - Any modern regex flavor can match a *lot* more than just regular languages. ([View Highlight](https://read.readwise.io/read/01jmkqbqy1s4d7wvy9j9havmkn)) ^855141573 - The regular expression is very simple: `(?1)` is a reference to the first subpattern, namely `(a(?1)?b)`. ([View Highlight](https://read.readwise.io/read/01jmkqr65rx95m9vcnmrn81bzs)) ^855142548 - The new thing now is the `(?=...)` which is a so called zero-width lookahead assertion. It checks that the following text matches the pattern, but it does not actually consume the text. ([View Highlight](https://read.readwise.io/read/01jmkqrvanpwf3rkpmh6zv5988)) ^855142576 - The reason is that lookbehind assertions (`(?<= ... )`) have one very significant limitation: They have to be fixed-width. This means that the length of the text matched by the assertion has to known in advance. ([View Highlight](https://read.readwise.io/read/01jmkqvd2t47415emx708gmc0k)) ^855142924 - Regex can match at least *some* context-sensitive languages, but it’s unknown whether it can match *all* of them. ([View Highlight](https://read.readwise.io/read/01jmkqwe92e8q5rdb33k9zjw97)) ^855143024 - Regular expressions with backreferences are NP-complete ([View Highlight](https://read.readwise.io/read/01jmkqx4ypqkhvarn4w02bk17g)) ^855143049