How to Happily Write an Interpreter

（一）

In an essay from a few days ago, “Random Thoughts on Software,” I offhandedly wrote: “It seems the age of lex/yacc and bison/flex is behind us. I once watched a colleague laboriously parse some system’s data files line by line in Perl, never once thinking to write a BNF. BNF was not an option for him.”

Many readers were puzzled and asked me: aren’t lex/yacc for writing compilers? I’m not inventing a new language, so what use are they to me?

This question reveals how deeply our domestic undergraduate education has been poisoned. The compilers teachers in their ivory towers have probably used lex/yacc to write nothing more than a useless toy language, and then passed their half-digested understanding on to their students. The students learn it half-baked, lose all interest, and after the exam hand the rote-memorized material back to their teachers, intact.

Don’t laugh — that’s exactly how I came up too. The one and only thing I ever did with lex/yacc was design a damn language.

The world already has so many languages that there’s simply no room for the likes of us to design yet another clumsy, cringe-worthy language with neither good looks nor performance. Besides, back around 2000 there was no magic tool like LLVM, nor a pensieve like GitHub from which to “steal” others’ ideas. A clumsy language you designed could get no further than parsing, with no practical use whatsoever.

Later lex/yacc evolved into flex/bison. At work I happened to flip through an O’Reilly book called ‘Flex & Bison,’ whose subtitle boldly read: text processing tools.

The book’s content was rather dogmatic and a little detached from real work, but the phrase “text processing tools” struck a chord: yes — lexical parsing (lex/flex) and grammar parsing (yacc/bison) are just better text processing tools (parsers), DSLs (Domain Specific Languages) for efficiently handling text that has grammar! They have absolutely nothing to do with compilers; it’s just that one of their use cases happens to involve compilers. We needn’t make them out to be so profound!

What tools do we have for text processing?

Regular expressions!

Which programming language today doesn’t support regular expressions? Likewise, which programmer today doesn’t use them (in their code)?

Regular expressions are also a text processing tool, also a DSL — except they can’t handle complex grammar.

As we know, in automata theory there are FSA (Finite State Automata) and PDA (PushDown Automata). The former can be expressed with regular expressions, while the latter can handle CFG (Context Free Grammar) — and CFG is precisely what flex/bison is meant to handle!

Unfortunately, most languages have no built-in support for CFG. Once the complexity of the text you’re handling exceeds what regular expressions can express, we’re stuck. For example — if you had to parse a piece of text like this, what would you do?

server {
  listen 80;
  server_name auth;
  access_log /var/log/nginx/auth.access.log;
  error_log /var/log/nginx/auth.error.log;
  location / {
    proxy_pass http://localhost:3000;
    include /etc/nginx/proxy_params;
  }
}

Regular expressions, of course, are powerless here. Reading character by character, splitting tokens by word, then handling the grammar of braces and semicolons — you’re essentially writing your own parser, and it’s hard to keep it efficient and extensible. So at times like this we reach for a third-party tool like flex/bison.

flex evolved from lex and does lexical analysis. Lexical analysis, put plainly, is chopping text into grammatical units you recognize. In the example above, server is one such unit; we call such a unit a token.

In flex, we can describe the tokens that appear in the above text like this:

%%
"server"      {return SERVER;}
"listen"      {return LISTEN;}
"SERVER_NAME" {return NAME;}
...

"{"           {return OP;}
"}"           {return CP;}
";"           {return TERMINATOR;}
[\s\t\r\n]    {/* ignore */}
[A-Za-z0-9\.\/:_]+  {printf("%s\n", yytext); return VALUE;}
%%

Next comes the grammar analysis stage. Grammar parsing is doing pattern matching, but unlike regular expression pattern matching, it lets you define a series of recursive rules. On standard Unix, the grammar parsing tool is bison. Let’s see how the above text is parsed with bison:

%%

server:
  | SERVER OP exp_list CP
  ;

exp_list:
  | subexp exp_list
  | exp TERMINATOR exp_list
  ;

subexp: LOCATION path OP exp_list CP
  ;

exp: keyword value
  ;

path: VALUE

