6. Multiplication

With the ease with which we eased us through addition, one could be lead to believe that multiplication was equally easy. After all, multiplication is almost the same as addition, a number on each side of an operator (4*5) and a cpu instruction to calculate the result. But not so fast. The difficulty arises when multiplication and addition are combined.
Compute 5+5*3. No, it's not 30, it's 20. That's the difficult part: multiplication must be done before addition. A general term for this is operator precedence. Multiplication has a higher precedence than addition, so it must be computed first. Thus, 5+5*3 is equal to 5+(5*3) rather than (5+5)*3.

Let's try to write a BNF for this, so that we have some guidance when implementing it. Here is our old BNF (for addition only)

addexp     ::= <value> {+ <value>}
expression ::= <addexp>

Here it is with support for multiplication:

mulexp     ::= <value> {* <value>}
addexp     ::= <mulexp> {+ <mulexp> }
expression ::= <addexp>

This may be seem strange. Why does it work? Let's look at 1+5*3. First expression calls addexp. Then addexp calls mulexp. And mulexp calls value, which loads 1 into eax. Control is returned to mulexp, which sees that Look is not *. Control is returned to addexp, which sees the + sign and pushes eax.
Everything is working normally so far (except that we did an unnecessary roundtrip through mulexp). Now comes the clever part. We are still in addexp, and 1 is pushed on the stack. Instead of calling value directly to get the next number, addexp calls mulexp, which in turn calls value to get the 5 into eax.
Now mulexp sees a *, so it pushes the 5 onto the stack, calls value again to get 3 in eax, and multiplies eax with the 5. So we now have the result of 3*5 in eax and 1 on the stack. (mulexp popped the 5 when multiplying.)
Finally we return addexp again, which adds the 1 from the stack to eax (15), to get the final result, 16.

The bottom line is: we multiplied before adding. You should read the description above again while looking at the actual code. If you need to, use the debugger to single-step through the code with the description above as an assistance to see what's going on.

The actual code is straightforward. AddExp() is modified to call MulExp() instead of Value().
MulExp() is written like the old AddExp(), but checks for the multiplication operator (*) instead of the addition operator (+) and, of course, issues an imul cpu instruction instead of an add instruction.

I recommend that you look here: http://flatassembler.net/docs.php?article=manual to get a description of all x86 assembly instructions. You can also download the same file as a pdf file.

In case you were wondering why we are using imul instead of just mul, it's because imul is for signed multiplication while mul is for unsigned for multiplication.

; mul.pb
IncludeFile "..\base2.pb"

Procedure Value()
  ; value  ::= <integer>
  Emit("mov  eax, " + GetInteger())
EndProcedure

Procedure MulExp()
  ; mulexp     ::= <value> {* <value>}
  Value()
  While Look = '*'
    GetLookWhite()
    Emit("push eax")
    Value()
    Emit("pop  ecx")
    Emit("imul eax, ecx")
  Wend
EndProcedure

Procedure AddExp()
  ; addexp     ::= <mulexp> {+ <mulexp> }
  MulExp()
  While Look = '+'
    GetLookWhite()
    Emit("push eax")
    MulExp()
    Emit("pop  ecx")
    Emit("add  eax, ecx")
  Wend
EndProcedure

Procedure Expression()
  ; expression ::= <AddExp>
  AddExp()
  
  If Look <> 0
    Expected("End of line")
  EndIf
EndProcedure

Init()
Expression()
Input()

Try to run it. Test it with some expressions and see if the generated code is correct (see the end of the tutorial "addition" for a how-to). Run it with single-stepping (see the PB help file about the debugger) to understand what's really going on in there.

If the program above works, and you understand why/how it works, then you have just completed the hardest part of writing a compiler.;
Once you grasp BNF and parsing you can do almost anything you want to (except generate efficient code, which is a problem all by itself). Mind you, there's a lot of work left, but when you understand this program you have passed a hurdle that enables you to learn the more advanced stuff. It's like creating a new space in your mind. Sort of being born. It doesn't automatically make you a great programmer, but it's the biggest hurdle.

Oups. I likened mastering multiplication to being born. What an unsuitable pun...

I repeat: You have just completed the hardest part of writing a compiler.