44185

Regarding “Let's Build A Compiler”, by Jack Crenshaw

Question:

<sub>(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).</sub>

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?

Answer1:

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>)

Recommend

  • “ORDER BY” in subquery - not avaliable in MonetDB?
  • Circle shape clipping with opengl-es in cocos2d
  • How to load shared libraries symbols for remote source level debugging with gdb and gdbserver?
  • Exit from a loop that contains time delay immediately after a key is pressed
  • Update web.config file in asp.net
  • Using bitbake is it possible to have a different do_install for a package based on the target image?
  • How would I send and receive packets over a WebSocket in Javascript
  • removing the default blue color on focus
  • Can I use worksheet_change for a specific column only?
  • NSMutableArray Access Issue
  • Timing loops with asynchronous functions
  • How do I add a File Type Association in a Windows Phone 8.1 app manifest?
  • Where these are stored?
  • In C what exactly happens if i use () to initialize a double dimension array instead of the {}?
  • Is it possible to define rest argument in OCaml?
  • How to make R's read_csv2() recognise the text characters properly
  • IE11 throwing “SCRIPT1014: invalid character” where all other browsers work
  • Convert Type Decimal to Hex (string) in .NET 3.5
  • presentShareDialogWithParams posts to FB wall, but callback handler results say error
  • Display images in Django
  • java inputstream
  • Problem deserializing objects from cache on MyBatis 3/Java
  • Installing Apache MyFaces 2 on WildFly 8.2.0
  • how to adjust image in a panel in Java swing?
  • Using jQuery closest() method with class selector
  • Array.prototype.includes - not transformed with babel
  • Possible to stop flickering java tooltip in heavyweight mode?
  • DirectX11 ClearRenderTargetViewback with transparent buffer?
  • Does CUDA 5 support STL or THRUST inside the device code?
  • Numpy divide by zero. Why?
  • Why can't I rebase on to an ancestor of source changesets if on a different branch?
  • JTable with a ScrollPane misbehaving
  • Can Visual Studio XAML designer handle font family names with spaces as a resource?
  • How can I remove ASP.NET Designer.cs files?
  • Are Kotlin's Float, Int etc optimised to built-in types in the JVM? [duplicate]
  • Binding checkboxes to object values in AngularJs
  • Converting MP3 duration time
  • Net Present Value in Excel for Grouped Recurring CF
  • jQuery Masonry / Isotope and fluid images: Momentary overlap on window resize
  • How to load view controller without button in storyboard?