Hacker News Reader

Regular expressions in modern programming languages and the regular expressions you learned about in your automata theory class are not the same thing. The back references present in the regular expressions discussed in the article make the entire system capable of handling even NP-complete problems. So yes, regular expressions (in the more common use of the term) can "parse".

View on HN

The back references present in the regular expressions discussed in the article make the entire system capable of handling even NP-complete problems.

Really? So, we can parse HTML with regular expressions nowadays?

I think a more appropriate word choice would be "recognize" instead of "parse", with regard to the OP of the thread.

I did allude to that, but regular expressions are still not quite up to the tasks you would use a parser for.

I can only hope this challenge inspires a spiteful hacker to create a full grammar parser in a regular expression. It won't be me, but I love how these types of comments can sometimes spawn the most interesting toy projects. :)

You may enjoy this http://www.a-k-r.org/abnf/

Reply on news.ycombinator.com