FOR循环控制流回填技术咨询：基于给定标记的实现说明

Great question! Let's break down how backpatching works for FOR loops, building on the IF-THEN-ELSE implementation you shared. Backpatching is all about filling in missing jump addresses in intermediate code once we know exactly where we need to jump to—critical for handling loops and conditionals in compilers.

First, let's recap the IF-THEN-ELSE example you provided to set context:

IF '(' expr M ')' stmt N ELSE L stmt L { backpatch($4, $9 - $4); backpatch($7, $11 - $7); }

Here, M tracks the list of jumps that need to go to the THEN branch when the expression is true, and N/L track jumps for the ELSE branch and exit. The backpatch calls fill in those target addresses once we reach the end of each branch.

Step 1: Map the FOR Loop Control Flow #

A standard FOR loop follows this execution path:

FOR (init_expr; cond_expr; incr_expr) body_stmt

1. Run the initialization expression once
2. Evaluate the condition expression:
   • If true → execute the loop body → run the increment expression → jump back to re-check the condition
   • If false → exit the loop entirely and continue with code after the loop

Step 2: Parse Your Marked FOR Structure #

You provided this marked FOR syntax:

FOR '(' expr ';' L expr M N ';' L expr N ')' L stmt N L

Let's assign each marker and symbol to its semantic role (so we know what we're patching):

• expr (position 3): Initialization expression (init_expr)
• L (position 5): Marker for the start of the condition check (cond_start)
• expr (position 6): Loop condition (cond_expr)
• M (position 7): true_list of cond_expr (jumps that need to go to the loop body when the condition passes)
• N (position 8): false_list of cond_expr (jumps that need to exit the loop when the condition fails)
• L (position 10): Marker for the start of the increment expression (incr_start)
• expr (position 11): Increment expression (incr_expr)
• N (position 12): Jump list after incr_expr (needs to jump back to cond_start)
• L (position 14): Marker for the end of the loop body (body_end)
• stmt (position 15): Loop body (body_stmt)
• N (position 16): Jump list after body_stmt (needs to jump to incr_start)
• L (position 17): Marker for the end of the entire FOR loop (loop_end)

Step 3: Implement Backpatching for the FOR Loop #

Using the roles above, here's the complete backpatching logic, with explanations for each step:

FOR '(' expr ';' L expr M N ';' L expr N ')' L stmt N L {
    // 1. Patch condition's true jumps to the loop body start
    backpatch($7, $15 - $7);
    
    // 2. Patch condition's false jumps to the end of the loop
    backpatch($8, $17 - $8);
    
    // 3. Patch loop body's exit jumps to the increment expression start
    backpatch($16, $11 - $16);
    
    // 4. Patch increment's exit jumps back to the condition check
    backpatch($12, $6 - $12);
}

Let's unpack each backpatch call: #

• backpatch($7, $15 - $7):
  $7 is the list of jumps triggered when cond_expr is true. We need these jumps to land at the start of the loop body ($15 is the position of stmt). This fills in the missing target address for all "true" condition jumps.
• backpatch($8, $17 - $8):
  $8 is the list of jumps triggered when cond_expr is false. These should exit the loop entirely, so we patch them to jump to loop_end ($17, the final marker).
• backpatch($16, $11 - $16):
  $16 tracks jumps that run after the loop body finishes. Once the body is done, we need to execute the increment expression, so we patch these jumps to target incr_start ($11, the start of the increment expr).
• backpatch($12, $6 - $12):
  $12 tracks jumps that run after the increment expression. After updating the loop variable, we need to re-check the condition, so we patch these jumps to target cond_start ($6, the start of the condition expr).

Key Difference from IF-THEN-ELSE #

Your IF-THEN-ELSE code handles one-way branching (either take the THEN or ELSE path, then exit). The FOR loop adds cyclic control flow—we have to jump back to re-evaluate the condition after the increment step. That's why we have two extra backpatch calls to handle the loop's "cycle" of body → increment → condition check.

内容的提问来源于stack exchange，提问作者Mohsen