Intermediate code uses “unlimited” temporaries. We have more temporaries than there are registers. Key: assign multiple temporaries to each register

example

Consider:

a := c + d
e := a + b
f := e - 1

notice how a and e are both dead after use, we can then allocate:

r1 := r2 + r3
r1 := r1 + r4
r1 := r1 - r1

key: *you can share a register between \(t_{1}\) and \(t_{2}\) if at any point at most one of \(t_1\) and \(t_2\) are alive.

algorithm

liveness check

go through liveness analysis to see what’s live or not at any particular moment.

Regular expressions express computation as a simple, logical discretion, through closure properties (such as properties of regular languages). a family of languages which satisfy closure properties of DFA regular languages, which turns out to be exactly the set of languages that DFA and NFA both recognize.

“What is the complexity of describing the strings in a language?”

definition

Let \(\Sigma\) be an alphabet, we define the regular expressions over \(\Sigma\):

• for all \(\sigma \in \Sigma\), \(\sigma\) is a regexp
• \(\varepsilon\) (empty string) is a regexp
• \(\emptyset\) (empty set) is a regexp

If \(R_1\), \(R_2\) are regexps, then:

did you know you can do matching inline too matching equivalent statements: test (\w+) \1; non-capture group (?:test)

lookaheads

• (?=pattern) true if pattern matches, but doesn’t touch the character pointer
• (?!pattern) true if pattern doesn’t match; also doesn’t advance pointer
• (?:pattern) will advance character pointer but will not create a capture group
• ^beginning of line
• end of line$

a language \(L’\) is a regular language if there exists some DFA \(M\) such that \(L’ = L(M)\).

additional information

a proper subset

a proper subset of a regular language isn’t necessarily regular

regular expressions are equivalent to regular languages

see regular expressions are equivalent to regular languages

properties of regular languages

union

union of two languages includes all strings in a or b:

\begin{align} A \cup B = \qty {w | w \in A\ OR\ w \in B } \end{align}

1. zinc binds to zur
2. zur inhibits zinc uptake channels
3. zinc uptake channel gets zoped