Syntax-directed translation

Question

I need help with syntax-directed translation. I don't know how to factorize a grammar so that I can generate quadruples for it.

Take this example:

S ::= If E then S1 else S2 

Is factorized into this(because we don't know the jump targets)

1. <ifstmt> ::= <truepart> S2
2. <truepart> ::= <ifclause> S1 else
3. <ifclause> ::= if E then

What is the general approach when factorizing ?

Answer 1

Generally you break every syntax construct apart at a place where you might need to generate code (as you have demonstrated with if-then-else), and attach a code generation action to the grammar-rule-reduction action of the parser.

While you can do this, you'll get pretty clumsy code; fundamentally you'll end up implementing a stack machine because the pure grammar can't keep track of context, so you have to assume it is recursively constructed (e.g., stack-like). If you this, you'll end with lots more and dumb quadruples than you really want. All that does is waste a back-end's time, if it is optimizing, or cause it to generate dumb code, if not.

Mostly when one is generating quads, one is interesting in something considerably more sophisticated than "syntax directed translation". In this case, it is better to build an AST, construct symbol tables and control flow graphs, perhaps even data flow graphs, and then construct quadruples from that.

Then you can focus on building a good backend to process those quads.