Writing compilers

[Martijn van Oosterhout]

On Tue, Nov 20, 2001 at 05:06:51AM +0000, Jeremy wrote:
> > 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.

You may want to look at parser generators like ANTLR. It takes a yacc like
description but produces a recursive descent parser. It basically has two
functions, one named check() whcih tries to match the next token but doesn't
eat (shift) it and match() which will match a token and shift it.

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

It's a bit tricky since your definition for an expression can be any of:

integer
expr '+' expr
expr '*' expr

And it's only the precedence rules that remove the ambiguity.

Note that you can't spit out code as you generate it. You have to store it
in memory making larger and larger chunks. To see why, consider the while
statement. The parser won't reduce that until it's reduced the entire body
of the loop, but you have to put some code before the body to deal with the
test and such. And jumps and offsets and such. You can get around this by
having actions partway through the rule so it triggers at the right time,
but some grammers cannot support that.

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