Generating intermediate code

Question

grammar semantic rules

I have a problem in backpatching "if-else" statements, for generating 3 address codes.

The grammar rule is :

 S -》 if E then M1 S1 N else M2 S2 

The semantic rules are : {

 backpatch(E.truelist, M1.quad)
 backpatch(E.falselist, M2.quad)
 S.nextlist = merge(S1.nextlist, N.nextlist,
 S2.nextlist)

}

Explanation :

 Merge(p1, p2) : concatinates lists pointed by p1 and p2)
 Backpatch(p, i) : inserts i as the target label for each of the statements in the list pointed to by p)
 S.nextlist : "goto" statements to the next instruction after this statement (s)

I don't understand why we need "N" in the semantic rules above. Why should we merge N.nextlist along with S1 and S2 nextlists for getting S.nextlist?? I mean why there is "N.nextlist" among other inputs? Tnx for answering, in advance :D

• D.W.: I suspect providing additional context might be helpful. It's not clear to me what you mean by backpatching, or what properties you want it to have, or what the merge does, or what the notation represents (e.g., truelist, quad, nextlist, etc.).
• Farehe.s: Sorry I thought these terms are known, I will edit the question l. Tnx for commenting ^_^
• Wandering Logic: What are M1, S1, N, M2, and S2? Is N the goto statement that jumps over the else block?

Answer 1

Normal assembly for if/then/else looks like:

JMP_FALSE <condexpr> elselabel
<thenstmt>
JMP endlabel
elselabel:
<elsestmt>
endlabel:

(You can substitute mnemonics as appropriate for your instruction set.)

This "backpatch" term is probably something specific to some specific code that your professor wrote, or the author of the textbook that you're using. In either case, it's not a promising term.

The "truelist" and "falselist" likely refer to definite assignment (and definite unassignment) tracking; most modern languages keep track of what variables (aka registers) have been definitely assigned (for at-least-once purposes) and some, like Java, keep track of what variables are definitely unassigned (for at-most-once purposes, like Java "final"). Having implemented this a few times, I've used both a non-sparse (custom bit array/set) and a sparse data structure for tracking assignment impact within a scope; in Java, the language is simple enough that register assignment can occur before definite assignment analysis, so the bit array works beautifully (since you can know the zero-based register numbers and use them as the bit indexes).

The "N" probably refers to the unconditional jump to end of if/then/else statement. Again, it's not a promising term, since it implies a number, and IR/assembly should never be dealing with a number when a label will do.

The "quad" term is another made-up term specific to whomever wrote the material that you are working from.

Also: s/them/then