Scribd
Upload
60 views

Backpatching in Compiler Design

Backpatching is a compiler design technique that delays the assignment of addresses to code or data structures until later in the compilation process, allowing for more efficient code generation. It is particularly useful in handling complex control structures and boolean expressions, enabling one-pass code generation by utilizing synthesized properties like truelist and falselist. The technique also aids in resolving code with forwarding branches and filling in blank labels during code generation.

Uploaded by

prajjwaltripathi70
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
60 views

Backpatching in Compiler Design

Backpatching is a compiler design technique that delays the assignment of addresses to code or data structures until later in the compilation process, allowing for more efficient code generation. It is particularly useful in handling complex control structures and boolean expressions, enabling one-pass code generation by utilizing synthesized properties like truelist and falselist. The technique also aids in resolving code with forwarding branches and filling in blank labels during code generation.

Uploaded by

prajjwaltripathi70
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Backpatching

Backpacking in compiler design refers to reducing the size of a compiler by removing unnecessary
components, such as unused variables, functions, or code, to make it more efficient and optimized. This
process is known as "compiler backpacking" or "compiler slimming".
Backpatching 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 or "backpatched" with the correct addresses once they
are known. Backpatching is commonly used in compilers for languages that support complex control
structures or dynamic memory allocation.

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
x < 100 || y > 200 && x != y

Let us first understand the expression: || 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:

100: if x < 100 goto ____


101: goto ____
102: if y > 200 goto ____
103: goto ____
104: if x!=y goto ____
105: goto ____
106: true
107: false

Now using backpatching,

100: if x < 100 goto __106__


101: goto __102__
102: if y > 200 goto __104__
103: goto __107__
104: if x!=y goto __106__
105: goto __107__
106: true
107: false

Generating Translation Rules:

B → B1 || MB2 {Backpatch(B1.fl,M.instr);
B.tl = merge(B1.tl,B2.tl);
B.fl = B2.fl }

B → B1 && MB2 {Backpatch(B1.tl,M.instr);


B.tl = B2.tl;
B.fl = merge(B1.fl,B2.fl);}

B → !B1 {B.tl = B1.fl ;


B.fl = B1.tl;}
B → B1 {B.tl = B1.tl;
B.fl = B1.fl;}

M→ ε {m.instr = nextinstr; }

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.
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.

You might also like