The whole Compiler Design formula sheet, to print

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.

Also at most one alternative of $A$ may derive $\epsilon$. The condition holds for every nonterminal exactly when no cell of the LL(1) table has two entries.

Applies to LL(1) and LR parsers on an accepted string $w$ of $|w|$ tokens whose parse tree has $p$ internal nodes, not counting the augmented start $S^{\prime }$. In LL, $|w|$ counts the matches and $p$ the expansions; in LR, $|w|$ counts the shifts and $p$ the reductions. A node for an $\epsilon$-production counts in $p$. Accept, and the final match of $, are not counted unless the question says so.

If $\beta$ is empty or nullable, $a$ itself is among the new lookaheads. The initial item is $S^{\prime }\to \cdot S$ with lookahead $. Goto works exactly as in LR(0), carrying the lookaheads along unchanged. Reduce by $A\to \alpha$ only on the item's own lookahead.

Each inclusion is proper. A grammar class here means the set of grammars the method parses without conflict. LL(1) is not contained in LALR(1), SLR(1) or LR(0), and none of those is contained in LL(1): LL(1) is incomparable with each of them. More generally every LL(k) grammar is LR(k).

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.

Also allowed: dependence on other attributes of $X_i$ itself, provided that creates no cycle. Not allowed: dependence on a synthesized attribute of the head $A$. Synthesized attributes of $A$ may use any attribute in the production, including $A$'s inherited attributes, provided no cycle results.

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.

Procedure $p$ (depth $n_p$) calls procedure $q$ (depth $n_q$), which is visible from $p$, so $n_q\le n_p+1$. Follow this many access links from $p$'s record; the record reached is the most recent activation of $q$'s lexical parent, and $q$'s access link is set to it. Cases: $n_q=n_p+1$ ($q$ declared inside $p$) gives 0, so the link points to $p$ itself; $n_q=n_p$ gives 1, so the link equals $p$'s own access link; $n_q<n_p$ gives $n_p-n_q+1$ links.

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

$n_2=u_2-l_2+1$ is the number of columns, and $l_1,l_2$ are the lower bounds. Row-major is the default for C-style arrays unless stated otherwise.

$n_1=u_1-l_1+1$ is the number of rows. Use this only when the question says the layout is column-major.

Each original assignment gets exactly one new name, and each $\varphi$ is one more assignment. Since each SSA name is assigned once, this is also the number of names created by assignments and $\varphi$-functions. Variables that are only read and never assigned (inputs) keep their names and are not counted.

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] = ∅.

An expression is available at a point if on every path to it the expression has been computed and its operands not changed since. IN[entry] = ∅; initialise OUT[B] to the set U of all expressions for every other block.