ert the input string into an arithmetic tree. The simple grammar accepted by the parser is defined as follows.
The parser is looking for an expression:
An expression is a term followed by a plus or a minus sign, which is followed by another expression. If an expression doesn't contain any plus or minus signs, it's equal to a term.
A term is a factor multiplied or divided by another term. If a term doesn't contain any multiplication or division operators, it's equal to a factor.
A factor can be any of the following:
An identifier corresponding to a variable
A minus sign followed by a factor (unary minus)
A whole expression enclosed in parentheses
For instance, the expression 1 + x * (2 - y) is parsed as shown in Figure 1.
Figure 1 The parsing of an arithmetic expression. The arrows with numbers correspond to the rules of grammar that are used to make each parsing step.
This grammar is simple and natural, but it has one flawthe arithmetic operators are right-associative instead of being left-associative. That means, for example, that a - b + c will be parsed as a - (b + c), which is not exactly what we'd expect. There are standard ways of fixing this grammar or modifying the parser, but that's beyond the scope of this section. (We'll revisit this issue later.)
Since we want our calculator to be able to use variables, we need a symbol table. A symbol table remembers names of variables. We'll also need to be able to assign values to variables. We can do it by expanding the definition of expression to include the following clause:
An expression can also be a term followed by the equal sign followed by another expression.
Not every term is appropriate on the left side of an assignment. It has to be an lvalue something that can be on the left side of an assignment. In our case, the only allowed type of lvalue will be an identifier corresponding to a variable. Similarly, anything that can be put on the right side of the assignment is called an rvalue. In our case, any expression is a valid rvalue.
You can also derive lvalue from "location value," since it represents a location where a value can be stored, and rvalue from "read value," since a value can be read from it.
We'll also introduce a scanner, which will convert the input string into a series of tokens. It will recognize arithmetic operators, numbers, and identifiers. This way, the parser will have an easier jobmatching sequences of tokens to grammatical productions.