Now let's get down to some really serious business. As you all know, there are other math operators than “addops” … expressions can also have multiply and divide operations. You also know that there is an implied operator precedence, or hierarchy, associated with expressions, so that in an expression like
2 + 3 * 4
we know that we're supposed to multiply first, then add. (See why we needed the stack?)
In the early days of compiler technology, people used some rather complex techniques to insure that the operator precedence rules were obeyed. It turns out, though, that none of this is necessary … the rules can be accommodated quite nicely by our top-down parsing technique. Up till now, the only form that we've considered for a term is that of a single decimal digit.
More generally, we can define a term as a product of factors; i.e.,
<term> ::= <factor> [ <mulop> <factor ]* |
What is a factor? For now, it's what a term used to be … a single digit.
Notice the symmetry: a term has the same form as an expression. As a matter of fact, we can add to our parser with a little judicious copying and renaming. But to avoid confusion, the listing below is the complete set of parsing routines. (Note the way we handle the reversal of operands in Divide.)
{ Parse and Translate a Math Factor } procedure Factor; begin EmitLn('MOVE #' + GetNum + ',D0') end; { Recognize and Translate a Multiply } procedure Multiply; begin Match('*'); Factor; EmitLn('MULS (SP)+,D0'); end; { Recognize and Translate a Divide } procedure Divide; begin Match('/'); Factor; EmitLn('MOVE (SP)+,D1'); EmitLn('DIVS D1,D0'); end; { Parse and Translate a Math Term } procedure Term; begin Factor; while Look in ['*', '/'] do begin EmitLn('MOVE D0,-(SP)'); case Look of '*': Multiply; '/': Divide; else Expected('Mulop'); end; end; end; { Recognize and Translate an Add } procedure Add; begin Match('+'); Term; EmitLn('ADD (SP)+,D0'); end; { Recognize and Translate a Subtract } procedure Subtract; begin Match('-'); Term; EmitLn('SUB (SP)+,D0'); EmitLn('NEG D0'); end; { Parse and Translate an Expression } procedure Expression; begin Term; while Look in ['+', '-'] do begin EmitLn('MOVE D0,-(SP)'); case Look of '+': Add; '-': Subtract; else Expected('Addop'); end; end; end; |
Hot dog! A nearly functional parser/translator, in only 55 lines of Pascal! The output is starting to look really useful, if you continue to overlook the inefficiency, which I hope you will. Remember, we're not trying to produce tight code here.