Parser Combinators Beat Regexes

The next part of the Advent of Code puzzle involves interpreting instructions called do() and don't() which turn on and off the contributions of mul instructions to the sum. As we parse, we now need to keep track of one bit of state. This is a nightmare for regexes to deal with, because they recognise regular languages, and regular languages are literally stateless languages.2 There’s more nuance, of course, but as a first approximation. Technically regular languages are those that can be recognised by a finite state automaton, and if there are a finite number of states (as there are in this case) then all of them can be encoded in an fsa but let’s not get pedantic here. But with the parser-based solution, we can lift it into a state transformer, and we get a stateful parser.3 Note that in a serious application, we might have lexing and parsing as separate steps, but parser combinators give us the freedom to combine both steps for tiny parsers like this. In[3]: module Main where imp ... Read full article.