Parsing Expressions: The Problem


If you haven’t thought much about the problem of expression parsing, you might assume that it is a simple task, but it isn’t. To better understand the problem, try to evaluate this sample expression:

 10  2 * 3

You know that this expression is equal to the value 4. Although you could easily create a program that would compute that specific expression, the question is how to create a program that gives the correct answer for any arbitrary expression. At first you might think of a routine something like this:

 a = get first operand while(operands present) {  op = get operator  b = get second operand  a = a op b }

This routine gets the first operand, the operator, and the second operand to perform the first operation; then it gets the next operator and operand to perform the next operation; and so on. However, if you use this basic approach, the expression 10 2 * 3 evaluates to 24 (that is, 8 * 3) instead of 4, because this procedure neglects the precedence of the operators. You cannot just evaluate the operands and operators in order from left to right because the rules of algebra dictate that multiplication must be done before subtraction. Moreover, the problem only gets worse when you add parentheses, exponentiation, variables, unary operators, and the like.

There are a number of ways to write a parser that evaluates numeric expressions. The one developed here is called a recursive-descent parser, and in the course of this chapter you will see how it got its name.




C# 2.0(c) The Complete Reference
C# 2.0: The Complete Reference (Complete Reference Series)
ISBN: 0072262095
EAN: 2147483647
Year: 2006
Pages: 300

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net