Compiler Design formula sheet

Conditions: no ${\beta }_i$ starts with $A$, and no ${\alpha }_i$ is $\epsilon$. $A^{\prime }$ is a new nonterminal. The new grammar has $n+m+1$ alternatives in total: $n$ for $A$ and $m+1$ for $A^{\prime }$.

Applies when two or more alternatives of $A$ share a nonempty prefix $\alpha$ (take the longest one); $A^{\prime }$ is a new nonterminal, and an empty ${\beta }_i$ becomes $\epsilon$. Repeat until no two alternatives of any nonterminal share a prefix.

The attribute being defined belongs to the head $A$; its arguments are attributes of the body symbols (or of $A$ itself).

The attribute being defined belongs to a body symbol $X_i$; the arguments may be attributes of the head and of the body symbols.

Holds under stack allocation, where every live activation has exactly one record on the stack. Counts the records on the stack at one instant; the maximum over the run is the peak stack depth. Includes the main program's record.

Static scoping with access links. A procedure at nesting depth $n_{\text{current}}$ uses a variable whose nearest enclosing declaration is at depth $d_{\text{var}}\le n_{\text{current}}$. Start at the current record and follow access links this many times; 0 means the variable is local.

For $x=E$ where $E$ has $n$ operator occurrences and nothing is shared. The scheme gives each operator a new temporary (temporaries are never reused) and then copies the last one to $x$. With a DAG, replace $n$ by the number of operator nodes in the DAG.

$w$ is the width of one element in bytes and $\text{low}$ is the lower bound of the index. For a 0-based array the term is just $i\times w$.

A variable is live at a point if its current value may be read later before being overwritten. Initialise IN[B] = ∅ for all B; OUT of an exit block is ∅ unless the question names live-out variables.

A definition reaches a point if some path from it to that point does not redefine the variable. Initialise OUT[B] = ∅; IN[entry] = ∅.