Operator precedence (addition, multiplication, etc.)
In the next step in addition to + and - we also support * (multiplication), / (division) and multiplication. Precedence is done the right way ...
Video tutorial
Lexical elements
The lexer now can generate three more operators (for multiplication, division and modulo). Besides that nothing changed:
-
Decimal constants are described by the regular expression 0|[1-9][0-9]*
-
The characters '+', '-', '*', '/' and '%' are operators.
Tokens end if the next character is a space or if the next character cannot be added to it.
Here the tokens generated for the character sequence “0123+-*/%”:
theon$ echo "0123+-*/%" | ulmcalc-step2-lexer DECIMAL_CONSTANT "0" at stdin:1.1 DECIMAL_CONSTANT "123" at stdin:1.2-4 PLUS at stdin:1.5 MINUS at stdin:1.6 ASTERISK at stdin:1.7 SLASH at stdin:1.8 PERCENT at stdin:1.9 theon$
Again, note that “0123” generated the decimal constants 0 and 123.
Grammar
\[\begin{array}{lcl}\langle\text{expression}\rangle & \to & \langle\text{exp}\rangle \\ \langle\text{exp}\rangle & \to & \langle\text{term}\rangle \\ & \to & \langle\text{exp}\rangle \quad \text{'+'} \quad \langle\text{term}\rangle \\ & \to & \langle\text{exp}\rangle \quad \text{'-'} \quad \langle\text{term}\rangle \\ \langle\text{term}\rangle & \to & \langle\text{factor}\rangle \\ & \to & \langle\text{term}\rangle \quad\text{'*'}\quad \langle\text{factor}\rangle \\ & \to & \langle\text{term}\rangle \quad\text{'/'}\quad \langle\text{factor}\rangle \\ & \to & \langle\text{term}\rangle \quad\text{'%'}\quad \langle\text{factor}\rangle \\ \langle\text{factor}\rangle & \to & \langle\text{primary}\rangle \\ & \to & \langle\text{unary-minus}\rangle \\ \langle\text{unary-minus}\rangle & \to & \text{'-'} \quad \langle\text{primary}\rangle \\ \langle\text{pimary}\rangle & \to & \langle\text{integer}\rangle \\ & \to & \text{'('} \quad \langle\text{exp}\rangle \quad \text{')'}\\ \langle\text{integer}\rangle & \to & \text{decimal-constant} \\ \end{array}\]Evaluation of the expression
Like in the previous “step1” version the value of a node get computed by traversing the tree and applying the following rules “on the way back” (i.e. after a node was visited):
-
If a node had just a child then take its value.
-
If a node was an operation node apply the operation to its two child nodes.
How our calculator does integer division
Note that we are doing integer arithmetic here. This becomes vivid when we do the division. Our calculator does division by rounding towards \(-\infty\). That means here
\[a \,/\, b:= \left\lfloor \frac{a}{b} \right\rfloor:= \text{max}\left\{ k \in \mathbb{Z}\,:\, k \leq \frac{a}{b} \right\}.\]So it is not surprising that “5 divided by 2 gives 2” because
\[5 \,/\, 2 := \left\lfloor \frac{5}{2} \right\rfloor = \left\lfloor 2.5 \right\rfloor = 2\]However, you should be aware that this means “-5 divided by 2 gives -3” because
\[-5 \,/\, 2 := \left\lfloor \frac{-5}{2} \right\rfloor = \left\lfloor -2.5 \right\rfloor = -3\]How integer division is done in C
Starting with the C99 standard integer division gets rounded towards zero. That means
\[a \,/\, b :=\left\{\begin{array}{ll} \left\lfloor \frac{a}{b} \right\rfloor, & \frac{a}{b} \geq 0, \\[0.2cm] \left\lceil \frac{a}{b} \right\rceil, & \frac{a}{b} < 0 \\\end{array}\right.\]with \(\lfloor \cdot \rfloor\) defined as above and
\[\left\lceil \frac{a}{b} \right\rceil:= \text{min}\left\{ k \in \mathbb{Z}\,:\, k \geq \frac{a}{b} \right\}.\]And that means:
-
“5 divided by 2 gives 2” and
-
“-5 divided by 2 gives -2”.
Before C99 the rounding could be depending on the hardware towards zero or towards \(-\infty\).
Example 2+3*4
The expression
get evaluated as
theon$ ulmcalc-step2.ast example2 14 theon$
Syntax tree
On the command line we can view the syntax tree of the expression as follows
theon$ ulmcalc-step2-jstree.ast -o tree-example2.html tree-example2 example2 theon$
For getting a nice SVG we can use ulmcalc-step2-jstree.ast
theon$ ulmcalc-step2-jstree.ast -o tree-example2.html tree-example2 example2 theon$
and get
Example (2+3)*4
Now we use parenthesis so that the addition should be evaluated first:
1 | (2+3)*4
|
This obviously works:
theon$ ulmcalc-step2.ast example3 20 theon$
Syntax tree
Looking at the syntax tree we see the difference caused by using the parenthesis:
Example (5+-2)/2
Here an expression that has a unary minus and a division
1 | (5+-2)/2
|
Note that we are doing integer arithmetic here:
theon$ ulmcalc-step2.ast example4 1 theon$
Syntax tree
Looking at the syntax tree we see the difference caused by using the parenthesis:
Example ((20+3*2) % (3+ -1) + 5) / 2
Just for fun we look at an expression that uses all supported operations
1 | ((20+3*2) % (2+2) + 5) / 2
|
which gives
theon$ ulmcalc-step2.ast example5 3 theon$
Syntax tree
Looking at the syntax tree we see the difference caused by using the parenthesis:
And if you are interested...
... here the changes in the lexer, parser and code generator:
-
scanner.cpp in /home/numerik/pub/ulm-calc/astl-calc-step2/,
-
parser.ypp in /home/numerik/pub/ulm-calc/astl-calc-step2/ and
-
eval_step2.ast in /home/numerik/pub/ulm-calc/lib/.