Writing compilers

[Martijn van Oosterhout]

On Tue, Nov 20, 2001 at 12:58:49AM +1100, jeremy at itassist.net.au wrote:
> x = 1 + ( 2 * 3 )...
> 
> becomes
> set I1, 1
> push I1
> set I1, 2
> mult I1, 3
> pop I2
> add I1, I2
> ...

That's not an entirely bad peice of code. If you machine was stack based it
would be completely trivial. With registers I think you simply treat the
registers as the top elements of the stack.

I'm not quite sure, I've never really written a compiler for a non-stack
based machine.

> In short, I don't get this 'shift and reduce' thing at all.  Could
> someone explain if I have to use it if I have a recursive descent parser
> (the notes I came across implied that I do, but I think I can do it
> using look-ahead).  If I do have to use it, what is it?  I've seen a run
> through of it, but it just didn't click.  I get the 'shift' bit - keep
> pushing operations(or should that be states?) onto a stack, but what's
> the go with taking them back off?  And how does it magically turn into a
> useful parse tree?

Maybe you should get the lex and yacc book that o'reilly sells. The basic
idea is that shifting means you deal with it later, reduce means you
complete a rule.

Also, depending on how your code works, the parse tree may not ever exist in
it's entirety. It's possible to go straight from source to code without
building the tree.

Say you had no parenthesis and you'd just gotten to the '*' (yes, you really
need lookahead. one token lookahead is sufficient for most grammers). Your
parsing stack would contain 1 + 2.  If you decide that the '*' has a higher
precedence, you shift it leading to:

1 + 2 * 3  ==>  1 + expr  ==>  expr

On the other had, if you decide that '+' has higher precedence, you reduce,
leading to:

1 + 2 * 3  ==>  expr * 3  ==>  expr

Now, as for how to generate code, that's very easy for stack based. With
each expression you store the instructions to calculate it. Then, to get the
instructions for A + B, you simply concatenate the instructions for A and B
and then execute the '+'. Done.

Ofcourse, real machines have registers meaning you have to allocate them and
make sure you don't use a register that's being used elsewhere...

I'm sure are books that can explain this better.

> While I'm at it, what is a handle plus sentential form?  Is this like
> subject+predicate in english grammar?

No idea.

HTH,
-- 
Martijn van Oosterhout <kleptog at svana.org>
http://svana.org/kleptog/
> Magnetism, electricity and motion are like a three-for-two special offer:
> if you have two of them, the third one comes free.