The convo about parsers with @jamiebuilds made me curious. He says regex is all you need for parenthesis matching, I say you need a parser.
We agree you need at least regex + depth counter because parenthesis matching is not a regular language.
But is that a parser? #200wordsTIL
First, you need to look at this picture. It's the Chomsky hierarchy of formal grammars. CompSci speak for "How big a class of problems can you solve using a language with certain properties"
Recursively enumerable languages are Turing complete. They solve all solvable problems.
Context-sensitive languages are like Turing machines with limited space.
Context-free languages produce stack-based automata.
Regular languages produce finite state machines. @davidkpiano's favorite.
Regular languages's achilles heel is that they can't count. You have to know all possible states in advance.
You can't match parentheses with a regex unless you know how deep the nesting goes in advance.
You can write a regex that matches parentheses up to, say, 1000 levels deep. But the 1001st level breaks it.
A possible solution are fancypants PCRE recursive regexes. You'll have "fun".
Or you can use a super simple regex and add a stack-based counter. Now you have a context-free grammar based language.
But is it a parser? Turns out that's a tough question to answer 👇
Wikipedia says that parsers are used for syntactical analysis and producing syntax trees. That's way more than we need for parenthesis matching. (https://en.wikipedia.org/wiki/Parsing)
HOWEVER, parenthesis matching with a stack is used as an example in this "Parsing Techniques: A practical guide" book https://books.google.com/books?id=05xA_d5dSwAC&pg=PA101&lpg=PA101&dq=does+parenthesis+matching+require+a+parser&source=bl&ots=3PuAaFi4Qf&sig=ACfU3U1cT3IRJuwtK1SUqcoEfpeW_tpt6A&hl=en&sa=X&ved=2ahUKEwjy2cnnko3gAhVIFTQIHWEWDJAQ6AEwBXoECAkQAQ#v=onepage&q=does%20parenthesis%20matching%20require%20a%20parser&f=false