Re:A Course on Automata Theory
by forgettableuser on Thursday August 20, 2015 @09:02AM
(#10091538)
I already knew Perl and Posix regex when I took automata. I cruised through the initial basics of regular expressions faster than my peers. But I got into trouble after I learned that regex contains a bunch of features (hacks) that have no grounding in pure automata theory. I had to unlearn a whole bunch of things.
[ Parent
| on HN ]
Professor Roberto Ierusalimschy (creator of Lua), was bothered by the problems of regex deviating from (real) regular expressions, like how captures create non-determinism, back references make pattern matching algorithms NP complete, no formally defined performance model, and so on. This led him to revisit prior research on PEGs (Parseable Expression Grammars) which are akin to Context-Free Grammars. He created a library called LPeg which was a PEG for Lua.
He gave a talk about all this which can be found here: https://vimeo.com/1485123
So he basically realized people were hacking regular expressions to get more power. So rather than playing that game, he climbed up a level on the automata ladder to get a more mathematically sound approach to the problem.