the AVM ${\left[\begin{array}{ll} {\mbox{\sc n}} &[H] \end{array}\right]}$, where $[H]$ encodes natural number $2x$.

The number in $[H]$ equals two times in $[F]$ if, and only if, the least-significant bit of in $[H]$ is 0, and the remaining bits form the same sequence as the number in $[F]$. Multiplication by two takes one derivation step.

#### Syntactic rules that increments by one.

Assume a nonterminal $A$ with some AVM ${\left[\begin{array}{ll} {\mbox{\sc n}} &[F] \end{array}\right]}$, where $[F]$ encodes natural number $x$. We present five syntactic rules that derive from this nonterminal $A$ a nonterminal $C$ with AVM ${\left[\begin{array}{ll} {\mbox{\sc n}} &[H] \end{array}\right]}$, where $[H]$ encodes natural number $x+1$.

The increment of requires two additional pointers in the AVM of $A$: attribute points to the next bit that has to be incremented; attribute points to the most-significant bit of the (intermediate) result. These additional pointers are hidden from the AVMs of the nonterminals $A$ and $C$.

The five rules from Table \[Tinc\] increment by one. Nonterminal $A$ rewrites, in one or more steps, to nonterminal $C$, potentially through a number of nonterminals $B$.

The first and fourth rule of Table \[Tinc\] state that adding one to a zero bit sets this bit to 