Backpatching in Compiler Design

One-Pass Code Generation Using Backpatching

Backpatching can be used to generate a boolean expressions program and the flow of control statements in a single pass. In jumping code for Boolean statements, the synthesized properties truelist and falselist of non-terminal B are utilized to handle labels.

• B.truelist, which is a list of the jump or conditional jump instructions, should contain the label to which control should move if B is true.
• When B is false, B.falselist is a list of instructions that will eventually result in the label to which control will be assigned. 
   

All of the jumps to true and false, as well as the label field, are left blank when the program for B is created. The lists B.truelist and B.falselist include these early leaps.

A list of jumps to the instruction immediately after the code for S is displayed by the synthesized attribute S.nextlist on a statement S, for example. It can generate instructions into an instruction array, with labels acting as indexes. Three functions are used to change the list of leaps:

• Makelist (i): Make a new list with only i, an index into the array of instructions, then return a pointer to the newly produced list with the makelist command.
   
• Merge (p1,p2): Returns a pointer to the concatenated list after concatenating the lists pointed to by p1 and p2.
   
• Backpatch (p, i): For each of the instructions on the record pointed to by p, inserts i like the target label.

Boolean Expressions

It can construct a translation scheme suitable for generating code for Boolean expressions during bottom-up parsing.

In grammar, a non-terminal marker M creates a semantic action that picks up the index of the next instruction to be created at the proper time.

The steps for backpatching using boolean expressions are as follows:

1. Production Table
2. Finding Three address codes 
3. Making the parse tree for the expression
    

Let’s look at an example to understand this concept clearly.

Let us first understand the expression: II stands for OR operation means either of the statements if true results the whole expression as TRUE. && stands for AND operation means both statements must be true if the expression needs to be true. 

In our expression, if x<100 is true, then there is no need to go to the next statement after the OR operation. If it is not the case, there is a need to go to the next statement. The next statement is again an expression that contains AND operation meaning both the statements must be true. If either statement fails then the whole expression will be considered false. Since in single pass where to go next is undefined as shown below:  

Now using backpatching,

Generating Translation Rules: 

Parse tree: 

Flow of Control Statement

Control statements are those that change the execution order of statements. Statements such as If, If-else, Switch-Case, and while-do are examples. In computer languages, Boolean statements are widely used to: 

• Alter the flow of control−Conditional expressions that change the flow of control in a statement are known as Boolean expressions. The program's location implies the value of such a Boolean statement. For example, if claim S is met, the phrase E must be true.
   
• Compute logical values− True or false values can be expressed using a Boolean expression. Three address instructions with logical operators can be used to compute such Boolean expressions in parallel to arithmetic expressions.

Labels and Gotos

Labels and Gotos are programming constructs that allow programmers to control the flow of execution in their code. A label is a named location in code that a goto statement can reference. A goto statement allows a programmer to transfer control to the labelled location in code, bypassing any statements in between. While powerful, goto statements are usually discouraged because they make code more difficult to understand and maintain. Goto statements are not supported by many computer languages, including Java and Python.

Some Competitive Questions on Backpatching

Question.1: If (a<b then t=1) else t=0.

Fill in the missing goto statements.

Solution:

In the above question, we need to fill the black spaces with the indexing of the lines where we have to jump in order to create a program that is mentioned in the above question. 

1. First of all in Line-1 if (a<b) we need to jump to line no 4 in order to get (t = 1).
    
2. Now if the condition in line no 1 is false then we will not jump and proceed further to the next line hence getting (t = 0).
    
3. To avoid going to line no 4 we need to exit the code at the last line so now we will jump to line no 5 from line no 3 in order to avoid line no 4 and hence we have filled all the black spaces. 
    

The answer to the above question is given below:

Question.2: If (a<b) && (c<d) then t=1 else t=0.

Fill in the missing goto statements.

Solution: In this question, a nested condition is given where we need to take the union of two conditions.

1. We need to get (t = 1) when the two conditions (a<b && c<d). This is possible when we travel along line 1 to line 4 and then get the value of t at line 6 and terminate at line 7.
    
2. When the first condition is false we need to get the value of t in line 2 and then terminate at line no 7. 
    
3. When the second condition is false, we need to jump to line 2 to get the t = 0 and terminate the immediate goto to 7. 
    

The answer to the above question is given below:

Question.3: For (i = 1; i <= n; i++){

X = a+b*c;

}

Fill In the missing goto statements.

Solution: In the question above, there is a need for a loop to be created in order to perform the task under a specific condition. Hence the explanation is given below.

1. First of all initialization of variables takes place in line no 1.
    
2. Now every loop has a necessary condition under which the loop repeats itself hence if (i <= n) we need to update the values of t1 and t2 and this can be done by jumping to line no 4 and then we again need to check the condition hence we need to return from line 8 to line no 2 back. 
    
3. If the condition in line no 2 is false then we need to end the loop and exit from line no 9 hence we will jump to line no 9. 
    

The answer to the above question is given below: 

Applications of Backpatching

• It aids in the resolution of code that has been seeded with forwarding branches.
   
• Backpatching is a technique for converting flow-of-control statements into a single pass.
   
• During the code generation process, it is the action of filling in blank labels with undetermined data.
   
• During bottom-up parsing, backpatching is utilized to generate quadruples for boolean expressions.

Frequently Asked Questions

What are the three functions used in Backpatching?

To generate code using backpatching, three procedures are run in two passes: makelist(), merge(), and backpatch(). 

What does backpatching entail?

Backpatching is a technique for converting flow-of-control statements into a single pass. During bottom-up parsing, backpatching is utilized to generate quadruples for boolean expressions. During the code generation process, it is the action of filling in unspecified information on labels. 

What is meant by back patching?

Back patching is a technique used in compiler design to delay the assignment of addresses to code or data structures until a later stage of the compilation process. This allows the compiler to generate code with placeholder addresses that are later updated with the correct addresses once they are known.

What are the methods of translating boolean expressions?

The two common methods of translating boolean expressions are algebraic and truth table methods. In the algebraic method, boolean expressions are manipulated using laws of boolean algebra. In the truth table method, the possible input combinations are listed and the output values are determined for each combination.

What are the three kinds of intermediate representation in compiler design?

The three kinds of intermediate representation (IR) in compiler design are high-level IR, mid-level IR, and low-level IR. High - level IR is the source code and is easy to read. Low- level IR is the optimization for efficient execution. Mid - level acts as a bridge between the High level and Low level.

Conclusion

Hope you learned something. But the knowledge never stops, we have gained knowledge of concepts of compiler design like backpatching for boolean expressions, Flow of control Statements, etc. and now we can easily do any question related to backpatching. To learn more you can visit our website for more articles. 

Recommended Reading:

• Lexical Analysis in Compiler Design
• Input Buffering in Compiler Design
• Top Down Parsing and Bottom Up Parsing
• Difference Between Compiler and Assembler
• Intermediate Code Generation in Compiler Design
• First and Follow in Compiler Design
• Switch Statements
• Phases of Compiler
• Type Checking-Introduction-Design Spaces-Attributes
• Basic Blocks In Compiler Design
• Control Flow
• Flow Graphs
   

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do upvote our blog to help other ninjas grow.

Happy Learning Ninja :)