Home |

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

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.

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.