Compilers: Principles and Practice by Pearson

408 Appendix A

Hypothesis: For i > 0, the sequence is A(i), A(i-1), ... A(1), S0, B(1), B(2),

... B(i-1), B(i).

Induction: For i + 1, from the definition of rec(), the sequence is A(i+1), sequence for i,

B(i+1). Proved.

Note that statement/s which come before the recursive call are executed in reverse order or

order of recursive descent, while statement/s which are after the recursive call are executed in

order of ascent from recursion.

In anticipation of a later section on regular expressions, Section A.4, this ET can be expressed by

a regular expression A*SB*.

Structural Induction

A special form of induction is sometimes useful. Let U be a ...