Evaluating Expressions

In Computer Science, the Art of Compiler writing is still considered somewhat of a Black Art; known only to the masters. Cryptic texts, enormous amounts of theory, more acronyms and notations than anyone should have to know are all barriers to entry in learning the basics of even implementing a simple language. Over the years, I€ve read just about every compiler book I could get my hands on and in each case I found myself somewhat surprised by the amount of assumed knowledge the reader was supposed to already have under their belt. Now, don€t get me wrong, there are plenty of great authors and educators on the topic of Compiler design, and I€ve learned a tremendous amount in reading their works. Still, I personally feel there is a gap; a step 1 if you will, somewhere between basic parsing and full-blown Compiler design. It is this gap I hope to fill in the pages that follow.

In order to provide a better understanding of what this book is about, let me first start by stating what this book is not about. This book is not an exploration of parsing techniques and error recover, formal language grammars, optimized code generation, or even efficient data structures. No, this book is about the basics; the core ideas required for parsing and interpreting a language. We€ll use a language we are all familiar with €“ Math Expressions €“ a language that we have a common understanding of what the basic symbols mean and the order of operations are. To me, this eliminates having to learn the rules of a toy language first and then having to work out the strategy to implement said toy language. Additionally, we€ll only be working with a small sub-set of the language, basic operators such as addition and subtraction, multiplication and division, grouping operators, negation, factorial and exponents. From there we€ll move on to variables and functions. Once we€ve got the basics covered, we€ll create a very simple math orientied language which allows for variable and function definitions, evaluation and printing out the results.

I chose math expressions due to the sheer number of user posts on various public forums asking the very question: €˜How do I evaluate a user supplied math expression?€ This question arises so frequently and so often with so many different answers and implementations, I decided to write this book as an attempt to hopefully ignite the spark in you to want to learn more about the subject of Compiler and Interpreter construction.

Lastly, I want to point out that there are a number of ways in which to implement an evaluator for math expressions. These approaches range from Reverse Polish Notation (RPN) stack based evaluators or the Shunting-yard algorithm by Edsger Dikjstra, all the way to byte code generation and executed via virtual machines. In the end, your solution should be driven by the requirements, and not the other way around.