Question:

_{(This question is mostly for people who have read the tutorial by Jack Crenshaw, but since it's a well known tutorial I think it's an appropriate question).}

I'm currently reading the great series "Let's Build A Compiler', by Jack Crenshaw.

I'm learning a lot and enjoying it very much. However I ran into something in the tutorial that doesn't make sense to me.

When learning how to evaluate a boolean expression, the following 'formula' for how a boolean epxression is composed is given:

<b-expression> ::= <b-term> [<orop> <b-term>]* <b-term> ::= <not-factor> [AND <not-factor>]* <not-factor> ::= [NOT] <b-factor> <b-factor> ::= <b-literal> | <b-variable> | <relation> <relation> ::= | <expression> [<relop> <expression] <expression> ::= <term> [<addop> <term>]* <term> ::= <signed factor> [<mulop> factor]* <signed factor>::= [<addop>] <factor> <factor> ::= <integer> | <variable> | (<b-expression>)

To implement this, while parsing a boolean expression, the boolExpression function calls the boolTerm function, which calls the notFactor function, etc... Each function saves it's value (1 or 0) onto a register or stack, eventually coming back to boolExpression.

By the time we're back at boolExpression, the register D0 holds the final value of the expression: 1 or 0.

As far as I understand, <em>after</em> getting the result of the expression (which is stored in the register D0), the flags need to be set accordingly (i.e. TST D0 - it sets the flags of the CPU to signify information about the value in D0).

This is so control structures such as if can check these flags to decide what to do - obviously after the boolean expression was evaluated.

However, for some reason the tutorial puts the TST D0 part, at the end of the relation function, instead of at the end of the boolExpression function - which is where I'd expect it to be.

I just can't figure out why.

boolExpression than shows several times in the book, never with TST D0 in the end, so I know it wasn't a typo or confusion.

I would think TST D0 needs to appear at the end of boolExpression, after we've returned from all the functions and we have the boolean value of the expression in D0. However the author put this inside relation, which is a function that may or may not be called sometimes in the middle of the chain, before knowing the final value of D0.

Can someone explain this to me? Why should the setting of the flags, i.e. TST D0 be inside the relation function? Why not in boolExpression?

Crenshaw himself explains it here (emphasis mine):

<blockquote>

Now, recall that we're using a zero or a -1 in register D0 to represent a Boolean value, and also that the loop constructs expect the flags to be set to correspond. In implementing all this on the 68000, things get a a little bit tricky. Since the loop constructs operate only on the flags, it would be nice (and also quite efficient) just to set up those flags, and not load anything into D0 at all. This would be fine for the loops and branches, but remember that the relation can be used ANYWHERE a Boolean factor could be used. We may be storing its result to a Boolean variable. Since we can't know at this point how the result is going to be used, we must allow for BOTH cases. Comparing numeric data is easy enough ... the 68000 has an operation for that ... but it sets the flags, not a value. What's more, the flags will always be set the same (zero if equal, etc.), while we need the zero flag set differently for the each of the different relops. The solution is found in the 68000 instruction Scc, which sets a byte value to 0000 or FFFF (funny how that works!) depending upon the result of the specified condition. If we make the destination byte to be D0, we get the Boolean value needed. <strong>Unfortunately, there's one final complication: unlike almost every other instruction in the 68000 set, Scc does NOT reset the condition flags to match the data being stored. So we have to do one last step, which is to test D0 and set the flags to match it.</strong> It must seem to be a trip around the moon to get what we want: we first perform the test, then test the flags to set data into D0, then test D0 to set the flags again. It is sort of roundabout, but it's the most straightforward way to get the flags right, and after all it's only a couple of instructions.

</blockquote>

(excerpt from <a href="http://www.epubbud.com/read.php?g=45SM7QEG&tocp=44" rel="nofollow">here</a>)