keyword: LISTEN
  | NAME        {printf("\t%s: ", "name");}
  | ALOG        {printf("\t%s: ", "access_log");}
  | ELOG        {printf("\t%s: ", "error_log");}
  | PROXY_PASS  {printf("\t%s: ", "proxy_pass");}
  | INCLUDE     {printf("\t%s: ", "include");}

value: VALUE
%%

The main body of the code is quite clear: a server {...} is matched with a single rule SERVER OP({) exp_list CP(}). When the parser encounters something it can’t recognize on its own, like exp_list, it looks for a rule named exp_list and continues matching. If you often use functional programming languages, you’ll find this way of writing rules strangely familiar.

The syntax bison uses to describe rules is a variant of BNF.

Below is the result of compiling and running. For demonstration purposes, I printed only the parts of the syntax tree I was interested in:

From the compilation process above, you can see that flex/bison is a DSL for C. So you can embed C code while processing lexical and grammar rules to transform the results you need. There must be some conventional interface between a DSL and its host language — which is why variables and functions like yytext, yyparser, yyterminate, yylex, and so on exist. They look strange, but if you look at them with the heart of someone viewing a DSL, they stop feeling so awkward.

（二）

Alas, most of today’s hipster programmers no longer use C — though many languages offer an FFI (Foreign Function Interface) to C. In Python, for instance, you can generate a parser with flex/bison and wrap it via FFI. Still, that’s rather troublesome. If only I could build parsers in my favorite language — how convenient that would be!

Well, where there’s a need there’s a product. Take a look at this wiki page: https://en.wikipedia.org/wiki/Comparison_of_parser_generators.

Let me talk in detail about four interesting tools.

First, the Clojure marvel instaparse. instaparse is the kind of tool that, if you’re building a parser with no language constraints, you simply must try. What other tools take a day to produce, instaparse can nail in an hour. Let’s look at an example:

We want to parse forms that follow certain rules: form {...}. A form can have subforms; one rule per line; each rule is key=value [validator], where the validator is optional. For example, things wrapped in [] are choices, and things wrapped in () are ranges. From this form we can generate two kinds of data: a schema for the form, and the form’s data. So the key question is how to parse a suitable data structure out of the form data, in preparation for generating the schema and data.

As you can see in the image above, with instaparse we can define a lexer/parser in a mere 18 lines of code. instaparse supports EBNF/ABNF syntax, making it easy to hide unwanted nodes from the generated parse tree (note the <...> parts). Let’s look at the result:

Beautiful! Clojure’s ability to transform data is immensely powerful. A tree like this can be converted with ease into a DOM tree (hiccup), and from there into an HTML form…

With instaparse, writing a parser becomes three simple steps:

• Define the grammar using BNF
• Hide the unwanted syntax nodes
• Transform the generated syntax tree

instaparse’s power lies not only in its simple grammar, but also in the fact that you can debug your code with a REPL! Debug your code with a REPL! Debug your code with a REPL! When you’re using flex/bison, switching back and forth between make and your editor, gloomily hunting for grammar definition problems, you’ll understand just how important a REPL is!

Of course, among my readers, Clojure programmers are, by my estimate, rather rare, so the vast majority can only look at instaparse and drool.

Alright, next let’s talk about jison. As you’ve probably guessed, this thing is JavaScript’s bison, bison gone rogue in JavaScript. First, an example of parsing create table in SQL. We want to achieve an effect like this:

What we need is to transform the create table syntax into a data structure, through which we can conveniently generate an HTML table. Well, to achieve this you only need to write a jison grammar file (similar to flex/bison) and then compile it with jison:

Pretty simple, right? The parse tree I generate here is just a JavaScript object. Then I can take this object and further generate a table like the one shown above.

What’s the advantage of building parsers with JavaScript/jison? You can do complex input validation on the browser side; you can let users enter text that conforms to a grammar you define, and then generate what you want from it — a mind map, say, or something like this project: https://github.com/bramp/js-sequence-diagrams. If you want to define a language that compiles to JavaScript (which I don’t recommend), you can look at CoffeeScript, which also uses jison.

