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:

1. makelist(i) – creates a new list containing only i, an index into the array of quadruples and returns pointer to the list it has made.
2. merge(i,j) – concatenates the lists pointed to by i and j ,and returns a pointer to the concatenated list.
3. backpatch(p,i) – inserts i as the target label for each of the statements on the list pointed to by p.

The Translation scheme is as follows :-

• We use emit to generate code that contains place holders to be filled in later by the backpatch procedure.

• The attributes E.truelist, E.falselist are synthesized.

• When the code for E is generated, addresses of jumps corresponding to the values true and false are left unspecified and put on the lists E.truelist and E.falselist, respectively.
• A marker non-terminal M is used to capture the numerical address of a statement we want to branch to.
• nextaddr is a global variable that stores the number of the next statement to be generated. In all examples we assume that nextaddr is initialized to 100.
• makelist is a function which creates a new list from one item.
• merge is a function which creates a sorted list of addresses from two such lists.

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:

• A has exactly one initial state q₀, which is not accessible from any other state. That is, for any state q and any letter a,  does not contain q₀.
•  has exactly one final state q_f, which is not co-accessible from any other state. That is, for any letter a,.
• Let c be the number of concatenation of the regular expression E and let s be the number of symbols apart from parentheses — that is, |, *, a and ε. Then, the number of states of A is 2s − c (linear in the size of E).
• The number of transitions leaving any state is at most two.
• Since an NFA of m states and at most e transitions from each state can match a string of length n in time O(emn), a Thompson NFA can do pattern matching in linear time, assuming a fixed-size alphabet.

Rules

N(s) and N(t) is the NFA of the subexpression s and t, respectively.

1. The empty-expression ε is converted to
2. A symbol a of the input alphabet is converted to
3. The union expression s|t is converted to atOptions = { 'key': 'a900f2dbf175e78754c26c6231a4b673', 'format': 'iframe', 'height': 90, 'width': 728, 'params': {} };