Recursive Descent Parser

A parser converts an expression based on a grammar to an object that can be executed as a computer program. When executed, the program produces output consistent with the defined result of the expression. A recursive descent parser produces a tree object for expressions derived from a recursive grammar. For example, the recursion sqrt(sqrt(x)) can be represented by the following tree:

tree1

Starting from the top, we find a square root function at the root node. The argument to this node is found in its child node, which happens to be another square root function. We must descend further to find a primitive value we can evaluate. Looking at the child of this second node, we find a primitive (x). Now we can evaluate the square root of x and pass the result up the tree to be evaluated by the first node.

The method of recursive descent based on walking through a tree is especially powerful for evaluating algebraic expressions because expressions can be infinitely nested (as far as we have the resources to encode and walk the tree). The following example shows how the algebraic expression a*(b+c) is encoded.

tree2

We walk this tree the same as before, stopping when we hit primitives (a, b, or c) and passing upwards the result of the function (operator) evaluations on them. When we reach the root node, the evaluation contains the result of our expression. This process of walking is consistent with a depth-first-search of the expression tree.

An expression tree encapsulates a recursive grammar. Accordingly, it is useful not only for translating a symbolic expression based on that grammar into computer code based on that grammar but also for translating between any two symbolic representations of that grammar. For example, we can use the same expression tree to translate the expression a*(b+c) into "a times the sum of b and c" or "times(a,plus(b,c))" and so on. To do so, we output text corresponding to the operators and arguments in the tree instead of executing them.

The applet above illustrates this translation principle for several different languages. This version of Parser is set to accept three variables in the form of an algebraic equation z = f(x, y). The default setting shows the function z = sin(x) + cos(y*x) as an assignment statement in C. You may change the language parsed by selecting one of the radio buttons at the top of the display. A subset of operators available in the selected language are displayed at the right (actually, all the operators of C and Java are available). This applet does not issue syntax error messages. If the expression you enter is invalid, the display will not change. Try correcting the expression and pressing the Enter key again. The graph is scaled on the interval (-1, 1) for both x and y, so you need to keep this in mind when entering expressions.

At the bottom of the panel I have included the translation of the input expression to MathML. You can learn more about this language at www.w3.org. MathML is an XML specification that allows us to encode, execute, and typeset symbolic math expressions.