Bucharest FP #21 — Parsing: How Does it Work?

Ionuț G. Stan — Parsing: How Does it Work?

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.

BIO: Ionuț is a software developer at Eloquentix, where he works on backend services using Scala. His current interests revolve around functional programming techniques, programming languages and compilers.