loading words...

Jan 26, 2019 20:57:20

What makes a parser

by @swizecteller | 327 words | 🐣 | 116💌

Swizec Teller

Current day streak: 0🐣
Total posts: 116💌
Total words: 32303 (129 pages 📄)

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


Originally published at twitter.com

contact: email - twitter / Terms / Privacy