Writing compilers

Jeremy jeremy at itassist.net.au
Tue Nov 20 16:06:51 EST 2001


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

I am writing for a stack based machine, so it will be fine.  I just wanted
to know what the fuss was about.  I've been burnt a couple of times by
doing things sub optimally because I couldn't be bothered learning the
proper technique.


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

On order.


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

That's what I'm doing at the moment, and it works fine.  The trouble is
that adding advanced features becomes very difficult, since it's harder to
keep track of context using a plain parser.


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

I'm not sure how to do lookahead in a recursive descent parser.  I can do
lookbehind, but that isn't quite the same thing.


> 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

I see.  So the parse tree would have a 'link' where you write 'expr' and
then I would dive down the parse tree till I find a node with no links then
work back up... cool.


 
> 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've been cheating and using a 'running total' register.  This is
definately inefficient but I hear there are good optimisers for assembler
thesedays.
--------------------------------------
I fought Muhammed Ali,
I seduced Mata Hari,
I even wore a sari when I impersonated Ghandi,
and I dare any man here to call me a liar....




More information about the linux mailing list