Making Languages

Introduction

Edit:

It’s been pointed out to me that making languages and making compilers aren’t technically the same thing, and using these words interchangeably can lead to confusion. I can’t (at this point) rename the collection, posts and links to “Making Compilers” because it would break loads of links; but that’s what this is really about. Making compilers.

I write PHP code every day. For as long as I can remember, there have been things in the language which I don’t like. Things I miss from other languages. Things I wish could be more strict or loose. Yet the ecosystem and community surrounding PHP are rich and inviting.

The idea of being able to create or change programming languages is fascinating to me. I have spent many hours trying to build my own compilers and thinking about my ideal programming language.

A Little Knowledge…

I am not educated in programming. Like many before me; I often find academic videos and papers beyond my grasp. The alternative, it seems, is a series of unhelpful tutorials for using other tools to generate a compiler for me.

What I want is to understand the essence of a compiler, without getting lost in tooling or indirection. I had to learn some basics, in preparation for speaking at a conference. They follow a similar structure to a template parser I wrote in Pro PHP MVC (Apress 2012). So I will begin with the concepts outlined in the talk, and see where things go from there.

Most of the code examples will be PHP. That doesn’t mean this stuff can only be done in PHP, and many of the algorithms have been ported from Ruby and C++. You might not like PHP, but I don’t care.

Topics

• Grammar
• Tokens
• Parse Trees
• Abstract Syntax Trees
• Interpretation
• Compilation
• Bonus: Safe
• Limitations
• Doctrine Common
• Recursive Decent Parsing Algorithm
• Recursive Decent Parsing Algorithm Limitations
• Deterministic Finite Automata
• Nondeterministic Finite Automata
• Finite Automata Limitations
• Deterministic Pushdown Automata
• Nondeterministic Pushdown Automata
• Converting Nondeterministic Automata to Deterministic Automata
• Pushdown Automata Parsing Algorithm
• Recki-CT
• …

Support

Writing this kind of stuff takes loads of time, but I would love to produce it all for free. If you enjoy reading it, and find it useful, please consider making a donation so it’s easier to keep writing.

I would also like to thank Joe Watkins, Anthony Ferrara, David Mosher, Alex Dover and Eric L. Barnes for their insightful feedback!