Parsing Expressions with C

There are various ways to parse and evaluate expressions. When working with a recursive downstream parser, you can think of expressions in the form of recursive data structures , i.e. definition of an expression is recursive. In other words, the concept of expression is defined through the concept of expression. For example, if we accept that only +, -, *, / and parentheses can be used in expressions, then all expressions can be defined by the following rules:

  expression -> addend [+ addend] [- addend]
 term -> factor [* factor] [/ factor]
 multiplier -> variable, number or (expression)

Square brackets mean an optional element, and the symbol -> means "spawns." Such rules are usually referred to as generative rules, or products . Therefore, the definition of a term is the following: "The term gives rise to a factor multiplied by a factor, or a factor divided by a factor." Notice that the priority of the operations is in the definition of the expression.

Let's take an example. The expression 10 + 5 * B consists of two terms: 10 and 5 * B. The second term consists of two factors: 5 and B. These factors are one number and one variable.

On the other hand, the expression 14 * (7 - C) contains two factors: 14 and (7 - C) . These factors are one number and one expression in brackets. The expression in brackets consists of two terms: a number and a variable.

The described process of analyzing expressions is the basis of the work of a recursive downstream parser, which essentially consists of a set of mutually recursive functions that call each other in a chain. At each stage of its work, the analyzer performs the specified operations in an algebraically correct sequence. To see how this happens, let's look at the expression below in accordance with the above generating rules and perform arithmetic operations:

  9/3 - (100 + 56) 

If the expression is parsed correctly, the parsing occurred in the following order:

1. Get the first term, 9/3.
2. Get each multiplier and divide numbers. The result is the number 3.
3. Get the second term, (100 + 56). At this point, the recursive processing of this subexpression begins.
4. Get both items and add. The result is the number 156.
5. Return from a recursive call and subtract 156 from 3. The final answer is -153.

If you are somewhat confused, do not worry. Parsing expressions is a rather complicated task to get used to. There are two main points to keep in mind when it comes to such a recursive representation of expressions. First, the priority of operations is implicitly laid down in the generating rules. Secondly, this method of parsing and calculating expressions is very similar to the way people compute mathematical expressions.