Write short notes on:
Back patching: The problem in generating three address codes in a single pass is that we may not know the labels that control must go to at the time jump statements are generated. So to get around this problem a series of branching statements with the targets of the jumps temporarily left unspecified is generated. BackPatching is putting the address instead of labels when the proper label is determined.
Backpatching Algorithms perform three types of operations:
The Translation scheme is as follows :-
Ex.-
E → E1 or M E2
backpatch(E1.falselist, M.quad)
E.truelist = merge(E1.truelist, E2.truelist)
E.falselist = E2.falselist
Thompson’s construction: To construct NFA (Non-deterministic Finite Automata) from a Regular expression, we present a technique that can be used as a recognizer for tokens corresponding to a regular expression. In this technique, a regular expression is first broken into simpler sub-expressions, then the corresponding NFA are constructed and finally, these small NFAs are combined with the help of regular expression operations. This construction is known as Thompson’s construction.
The algorithm
The algorithm works recursively by splitting an expression into its constituent sub-expressions, from which the NFA will be constructed using a set of rules. More precisely, from a regular expression E, the obtained automaton A with the transition function δ respects the following properties:
Rules
N(s) and N(t) is the NFA of the subexpression s and t, respectively.
Constant folding and copy propagation:
Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the nteger literal 2
, but they may also be variables whose values are known at compile time. Consider the statement:
i = 320 * 200 * 32;
Most modern compilers would not actually generate two multiply instructions and a store for this statement. Instead, they identify constructs such as these and substitute the computed values at compile time (in this case, 2,048,000). The resulting code would load the computed value and store it rather than loading and multiplying several values.
Constant folding can even use arithmetic identities. When x
is an integer type, the value of 0 * x
is zero even if the compiler does not know the value of x
.
Constant folding may apply to more than just numbers. Concatenation of string literals and constant strings can be constant folded. Code such as "abc" + "def"
may be replaced with "abcdef"
.
Constant folding can be done in a compiler's front end on the IR tree that represents the high-level source language, before it is translated into three-address code, or in the back end, as an adjunct to constant propagation.
In compiler theory, copy propagation is the process of replacing the occurrences of targets of direct assignments with their values. A direct assignment is an instruction of the form x = y, which simply assigns the value of y to x.
From the following code:
y = x
z = 3 + y
Copy propagation would yield:
z = 3 + x
Copy propagation often makes use of reaching definitions, use-def chains and def-use chains when computing which occurrences of the target may be safely replaced. If all upwards exposed uses of the target may be safely modified, the assignment operation may be eliminated.
Copy propagation is a useful "clean up" optimization frequently used after other optimizations have already been run. Some optimizations—such as elimination of common sub expressions—require that copy propagation be run afterwards in order to achieve an increase in efficiency.
Draw the syntax tree and DAG from the following expression.
if x>0 then x=3*(y+1) else y=y+1
What is linear searching?
Distinguish between Decision table versus decision tree
Distinguish Testing vs. Quality Control & Assurance and Audit
Write a C program to find the factorial of any number.