==================================================== Operator precedence (addition, multiplication, etc.) [TOC] ==================================================== In the next step in addition to `+` and `-` we also support `*` (multiplication), `/` (division) and multiplication. Precedence is done _the right way_ ... Video tutorial ============== ---- VIDEO ------------------------------ https://www.youtube.com/embed/iWIxTSV8jNo ----------------------------------------- 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+-*/%": ---- SHELL(path=session07/ulm-calc/scripts) ------------------------------------- echo "0123+-*/%" | ulmcalc-step2-lexer -------------------------------------------------------------------------------- Again, note that "0123" generated the decimal constants 0 and 123. Grammar ======= ---- LATEX --------------------------------------------------------------------- \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 ---- LATEX --------------------------------------------------------------------- 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 ---- LATEX --------------------------------------------------------------------- 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 ---- LATEX --------------------------------------------------------------------- -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 ---- LATEX --------------------------------------------------------------------- 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 ---- LATEX --------------------------------------------------------------------- \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 ---- CODE(file=session07/ulm-calc/scripts/example2) ---------------------------- 2+3*4 -------------------------------------------------------------------------------- get evaluated as ---- SHELL(path=session07/ulm-calc/scripts) ------------------------------------- ulmcalc-step2.ast example2 -------------------------------------------------------------------------------- Syntax tree ----------- On the command line we can view the syntax tree of the expression as follows ---- SHELL(path=session07/ulm-calc/scripts) ------------------------------------- ulmcalc-step2-jstree.ast -o tree-example2.html tree-example2 example2 -------------------------------------------------------------------------------- For getting a nice SVG we can use `ulmcalc-step2-jstree.ast` ---- SHELL(path=session07/ulm-calc/scripts) ------------------------------------- ulmcalc-step2-jstree.ast -o tree-example2.html tree-example2 example2 -------------------------------------------------------------------------------- and get ---- RAW ------------------------------------ session07/ulm-calc/scripts/tree-example2.html --------------------------------------------- Example `(2+3)*4` ================= Now we use parenthesis so that the addition should be evaluated first: ---- CODE(file=session07/ulm-calc/scripts/example3) ---------------------------- (2+3)*4 -------------------------------------------------------------------------------- This obviously works: ---- SHELL(path=session07/ulm-calc/scripts) ------------------------------------- ulmcalc-step2.ast example3 -------------------------------------------------------------------------------- Syntax tree ----------- Looking at the syntax tree we see the difference caused by using the parenthesis: ---- SHELL(path=session07/ulm-calc/scripts,hide) ------------------------------- ulmcalc-step2-jstree.ast -o tree-example3.html tree-example3 example3 -------------------------------------------------------------------------------- ---- RAW ------------------------------------ session07/ulm-calc/scripts/tree-example3.html --------------------------------------------- Example `(5+-2)/2` ================== Here an expression that has a unary minus and a division ---- CODE(file=session07/ulm-calc/scripts/example4) ---------------------------- (5+-2)/2 -------------------------------------------------------------------------------- Note that we are doing integer arithmetic here: ---- SHELL(path=session07/ulm-calc/scripts) ------------------------------------- ulmcalc-step2.ast example4 -------------------------------------------------------------------------------- Syntax tree ----------- Looking at the syntax tree we see the difference caused by using the parenthesis: ---- SHELL(path=session07/ulm-calc/scripts,hide) ------------------------------------- ulmcalc-step2-jstree.ast -o tree-example4.html tree-example4 example4 -------------------------------------------------------------------------------- ---- RAW ------------------------------------ session07/ulm-calc/scripts/tree-example4.html --------------------------------------------- Example `((20+3*2) % (3+ -1) + 5) / 2` ====================================== Just for fun we look at an expression that uses all supported operations ---- CODE(file=session07/ulm-calc/scripts/example5) ---------------------------- ((20+3*2) % (2+2) + 5) / 2 -------------------------------------------------------------------------------- which gives ---- SHELL(path=session07/ulm-calc/scripts) ------------------------------------- ulmcalc-step2.ast example5 -------------------------------------------------------------------------------- Syntax tree ----------- Looking at the syntax tree we see the difference caused by using the parenthesis: ---- SHELL(path=session07/ulm-calc/scripts,hide) ------------------------------------- ulmcalc-step2-jstree.ast -o tree-example5.html tree-example5 example5 -------------------------------------------------------------------------------- ---- RAW ------------------------------------ session07/ulm-calc/scripts/tree-example5.html --------------------------------------------- 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/`. :links: scanner.cpp -> file:session07/ulm-calc/astl-calc-step2/scanner.cpp parser.ypp -> file:session07/ulm-calc/astl-calc-step2/parser.ypp eval_step2.ast -> file:session07/ulm-calc/lib/eval_step2.ast :navigate: up -> doc:index back -> doc:session07/page02 next -> doc:session07/page04