Chapter 27: A Recursive-Descent Expression Parser

Overview

How do you write a program that will take as input a string containing a numeric expression, such as (10 − 5) * 3, and compute the proper answer? If there is still a “high priesthood” among programmers, it must be those few who know how to do this. Many otherwise accomplished programmers are mystified by the way a high-level language converts algebraic expressions into instructions that a computer can execute. This procedure is called expression parsing, and it is the backbone of all language compilers and interpreters, spreadsheets, and anything else that needs to convert numeric expressions into a form that the computer can use.

Although mysterious to the uninitiated, expression parsing is a well-defined task for which there is a rather elegant solution. This is because expression parsing works according to the strict rules of algebra. This chapter develops what is commonly referred to as a recursive-descent parser and all the necessary support routines that enable you to evaluate numeric expressions. Once you have mastered the operation of the parser, you can easily enhance and modify it to suit your needs.

Aside from being a useful piece of code in itself, the parser developed here also serves a second purpose: It illustrates the power and range of the C# language. A parser is a “pure code” application. It doesn’t interface to the network, use a GUI, or make use of limited system resources. It is the type of code that in the past would normally have been written in C++. The fact that a parser can be easily created using C# shows that C# is suitable for nearly any programming task.