Next let’s talk about another marvel: antlr4. I only came into contact with antlr4 while writing this article, so I’m still in the first-flush-of-love phase. Aside from its distinctive parser design — LL(*) — antlr4 strikes me as powerful in three ways:

• A wealth of ready-made grammar definitions (almost all MIT/BSD licensed — bow down, kid!). Open this repo: https://github.com/antlr/grammars-v4 — do you feel like crying?
• It generates parsers in mainstream programming languages. You can easily generate Python, JavaScript, and other source code from a grammar file, then integrate it into your own project. Keep crying.
• SAX-like event driven. antlr4 generates the complex syntax tree for you directly — generally, the trees antlr4 produces aren’t as clean as those from instaparse/bison, so working with them directly is a bit painful. antlr4’s innovation is: I’ll build the tree for you first, then you can traverse it as you like. Like SAX handling XML, for each rule (analogous to each Node in XML) you can set an enter listener and an exit listener. You register callbacks on the nodes you care about, and antlr4 hands you the context to process.

Since antlr4 has grammar definitions for most languages, you can spend your energy on transformation rather than on defining grammars. For example, the boss says: “Xiao Ming, find me every function in our codebase that’s over 100 lines and has not a single comment — I want to look over these no-comment-writing bastards.”

This kind of nauseating request, which once seemed impossible, might now take just a day to nail:

• If the code is Python 3, find the Python 3 g4 file and use antlr4 to generate a lexer/parser.
• Listen to every def rule, count the effective lines of code inside (excluding blank lines) and the number of comments. If comments are zero and code lines exceed 100, record the function name, file name, and start/end line numbers. Then use git blame to find the author and generate a CSV file.
• Open the CSV in Excel, tidy the formatting a bit, notify every friend you recognize and everyone whose name looks like a Chinese name to add comments to their code ASAP, cross them off the list (heh heh), then compile a top-10 list of the worst offenders, with pie charts, bar charts, or whatever else you — the resident spreadsheet wizard — fancy.
• Send the Excel file to the boss.

Yes, bask in your colleagues’ blessings — and if someone offers to buy you dinner, don’t refuse, especially if it’s a girl (or a guy). :)

Alright, the last one: parsec. parsec is a marvel. A Haskell marvel I’ve never used but can’t resist running my mouth about. Haskell is a language that drives you to the brink of madness once you learn it. Look at Murong Fu, who practiced the “Shifting Stars” technique and went mad on the road to restoring his kingdom; look at Zhang Jiaozhu, who practiced the “Heaven and Earth Great Shift” and, on the road to revolution, couldn’t decide which beauty to choose and shamefully went into hiding — you can see that if your head is filled with composition, you will inevitably end up looking like a madman (great wisdom appearing as folly).

The parsers described above are actually all parser generators, and the code they generate is non-composable. You can’t write a SQL parser by first writing a parser for select, then a parser for create table, and composing the two into a parser that supports both. You simply can’t. But parsec can. In parsec, you start from very fine-grained parsers and compose them all the way up into a very complex one. Of course, parsec has already built many parsers for you; you just need to define a few new ones and compose them with the existing ones.

That’s what parsec means by “A monadic parser combinator.” God, monads again… Let’s set monads aside for now; I’ll cover them in a later article.

（三）

This article hasn’t told you about LALR(1), LL(1), LL(*), and other concepts; it hasn’t explained in detail the specific steps of a lexical parser or a grammar parser; and though it gave some examples of BNF (and its variants), it didn’t touch on how to write BNF. These things matter, but before you write a parser they’re all beside the point. What you need to know is that besides regular expressions, you have other tools for handling more complex formatted text. You should have gotten a sense of some possible use cases for parsers, and you’ve seen how some of the main tools are used, along with their pros and cons.

You don’t have to drop what you’re doing right now to learn these tools — one of the best ways to learn is learning by practising, not learning by reading a book (manual). The next time your boss gives you a text-processing task, just remember that besides regular expressions, you have other tools for handling more complex problems — that’s enough. Take the task, and trust that the power of the deadline will be enough to turn you from a rookie into a big rookie.