CODEWITHSUNDEEP
compiler-constructionsyntaxcontext-free-grammar
mrjasmin
mrjasmin

Reputation: 1270

Syntax-directed translation

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 ?

Upvotes: 3

Views: 420

Answers (1)

Ira Baxter
Ira Baxter

Reputation: 95354

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.

Upvotes: 1

Related Questions