Abstract

Transforming text to some in-memory data structure — parsing, as it's usually called — is perceived as a form of black magic. It looks like a complicated thing to do and parsing an actual programming language even more so. It is actually held in such a high regard that some people seem to mistake parsing for the task of writing a compiler or interpreter in its entirety, which is certainly not the case.

While not always a trivial task, parsing is probably easier than you think and I'll try to prove it during this presentation. We'll see how a stream of characters is transformed into a stream of tokens, which are then fed to the parser proper that will finally derive an in-memory tree data structure. I will be using Scala as the implementation language and a subset of Standard ML as the language to parse.