124  INTRODUCTION  MANGLE §1

1* . Introduction. This program converts a file to a Pascal file. It was written by D. E. Knuth in September, 1981; a somewhat similar SAIL program had been developed in March, 1979. Since this program describes itself, a bootstrapping process involving hand-translation had to be used to get started.

For large files one should have a large memory, since keeps all the Pascal text in memory (in an abbreviated form). The program uses a few features of the local Pascal compiler that may need to be changed in other installations:

1) Case statements have a default.

2) Input-output routines may need to be adapted for use with a particular character set and/or for printing messages on the user’s terminal.

These features are also present in the Pascal version of TEX, where they are used in a similar (but more complex) way. System-dependent portions of can be identified by looking at the entries for ‘system dependencies’ in the index below.

The “banner line” defined here should be changed whenever is modified.

For the Modula-2 versions of , we add a second decimal point and number to the main version number, so we can differentiate between changes to the standard and changes local to the Modula-2 version.

define banner ≡ ´ ␣ ␣ ␣ ␣ ␣ ␣ ´

2. The program begins with a fairly normal header, made up of pieces that will mostly be filled in later. The input comes from files web file and change file, the Pascal output goes to file Pascal file, and the string pool output goes to file pool .

If it is necessary to abort the job because of a fatal error, the program calls the ‘jump out ’ procedure, which goes to the label end of TANGLE .

define end of TANGLE = 9999 { go here to wrap it up } ⟨ Compiler directives 4 ⟩ program TANGLE (web file, change file, Pascal file, pool );

label end of TANGLE ; { go here to finish }

const ⟨ Constants in the outer block 8* ⟩

type ⟨ Types in the outer block 11 ⟩

var ⟨ Globals in the outer block 9 ⟩

⟨ Error handling procedures 30 ⟩ procedure initialize;

var ⟨ Local variables for initialization 16 ⟩ begin ⟨ Set initial values 10 ⟩ end;

3. Some of this code is optional for use when debugging only; such material is enclosed between the delimiters debug and gubed. Other parts, delimited by stat and tats, are optionally included if statistics about ’s memory usage are desired.

define debug ≡ { change this to ‘debug ≡ ’ when debugging }

define gubed ≡ { change this to ‘gubed ≡ ’ when debugging }

format debug ≡ begin

format gubed ≡ end

define stat ≡ { change this to ‘stat ≡ ’ when gathering usage statistics }

define tats ≡ { change this to ‘tats ≡ ’ when gathering usage statistics }

format stat ≡ begin

format tats ≡ end

§4  MANGLE  INTRODUCTION 125

4. The Pascal compiler used to develop this system has “compiler directives” that can appear in comments whose first character is a dollar sign. In production versions of these directives tell the compiler that it is safe to avoid range checks and to leave out the extra code it inserts for the Pascal debugger’s benefit, although interrupts will occur if there is arithmetic overflow. ⟨ Compiler directives 4 ⟩ ≡

$C−, A+, D− { no range check, catch arithmetic overflow, no debug overhead } debug $C+, D+ gubed { but turn everything on when debugging }

This code is used in section 2.

5. Labels are given symbolic names by the following definitions. We insert the label ‘exit :’ just before the ‘end’ of a procedure in which we have used the ‘return’ statement defined below; the label ‘restart ’ is occasionally used at the very beginning of a procedure; and the label ‘reswitch’ is occasionally used just prior to a case statement in which some cases change the conditions and we wish to branch to the newly applicable case. Loops that are set up with the loop construction defined below are commonly exited by going to ‘done’ or to ‘found ’ or to ‘not found ’, and they are sometimes repeated by going to ‘continue’.

define exit = 10 { go here to leave a procedure }

define restart = 20 { go here to start a procedure again }

define reswitch = 21 { go here to start a case statement again }

define continue = 22 { go here to resume a loop }

define done = 30 { go here to exit a loop }

define found = 31 { go here when you’ve found it }

define not found = 32 { go here when you’ve found something else }

6. Here are some macros for common programming idioms.

define incr (#) ≡ # ← # + 1 { increase a variable by unity }

define decr (#) ≡ # ← # − 1 { decrease a variable by unity }

define loop ≡ while true do { repeat over and over until a goto happens } define do nothing ≡ { empty statement } define return ≡ goto exit { terminate a procedure call } format return ≡ nil format loop ≡ xclause

7. We assume that case statements may include a default case that applies if no matching label is found. Thus, we shall use constructions like

case x of

1: ⟨ code for x = 1 ⟩; 3: ⟨ code for x = 3 ⟩; othercases ⟨ code for x ≠ 1 and x ≠ 3 ⟩ endcases

since most Pascal compilers have plugged this hole in the language by incorporating some sort of default mechanism. For example, the compiler used to develop and TEX allows ‘others :’ as a default label, and other Pascals allow syntaxes like ‘else’ or ‘otherwise’ or ‘otherwise:’, etc. The definitions of othercases and endcases should be changed to agree with local conventions. (Of course, if no default mechanism is available, the case statements of this program must be extended by listing all remaining cases. The author would have taken the trouble to modify so that such extensions were done automatically, if he had not wanted to encourage Pascal compiler writers to make this important change in Pascal, where it belongs.)

define othercases ≡ others : { default for cases not listed explicitly }

define endcases ≡ end { follows the default case in an extended case statement } format othercases ≡ else format endcases ≡ end 8* . The following parameters are set big enough to handle TEX, so they should be sufficient for most applications of . ⟨ Constants in the outer block 8* ⟩ ≡

buf size = 100; { maximum length of input line } max bytes = 45000; { 1/ww times the number of bytes in identifiers, strings, and module names; must

be less than 65536 } max toks = 50000;

{ 1/zz times the number of bytes in compressed Pascal code; must be less than 65536 } max names = 4000; { number of identifiers, strings, module names; must be less than 10240 } max texts = 2000; { number of replacement texts, must be less than 10240 } hash size = 353; { should be prime } longest name = 400; { module names shouldn’t be longer than this } line length = 72; { lines of Pascal output have at most this many characters } out buf size = 144; { length of output buffer, should be twice line length } stack size = 50; { number of simultaneous levels of macro expansion } max id length = 31; { long identifiers are chopped to this length, which must not exceed line length } unambig length = 20; { identifiers must be unique if chopped to this length }

This code is used in section 2.

9. A global variable called history will contain one of four values at the end of every run: spotless means that no unusual messages were printed; harmless message means that a message of possible interest was printed but no serious errors were detected; error message means that at least one error was found; fatal message means that the program terminated abnormally. The value of history does not influence the behavior of the program; it is simply computed for the convenience of systems that might want to use such information.

define spotless = 0 { history value for normal jobs } define harmless message = 1 { history value when non-serious info was printed } define error message = 2 { history value when an error was noted } define fatal message = 3 { history value when we had to stop prematurely } define mark harmless ≡ if history = spotless then history ← harmless message define mark error ≡ history ← error message define mark fatal ≡ history ← fatal message

⟨ Globals in the outer block 9 ⟩ ≡ history : spotless . . fatal message; { how bad was this run? }

See also sections 13, 20, 23, 25, 27, 29, 38, 40, 44, 50, 65, 70, 79, 80, 82, 86, 94, 95, 100, 124, 126, 143, 156, 164, 171, 179,

and 185. This code is used in section 2.

10. ⟨ Set initial values 10 ⟩ ≡ history ← spotless ;

See also sections 14, 17, 18, 21, 26, 42, 46, 48, 52, 71, 144, 152, and 180. This code is used in section 2.

§11  MANGLE  THE CHARACTER SET 127

11. The character set. One of the main goals in the design of has been to make it readily portable between a wide variety of computers. Yet by its very nature must use a greater variety of characters than most computer programs deal with, and character encoding is one of the areas in which existing machines differ most widely from each other.

To resolve this problem, all input to and is converted to an internal seven-bit code that is essentially standard ASCII, the “American Standard Code for Information Interchange.” The conversion is done immediately when each character is read in. Conversely, characters are converted from ASCII to the user’s external representation just before they are output.

Such an internal code is relevant to users of only because it is the code used for preprocessed constants like . If you are writing a program in that makes use of such one-character constants, you should convert your input to ASCII form, like and do. Otherwise ’s internal coding scheme does not affect you.

Here is a table of the standard visible ASCII codes:

0  1  2  3  4  5  6  7

          ´ 040  ␣       !       "       #       $       %       &       '
          ´ 050  (       )       *       +       ,       -       .       /
          ´ 060  0       1       2       3       4       5       6       7
          ´ 070  8       9       :       ;       <       =       >       ?
          ´ 100  @       A       B       C       D       E       F       G
          ´ 110  H       I       J       K       L       M       N       O
          ´ 120  P       Q       R       S       T       U       V       W
          ´ 130  X       Y       Z       [       \       ]       ^_
          ´ 140  `       a       b       c       d       e       f       g
          ´ 150  h       i       j       k       l       m       n       o
          ´ 160  p       q       r       s       t       u       v       w
          ´ 170  x       y       z       {       |       }       ~

(Actually, of course, code ´ 040 is an invisible blank space.) Code ´ 136 was once an upward arrow ( ), and code ´ 137 was once a left arrow ( ), in olden times when the first draft of ASCII code was prepared; but works with today’s standard ASCII in which those codes represent circumflex and underline as shown. ⟨ Types in the outer block 11 ⟩ ≡

ASCII code = 0 . . 127; { seven-bit numbers, a subrange of the integers }

See also sections 12, 37, 39, 43, and 78. This code is used in section 2.

128  THE CHARACTER SET  MANGLE §12

12. The original Pascal compiler was designed in the late 60s, when six-bit character sets were common, so it did not make provision for lowercase letters. Nowadays, of course, we need to deal with both capital and small letters in a convenient way, so assumes that it is being used with a Pascal whose character set contains at least the characters of standard ASCII as listed above. Some Pascal compilers use the original name char for the data type associated with the characters in text files, while other Pascals consider char to be a 64-element subrange of a larger data type that has some other name.

In order to accommodate this difference, we shall use the name text char to stand for the data type of the characters in the input and output files. We shall also assume that text char consists of the elements chr (first text char ) through chr (last text char ), inclusive. The following definitions should be adjusted if necessary.

define text char ≡ char { the data type of characters in text files }

define first text char = 0 { ordinal number of the smallest element of text char }

define last text char = 127 { ordinal number of the largest element of text char } ⟨ Types in the outer block 11 ⟩ +≡

text file = packed file of text char ;

13. The  and  processors convert between ASCII code and the user’s external character set

by means of arrays xord and xchr that are analogous to Pascal’s ord and chr functions. ⟨ Globals in the outer block 9 ⟩ +≡ xord : array [text char ] of ASCII code; { specifies conversion of input characters } xchr : array [ASCII code] of text char ; { specifies conversion of output characters } 14. If we assume that every system using is able to read and write the visible characters of standard ASCII (although not necessarily using the ASCII codes to represent them), the following assignment statements initialize most of the xchr array properly, without needing any system-dependent changes. For example, the statement ´ ´ ´ that appears in the present file might be encoded in, say, EBCDIC code on the external medium on which it resides, but will convert from this external code to ASCII and back again. Therefore the assignment statement ´ ´ will appear in the corresponding Pascal file, and Pascal will compile this statement so that xchr [65] receives the character in the external (char ) code. Note that it would be quite incorrect to say ´ , because is a constant of type integer , not char , and because we have = 65 regardless of the external character set. ⟨ Set initial values 10 ⟩ +≡

xchr [´ 40 ] ← ´ ␣´ ; xchr [´ 41 ] ← ´ ´ ; xchr [´ 42 ] ← ´ ´ ; xchr [´ 43 ] ← ´ #´ ; xchr [´ 44 ] ← ´ $´ ; xchr [´ 45 ] ← ´ %´ ; xchr [´ 46 ] ← ´ ´ ; xchr [´ 47 ] ← ´ ´ ´ ´ ; xchr [´ 50 ] ← ´ ´ ; xchr [´ 51 ] ← ´ ´ ; xchr [´ 52 ] ← ´ ´ ; xchr [´ 53 ] ← ´ ´ ; xchr [´ 54 ] ← ´ ´ ; xchr [´ 55 ] ← ´ ´ ; xchr [´ 56 ] ← ´ ´ ; xchr [´ 57 ] ← ´ ´ ; xchr [´ 60 ] ← ´ ´ ; xchr [´ 61 ] ← ´ ´ ; xchr [´ 62 ] ← ´ ´ ; xchr [´ 63 ] ← ´ ´ ; xchr [´ 64 ] ← ´ ´ ; xchr [´ 65 ] ← ´ ´ ; xchr [´ 66 ] ← ´ ´ ; xchr [´ 67 ] ← ´ ´ ; xchr [´ 70 ] ← ´ ´ ; xchr [´ 71 ] ← ´ ´ ; xchr [´ 72 ] ← ´ ´ ; xchr [´ 73 ] ← ´ ´ ; xchr [´ 74 ] ← ´ ´ ; xchr [´ 75 ] ← ´ ´ ; xchr [´ 76 ] ← ´ ´ ; xchr [´ 77 ] ← ´ ´ ; xchr [´ 100 ] ← ´ ´ ; xchr [´ 101 ] ← ´ ´ ; xchr [´ 102 ] ← ´ ´ ; xchr [´ 103 ] ← ´ ´ ; xchr [´ 104 ] ← ´ ´ ; xchr [´ 105 ] ← ´ ´ ; xchr [´ 106 ] ← ´ ´ ; xchr [´ 107 ] ← ´ ´ ; xchr [´ 110 ] ← ´ ´ ; xchr [´ 111 ] ← ´ ´ ; xchr [´ 112 ] ← ´ ´ ; xchr [´ 113 ] ← ´ ´ ; xchr [´ 114 ] ← ´ ´ ; xchr [´ 115 ] ← ´ ´ ; xchr [´ 116 ] ← ´ ´ ; xchr [´ 117 ] ← ´ ´ ; xchr [´ 120 ] ← ´ ´ ; xchr [´ 121 ] ← ´ ´ ; xchr [´ 122 ] ← ´ ´ ; xchr [´ 123 ] ← ´ ´ ; xchr [´ 124 ] ← ´ ´ ; xchr [´ 125 ] ← ´ ´ ; xchr [´ 126 ] ← ´ ´ ; xchr [´ 127 ] ← ´ ´ ; xchr [´ 130 ] ← ´ ´ ; xchr [´ 131 ] ← ´ ´ ; xchr [´ 132 ] ← ´ ´ ; xchr [´ 133 ] ← ´ ´ ; xchr [´ 134 ] ← ´ ´ ; xchr [´ 135 ] ← ´ ´ ; xchr [´ 136 ] ← ´ ´ ; xchr [´ 137 ] ← ´ ´ ; xchr [´ 140 ] ← ´ ` ´ ; xchr [´ 141 ] ← ´ ´ ; xchr [´ 142 ] ← ´ ´ ; xchr [´ 143 ] ← ´ ´ ; xchr [´ 144 ] ← ´ ´ ; xchr [´ 145 ] ← ´ ´ ; xchr [´ 146 ] ← ´ ´ ; xchr [´ 147 ] ← ´ ´ ; xchr [´ 150 ] ← ´ ´ ; xchr [´ 151 ] ← ´ ´ ; xchr [´ 152 ] ← ´ ´ ; xchr [´ 153 ] ← ´ ´ ; xchr [´ 154 ] ← ´ ´ ; xchr [´ 155 ] ← ´ ´ ; xchr [´ 156 ] ← ´ ´ ; xchr [´ 157 ] ← ´ ´ ; xchr [´ 160 ] ← ´ ´ ; xchr [´ 161 ] ← ´ ´ ; xchr [´ 162 ] ← ´ ´ ; xchr [´ 163 ] ← ´ ´ ; xchr [´ 164 ] ← ´ ´ ; xchr [´ 165 ] ← ´ ´ ; xchr [´ 166 ] ← ´ ´ ; xchr [´ 167 ] ← ´ ´ ; xchr [´ 170 ] ← ´ ´ ; xchr [´ 171 ] ← ´ ´ ; xchr [´ 172 ] ← ´ ´ ; xchr [´ 173 ] ← ´ ´ ; xchr [´ 174 ] ← ´ ´ ; xchr [´ 175 ] ← ´ ´ ; xchr [´ 176 ] ← ´ ´ ; xchr [0] ← ´ ␣´ ; xchr [´ 177 ] ← ´ ␣´ ; { these ASCII codes are not used }

15. Some of the ASCII codes below ´ 40 have been given symbolic names in  and  because

they are used with a special meaning.

define and sign = ´ 4 { equivalent to ‘ ’ } define not sign = ´ 5 { equivalent to ‘ ’ } define set element sign = ´ 6 { equivalent to ‘ ’ } define tab mark = ´ 11 { ASCII code used as tab-skip } define line feed = ´ 12 { ASCII code thrown away at end of line } define form feed = ´ 14 { ASCII code used at end of page } define carriage return = ´ 15 { ASCII code used at end of line } define left arrow = ´ 30 { equivalent to ‘ ’ } define not equal = ´ 32 { equivalent to ‘ ’ } define less or equal = ´ 34 { equivalent to ‘ ’ } define greater or equal = ´ 35 { equivalent to ‘ ’ } define equivalence sign = ´ 36 { equivalent to ‘ ’ } define or sign = ´ 37 { equivalent to ‘ ’ } 16. When we initialize the xord array and the remaining parts of xchr , it will be convenient to make use of an index variable, i. ⟨ Local variables for initialization 16 ⟩ ≡ i: 0 . . last text char ;

See also sections 41, 45, and 51. This code is used in section 2.

17. Here now is the system-dependent part of the character set. If is being implemented on a gardenvariety Pascal for which only standard ASCII codes will appear in the input and output files, you don’t need to make any changes here. But at MIT, for example, the code in this module should be changed to

for i ← 1 to ´ 37 do xchr [i] ← chr (i);

’s character set is essentially identical to MIT’s, even with respect to characters less than ´ 40 .

Changes to the present module will make more friendly on computers that have an extended character set, so that one can type things like instead of . If you have an extended set of characters that are easily incorporated into text files, you can assign codes arbitrarily here, giving an xchr equivalent to whatever characters the users of are allowed to have in their input files, provided that unsuitable characters do not correspond to special codes like carriage return that are listed above.

(The present file does not contain any of the non-ASCII characters, because it is intended to be used with all implementations of . It was originally created on a Stanford system that has a convenient extended character set, then “sanitized” by applying another program that transliterated all of the non-standard characters into standard equivalents.) ⟨ Set initial values 10 ⟩ +≡

for i ← 1 to ´ 37 do xchr [i] ← ´ ␣´ ;

18. The following system-independent code makes the xord array contain a suitable inverse to the information in xchr . ⟨ Set initial values 10 ⟩ +≡

for i ← first text char to last text char do xord [chr (i)] ← ´ 40 ;

for i ← 1 to ´ 176 do xord [xchr [i]] ← i;

§19  MANGLE  INPUT AND OUTPUT 131

19. Input and output. The input conventions of this program are intended to be very much like those of TEX (except, of course, that they are much simpler, because much less needs to be done). Furthermore they are identical to those of . Therefore people who need to make modifications to all three systems should be able to do so without too many headaches.

We use the standard Pascal input/output procedures in several places that TEX cannot, since does not have to deal with files that are named dynamically by the user, and since there is no input from the terminal.

20. Terminal output is done by writing on file term out , which is assumed to consist of characters of type text char :

define print (#) ≡ write(term out , #) { ‘print ’ means write on the terminal }

define print ln(#) ≡ write ln(term out , #) { ‘print ’ and then start new line }

define new line ≡ write ln(term out ) { start new line }

define print nl (#) ≡ { print information starting on a new line } begin new line; print (#); end

⟨ Globals in the outer block 9 ⟩ +≡ term out : text file; { the terminal as an output file }

21. Different systems have different ways of specifying that the output on a certain file will appear on the user’s terminal. Here is one way to do this on the Pascal system that was used in ’s initial development: ⟨ Set initial values 10 ⟩ +≡

rewrite(term out , ´ ´ ); { send term out output to the terminal }

22. The update terminal procedure is called when we want to make sure that everything we have output to the terminal so far has actually left the computer’s internal buffers and been sent.

define update terminal ≡ break (term out ) { empty the terminal output buffer }

23. The main input comes from web file; this input may be overridden by changes in change file. (If change file is empty, there are no changes.) ⟨ Globals in the outer block 9 ⟩ +≡ web file: text file; { primary input } change file: text file; { updates }

24. The following code opens the input files. Since these files were listed in the program header, we assume that the Pascal runtime system has already checked that suitable file names have been given; therefore no additional error checking needs to be done. procedure open input ; { prepare to read web file and change file }

begin reset (web file); reset (change file);

end;

25. The main output goes to Pascal file, and string pool constants are written to the pool file. ⟨ Globals in the outer block 9 ⟩ +≡ Pascal file: text file; pool : text file;

132  INPUT AND OUTPUT  MANGLE §26

26. The following code opens Pascal file and pool . Since these files were listed in the program header, we assume that the Pascal runtime system has checked that suitable external file names have been given. ⟨ Set initial values 10 ⟩ +≡

rewrite(Pascal file); rewrite(pool );

27. Input goes into an array called buffer . ⟨ Globals in the outer block 9 ⟩ +≡ buffer : array [0 . . buf size] of ASCII code;

28. The input ln procedure brings the next line of input from the specified file into the buffer array and returns the value true, unless the file has already been entirely read, in which case it returns false. The conventions of TEX are followed; i.e., ASCII code numbers representing the next line of the file are input into buffer [0], buffer [1], …, buffer [limit − 1]; trailing blanks are ignored; and the global variable limit is set to the length of the line. The value of limit must be strictly less than buf size.

We assume that none of the ASCII code values of buffer [j] for 0 ≤ j < limit is equal to 0, ´ 177 , line feed , form feed , or carriage return. function input ln(var f : text file): boolean; { inputs a line or returns false }

var final limit : 0 . . buf size; { limit without trailing blanks }

begin limit ← 0; final limit ← 0;

if eof (f) then input ln ← false

else begin while ¬eoln(f) do begin buffer [limit ] ← xord [f↑]; get (f); incr (limit ); if buffer [limit − 1] ≠ ␣ then final limit ← limit ; if limit = buf size then

begin while ¬eoln(f) do get (f);

decr (limit ); { keep buffer [buf size] empty }

print nl (´ ␣ ␣ ␣ ␣ ´ ); loc ← 0; error ; end; end;

read ln(f); limit ← final limit ; input ln ← true; end;

end;

§29  MANGLE  REPORTING ERRORS TO THE USER 133

29. Reporting errors to the user. The processor operates in two phases: first it inputs the source file and stores a compressed representation of the program, then it produces the Pascal output from the compressed representation.

The global variable phase one tells whether we are in Phase I or not. ⟨ Globals in the outer block 9 ⟩ +≡ phase one: boolean; { true in Phase I, false in Phase II }

30. If an error is detected while we are debugging, we usually want to look at the contents of memory. A special procedure will be declared later for this purpose. ⟨ Error handling procedures 30 ⟩ ≡

debug procedure debug help; forward ; gubed

See also sections 31 and 34. This code is used in section 2.

31. During the first phase, syntax errors are reported to the user by saying

‘err print (´ ␣ ␣ ´ )’,

followed by ‘jump out ’ if no recovery from the error is provided. This will print the error message followed by an indication of where the error was spotted in the source file. Note that no period follows the error message, since the error routine will automatically supply a period.

Errors that are noticed during the second phase are reported to the user in the same fashion, but the error message will be followed by an indication of where the error was spotted in the output file.

The actual error indications are provided by a procedure called error .

define err print (#) ≡ begin new line; print (#); error ; end

⟨ Error handling procedures 30 ⟩ +≡ procedure error ; { prints ’ ’ and location of error message }

var j: 0 . . out buf size; { index into out buf }

k, l: 0 . . buf size; { indices into buffer } begin if phase one then ⟨ Print error location based on input buffer 32 ⟩ else ⟨ Print error location based on output buffer 33 ⟩; update terminal ; mark error ; debug debug help; gubed end;

134  REPORTING ERRORS TO THE USER  MANGLE §32

32. The error locations during Phase I can be indicated by using the global variables loc, line, and changing , which tell respectively the first unlooked-at position in buffer , the current line number, and whether or not the current line is from change file or web file. This routine should be modified on systems whose standard text editor has special line-numbering conventions. ⟨ Print error location based on input buffer 32 ⟩ ≡

begin if changing then print (´ ␣ ␣ ␣´ ) else print (´ ␣ ´ ); print ln(´ ´ , line : 1, ´ ´ ); if loc ≥ limit then l ← limit else l ← loc; for k ← 1 to l do

if buffer [k − 1] = tab mark then print (´ ␣´ )

else print (xchr [buffer [k − 1]]); { print the characters already read } new line; for k ← 1 to l do print (´ ␣´ ); { space out the next line } for k ← l + 1 to limit do print (xchr [buffer [k − 1]]); { print the part not yet read } print (´ ␣´ ); { this space separates the message from future asterisks } end

This code is used in section 31.

33. The position of errors detected during the second phase can be indicated by outputting the partiallyfilled output buffer, which contains out ptr entries. ⟨ Print error location based on output buffer 33 ⟩ ≡

begin print ln(´ ␣ ´ , line : 1, ´ ´ ); for j ← 1 to out ptr do print (xchr [out buf [j − 1]]); { print current partial line } print (´ ␣´ ); { indicate that this information is partial } end

This code is used in section 31.

34. The jump out procedure just cuts across all active procedure levels and jumps out of the program. This is the only non-local goto statement in . It is used when no recovery from a particular error has been provided.

Some Pascal compilers do not implement non-local goto statements. In such cases the code that appears at label end of TANGLE should be copied into the jump out procedure, followed by a call to a system procedure that terminates the program.

define fatal error (#) ≡ begin new line; print (#); error ; mark fatal ; jump out ; end

⟨ Error handling procedures 30 ⟩ +≡ procedure jump out ;

begin goto end of TANGLE ; end;

35. Sometimes the program’s behavior is far different from what it should be, and prints an error message that is really for the maintenance person, not the user. In such cases the program says confusion(´ ␣ ␣ ␣ ␣ ´ ).

define confusion(#) ≡ fatal error (´ ␣ ␣ ´ ´ ␣ ␣ ´ , #, ´ ´ )

36. An overflow stop occurs if ’s tables aren’t large enough.

define overflow (#) ≡ fatal error (´ ␣ ␣´ , #, ´ ␣ ␣ ´ )

§37  MANGLE  DATA STRUCTURES 135

37. Data structures. Most of the user’s Pascal code is packed into seven- or eight-bit integers in two large arrays called byte mem and tok mem. The byte mem array holds the names of identifiers, strings, and modules; the tok mem array holds the replacement texts for macros and modules. Allocation is sequential, since things are deleted only during Phase II, and only in a last-in-first-out manner.

Auxiliary arrays byte start and tok start are used as directories to byte mem and tok mem, and the link , ilk , equiv , and text link arrays give further information about names. These auxiliary arrays consist of sixteen-bit items. ⟨ Types in the outer block 11 ⟩ +≡

eight bits = 0 . . 255; { unsigned one-byte quantity }

sixteen bits = 0 . . 65535; { unsigned two-byte quantity }

38. has been designed to avoid the need for indices that are more than sixteen bits wide, so that it can be used on most computers. But there are programs that need more than 65536 tokens, and some programs even need more than 65536 bytes; TEX is one of these. To get around this problem, a slight complication has been added to the data structures: byte mem and tok mem are two-dimensional arrays, whose first index is either 0 or 1. (For generality, the first index is actually allowed to run between 0 and ww − 1 in byte mem, or between 0 and zz − 1 in tok mem, where ww and zz are set to 2 and 3; the program will work for any positive values of ww and zz , and it can be simplified in obvious ways if ww = 1 or zz = 1.)

define ww = 2 { we multiply the byte capacity by approximately this amount }

define zz = 3 { we multiply the token capacity by approximately this amount } ⟨ Globals in the outer block 9 ⟩ +≡ byte mem: packed array [0 . . ww − 1, 0 . . max bytes ] of ASCII code; { characters of names } tok mem: packed array [0 . . zz − 1, 0 . . max toks ] of eight bits ; { tokens } byte start : array [0 . . max names ] of sixteen bits ; { directory into byte mem } tok start : array [0 . . max texts ] of sixteen bits ; { directory into tok mem } link : array [0 . . max names ] of sixteen bits ; { hash table or tree links } ilk : array [0 . . max names ] of sixteen bits ; { type codes or tree links } equiv : array [0 . . max names ] of sixteen bits ; { info corresponding to names } text link : array [0 . . max texts ] of sixteen bits ; { relates replacement texts }

39. The names of identifiers are found by computing a hash address h and then looking at strings of bytes signified by hash[h], link [hash[h]], link [link [hash[h]]], …, until either finding the desired name or encountering a zero.

A ‘name pointer ’ variable, which signifies a name, is an index into byte start . The actual sequence of characters in the name pointed to by p appears in positions byte start [p] to byte start [p + ww ] − 1, inclusive, in the segment of byte mem whose first index is p mod ww . Thus, when ww = 2 the even-numbered name bytes appear in byte mem[0, ∗] and the odd-numbered ones appear in byte mem[1, ∗]. The pointer 0 is used for undefined module names; we don’t want to use it for the names of identifiers, since 0 stands for a null pointer in a linked list.

Strings are treated like identifiers; the first character (a double-quote) distinguishes a string from an alphabetic name, but for ’s purposes strings behave like numeric macros. (A ‘string’ here refers to the strings delimited by double-quotes that processes. Pascal string constants delimited by singlequote marks are not given such special treatment; they simply appear as sequences of characters in the Pascal texts.) The total number of strings in the string pool is called string ptr , and the total number of names in byte mem is called name ptr . The total number of bytes occupied in byte mem[w, ∗] is called byte ptr [w].

We usually have byte start [name ptr + w] = byte ptr [(name ptr + w) mod ww ] for 0 ≤ w < ww , since these are the starting positions for the next ww names to be stored in byte mem.

define length(#) ≡ byte start [# + ww ] − byte start [#] { the length of a name } ⟨ Types in the outer block 11 ⟩ +≡

name pointer = 0 . . max names ; { identifies a name }

136  DATA STRUCTURES  MANGLE §40

40. ⟨ Globals in the outer block 9 ⟩ +≡ name ptr : name pointer ; { first unused position in byte start } string ptr : name pointer ; { next number to be given to a string of length ≠ 1 } byte ptr : array [0 . . ww − 1] of 0 . . max bytes ; { first unused position in byte mem } pool check sum: integer ; { sort of a hash for the whole string pool }

41. ⟨ Local variables for initialization 16 ⟩ +≡ wi : 0 . . ww − 1; { to initialize the byte mem indices }

42. ⟨ Set initial values 10 ⟩ +≡

for wi ← 0 to ww − 1 do begin byte start [wi ] ← 0; byte ptr [wi ] ← 0; end;

byte start [ww ] ← 0; { this makes name 0 of length zero }

name ptr ← 1; string ptr ← 128; pool check sum ← 271828;

43. Replacement texts are stored in tok mem, using similar conventions. A ‘text pointer ’ variable is an index into tok start , and the replacement text that corresponds to p runs from positions tok start [p] to tok start [p + zz ] − 1, inclusive, in the segment of tok mem whose first index is p mod zz . Thus, when zz = 2 the even-numbered replacement texts appear in tok mem[0, ∗] and the odd-numbered ones appear in tok mem[1, ∗]. Furthermore, text link [p] is used to connect pieces of text that have the same name, as we shall see later. The pointer 0 is used for undefined replacement texts.

The first position of tok mem[z, ∗] that is unoccupied by replacement text is called tok ptr [z], and the first unused location of tok start is called text ptr . We usually have the identity tok start [text ptr + z] = tok ptr [(text ptr + z) mod zz ], for 0 ≤ z < zz , since these are the starting positions for the next ww replacement texts to be stored in tok mem. ⟨ Types in the outer block 11 ⟩ +≡

text pointer = 0 . . max texts ; { identifies a replacement text }

44. It is convenient to maintain a variable z that is equal to text ptr mod zz , so that we always insert tokens into segment z of tok mem. ⟨ Globals in the outer block 9 ⟩ +≡

text ptr : text pointer ; { first unused position in tok start }

tok ptr : array [0 . . zz − 1] of 0 . . max toks ; { first unused position in a given segment of tok mem } z: 0 . . zz − 1; { current segment of tok mem } stat max tok ptr : array [0 . . zz − 1] of 0 . . max toks ; { largest values assumed by tok ptr } tats

45. ⟨ Local variables for initialization 16 ⟩ +≡ zi : 0 . . zz − 1; { to initialize the tok mem indices }

46. ⟨ Set initial values 10 ⟩ +≡

for zi ← 0 to zz − 1 do begin tok start [zi ] ← 0; tok ptr [zi ] ← 0; end;

tok start [zz ] ← 0; { this makes replacement text 0 of length zero }

text ptr ← 1; z ← 1 mod zz ; 47. Four types of identifiers are distinguished by their ilk :

normal identifiers will appear in the Pascal program as ordinary identifiers since they have not been defined to be macros; the corresponding value in the equiv array for such identifiers is a link in a secondary hash table that is used to check whether any two of them agree in their first unambig length characters after underline symbols are removed and lowercase letters are changed to uppercase.

numeric identifiers have been defined to be numeric macros; their equiv value contains the corresponding

numeric value plus 2^{15}. Strings are treated as numeric macros. simple identifiers have been defined to be simple macros; their equiv value points to the corresponding

replacement text. parametric identifiers have been defined to be parametric macros; like simple identifiers, their equiv value

points to the replacement text. define normal = 0 { ordinary identifiers have normal ilk } define numeric = 1 { numeric macros and strings have numeric ilk } define simple = 2 { simple macros have simple ilk } define parametric = 3 { parametric macros have parametric ilk }

48. The names of modules are stored in byte mem together with the identifier names, but a hash table is not used for them because needs to be able to recognize a module name when given a prefix of that name. A conventional binary seach tree is used to retrieve module names, with fields called llink and rlink in place of link and ilk . The root of this tree is rlink [0]. If p is a pointer to a module name, equiv [p] points to its replacement text, just as in simple and parametric macros, unless this replacement text has not yet been defined (in which case equiv [p] = 0).

define llink ≡ link { left link in binary search tree for module names } define rlink ≡ ilk { right link in binary search tree for module names }

⟨ Set initial values 10 ⟩ +≡ rlink [0] ← 0; { the binary search tree starts out with nothing in it } equiv [0] ← 0; { the undefined module has no replacement text }

49. Here is a little procedure that prints the text of a given name. procedure print id (p : name pointer ); { print identifier or module name }

var k: 0 . . max bytes ; { index into byte mem }

w: 0 . . ww − 1; { segment of byte mem } begin if p ≥ name ptr then print (´ ´ ) else begin w ← p mod ww ;

for k ← byte start [p] to byte start [p + ww ] − 1 do print (xchr [byte mem[w, k]]); end;

138  SEARCHING FOR IDENTIFIERS  MANGLE §50

end; 50. Searching for identifiers. The hash table described above is updated by the id lookup procedure, which finds a given identifier and returns a pointer to its index in byte start . If the identifier was not already present, it is inserted with a given ilk code; and an error message is printed if the identifier is being doubly defined.

Because of the way ’s scanning mechanism works, it is most convenient to let id lookup search for an identifier that is present in the buffer array. Two other global variables specify its position in the buffer: the first character is buffer [id first ], and the last is buffer [id loc −1]. Furthermore, if the identifier is really a string, the global variable double chars tells how many of the characters in the buffer appear twice (namely and ), since this additional information makes it easy to calculate the true length of the string. The final double-quote of the string is not included in its “identifier,” but the first one is, so the string length is id loc − id first − double chars − 1.

We have mentioned that normal identifiers belong to two hash tables, one for their true names as they appear in the file and the other when they have been reduced to their first unambig length characters. The hash tables are kept by the method of simple chaining, where the heads of the individual lists appear in the hash and chop hash arrays. If h is a hash code, the primary hash table list starts at hash[h] and proceeds through link pointers; the secondary hash table list starts at chop hash[h] and proceeds through equiv pointers. Of course, the same identifier will probably have two different values of h.

The id lookup procedure uses an auxiliary array called chopped id to contain up to unambig length characters of the current identifier, if it is necessary to compute the secondary hash code. (This array could be declared local to id lookup, but in general we are making all array declarations global in this program, because some compilers and some machine architectures make dynamic array allocation inefficient.) ⟨ Globals in the outer block 9 ⟩ +≡ id first : 0 . . buf size; { where the current identifier begins in the buffer } id loc: 0 . . buf size; { just after the current identifier in the buffer } double chars : 0 . . buf size; { correction to length in case of strings } hash, chop hash: array [0 . . hash size] of sixteen bits ; { heads of hash lists } chopped id : array [0 . . unambig length] of ASCII code; { chopped identifier }

51. Initially all the hash lists are empty. ⟨ Local variables for initialization 16 ⟩ +≡ h: 0 . . hash size; { index into hash-head arrays }

52. ⟨ Set initial values 10 ⟩ +≡

§53  MANGLE  SEARCHING FOR IDENTIFIERS 139

for h ← 0 to hash size − 1 do begin hash[h] ← 0; chop hash[h] ← 0; end; 53. Here now is the main procedure for finding identifiers (and strings). The parameter t is set to normal except when the identifier is a macro name that is just being defined; in the latter case, t will be numeric, simple, or parametric. function id lookup(t : eight bits ): name pointer ; { finds current identifier }

label found , not found ; var c: eight bits ; { byte being chopped }

i: 0 . . buf size; { index into buffer }

h: 0 . . hash size; { hash code }

k: 0 . . max bytes ; { index into byte mem }

w: 0 . . ww − 1; { segment of byte mem }

l: 0 . . buf size; { length of the given identifier }

p, q: name pointer ; { where the identifier is being sought }

s: 0 . . unambig length; { index into chopped id } begin l ← id loc − id first ; { compute the length } ⟨ Compute the hash code h 54 ⟩; ⟨ Compute the name location p 55 ⟩; if (p = name ptr ) ∨ (t ≠ normal ) then ⟨ Update the tables and check for possible errors 57 ⟩; id lookup ← p; end;

54. A simple hash code is used: If the sequence of ASCII codes is c_{1}c_{2} … c_{m}, its hash value will be

(2^{n−1}c_{1} + 2^{n−2}c_{2} + ⋯ + c_{n}) mod hash size.

⟨ Compute the hash code h 54 ⟩ ≡ h ← buffer [id first ]; i ← id first + 1; while i < id loc do

begin h ← (h + h + buffer [i]) mod hash size; incr (i);

end

This code is used in section 53.

55. If the identifier is new, it will be placed in position p = name ptr , otherwise p will point to its existing location. ⟨ Compute the name location p 55 ⟩ ≡

p ← hash[h]; while p ≠ 0 do

begin if length(p) = l then ⟨ Compare name p with current identifier, goto found if equal 56 ⟩; p ← link [p]; end;

p ← name ptr ; { the current identifier is new } link [p] ← hash[h]; hash[h] ← p; { insert p at beginning of hash list }

found :

This code is used in section 53.

56. ⟨ Compare name p with current identifier, goto found if equal 56 ⟩ ≡ begin i ← id first ; k ← byte start [p]; w ← p mod ww ; while (i < id loc) ∧ (buffer [i] = byte mem[w, k]) do

begin incr (i); incr (k);

end; if i = id loc then goto found ; { all characters agree } end

This code is used in section 55.

57. ⟨ Update the tables and check for possible errors 57 ⟩ ≡

begin if ((p ≠ name ptr ) ∧ (t ≠ normal ) ∧ (ilk [p] = normal )) ∨ ((p = name ptr ) ∧ (t = normal ) ∧ (buffer [id first ] ≠ )) then ⟨ Compute the secondary hash code h and put the first characters into the auxiliary array chopped id 58 ⟩;

if p ≠ name ptr then ⟨ Give double-definition error and change p to type t 59 ⟩ else ⟨ Enter a new identifier into the table at position p 61 ⟩; end

This code is used in section 53.

58. The following routine, which is called into play when it is necessary to look at the secondary hash table, computes the same hash function as before (but on the chopped data), and places a zero after the chopped identifier in chopped id to serve as a convenient sentinel. ⟨ Compute the secondary hash code h and put the first characters into the auxiliary array chopped id 58 ⟩ ≡

begin i ← id first ; s ← 0; h ← 0; while (i < id loc) ∧ (s < unambig length) do

begin if buffer [i] ≠ then begin if buffer [i] ≥ then chopped id [s] ← buffer [i] − ´ 40 else chopped id [s] ← buffer [i]; h ← (h + h + chopped id [s]) mod hash size; incr (s); end;

incr (i);

end; chopped id [s] ← 0; end

This code is used in section 57.

59. If a macro has appeared before it was defined, will still work all right; after all, such behavior is typical of the replacement texts for modules, which act very much like macros. However, an undefined numeric macro may not be used on the right-hand side of another numeric macro definition, so finds it simplest to make a blanket rule that macros should be defined before they are used. The following routine gives an error message and also fixes up any damage that may have been caused. ⟨ Give double-definition error and change p to type t 59 ⟩ ≡

{ now p ≠ name ptr and t ≠ normal } begin if ilk [p] = normal then

begin err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); ⟨ Remove p from secondary hash table 60 ⟩; end

else err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); ilk [p] ← t; end

This code is used in section 57.

60. When we have to remove a secondary hash entry, because a normal identifier is changing to another ilk , the hash code h and chopped identifier have already been computed. ⟨ Remove p from secondary hash table 60 ⟩ ≡

q ← chop hash[h]; if q = p then chop hash[h] ← equiv [p] else begin while equiv [q] ≠ p do q ← equiv [q];

equiv [q] ← equiv [p];

end

This code is used in section 59.

61. The following routine could make good use of a generalized pack procedure that puts items into just part of a packed array instead of the whole thing. ⟨ Enter a new identifier into the table at position p 61 ⟩ ≡

begin if (t = normal ) ∧ (buffer [id first ] ≠ ) then

⟨ Check for ambiguity and update secondary hash 62 ⟩; w ← name ptr mod ww ; k ← byte ptr [w]; if k + l > max bytes then overflow (´ ␣ ´ ); if name ptr > max names − ww then overflow (´ ´ ); i ← id first ; { get ready to move the identifier into byte mem } while i < id loc do

begin byte mem[w, k] ← buffer [i]; incr (k); incr (i); end;

byte ptr [w] ← k; byte start [name ptr + ww ] ← k; incr (name ptr ); if buffer [id first ] ≠ then ilk [p] ← t else ⟨ Define and output a new string of the pool 64 ⟩; end

This code is used in section 57.

62. ⟨ Check for ambiguity and update secondary hash 62 ⟩ ≡ begin q ← chop hash[h]; while q ≠ 0 do

begin ⟨ Check if q conflicts with p 63 ⟩;

q ← equiv [q];

end; equiv [p] ← chop hash[h]; chop hash[h] ← p; { put p at front of secondary list } end

This code is used in section 61.

63. ⟨ Check if q conflicts with p 63 ⟩ ≡ begin k ← byte start [q]; s ← 0; w ← q mod ww ; while (k < byte start [q + ww ]) ∧ (s < unambig length) do

begin c ← byte mem[w, k];

if c ≠ then begin if c ≥ then c ← c − ´ 40 ; { convert to uppercase } if chopped id [s] ≠ c then goto not found ; incr (s); end;

incr (k);

end; if (k = byte start [q + ww ]) ∧ (chopped id [s] ≠ 0) then goto not found ; print nl (´ ␣ ␣ ␣ ␣´ ); for k ← byte start [q] to byte start [q + ww ] − 1 do print (xchr [byte mem[w, k]]); error ; q ← 0; { only one conflict will be printed, since equiv [0] = 0 }

not found : end

This code is used in section 62.

64. We compute the string pool check sum by working modulo a prime number that is large but not so large that overflow might occur.

define check sum prime ≡ ´ 3777777667 { 2^{29} − 73 } ⟨ Define and output a new string of the pool 64 ⟩ ≡

begin ilk [p] ← numeric; { strings are like numeric macros } if l − double chars = 2 then { this string is for a single character }

equiv [p] ← buffer [id first + 1] + ´ 100000 else begin equiv [p] ← string ptr + ´ 100000 ; l ← l − double chars − 1;

if l > 99 then err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); incr (string ptr ); write(pool , xchr [ + l div 10], xchr [ + l mod 10]); { output the length } pool check sum ← pool check sum + pool check sum + l; while pool check sum > check sum prime do pool check sum ← pool check sum − check sum prime; i ← id first + 1; while i < id loc do

begin write(pool , xchr [buffer [i]]); { output characters of string }

pool check sum ← pool check sum + pool check sum + buffer [i];

while pool check sum > check sum prime do pool check sum ← pool check sum − check sum prime; if (buffer [i] = ) ∨ (buffer [i] = ) then i ← i + 2

{ omit second appearance of doubled character } else incr (i); end;

write ln(pool ); end;

end

This code is used in section 61.

§65  MANGLE  SEARCHING FOR MODULE NAMES 143

65. Searching for module names. The mod lookup procedure finds the module name mod text [1 . . l] in the search tree, after inserting it if necessary, and returns a pointer to where it was found. ⟨ Globals in the outer block 9 ⟩ +≡ mod text : array [0 . . longest name] of ASCII code; { name being sought for }

66. According to the rules of , no module name should be a proper prefix of another, so a “clean” comparison should occur between any two names. The result of mod lookup is 0 if this prefix condition is violated. An error message is printed when such violations are detected during phase two of .

define less = 0 { the first name is lexicographically less than the second } define equal = 1 { the first name is equal to the second } define greater = 2 { the first name is lexicographically greater than the second } define prefix = 3 { the first name is a proper prefix of the second } define extension = 4 { the first name is a proper extension of the second }

function mod lookup(l : sixteen bits ): name pointer ; { finds module name } label found ; var c: less . . extension; { comparison between two names }

j: 0 . . longest name; { index into mod text }

k: 0 . . max bytes ; { index into byte mem }

w: 0 . . ww − 1; { segment of byte mem }

p: name pointer ; { current node of the search tree }

q: name pointer ; { father of node p } begin c ← greater ; q ← 0; p ← rlink [0]; { rlink [0] is the root of the tree } while p ≠ 0 do

begin ⟨ Set c to the result of comparing the given name to name p 68 ⟩; q ← p; if c = less then p ← llink [q] else if c = greater then p ← rlink [q]

else goto found ; end;

⟨ Enter a new module name into the tree 67 ⟩; found : if c ≠ equal then

begin err print (´ ␣ ␣ ␣ ´ ); p ← 0; end;

mod lookup ← p; end;

67. ⟨ Enter a new module name into the tree 67 ⟩ ≡ w ← name ptr mod ww ; k ← byte ptr [w]; if k + l > max bytes then overflow (´ ␣ ´ ); if name ptr > max names − ww then overflow (´ ´ ); p ← name ptr ; if c = less then llink [q] ← p else rlink [q] ← p; llink [p] ← 0; rlink [p] ← 0; c ← equal ; equiv [p] ← 0; for j ← 1 to l do byte mem[w, k + j − 1] ← mod text [j]; byte ptr [w] ← k + l; byte start [name ptr + ww ] ← k + l; incr (name ptr );

This code is used in section 66.

144  SEARCHING FOR MODULE NAMES  MANGLE §68

68. ⟨ Set c to the result of comparing the given name to name p 68 ⟩ ≡ begin k ← byte start [p]; w ← p mod ww ; c ← equal ; j ← 1; while (k < byte start [p + ww ]) ∧ (j ≤ l) ∧ (mod text [j] = byte mem[w, k]) do

begin incr (k); incr (j); end;

if k = byte start [p + ww ] then if j > l then c ← equal else c ← extension

else if j > l then c ← prefix

else if mod text [j] < byte mem[w, k] then c ← less

else c ← greater ; end

This code is used in sections 66 and 69.

69. The prefix lookup procedure is supposed to find exactly one module name that has mod text [1 . . l] as a prefix. Actually the algorithm silently accepts also the situation that some module name is a prefix of mod text [1 . . l], because the user who painstakingly typed in more than necessary probably doesn’t want to be told about the wasted effort. function prefix lookup(l : sixteen bits ): name pointer ; { finds name extension }

var c: less . . extension; { comparison between two names } count : 0 . . max names ; { the number of hits } j: 0 . . longest name; { index into mod text } k: 0 . . max bytes ; { index into byte mem } w: 0 . . ww − 1; { segment of byte mem } p: name pointer ; { current node of the search tree } q: name pointer ; { another place to resume the search after one branch is done } r: name pointer ; { extension found }

begin q ← 0; p ← rlink [0]; count ← 0; r ← 0; { begin search at root of tree } while p ≠ 0 do

begin ⟨ Set c to the result of comparing the given name to name p 68 ⟩; if c = less then p ← llink [p] else if c = greater then p ← rlink [p]

else begin r ← p; incr (count ); q ← rlink [p]; p ← llink [p];

end; if p = 0 then

begin p ← q; q ← 0;

end; end;

if count ≠ 1 then if count = 0 then err print (´ ␣ ␣ ␣ ␣ ´ ) else err print (´ ␣ ␣ ´ );

§70  MANGLE  TOKENS 145

prefix lookup ← r; { the result will be 0 if there was no match } end; 70. Tokens. Replacement texts, which represent Pascal code in a compressed format, appear in tok mem as mentioned above. The codes in these texts are called ‘tokens’; some tokens occupy two consecutive eightbit byte positions, and the others take just one byte.

If p > 0 points to a replacement text, tok start [p] is the tok mem position of the first eight-bit code of that text. If text link [p] = 0, this is the replacement text for a macro, otherwise it is the replacement text for a module. In the latter case text link [p] is either equal to module flag , which means that there is no further text for this module, or text link [p] points to a continuation of this replacement text; such links are created when several modules have Pascal texts with the same name, and they also tie together all the Pascal texts of unnamed modules. The replacement text pointer for the first unnamed module appears in text link [0], and the most recent such pointer is last unnamed .

define module flag ≡ max texts { final link in module replacement texts } ⟨ Globals in the outer block 9 ⟩ +≡ last unnamed : text pointer ; { most recent replacement text of unnamed module }

71. ⟨ Set initial values 10 ⟩ +≡ last unnamed ← 0; text link [0] ← 0;

72* . If the first byte of a token is less than ´ 200 , the token occupies a single byte. Otherwise we make a sixteen-bit token by combining two consecutive bytes a and b. If ´ 200 ≤ a < ´ 250 , then (a − ´ 200 ) × 2^{8} + b points to an identifier; if ´ 250 ≤ a < ´ 320 , then (a − ´ 250 ) × 2^{8} + b points to a module name; otherwise, i.e., if ´ 320 ≤ a < ´ 400 , then (a − ´ 320 ) × 2^{8} + b is the number of the module in which the current replacement text appears.

Codes less than ´ 200 are 7-bit ASCII codes that represent themselves. In particular, a single-character identifier like ‘x’ will be a one-byte token, while all longer identifiers will occupy two bytes.

Some of the 7-bit ASCII codes will not be present, however, so we can use them for special purposes. The following symbolic names are used:

param denotes insertion of a parameter. This occurs only in the replacement texts of parametric macros,

outside of single-quoted strings in those texts. begin comment denotes , which will become either or . end comment denotes , which will become either or . octal denotes the ´ that precedes an octal constant. hex denotes the that precedes a hexadecimal constant. check sum denotes the that denotes the string pool check sum. join denotes the concatenation of adjacent items with no space or line breaks allowed between them (the

operation of ). double dot denotes ‘ ’ in Pascal. verbatim denotes the that begins a verbatim Pascal string. It is also used for the end of the string. force line denotes the that forces a new line in the Pascal output. define param = 0 { ASCII null code will not appear } define verbatim = ´ 2 { extended ASCII alpha should not appear } define force line = ´ 3 { extended ASCII beta should not appear } define begin comment = ´ 11 { ASCII tab mark will not appear } define end comment = ´ 12 { ASCII line feed will not appear } define octal = ´ 14 { ASCII form feed will not appear } define hex = ´ 15 { ASCII carriage return will not appear } define double dot = ´ 40 { ASCII space will not appear except in strings } define check sum = 1 { this control code should not appear in normal text } define join = ´ 177 { ASCII delete will not appear }

146  TOKENS  MANGLE §73

73. The following procedure is used to enter a two-byte value into tok mem when a replacement text is being generated. procedure store two bytes (x : sixteen bits ); { stores high byte, then low byte }

begin if tok ptr [z] + 2 > max toks then overflow (´ ´ ); tok mem[z, tok ptr [z]] ← x div ´ 400 ; { this could be done by a shift command } tok mem[z, tok ptr [z] + 1] ← x mod ´ 400 ; { this could be done by a logical and } tok ptr [z] ← tok ptr [z] + 2; end;

74. When is being operated in debug mode, it has a procedure to display a replacement text in symbolic form. This procedure has not been spruced up to generate a real great format, but at least the results are not as bad as a memory dump.

debug procedure print repl (p : text pointer ); var k: 0 . . max toks ; { index into tok mem }

a: sixteen bits ; { current byte(s) }

zp: 0 . . zz − 1; { segment of tok mem being accessed } begin if p ≥ text ptr then print (´ ´ ) else begin k ← tok start [p]; zp ← p mod zz ;

while k < tok start [p + zz ] do begin a ← tok mem[zp, k]; if a ≥ ´ 200 then ⟨ Display two-byte token starting with a 75 ⟩ else ⟨ Display one-byte token a 76 ⟩; incr (k); end;

end; end; gubed

75. ⟨ Display two-byte token starting with a 75 ⟩ ≡ begin incr (k); if a < ´ 250 then { identifier or string }

begin a ← (a − ´ 200 ) ∗ ´ 400 + tok mem[zp, k]; print id (a);

if byte mem[a mod ww , byte start [a]] = then print (´ ´ )

else print (´ ␣´ );

end else if a < ´ 320 then { module name }

begin print (´ ´ ); print id ((a − ´ 250 ) ∗ ´ 400 + tok mem[zp, k]); print (´ ´ );

end else begin a ← (a − ´ 320 ) ∗ ´ 400 + tok mem[zp, k]; { module number }

print (´ ´ , xchr [ ], a : 1, ´ ´ , xchr [ ]); { can’t use right brace between debug and gubed } end;

end

This code is used in section 74.

76. ⟨ Display one-byte token a 76 ⟩ ≡

case a of

begin comment : print (´ ´ , xchr [ ]); end comment : print (´ ´ , xchr [ ]); { can’t use right brace between debug and gubed } octal : print (´ ´ ´ ´ ); hex : print (´ ´ ); check sum: print (´ $´ ); param: print (´ #´ ); : print (´ ´ ); verbatim: print (´ ´ ); force line: print (´ ´ ); othercases print (xchr [a]) endcases

This code is used in section 74.

148  STACKS FOR OUTPUT  MANGLE §77

77. Stacks for output. Let’s make sure that our data structures contain enough information to produce the entire Pascal program as desired, by working next on the algorithms that actually do produce that program.

78. The output process uses a stack to keep track of what is going on at different “levels” as the macros are being expanded. Entries on this stack have five parts:

end field is the tok mem location where the replacement text of a particular level will end; byte field is the tok mem location from which the next token on a particular level will be read; name field points to the name corresponding to a particular level; repl field points to the replacement text currently being read at a particular level. mod field is the module number, or zero if this is a macro.

The current values of these five quantities are referred to quite frequently, so they are stored in a separate place instead of in the stack array. We call the current values cur end , cur byte, cur name, cur repl , and cur mod .

The global variable stack ptr tells how many levels of output are currently in progress. The end of all output occurs when the stack is empty, i.e., when stack ptr = 0. ⟨ Types in the outer block 11 ⟩ +≡ output state = record end field : sixteen bits ; { ending location of replacement text }

byte field : sixteen bits ; { present location within replacement text } name field : name pointer ; { byte start index for text being output } repl field : text pointer ; { tok start index for text being output } mod field : 0 . . ´ 27777 ; { module number or zero if not a module } end;

79. define cur end ≡ cur state.end field { current ending location in tok mem } define cur byte ≡ cur state.byte field { location of next output byte in tok mem } define cur name ≡ cur state.name field { pointer to current name being expanded } define cur repl ≡ cur state.repl field { pointer to current replacement text } define cur mod ≡ cur state.mod field { current module number being expanded }

⟨ Globals in the outer block 9 ⟩ +≡ cur state: output state; { cur end , cur byte, cur name, cur repl } stack : array [1 . . stack size] of output state; { info for non-current levels } stack ptr : 0 . . stack size; { first unused location in the output state stack }

80. It is convenient to keep a global variable zo equal to cur repl mod zz . ⟨ Globals in the outer block 9 ⟩ +≡ zo: 0 . . zz − 1; { the segment of tok mem from which output is coming }

81. Parameters must also be stacked. They are placed in tok mem just above the other replacement texts, and dummy parameter ‘names’ are placed in byte start just after the other names. The variables text ptr and tok ptr [z] essentially serve as parameter stack pointers during the output phase, so there is no need for a separate data structure to handle this problem.

§83  MANGLE  STACKS FOR OUTPUT 149

82. There is an implicit stack corresponding to meta-comments that are output via and . But this stack need not be represented in detail, because we only need to know whether it is empty or not. A global variable brace level tells how many items would be on this stack if it were present. ⟨ Globals in the outer block 9 ⟩ +≡ brace level : eight bits ; { current depth of … nesting } 83. To get the output process started, we will perform the following initialization steps. We may assume that text link [0] is nonzero, since it points to the Pascal text in the first unnamed module that generates code; if there are no such modules, there is nothing to output, and an error message will have been generated before we do any of the initialization. ⟨ Initialize the output stacks 83 ⟩ ≡

stack ptr ← 1; brace level ← 0; cur name ← 0; cur repl ← text link [0]; zo ← cur repl mod zz ; cur byte ← tok start [cur repl ]; cur end ← tok start [cur repl + zz ]; cur mod ← 0;

This code is used in section 112.

84. When the replacement text for name p is to be inserted into the output, the following subroutine is called to save the old level of output and get the new one going. procedure push level (p : name pointer ); { suspends the current level }

begin if stack ptr = stack size then overflow (´ ´ )

else begin stack [stack ptr ] ← cur state; { save cur end , cur byte, etc. } incr (stack ptr ); cur name ← p; cur repl ← equiv [p]; zo ← cur repl mod zz ; cur byte ← tok start [cur repl ]; cur end ← tok start [cur repl + zz ]; cur mod ← 0; end;

end;

85. When we come to the end of a replacement text, the pop level subroutine does the right thing: It either moves to the continuation of this replacement text or returns the state to the most recently stacked level. Part of this subroutine, which updates the parameter stack, will be given later when we study the parameter stack in more detail. procedure pop level ; { do this when cur byte reaches cur end }

label exit ;

begin if text link [cur repl ] = 0 then { end of macro expansion } begin if ilk [cur name] = parametric then ⟨ Remove a parameter from the parameter stack 91 ⟩; end

else if text link [cur repl ] < module flag then { link to a continuation } begin cur repl ← text link [cur repl ]; { we will stay on the same level } zo ← cur repl mod zz ; cur byte ← tok start [cur repl ]; cur end ← tok start [cur repl + zz ]; return; end;

decr (stack ptr ); { we will go down to the previous level }

if stack ptr > 0 then begin cur state ← stack [stack ptr ]; zo ← cur repl mod zz ; end;

exit : end;

86. The heart of the output procedure is the get output routine, which produces the next token of output that is not a reference to a macro. This procedure handles all the stacking and unstacking that is necessary. It returns the value number if the next output has a numeric value (the value of a numeric macro or string), in which case cur val has been set to the number in question. The procedure also returns the value module number if the next output begins or ends the replacement text of some module, in which case cur val is that module’s number (if beginning) or the negative of that value (if ending). And it returns the value identifier if the next output is an identifier of length two or more, in which case cur val points to that identifier name.

define number = ´ 200 { code returned by get output when next output is numeric } define module number = ´ 201 { code returned by get output for module numbers } define identifier = ´ 202 { code returned by get output for identifiers }

⟨ Globals in the outer block 9 ⟩ +≡ cur val : integer ; { additional information corresponding to output token } 87. If get output finds that no more output remains, it returns the value zero. function get output : sixteen bits ; { returns next token after macro expansion }

label restart , done, found ; var a: sixteen bits ; { value of current byte }

b: eight bits ; { byte being copied }

bal : sixteen bits ; { excess of versus while copying a parameter } k: 0 . . max bytes ; { index into byte mem } w: 0 . . ww − 1; { segment of byte mem }

begin restart : if stack ptr = 0 then begin a ← 0; goto found ; end;

if cur byte = cur end then begin cur val ← −cur mod ; pop level ; if cur val = 0 then goto restart ; a ← module number ; goto found ; end;

a ← tok mem[zo, cur byte]; incr (cur byte); if a < ´ 200 then { one-byte token }

if a = param then ⟨ Start scanning current macro parameter, goto restart 92 ⟩ else goto found ;

a ← (a − ´ 200 ) ∗ ´ 400 + tok mem[zo, cur byte]; incr (cur byte); if a < ´ 24000 then { ´ 24000 = (´ 250 − ´ 200 ) ∗ ´ 400 }

⟨ Expand macro a and goto found , or goto restart if no output found 89 ⟩; if a < ´ 50000 then { ´ 50000 = (´ 320 − ´ 200 ) ∗ ´ 400 }

⟨ Expand module a − ´ 24000 , goto restart 88 ⟩; cur val ← a − ´ 50000 ; a ← module number ; cur mod ← cur val ;

found : debug if trouble shooting then debug help; gubed get output ← a; end;

88. The user may have forgotten to give any Pascal text for a module name, or the Pascal text may have been associated with a different name by mistake. ⟨ Expand module a − ´ 24000 , goto restart 88 ⟩ ≡

begin a ← a − ´ 24000 ; if equiv [a] ≠ 0 then push level (a) else if a ≠ 0 then

begin print nl (´ ␣ ␣ ␣ ´ ); print id (a); print (´ ´ ); error ; end;

goto restart ; end

This code is used in section 87.

89. ⟨ Expand macro a and goto found , or goto restart if no output found 89 ⟩ ≡ begin case ilk [a] of normal : begin cur val ← a; a ← identifier ;

end; numeric: begin cur val ← equiv [a] − ´ 100000 ; a ← number ;

end; simple: begin push level (a); goto restart ;

end; parametric: begin ⟨ Put a parameter on the parameter stack, or goto restart if error occurs 90 ⟩;

push level (a); goto restart ;

end; othercases confusion(´ ´ ) endcases; goto found ; end

This code is used in section 87.

90. We come now to the interesting part, the job of putting a parameter on the parameter stack. First we pop the stack if necessary until getting to a level that hasn’t ended. Then the next character must be a ‘ ’; and since parentheses are balanced on each level, the entire parameter must be present, so we can copy it without difficulty. ⟨ Put a parameter on the parameter stack, or goto restart if error occurs 90 ⟩ ≡

while (cur byte = cur end ) ∧ (stack ptr > 0) do pop level ; if (stack ptr = 0) ∨ (tok mem[zo, cur byte] ≠ ) then

begin print nl (´ ␣ ␣ ␣ ␣ ␣´ ); print id (a); error ; goto restart ; end;

⟨ Copy the parameter into tok mem 93 ⟩; equiv [name ptr ] ← text ptr ; ilk [name ptr ] ← simple; w ← name ptr mod ww ; k ← byte ptr [w]; debug if k = max bytes then overflow (´ ␣ ´ ); byte mem[w, k] ← # ; incr (k); byte ptr [w] ← k; gubed { this code has set the parameter identifier for debugging printouts } if name ptr > max names − ww then overflow (´ ´ ); byte start [name ptr + ww ] ← k; incr (name ptr ); if text ptr > max texts − zz then overflow (´ ´ ); text link [text ptr ] ← 0; tok start [text ptr + zz ] ← tok ptr [z]; incr (text ptr ); z ← text ptr mod zz

This code is used in section 89.

91. The pop level routine undoes the effect of parameter-pushing when a parameter macro is finished: ⟨ Remove a parameter from the parameter stack 91 ⟩ ≡

begin decr (name ptr ); decr (text ptr ); z ← text ptr mod zz ; stat if tok ptr [z] > max tok ptr [z] then max tok ptr [z] ← tok ptr [z]; tats { the maximum value of tok ptr occurs just before parameter popping } tok ptr [z] ← tok start [text ptr ]; debug decr (byte ptr [name ptr mod ww ]); gubed end

This code is used in section 85.

92. When a parameter occurs in a replacement text, we treat it as a simple macro in position (name ptr −1): ⟨ Start scanning current macro parameter, goto restart 92 ⟩ ≡

begin push level (name ptr − 1); goto restart ;

end

This code is used in section 87.

93. Similarly, a param token encountered as we copy a parameter is converted into a simple macro call for name ptr − 1. Some care is needed to handle cases like macro(#; print (´ # ´ )); the # token will have been changed to param outside of strings, but we still must distinguish ‘real’ parentheses from those in strings.

define app repl (#) ≡ begin if tok ptr [z] = max toks then overflow (´ ´ ); tok mem[z, tok ptr [z]] ← #; incr (tok ptr [z]); end

⟨ Copy the parameter into tok mem 93 ⟩ ≡ bal ← 1; incr (cur byte); { skip the opening ‘ ’ } loop begin b ← tok mem[zo, cur byte]; incr (cur byte);

if b = param then store two bytes (name ptr + ´ 77777 )

else begin if b ≥ ´ 200 then begin app repl (b); b ← tok mem[zo, cur byte]; incr (cur byte); end

else case b of

: incr (bal );

: begin decr (bal ); if bal = 0 then goto done; end;

´ : repeat app repl (b); b ← tok mem[zo, cur byte]; incr (cur byte);

until b = ´ ; { copy string, don’t change bal }

othercases do nothing

endcases; app repl (b); end; end;

done:

This code is used in section 90.

§94  MANGLE  PRODUCING THE OUTPUT 153

94. Producing the output. The get output routine above handles most of the complexity of output generation, but there are two further considerations that have a nontrivial effect on ’s algorithms.

First, we want to make sure that the output is broken into lines not exceeding line length characters per line, where these breaks occur at valid places (e.g., not in the middle of a string or a constant or an identifier, not between ‘ ’ and ‘ ’, not at a ‘ ’ position where quantities are being joined together). Therefore we assemble the output into a buffer before deciding where the line breaks will appear. However, we make very little attempt to make “logical” line breaks that would enhance the readability of the output; people are supposed to read the input of or the TEXed output of , but not the tangled-up output. The only concession to readability is that a break after a semicolon will be made if possible, since commonly used “pretty printing” routines give better results in such cases.

Second, we want to decimalize non-decimal constants, and to combine integer quantities that are added or subtracted, because Pascal doesn’t allow constant expressions in subrange types or in case labels. This

means we want to have a procedure that treats a construction like  as equivalent to ‘  ’, while
also leaving ‘  ’ and ‘  ’ untouched. Consider also ‘  ’ versus ‘  ’. We

shall not combine integers preceding or following , , , , or . Note that if y has been defined to equal −2, we must expand ‘ ’ into ‘ ’; but ‘ ’ can expand into ‘ ’ and we can even change ‘ ’ to ‘ ’ because Pascal has a nonstandard mod operation!

154  PRODUCING THE OUTPUT  MANGLE §95

The following solution to these problems has been adopted: An array out buf contains characters that have been generated but not yet output, and there are three pointers into this array. One of these, out ptr , is the number of characters currently in the buffer, and we will have 1 ≤ out ptr ≤ line length most of the time. The second is break ptr , which is the largest value ≤ out ptr such that we are definitely entitled to end a line by outputting the characters out buf [1 . . (break ptr − 1)]; we will always have break ptr ≤ line length. Finally, semi ptr is either zero or the largest known value of a legal break after a semicolon or comment on the current line; we will always have semi ptr ≤ break ptr . ⟨ Globals in the outer block 9 ⟩ +≡ out buf : array [0 . . out buf size] of ASCII code; { assembled characters } out ptr : 0 . . out buf size; { first available place in out buf } break ptr : 0 . . out buf size; { last breaking place in out buf } semi ptr : 0 . . out buf size; { last semicolon breaking place in out buf } 95. Besides having those three pointers, the output process is in one of several states:

num or id means that the last item in the buffer is a number or identifier, hence a blank space or line

break must be inserted if the next item is also a number or identifier. unbreakable means that the last item in the buffer was followed by the operation that inhibits spaces

between it and the next item. sign means that the last item in the buffer is to be followed by or , depending on whether out app is

positive or negative. sign val means that the decimal equivalent of |out val | should be appended to the buffer. If out val < 0,

or if out val = 0 and last sign < 0, the number should be preceded by a minus sign. Otherwise it should be preceded by the character out sign unless out sign = 0; the out sign variable is either 0 or ␣ or .

sign val sign is like sign val , but also append or afterwards, depending on whether out app is positive

or negative. sign val val is like sign val , but also append the decimal equivalent of out app including its sign, using

last sign in case out app = 0. misc means none of the above.

For example, the output buffer and output state run through the following sequence as we generate characters from ‘ ’:

output out buf  out state out sign out val out app last sign
(  misc
x  num or id
−  sign  −1  −1
15  sign val  −15  −15
+  sign val sign  −15  +1  +1
19  sign val val  −15  +19  +1
−  sign val sign  +4  −1  −1
2  sign val val  +4  −2  −2
)  misc

At each stage we have put as much into the buffer as possible without knowing what is coming next. Examples like ‘ ’ indicate why last sign is needed to associate the proper sign with an output of zero.

In states num or id , unbreakable, and misc the last item in the buffer lies between break ptr and out ptr −1, inclusive; in the other states we have break ptr = out ptr .

The numeric values assigned to num or id , etc., have been chosen to shorten some of the program logic; for example, the program makes use of the fact that sign + 2 = sign val sign.

define misc = 0 { state associated with special characters } define num or id = 1 { state associated with numbers and identifiers } define sign = 2 { state associated with pending or } define sign val = num or id + 2 { state associated with pending sign and value } define sign val sign = sign + 2 { sign val followed by another pending sign } define sign val val = sign val + 2 { sign val followed by another pending value } define unbreakable = sign val val + 1 { state associated with }

⟨ Globals in the outer block 9 ⟩ +≡ out state: eight bits ; { current status of partial output } out val , out app: integer ; { pending values } out sign: ASCII code; { sign to use if appending out val ≥ 0 } last sign: −1 . . +1; { sign to use if appending a zero } 96. During the output process, line will equal the number of the next line to be output. ⟨ Initialize the output buffer 96 ⟩ ≡

out state ← misc; out ptr ← 0; break ptr ← 0; semi ptr ← 0; out buf [0] ← 0; line ← 1;

This code is used in section 112.

97. Here is a routine that is invoked when out ptr > line length or when it is time to flush out the final line. The flush buffer procedure often writes out the line up to the current break ptr position, then moves the remaining information to the front of out buf . However, it prefers to write only up to semi ptr , if the residual line won’t be too long.

define check break ≡

if out ptr > line length then flush buffer

procedure flush buffer ; { writes one line to output file }

var k: 0 . . out buf size; { index into out buf }

b: 0 . . out buf size; { value of break ptr upon entry } begin b ← break ptr ; if (semi ptr ≠ 0) ∧ (out ptr − semi ptr ≤ line length) then break ptr ← semi ptr ; for k ← 1 to break ptr do write(Pascal file, xchr [out buf [k − 1]]); write ln(Pascal file); incr (line); if line mod 100 = 0 then

begin print (´ ´ );

if line mod 500 = 0 then print (line : 1);

update terminal ; { progress report }

end; if break ptr < out ptr then

begin if out buf [break ptr ] = ␣ then begin incr (break ptr ); { drop space at break } if break ptr > b then b ← break ptr ; end;

for k ← break ptr to out ptr − 1 do out buf [k − break ptr ] ← out buf [k]; end;

out ptr ← out ptr − break ptr ; break ptr ← b − break ptr ; semi ptr ← 0; if out ptr > line length then

begin err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); out ptr ← line length; end;

end;

98. ⟨ Empty the last line from the buffer 98 ⟩ ≡ break ptr ← out ptr ; semi ptr ← 0; flush buffer ; if brace level ≠ 0 then err print (´ ␣ ␣ ␣ ␣ ␣ ␣´ , brace level : 1);

This code is used in section 112.

99. Another simple and useful routine appends the decimal equivalent of a nonnegative integer to the output buffer.

define app(#) ≡ begin out buf [out ptr ] ← #; incr (out ptr ); { append a single character } end

procedure app val (v : integer ); { puts v into buffer, assumes v ≥ 0 } var k: 0 . . out buf size; { index into out buf } begin k ← out buf size; { first we put the digits at the very end of out buf } repeat out buf [k] ← v mod 10; v ← v div 10; decr (k); until v = 0; repeat incr (k); app(out buf [k] + ); until k = out buf size; { then we append them, most significant first } end;

100. The output states are kept up to date by the output routines, which are called send out , send val , and send sign. The send out procedure has two parameters: t tells the type of information being sent and v contains the information proper. Some information may also be passed in the array out contrib.

If t = misc then v is a character to be output. If t = str then v is the length of a string or something like ‘ ’ in out contrib. If t = ident then v is the length of an identifier in out contrib. If t = frac then v is the length of a fraction and/or exponent in out contrib. define str = 1 { send out code for a string } define ident = 2 { send out code for an identifier } define frac = 3 { send out code for a fraction }

⟨ Globals in the outer block 9 ⟩ +≡ out contrib: array [1 . . line length] of ASCII code; { a contribution to out buf }

101. A slightly subtle point in the following code is that the user may ask for a join operation (i.e., ) following whatever is being sent out. We will see later that join is implemented in part by calling send out (frac, 0). procedure send out (t : eight bits ; v : sixteen bits ); { outputs v of type t }

label restart ; var k: 0 . . line length; { index into out contrib } begin ⟨ Get the buffer ready for appending the new information 102 ⟩; if t ≠ misc then

for k ← 1 to v do app(out contrib[k]) else app(v); check break ; if (t = misc) ∧ ((v = ) ∨ (v = )) then

begin semi ptr ← out ptr ; break ptr ← out ptr ; end;

if t ≥ ident then out state ← num or id { t = ident or frac } else out state ← misc { t = str or misc } end; 102. Here is where the buffer states for signs and values collapse into simpler states, because we are about to append something that doesn’t combine with the previous integer constants.

We use an ASCII-code trick: Since − 1 = and + 1 = , we have − c = sign of c, when |c| = 1. ⟨ Get the buffer ready for appending the new information 102 ⟩ ≡ restart : case out state of

num or id : if t ≠ frac then begin break ptr ← out ptr ; if t = ident then app( ␣ ); end;

sign: begin app( − out app); check break ; break ptr ← out ptr ;

end; sign val , sign val sign: begin ⟨ Append out val to buffer 103 ⟩;

out state ← out state − 2; goto restart ;

end; sign val val : ⟨ Reduce sign val val to sign val and goto restart 104 ⟩; misc: if t ≠ frac then break ptr ← out ptr ;

othercases do nothing { this is for unbreakable state } endcases

This code is used in section 101.

103. ⟨ Append out val to buffer 103 ⟩ ≡ if (out val < 0) ∨ ((out val = 0) ∧ (last sign < 0)) then app( ) else if out sign > 0 then app(out sign); app val (abs (out val )); check break ;

This code is used in sections 102 and 104.

104. ⟨ Reduce sign val val to sign val and goto restart 104 ⟩ ≡

begin if (t = frac) ∨ (⟨ Contribution is or or or 105 ⟩) then begin ⟨ Append out val to buffer 103 ⟩; out sign ← ; out val ← out app; end

else out val ← out val + out app; out state ← sign val ; goto restart ; end

This code is used in section 102.

105. ⟨ Contribution is or or  or  105 ⟩ ≡

((t = ident ) ∧ (v = 3) ∧ (((out contrib[1] = ) ∧ (out contrib[2] = ) ∧ (out contrib[3] = )) ∨ ((out contrib[1] = ) ∧ (out contrib[2] = ) ∧ (out contrib[3] = )))) ∨ ((t = misc) ∧ ((v = ) ∨ (v = )))

This code is used in section 104.

106. The following routine is called with v = ±1 when a plus or minus sign is appended to the output. It extends Pascal to allow repeated signs (e.g., ‘ ’ is equivalent to ‘ ’), rather than to give an error message. The signs following ‘ ’ in real constants are treated as part of a fraction, so they are not seen by this routine. procedure send sign(v : integer );

begin case out state of

sign, sign val sign: out app ← out app ∗ v; sign val : begin out app ← v; out state ← sign val sign;

end; sign val val : begin out val ← out val + out app; out app ← v; out state ← sign val sign;

end; othercases begin break ptr ← out ptr ; out app ← v; out state ← sign;

end endcases; last sign ← out app; end;

107. When a (signed) integer value is to be output, we call send val .

define bad case = 666 { this is a label used below } procedure send val (v : integer ); { output the (signed) value v }

label bad case, { go here if we can’t keep v in the output state }

exit ;

begin case out state of

num or id : begin ⟨ If previous output was or , goto bad case 110 ⟩; out sign ← ␣ ; out state ← sign val ; out val ← v; break ptr ← out ptr ; last sign ← +1; end;

misc: begin ⟨ If previous output was or , goto bad case 109 ⟩; out sign ← 0; out state ← sign val ; out val ← v; break ptr ← out ptr ; last sign ← +1; end;

⟨ Handle cases of send val when out state contains a sign 108 ⟩

othercases goto bad case

endcases; return;

bad case: ⟨ Append the decimal value of v, with parentheses if negative 111 ⟩; exit : end;

108. ⟨ Handle cases of send val when out state contains a sign 108 ⟩ ≡ sign: begin out sign ← ; out state ← sign val ; out val ← out app ∗ v;

end; sign val : begin out state ← sign val val ; out app ← v;

err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); end;

sign val sign: begin out state ← sign val val ; out app ← out app ∗ v;

end; sign val val : begin out val ← out val + out app; out app ← v;

err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); end;

This code is used in section 107.

109. ⟨ If previous output was or , goto bad case 109 ⟩ ≡

if (out ptr = break ptr + 1) ∧ ((out buf [break ptr ] = ) ∨ (out buf [break ptr ] = )) then

goto bad case

This code is used in section 107.

110. ⟨ If previous output was or , goto bad case 110 ⟩ ≡

if (out ptr = break ptr + 3) ∨ ((out ptr = break ptr + 4) ∧ (out buf [break ptr ] = ␣ )) then if ((out buf [out ptr − 3] = ) ∧ (out buf [out ptr − 2] = ) ∧ (out buf [out ptr − 1] = ))∨ ((out buf [out ptr − 3] = ) ∧ (out buf [out ptr − 2] = ) ∧ (out buf [out ptr − 1] = )) then

goto bad case

This code is used in section 107.

111. ⟨ Append the decimal value of v, with parentheses if negative 111 ⟩ ≡

if v ≥ 0 then

begin if out state = num or id then begin break ptr ← out ptr ; app( ␣ ); end;

app val (v); check break ; out state ← num or id ; end

else begin app( ); app( ); app val (−v); app( ); check break ; out state ← misc;

end

This code is used in section 107.

160  THE BIG OUTPUT SWITCH  MANGLE §112

112. The big output switch. To complete the output process, we need a routine that takes the results of get output and feeds them to send out , send val , or send sign. This procedure ‘send the output ’ will be invoked just once, as follows: ⟨ Phase II: Output the contents of the compressed tables 112 ⟩ ≡

if text link [0] = 0 then begin print nl (´ ␣ ␣ ␣ ␣ ´ ); mark harmless ; end

else begin print nl (´ ␣ ␣ ␣ ´ ); update terminal ; ⟨ Initialize the output stacks 83 ⟩; ⟨ Initialize the output buffer 96 ⟩; send the output ; ⟨ Empty the last line from the buffer 98 ⟩; print nl (´ ´ ); end

This code is used in section 182.

113. A many-way switch is used to send the output:

define get fraction = 2 { this label is used below } procedure send the output ;

label get fraction, { go here to finish scanning a real constant }

reswitch, continue; var cur char : eight bits ; { the latest character received }

k: 0 . . line length; { index into out contrib } j: 0 . . max bytes ; { index into byte mem } w: 0 . . ww − 1; { segment of byte mem } n: integer ; { number being scanned }

begin while stack ptr > 0 do

begin cur char ← get output ; reswitch: case cur char of

0: do nothing ; { this case might arise if output ends unexpectedly } ⟨ Cases related to identifiers 116 ⟩ ⟨ Cases related to constants, possibly leading to get fraction or reswitch 119 ⟩ , : send sign( − cur char ); ⟨ Cases like and 114 ⟩ ´ : ⟨ Send a string, goto reswitch 117 ⟩; ⟨ Other printable characters 115* ⟩: send out (misc, cur char ); ⟨ Cases involving and 121* ⟩ join: begin send out (frac, 0); out state ← unbreakable;

end; verbatim: ⟨ Send verbatim string 118 ⟩; force line: ⟨ Force a line break 122 ⟩; othercases err print (´ ␣ ´ ´ ␣ ␣ ␣ ␣´ , cur char : 1) endcases; goto continue;

§114  MANGLE  THE BIG OUTPUT SWITCH 161

get fraction: ⟨ Special code to finish real constants 120 ⟩; continue: end; end; 114. ⟨ Cases like and 114 ⟩ ≡ and sign: begin out contrib[1] ← ; out contrib[2] ← ; out contrib[3] ← ; send out (ident , 3);

end; not sign: begin out contrib[1] ← ; out contrib[2] ← ; out contrib[3] ← ; send out (ident , 3);

end; set element sign: begin out contrib[1] ← ; out contrib[2] ← ; send out (ident , 2);

end; or sign: begin out contrib[1] ← ; out contrib[2] ← ; send out (ident , 2);

end; left arrow : begin out contrib[1] ← ; out contrib[2] ← ; send out (str , 2);

end; not equal : begin out contrib[1] ← ; out contrib[2] ← ; send out (str , 2);

end; less or equal : begin out contrib[1] ← ; out contrib[2] ← ; send out (str , 2);

end; greater or equal : begin out contrib[1] ← ; out contrib[2] ← ; send out (str , 2);

end; equivalence sign: begin out contrib[1] ← ; out contrib[2] ← ; send out (str , 2);

end; double dot : begin out contrib[1] ← ; out contrib[2] ← ; send out (str , 2);

end;

This code is used in section 113.

115* . Please don’t ask how all of the following characters can actually get through outside of strings. It seems that and cannot actually occur at this point of the program, but they have been included just in case changes.

If is producing code for a Pascal compiler that uses ‘ ’ and ‘ ’ instead of square brackets (e.g., on machines with EBCDIC code), one should remove and from this list and put them into the preceding module in the appropriate way. Similarly, some compilers want ‘ ’ to be converted to ‘ ’. ⟨ Other printable characters 115* ⟩ ≡

, , # , $ , % , , , , , , , , , , , , , , , , , ,

, ` , , , ,

This code is used in section 113.

116. Single-character identifiers represent themselves, while longer ones appear in byte mem. All must be converted to uppercase, with underlines removed. Extremely long identifiers must be chopped.

(Some Pascal compilers work with lowercase letters instead of uppercase. If this module of is changed, it’s also necessary to change from uppercase to lowercase in the modules that are listed in the index under “uppercase”.)

define up to(#) ≡ # − 24, # − 23, # − 22, # − 21, # − 20, # − 19, # − 18, # − 17, # − 16, # − 15, # − 14, # − 13,

# − 12, # − 11, # − 10, # − 9, # − 8, # − 7, # − 6, # − 5, # − 4, # − 3, # − 2, # − 1, #

⟨ Cases related to identifiers 116 ⟩ ≡ , up to( ): begin out contrib[1] ← cur char ; send out (ident , 1);

end; , up to( ): begin out contrib[1] ← cur char − ´ 40 ; send out (ident , 1);

end; identifier : begin k ← 0; j ← byte start [cur val ]; w ← cur val mod ww ;

while (k < max id length) ∧ (j < byte start [cur val + ww ]) do begin incr (k); out contrib[k] ← byte mem[w, j]; incr (j); if out contrib[k] ≥ then out contrib[k] ← out contrib[k] − ´ 40 else if out contrib[k] = then decr (k); end;

send out (ident , k); end;

This code is used in section 113.

117. After sending a string, we need to look ahead at the next character, in order to see if there were two consecutive single-quote marks. Afterwards we go to reswitch to process the next character. ⟨ Send a string, goto reswitch 117 ⟩ ≡

begin k ← 1; out contrib[1] ← ´ ; repeat if k < line length then incr (k);

out contrib[k] ← get output ; until (out contrib[k] = ´ ) ∨ (stack ptr = 0); if k = line length then err print (´ ␣ ␣ ␣ ´ ); send out (str , k); cur char ← get output ; if cur char = ´ then out state ← unbreakable; goto reswitch; end

This code is used in section 113.

118. Sending a verbatim string is similar, but we don’t have to look ahead. ⟨ Send verbatim string 118 ⟩ ≡

begin k ← 0; repeat if k < line length then incr (k);

out contrib[k] ← get output ; until (out contrib[k] = verbatim) ∨ (stack ptr = 0); if k = line length then err print (´ ␣ ␣ ␣ ␣ ´ ); send out (str , k − 1); end

This code is used in section 113.

119. In order to encourage portable software, complains if the constants get dangerously close to the largest value representable on a 32-bit computer (2^{31} − 1).

define digits ≡ , , , , , , , , , ⟨ Cases related to constants, possibly leading to get fraction or reswitch 119 ⟩ ≡ digits : begin n ← 0;

repeat cur char ← cur char − ; if n ≥ ´ 1463146314 then err print (´ ␣ ␣ ␣ ´ ) else n ← 10 ∗ n + cur char ; cur char ← get output ;

until (cur char > ) ∨ (cur char < ); send val (n); k ← 0; if cur char = then cur char ← ; if cur char = then goto get fraction else goto reswitch; end;

check sum: send val (pool check sum); octal : begin n ← 0; cur char ← ;

repeat cur char ← cur char − ; if n ≥ ´ 2000000000 then err print (´ ␣ ␣ ␣ ´ ) else n ← 8 ∗ n + cur char ; cur char ← get output ;

until (cur char > ) ∨ (cur char < ); send val (n); goto reswitch; end;

hex : begin n ← 0; cur char ← ;

repeat if cur char ≥ then cur char ← cur char + 10 − else cur char ← cur char − ; if n ≥ ˝ 8000000 then err print (´ ␣ ␣ ␣ ´ ) else n ← 16 ∗ n + cur char ; cur char ← get output ;

until (cur char > ) ∨ (cur char < ) ∨ ((cur char > ) ∧ (cur char < )); send val (n); goto reswitch; end;

number : send val (cur val ); : begin k ← 1; out contrib[1] ← ; cur char ← get output ;

if cur char = then begin out contrib[2] ← ; send out (str , 2); end

else if (cur char ≥ ) ∧ (cur char ≤ ) then goto get fraction

else begin send out (misc, ); goto reswitch;

end; end;

This code is used in section 113.

120. The following code appears at label ‘get fraction’, when we want to scan to the end of a real constant. The first k characters of a fraction have already been placed in out contrib, and cur char is the next character. ⟨ Special code to finish real constants 120 ⟩ ≡

repeat if k < line length then incr (k); out contrib[k] ← cur char ; cur char ← get output ; if (out contrib[k] = ) ∧ ((cur char = ) ∨ (cur char = )) then

begin if k < line length then incr (k);

out contrib[k] ← cur char ; cur char ← get output ; end

else if cur char = then cur char ← ; until (cur char ≠ ) ∧ ((cur char < ) ∨ (cur char > )); if k = line length then err print (´ ␣ ␣ ␣ ´ ); send out (frac, k); goto reswitch

This code is used in section 113.

121* . Some Pascal compilers do not recognize comments in braces, so the comments must be delimited by ‘ ’ and ‘ ’. In such cases the statement ‘send out (misc, )’ that appears here should be replaced by ‘begin out contrib[1] ← ; out contrib[2] ← ; send out (str , 2); end’, and a similar change should be made to ‘send out (misc, )’.

Note: This is definitely the case with Modula-2, so the change must be made. define send left comment ≡

begin out contrib[1] ← ; out contrib[2] ← ; send out (str , 2); end

define send right comment ≡ begin out contrib[1] ← ; out contrib[2] ← ; send out (str , 2); end

⟨ Cases involving and 121* ⟩ ≡ begin comment : begin send left comment ; incr (brace level );

end; end comment : if brace level > 0 then

begin decr (brace level ); send right comment ;

end else err print (´ ␣ ␣ ´ );

module number : begin send left comment ;

if cur val < 0 then begin send out (misc, ); send val (−cur val ); end

else begin send val (cur val ); send out (misc, );

end; send right comment ; end;

This code is used in section 113.

122. ⟨ Force a line break 122 ⟩ ≡ begin send out (str , 0); { normalize the buffer } while out ptr > 0 do

begin if out ptr ≤ line length then break ptr ← out ptr ;

flush buffer ;

end; out state ← misc; end

This code is used in section 113.

§123  MANGLE  INTRODUCTION TO THE INPUT PHASE 165

123. Introduction to the input phase. We have now seen that will be able to output the full Pascal program, if we can only get that program into the byte memory in the proper format. The input process is something like the output process in reverse, since we compress the text as we read it in and we expand it as we write it out.

There are three main input routines. The most interesting is the one that gets the next token of a Pascal text; the other two are used to scan rapidly past TEX text in the source code. One of the latter routines will jump to the next token that starts with ‘ ’, and the other skips to the end of a Pascal comment.

124. But first we need to consider the low-level routine get line that takes care of merging change file into web file. The get line procedure also updates the line numbers for error messages. ⟨ Globals in the outer block 9 ⟩ +≡ line: integer ; { the number of the current line in the current file } other line: integer ; { the number of the current line in the input file that is not currently being read } temp line: integer ; { used when interchanging line with other line } limit : 0 . . buf size; { the last character position occupied in the buffer } loc: 0 . . buf size; { the next character position to be read from the buffer } input has ended : boolean; { if true, there is no more input } changing : boolean; { if true, the current line is from change file }

125. As we change changing from true to false and back again, we must remember to swap the values of line and other line so that the err print routine will be sure to report the correct line number.

define change changing ≡ changing ← ¬changing ; temp line ← other line; other line ← line; line ← temp line { line ↔ other line }

126. When changing is false, the next line of change file is kept in change buffer [0 . . change limit ], for purposes of comparison with the next line of web file. After the change file has been completely input, we set change limit ← 0, so that no further matches will be made. ⟨ Globals in the outer block 9 ⟩ +≡ change buffer : array [0 . . buf size] of ASCII code; change limit : 0 . . buf size; { the last position occupied in change buffer }

127. Here’s a simple function that checks if the two buffers are different. function lines dont match: boolean;

label exit ;

var k: 0 . . buf size; { index into the buffers }

begin lines dont match ← true;

if change limit ≠ limit then return;

if limit > 0 then

for k ← 0 to limit − 1 do

if change buffer [k] ≠ buffer [k] then return; lines dont match ← false;

166  INTRODUCTION TO THE INPUT PHASE  MANGLE §128

exit : end; 128. Procedure prime the change buffer sets change buffer in preparation for the next matching operation. Since blank lines in the change file are not used for matching, we have (change limit = 0) ∧ ¬changing if and only if the change file is exhausted. This procedure is called only when changing is true; hence error messages will be reported correctly. procedure prime the change buffer ;

label continue, done, exit ;

var k: 0 . . buf size; { index into the buffers }

begin change limit ← 0; { this value will be used if the change file ends } ⟨ Skip over comment lines in the change file; return if end of file 129 ⟩; ⟨ Skip to the next nonblank line; return if end of file 130 ⟩; ⟨ Move buffer and limit to change buffer and change limit 131 ⟩;

exit : end;

129. While looking for a line that begins with in the change file, we allow lines that begin with , as long as they don’t begin with or (which would probably indicate that the change file is fouled up). ⟨ Skip over comment lines in the change file; return if end of file 129 ⟩ ≡

loop begin incr (line); if ¬input ln(change file) then return; if limit < 2 then goto continue; if buffer [0] ≠ then goto continue; if (buffer [1] ≥ ) ∧ (buffer [1] ≤ ) then buffer [1] ← buffer [1] + − ; { lowercasify } if buffer [1] = then goto done; if (buffer [1] = ) ∨ (buffer [1] = ) then

begin loc ← 2; err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); end;

continue: end; done:

This code is used in section 128.

130. Here we are looking at lines following the . ⟨ Skip to the next nonblank line; return if end of file 130 ⟩ ≡

repeat incr (line);

if ¬input ln(change file) then begin err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); return; end;

until limit > 0;

This code is used in section 128.

131. ⟨ Move buffer and limit to change buffer and change limit 131 ⟩ ≡ begin change limit ← limit ; if limit > 0 then

for k ← 0 to limit − 1 do change buffer [k] ← buffer [k]; end

This code is used in sections 128 and 132.

132. The following procedure is used to see if the next change entry should go into effect; it is called only when changing is false. The idea is to test whether or not the current contents of buffer matches the current contents of change buffer . If not, there’s nothing more to do; but if so, a change is called for: All of the text down to the is supposed to match. An error message is issued if any discrepancy is found. Then the procedure prepares to read the next line from change file. procedure check change; { switches to change file if the buffers match }

label exit ; var n: integer ; { the number of discrepancies found }

k: 0 . . buf size; { index into the buffers } begin if lines dont match then return; n ← 0; loop begin change changing ; { now it’s true }

incr (line); if ¬input ln(change file) then

begin err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); change limit ← 0; change changing ;

{ false again } return; end;

⟨ If the current line starts with , report any discrepancies and return 133 ⟩; ⟨ Move buffer and limit to change buffer and change limit 131 ⟩; change changing ; { now it’s false } incr (line); if ¬input ln(web file) then

begin err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); input has ended ← true; return; end;

if lines dont match then incr (n); end;

exit : end;

133. ⟨ If the current line starts with , report any discrepancies and return 133 ⟩ ≡

if limit > 1 then

if buffer [0] = then

begin if (buffer [1] ≥ ) ∧ (buffer [1] ≤ ) then buffer [1] ← buffer [1] + − ;

{ lowercasify } if (buffer [1] = ) ∨ (buffer [1] = ) then

begin loc ← 2; err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); end

else if buffer [1] = then

begin if n > 0 then begin loc ← 2; err print (´ ␣ ␣´ , n : 1, ´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); end; return; end;

end

This code is used in section 132.

134. ⟨ Initialize the input system 134 ⟩ ≡ open input ; line ← 0; other line ← 0; changing ← true; prime the change buffer ; change changing ; limit ← 0; loc ← 1; buffer [0] ← ␣ ; input has ended ← false;

This code is used in section 182.

135. The get line procedure is called when loc > limit ; it puts the next line of merged input into the buffer and updates the other variables appropriately. A space is placed at the right end of the line. procedure get line; { inputs the next line }

label restart ; begin restart : if changing then ⟨ Read from change file and maybe turn off changing 137 ⟩; if ¬changing then

begin ⟨ Read from web file and maybe turn on changing 136 ⟩;

if changing then goto restart ;

end; loc ← 0; buffer [limit ] ← ␣ ; end;

136. ⟨ Read from web file and maybe turn on changing 136 ⟩ ≡ begin incr (line); if ¬input ln(web file) then input has ended ← true else if limit = change limit then

if buffer [0] = change buffer [0] then

if change limit > 0 then check change; end

This code is used in section 135.

137. ⟨ Read from change file and maybe turn off changing 137 ⟩ ≡ begin incr (line); if ¬input ln(change file) then

begin err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); buffer [0] ← ; buffer [1] ← ; limit ← 2; end;

if limit > 1 then { check if the change has ended }

if buffer [0] = then

begin if (buffer [1] ≥ ) ∧ (buffer [1] ≤ ) then buffer [1] ← buffer [1] + − ;

{ lowercasify } if (buffer [1] = ) ∨ (buffer [1] = ) then

begin loc ← 2; err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); end

else if buffer [1] = then begin prime the change buffer ; change changing ; end;

end; end

This code is used in section 135.

138. At the end of the program, we will tell the user if the change file had a line that didn’t match any relevant line in web file. ⟨ Check that all changes have been read 138 ⟩ ≡

if change limit ≠ 0 then { changing is false } begin for loc ← 0 to change limit do buffer [loc] ← change buffer [loc]; limit ← change limit ; changing ← true; line ← other line; loc ← change limit ; err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); end

This code is used in section 183.

139. Important milestones are reached during the input phase when certain control codes are sensed. Control codes in begin with ‘ ’, and the next character identifies the code. Some of these are of interest

only to , so ignores them; the others are converted by into internal code numbers by the control code function below. The ordering of these internal code numbers has been chosen to simplify the program logic; larger numbers are given to the control codes that denote more significant milestones.

define ignore = 0 { control code of no interest to } define control text = ´ 203 { control code for ‘ ’, ‘ ’, etc. } define format = ´ 204 { control code for ‘ ’ } define definition = ´ 205 { control code for ‘ ’ } define begin Pascal = ´ 206 { control code for ‘ ’ } define module name = ´ 207 { control code for ‘ ’ } define new module = ´ 210 { control code for ‘ ␣’ and ‘ ’ }

function control code(c : ASCII code): eight bits ; { convert c after }

begin case c of

: control code ← ; { ‘quoted’ at sign } ´ : control code ← octal ; { precedes octal constant } : control code ← hex ; { precedes hexadecimal constant } $ : control code ← check sum; { string pool check sum } ␣ , tab mark : control code ← new module; { beginning of a new module } : begin print (´ ´ , module count + 1 : 1); update terminal ; { print a progress report }

control code ← new module; { beginning of a new module } end;

, : control code ← definition; { macro definition } , : control code ← format ; { format definition } : control code ← begin comment ; { begin-comment delimiter } : control code ← end comment ; { end-comment delimiter } , : control code ← begin Pascal ; { Pascal text in unnamed module } , , , , : control code ← control text ; { control text to be ignored } : control code ← join; { concatenate two tokens } : control code ← module name; { beginning of a module name } : control code ← verbatim; { beginning of Pascal verbatim mode } : control code ← force line; { force a new line in Pascal output } othercases control code ← ignore { ignore all other cases } endcases; end; 140. The skip ahead procedure reads through the input at fairly high speed until finding the next nonignorable control code, which it returns. function skip ahead : eight bits ; { skip to next control code }

label done;

var c: eight bits ; { control code found }

begin loop

begin if loc > limit then begin get line;

if input has ended then

begin c ← new module; goto done;

end; end;

buffer [limit + 1] ← ;

while buffer [loc] ≠ do incr (loc);

if loc ≤ limit then begin loc ← loc + 2; c ← control code(buffer [loc − 1]); if (c ≠ ignore) ∨ (buffer [loc − 1] = ) then goto done; end; end;

done: skip ahead ← c; end;

141. The skip comment procedure reads through the input at somewhat high speed until finding the first unmatched right brace or until coming to the end of the file. It ignores characters following ‘ ’ characters, since all braces that aren’t nested are supposed to be hidden in that way. For example, consider the process of skipping the first comment below, where the string containing the right brace has been typed as ` ´ in the file. procedure skip comment ; { skips to next unmatched ‘ ’ }

label exit ;

var bal : eight bits ; { excess of left braces }

c: ASCII code; { current character } begin bal ← 0; loop begin if loc > limit then

begin get line;

if input has ended then

begin err print (´ ␣ ␣ ␣ ␣ ´ ); return; end; end;

c ← buffer [loc]; incr (loc); ⟨ Do special things when c = , , , ; return at end 142* ⟩; end;

exit : end; 142* . ⟨ Do special things when c = , , , ; return at end 142* ⟩ ≡

if c = then begin c ← buffer [loc]; if (c ≠ ␣ ) ∧ (c ≠ tab mark ) ∧ (c ≠ ) ∧ (c ≠ ) ∧ (c ≠ ) then incr (loc) else begin err print (´ ␣ ␣ ␣ ␣ ´ ); decr (loc); return;

end end

else if (c = ) ∧ (buffer [loc] ≠ ) then incr (loc)

else if (c = ) ∧ (buffer [loc] = ) then begin incr (bal ); incr (loc); end

else if (c = ) ∧ (buffer [loc] = ) then begin incr (loc); if bal = 0 then return; decr (bal ); end

This code is used in section 141.

172  INPUTTING THE NEXT TOKEN  MANGLE §143

143. Inputting the next token. As stated above, ’s most interesting input procedure is the get next routine that inputs the next token. However, the procedure isn’t especially difficult.

In most cases the tokens output by get next have the form used in replacement texts, except that two-byte tokens are not produced. An identifier that isn’t one letter long is represented by the output ‘identifier ’, and in such a case the global variables id first and id loc will have been set to the appropriate values needed by the id lookup procedure. A string that begins with a double-quote is also considered an identifier , and in such a case the global variable double chars will also have been set appropriately. Control codes produce the corresponding output of the control code function above; and if that code is module name, the value of cur module will point to the byte start entry for that module name.

Another global variable, scanning hex , is true during the time that the letters through should be treated as if they were digits. ⟨ Globals in the outer block 9 ⟩ +≡ cur module: name pointer ; { name of module just scanned } scanning hex : boolean; { are we scanning a hexadecimal constant? }

144. ⟨ Set initial values 10 ⟩ +≡ scanning hex ← false;

145* . At the top level, get next is a multi-way switch based on the next character in the input buffer. A new module code is inserted at the very end of the input file. function get next : eight bits ; { produces the next input token }

label restart , done, found ; var c: eight bits ; { the current character }

d: eight bits ; { the next character }

j, k: 0 . . longest name; { indices into mod text } begin restart : if loc > limit then

begin get line;

if input has ended then

begin c ← new module; goto found ; end;

end; c ← buffer [loc]; incr (loc); if scanning hex then ⟨ Go to found if c is a hexadecimal digit, otherwise set scanning hex ← false 146 ⟩;

case c of

, up to( ), , up to( ): ⟨ Get an identifier 148 ⟩; : ⟨ Get a preprocessed string 149 ⟩; : ⟨ Get control code and possible module name 150 ⟩; ⟨ Compress two-symbol combinations like ‘ ’ 147* ⟩ ␣ , tab mark : goto restart ; { ignore spaces and tabs }

othercases do nothing

endcases; found : debug if trouble shooting then debug help; gubed

get next ← c; end;

146. ⟨ Go to found if c is a hexadecimal digit, otherwise set scanning hex ← false 146 ⟩ ≡ if ((c ≥ ) ∧ (c ≤ )) ∨ ((c ≥ ) ∧ (c ≤ )) then goto found else scanning hex ← false

This code is used in section 145*.

§147  MANGLE  INPUTTING THE NEXT TOKEN 173

147* . Note that the following code substitutes and for the respective combinations ‘ ’ and ‘ ’. Explicit braces should be used for TEX comments in Pascal text.

define compress (#) ≡

begin if loc ≤ limit then begin c ← #; incr (loc); end; end

⟨ Compress two-symbol combinations like ‘ ’ 147* ⟩ ≡ : if buffer [loc] = then compress (double dot )

else if buffer [loc] = then compress ( ); : if buffer [loc] = then compress (left arrow ); : if buffer [loc] = then compress (equivalence sign); : if buffer [loc] = then compress (greater or equal ); : if buffer [loc] = then compress (less or equal )

else if buffer [loc] = then compress (not equal ); : if buffer [loc] = then

begin incr (loc); skip comment ; goto restart ;

end else if buffer [loc] = then compress ( );

This code is used in section 145*.

148. We have to look at the preceding character to make sure this isn’t part of a real constant, before trying to find an identifier starting with ‘ ’ or ‘ ’. ⟨ Get an identifier 148 ⟩ ≡

begin if ((c = ) ∨ (c = )) ∧ (loc > 1) then

if (buffer [loc − 2] ≤ ) ∧ (buffer [loc − 2] ≥ ) then c ← 0; if c ≠ 0 then

begin decr (loc); id first ← loc; repeat incr (loc); d ← buffer [loc]; until ((d < ) ∨ ((d > ) ∧ (d < )) ∨ ((d > ) ∧ (d < )) ∨ (d > )) ∧ (d ≠ ); if loc > id first + 1 then

begin c ← identifier ; id loc ← loc; end; end

else c ← ; { exponent of a real constant } end

This code is used in section 145*.

149. A string that starts and ends with double-quote marks is converted into an identifier that behaves like a numeric macro by means of the following piece of the program. ⟨ Get a preprocessed string 149 ⟩ ≡

begin double chars ← 0; id first ← loc − 1; repeat d ← buffer [loc]; incr (loc);

if (d = ) ∨ (d = ) then

if buffer [loc] = d then begin incr (loc); d ← 0; incr (double chars ); end

else begin if d = then err print (´ ␣ ␣ ␣ ␣ ´ )

end else if loc > limit then

begin err print (´ ␣ ␣ ␣ ´ ´ ␣ ´ ); d ← ; end;

until d = ; id loc ← loc − 1; c ← identifier ; end

This code is used in section 145*.

150. After an sign has been scanned, the next character tells us whether there is more work to do. ⟨ Get control code and possible module name 150 ⟩ ≡

begin c ← control code(buffer [loc]); incr (loc); if c = ignore then goto restart else if c = hex then scanning hex ← true

else if c = module name then ⟨ Scan the module name and make cur module point to it 151 ⟩

else if c = control text then begin repeat c ← skip ahead ; until c ≠ ; if buffer [loc − 1] ≠ then err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); goto restart ; end;

end

This code is used in section 145*.

151. ⟨ Scan the module name and make cur module point to it 151 ⟩ ≡ begin ⟨ Put module name into mod text [1 . . k] 153 ⟩; if k > 3 then

begin if (mod text [k] = ) ∧ (mod text [k − 1] = ) ∧ (mod text [k − 2] = ) then

cur module ← prefix lookup(k − 3) else cur module ← mod lookup(k); end

else cur module ← mod lookup(k); end

This code is used in section 150.

152. Module names are placed into the mod text array with consecutive spaces, tabs, and carriage-returns replaced by single spaces. There will be no spaces at the beginning or the end. (We set mod text [0] ← ␣ to facilitate this, since the mod lookup routine uses mod text [1] as the first character of the name.) ⟨ Set initial values 10 ⟩ +≡

mod text [0] ← ␣ ; 153. ⟨ Put module name into mod text [1 . . k] 153 ⟩ ≡

k ← 0; loop begin if loc > limit then

begin get line;

if input has ended then

begin err print (´ ␣ ␣ ␣ ␣ ␣ ´ ); goto done; end;

end; d ← buffer [loc]; ⟨ If end of name, goto done 154 ⟩; incr (loc); if k < longest name − 1 then incr (k); if (d = ␣ ) ∨ (d = tab mark ) then

begin d ← ␣ ;

if mod text [k − 1] = ␣ then decr (k);

end; mod text [k] ← d; end;

done: ⟨ Check for overlong name 155 ⟩;

if (mod text [k] = ␣ ) ∧ (k > 0) then decr (k);

This code is used in section 151.

154. ⟨ If end of name, goto done 154 ⟩ ≡

if d = then begin d ← buffer [loc + 1]; if d = then

begin loc ← loc + 2; goto done;

end; if (d = ␣ ) ∨ (d = tab mark ) ∨ (d = ) then

begin err print (´ ␣ ␣ ␣ ´ ´ ␣ ´ ); goto done; end;

incr (k); mod text [k] ← ; incr (loc); { now d = buffer [loc] again } end

This code is used in section 153.

155. ⟨ Check for overlong name 155 ⟩ ≡

if k ≥ longest name − 2 then begin print nl (´ ␣ ␣ ␣ ␣ ␣´ ); for j ← 1 to 25 do print (xchr [mod text [j]]); print (´ ´ ); mark harmless ; end

This code is used in section 153.

176  SCANNING A NUMERIC DEFINITION  MANGLE §156

156. Scanning a numeric definition. When looks at the Pascal text following the ‘ ’ of a numeric macro definition, it calls on the precedure scan numeric(p), where p points to the name that is to be defined. This procedure evaluates the right-hand side, which must consist entirely of integer constants and defined numeric macros connected with and signs (no parentheses). It also sets the global variable next control to the control code that terminated this definition.

A definition ends with the control codes definition, format , module name, begin Pascal , and new module, all of which can be recognized by the fact that they are the largest values get next can return.

define end of definition(#) ≡ (# ≥ format ) { is # a control code ending a definition? } ⟨ Globals in the outer block 9 ⟩ +≡ next control : eight bits ; { control code waiting to be acted upon }

157. The evaluation of a numeric expression makes use of two variables called the accumulator and the next sign. At the beginning, accumulator is zero and next sign is +1. When a or is scanned, next sign is multiplied by the value of that sign. When a numeric value is scanned, it is multiplied by next sign and added to the accumulator , then next sign is reset to +1.

define add in(#) ≡ begin accumulator ← accumulator + next sign ∗ (#); next sign ← +1; end

procedure scan numeric(p : name pointer ); { defines numeric macros } label reswitch, done; var accumulator : integer ; { accumulates sums }

next sign: −1 . . +1; { sign to attach to next value } q: name pointer ; { points to identifiers being evaluated } val : integer ; { constants being evaluated }

begin ⟨ Set accumulator to the value of the right-hand side 158 ⟩;

if abs (accumulator ) ≥ ´ 100000 then begin err print (´ ␣ ␣ ␣ ␣´ , accumulator : 1); accumulator ← 0; end;

equiv [p] ← accumulator + ´ 100000 ; { name p now is defined to equal accumulator }

end;

§158  MANGLE  SCANNING A NUMERIC DEFINITION 177

158. ⟨ Set accumulator to the value of the right-hand side 158 ⟩ ≡ accumulator ← 0; next sign ← +1; loop begin next control ← get next ; reswitch: case next control of

digits : begin ⟨ Set val to value of decimal constant, and set next control to the following token 160 ⟩; add in(val ); goto reswitch; end;

octal : begin ⟨ Set val to value of octal constant, and set next control to the following token 161 ⟩; add in(val ); goto reswitch; end;

hex : begin ⟨ Set val to value of hexadecimal constant, and set next control to the following token 162 ⟩; add in(val ); goto reswitch; end;

identifier : begin q ← id lookup(normal );

if ilk [q] ≠ numeric then begin next control ← ; goto reswitch; { leads to error } end;

add in(equiv [q] − ´ 100000 ); end;

: do nothing ;

: next sign ← −next sign;

format , definition, module name, begin Pascal , new module: goto done;

: err print (´ ␣ ␣ ␣ ␣ ␣ ´ );

othercases ⟨ Signal error, flush rest of the definition 159 ⟩

endcases;

end; done:

This code is used in section 157.

159. ⟨ Signal error, flush rest of the definition 159 ⟩ ≡ begin err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); repeat next control ← skip ahead until end of definition(next control ); if next control = module name then

begin { we want to scan the module name too }

loc ← loc − 2; next control ← get next ;

end; accumulator ← 0; goto done; end

This code is used in section 158.

160. ⟨ Set val to value of decimal constant, and set next control to the following token 160 ⟩ ≡ val ← 0; repeat val ← 10 ∗ val + next control − ; next control ← get next ; until (next control > ) ∨ (next control < )

This code is used in section 158.

161. ⟨ Set val to value of octal constant, and set next control to the following token 161 ⟩ ≡ val ← 0; next control ← ; repeat val ← 8 ∗ val + next control − ; next control ← get next ; until (next control > ) ∨ (next control < )

This code is used in section 158.

162. ⟨ Set val to value of hexadecimal constant, and set next control to the following token 162 ⟩ ≡ val ← 0; next control ← ; repeat if next control ≥ then next control ← next control + + 10 − ;

val ← 16 ∗ val + next control − ; next control ← get next ; until (next control > ) ∨ (next control < ) ∨ ((next control > ) ∧ (next control < ))

This code is used in section 158.

§163  MANGLE  SCANNING A MACRO DEFINITION 179

163. Scanning a macro definition. The rules for generating the replacement texts corresponding to simple macros, parametric macros, and Pascal texts of a module are almost identical, so a single procedure is used for all three cases. The differences are that

a) The sign # denotes a parameter only when it appears outside of strings in a parametric macro; otherwise it stands for the ASCII character #. (This is not used in standard Pascal, but some Pascals allow, for example, ‘ #’ after a certain kind of file name.)

b) Module names are not allowed in simple macros or parametric macros; in fact, the appearance of a module name terminates such macros and denotes the name of the current module.

c) The symbols and and are not allowed after module names, while they terminate macro definitions.

164. Therefore there is a procedure scan repl whose parameter t specifies either simple or parametric or module name. After scan repl has acted, cur repl text will point to the replacement text just generated, and next control will contain the control code that terminated the activity. ⟨ Globals in the outer block 9 ⟩ +≡ cur repl text : text pointer ; { replacement text formed by scan repl }

165. procedure scan repl (t : eight bits ); { creates a replacement text }

label continue, done, found ; var a: sixteen bits ; { the current token }

b: ASCII code; { a character from the buffer } bal : eight bits ; { left parentheses minus right parentheses }

begin bal ← 0; loop begin continue: a ← get next ;

case a of

: incr (bal ); : if bal = 0 then err print (´ ␣ ␣ ´ )

else decr (bal ); ´ : ⟨ Copy a string from the buffer to tok mem 168 ⟩; # : if t = parametric then a ← param; ⟨ In cases that a is a non-ASCII token (identifier , module name, etc.), either process it and change a to

a byte that should be stored, or goto continue if a should be ignored, or goto done if a signals the end of this replacement text 167 ⟩

othercases do nothing

endcases; app repl (a); { store a in tok mem } end;

done: next control ← a; ⟨ Make sure the parentheses balance 166 ⟩; if text ptr > max texts − zz then overflow (´ ´ ); cur repl text ← text ptr ; tok start [text ptr + zz ] ← tok ptr [z]; incr (text ptr ); if z = zz − 1 then z ← 0 else incr (z); end;

180  SCANNING A MACRO DEFINITION  MANGLE §166

166. ⟨ Make sure the parentheses balance 166 ⟩ ≡

if bal > 0 then begin if bal = 1 then err print (´ ␣ ␣ ´ ) else err print (´ ␣ ␣´ , bal : 1, ´ ␣ ´ ´ ´ ); while bal > 0 do

begin app repl ( ); decr (bal );

end; end

This code is used in section 165.

167. ⟨ In cases that a is a non-ASCII token (identifier , module name, etc.), either process it and change a to a byte that should be stored, or goto continue if a should be ignored, or goto done if a signals the end of this replacement text 167 ⟩ ≡

identifier : begin a ← id lookup(normal ); app repl ((a div ´ 400 ) + ´ 200 ); a ← a mod ´ 400 ;

end; module name: if t ≠ module name then goto done

else begin app repl ((cur module div ´ 400 ) + ´ 250 ); a ← cur module mod ´ 400 ;

end; verbatim: ⟨ Copy verbatim string from the buffer to tok mem 169 ⟩; definition, format , begin Pascal : if t ≠ module name then goto done

else begin err print (´ ␣ ´ , xchr [buffer [loc − 1]], ´ ␣ ␣ ␣ ␣ ␣ ´ ); goto continue;

end; new module: goto done;

This code is used in section 165.

168. ⟨ Copy a string from the buffer to tok mem 168 ⟩ ≡ begin b ← ´ ; loop begin app repl (b);

if b = then if buffer [loc] = then incr (loc) { store only one } else err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ );

if loc = limit then begin err print (´ ␣ ␣ ´ ´ ␣ ´ ); buffer [loc] ← ´ ; buffer [loc + 1] ← 0; end;

b ← buffer [loc]; incr (loc); if b = ´ then

begin if buffer [loc] ≠ ´ then goto found

else begin incr (loc); app repl ( ´ );

end; end;

end; found : end { now a holds the final ´ that will be stored }

This code is used in section 165.

169. ⟨ Copy verbatim string from the buffer to tok mem 169 ⟩ ≡ begin app repl (verbatim); buffer [limit + 1] ← ; while buffer [loc] ≠ do

begin app repl (buffer [loc]); incr (loc); if loc < limit then

if (buffer [loc] = ) ∧ (buffer [loc + 1] = ) then begin app repl ( ); loc ← loc + 2; end;

end; if loc ≥ limit then err print (´ ␣ ␣ ␣ ´ ´ ␣ ´ ) else if buffer [loc + 1] ≠ then err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); loc ← loc + 2; end { another verbatim byte will be stored, since a = verbatim }

This code is used in section 167.

170. The following procedure is used to define a simple or parametric macro, just after the ‘ ’ of its definition has been scanned. procedure define macro(t : eight bits );

182  SCANNING A MODULE  MANGLE §171

var p: name pointer ; { the identifier being defined } begin p ← id lookup(t); scan repl (t); equiv [p] ← cur repl text ; text link [cur repl text ] ← 0; end; 171. Scanning a module. The scan module procedure starts when ‘ ␣’ or ‘ ’ has been sensed in the input, and it proceeds until the end of that module. It uses module count to keep track of the current module number; with luck, and will both assign the same numbers to modules. ⟨ Globals in the outer block 9 ⟩ +≡ module count : 0 . . ´ 27777 ; { the current module number }

172. The top level of scan module is trivial. procedure scan module;

label continue, done, exit ;

var p: name pointer ; { module name for the current module }

begin incr (module count ); ⟨ Scan the definition part of the current module 173 ⟩; ⟨ Scan the Pascal part of the current module 175 ⟩;

exit : end;

173. ⟨ Scan the definition part of the current module 173 ⟩ ≡ next control ← 0; loop begin continue: while next control ≤ format do

begin next control ← skip ahead ; if next control = module name then

begin { we want to scan the module name too } loc ← loc − 2; next control ← get next ; end; end;

if next control ≠ definition then goto done; next control ← get next ; { get identifier name } if next control ≠ identifier then

begin err print (´ ␣ ␣ ␣ ␣ ␣ ␣´ , ´ ␣ ␣ ␣ ␣ ´ ); goto continue; end;

next control ← get next ; { get token after the identifier } if next control = then

begin scan numeric(id lookup(numeric)); goto continue;

end else if next control = equivalence sign then

begin define macro(simple); goto continue; end

else ⟨ If the next text is ‘(#) ≡’, call define macro and goto continue 174 ⟩; err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); end;

done:

This code is used in section 172.

§174  MANGLE  SCANNING A MODULE 183

174. ⟨ If the next text is ‘(#) ≡’, call define macro and goto continue 174 ⟩ ≡

if next control = then begin next control ← get next ; if next control = # then

begin next control ← get next ; if next control = then

begin next control ← get next ; if next control = then

begin err print (´ ␣ ␣ ␣ ␣ ´ ); next control ← equivalence sign; end;

if next control = equivalence sign then begin define macro(parametric); goto continue; end; end; end;

end;

This code is used in section 173.

175. ⟨ Scan the Pascal part of the current module 175 ⟩ ≡

case next control of

begin Pascal : p ← 0; module name: begin p ← cur module;

⟨ Check that = or ≡ follows this module name, otherwise return 176 ⟩; end;

othercases return

endcases; ⟨ Insert the module number into tok mem 177 ⟩; scan repl (module name); { now cur repl text points to the replacement text } ⟨ Update the data structure so that the replacement text is accessible 178 ⟩;

This code is used in section 172.

176. ⟨ Check that = or ≡ follows this module name, otherwise return 176 ⟩ ≡ repeat next control ← get next ; until next control ≠ ; { allow optional ‘ ’ } if (next control ≠ ) ∧ (next control ≠ equivalence sign) then

begin err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); repeat next control ← skip ahead ; until next control = new module; return; end

This code is used in section 175.

177. ⟨ Insert the module number into tok mem 177 ⟩ ≡ store two bytes (´ 150000 + module count ); { ´ 150000 = ´ 320 ∗ ´ 400 }

This code is used in section 175.

178. ⟨ Update the data structure so that the replacement text is accessible 178 ⟩ ≡

if p = 0 then { unnamed module } begin text link [last unnamed ] ← cur repl text ; last unnamed ← cur repl text ; end

else if equiv [p] = 0 then equiv [p] ← cur repl text { first module of this name }

else begin p ← equiv [p]; while text link [p] < module flag do p ← text link [p]; { find end of list } text link [p] ← cur repl text ; end;

text link [cur repl text ] ← module flag ; { mark this replacement text as a nonmacro }

This code is used in section 175.

§179  MANGLE  DEBUGGING 185

179. Debugging. The Pascal debugger with which was developed allows breakpoints to be set, and variables can be read and changed, but procedures cannot be executed. Therefore a ‘debug help’ procedure has been inserted in the main loops of each phase of the program; when ddt and dd are set to appropriate values, symbolic printouts of various tables will appear.

The idea is to set a breakpoint inside the debug help routine, at the place of ‘breakpoint :’ below. Then when debug help is to be activated, set trouble shooting equal to true. The debug help routine will prompt you for values of ddt and dd , discontinuing this when ddt ≤ 0; thus you type 2n + 1 integers, ending with zero or a negative number. Then control either passes to the breakpoint, allowing you to look at and/or change variables (if you typed zero), or to exit the routine (if you typed a negative value).

Another global variable, debug cycle, can be used to skip silently past calls on debug help. If you set debug cycle > 1, the program stops only every debug cycle times debug help is called; however, any error stop will set debug cycle to zero. ⟨ Globals in the outer block 9 ⟩ +≡

debug trouble shooting : boolean; { is debug help wanted? } ddt : integer ; { operation code for the debug help routine } dd : integer ; { operand in procedures performed by debug help } debug cycle: integer ; { threshold for debug help stopping } debug skipped : integer ; { we have skipped this many debug help calls } term in: text file; { the user’s terminal as an input file }

gubed

180. The debugging routine needs to read from the user’s terminal. ⟨ Set initial values 10 ⟩ +≡

debug trouble shooting ← true; debug cycle ← 1; debug skipped ← 0;

trouble shooting ← false; debug cycle ← 99999; { use these when it almost works }

reset (term in, ´ ´ , ´ ´ ); { open term in as the terminal, don’t do a get }

gubed

186  DEBUGGING  MANGLE §181

181. define breakpoint = 888 { place where a breakpoint is desirable } debug procedure debug help; { routine to display various things } label breakpoint , exit ; var k: integer ; { index into various arrays } begin incr (debug skipped ); if debug skipped < debug cycle then return; debug skipped ← 0; loop begin write(term out , ´ #´ ); update terminal ; { prompt }

read (term in, ddt ); { read a list of integers } if ddt < 0 then return else if ddt = 0 then

begin goto breakpoint ; { go to every label at least once } breakpoint : ddt ← 0;

end else begin read (term in, dd );

case ddt of

1: print id (dd ); 2: print repl (dd ); 3: for k ← 1 to dd do print (xchr [buffer [k]]); 4: for k ← 1 to dd do print (xchr [mod text [k]]); 5: for k ← 1 to out ptr do print (xchr [out buf [k]]); 6: for k ← 1 to dd do print (xchr [out contrib[k]]); othercases print (´ ´ ) endcases; end;

end; exit : end;

gubed

§182  MANGLE  THE MAIN PROGRAM 187

182. The main program. We have defined plenty of procedures, and it is time to put the last pieces of the puzzle in place. Here is where starts, and where it ends.

begin initialize; ⟨ Initialize the input system 134 ⟩; print ln(banner ); { print a “banner line” } ⟨ Phase I: Read all the user’s text and compress it into tok mem 183 ⟩; stat for zo ← 0 to zz − 1 do max tok ptr [zo] ← tok ptr [zo]; tats ⟨ Phase II: Output the contents of the compressed tables 112 ⟩;

end of TANGLE : if string ptr > 128 then ⟨ Finish off the string pool file 184 ⟩;

stat ⟨ Print statistics about memory usage 186 ⟩; tats { here files should be closed if the operating system requires it }

⟨ Print the job history 187 ⟩; end.

183. ⟨ Phase I: Read all the user’s text and compress it into tok mem 183 ⟩ ≡ phase one ← true; module count ← 0; repeat next control ← skip ahead ; until next control = new module; while ¬input has ended do scan module; ⟨ Check that all changes have been read 138 ⟩; phase one ← false;

This code is used in section 182.

184. ⟨ Finish off the string pool file 184 ⟩ ≡ begin print nl (string ptr − 128 : 1, ´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); write(pool , ´ ´ ); for string ptr ← 1 to 9 do

begin out buf [string ptr ] ← pool check sum mod 10; pool check sum ← pool check sum div 10; end;

for string ptr ← 9 downto 1 do write(pool , xchr [ + out buf [string ptr ]]); write ln(pool ); end

This code is used in section 182.

185. ⟨ Globals in the outer block 9 ⟩ +≡ stat wo: 0 . . ww − 1; { segment of memory for which statistics are being printed } tats

186. ⟨ Print statistics about memory usage 186 ⟩ ≡ print nl (´ ␣ ␣ ´ ); print nl (name ptr : 1, ´ ␣ ␣´ , text ptr : 1, ´ ␣ ␣ ´ ); print nl (byte ptr [0] : 1); for wo ← 1 to ww − 1 do print (´ ´ , byte ptr [wo] : 1); print (´ ␣ ␣´ , max tok ptr [0] : 1); for zo ← 1 to zz − 1 do print (´ ´ , max tok ptr [zo] : 1); print (´ ␣ ´ );

This code is used in section 182.

188  THE MAIN PROGRAM  MANGLE §187

187. Some implementations may wish to pass the history value to the operating system so that it can be used to govern whether or not other programs are started. Here we simply report the history to the user. ⟨ Print the job history 187 ⟩ ≡

case history of

spotless : print nl (´ ␣ ␣ ␣ ´ ); harmless message: print nl (´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); error message: print nl (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); fatal message: print nl (´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); end { there are no other cases }

This code is used in section 182.

§188  MANGLE  SYSTEM-DEPENDENT CHANGES 189

188. System-dependent changes. This module should be replaced, if necessary, by changes to the program that are necessary to make work at a particular installation. It is usually best to design your change file so that all changes to previous modules preserve the module numbering; then everybody’s version will be consistent with the printed program. More extensive changes, which introduce new modules, can be inserted here; then only the index itself will get a new module number.

190  INDEX  MANGLE §189

189* . Index. Here is a cross-reference table for the processor. All modules in which an identifier is used are listed with that identifier, except that reserved words are indexed only when they appear in format definitions, and the appearances of identifiers in module names are not indexed. Underlined entries correspond to where the identifier was declared. Error messages and a few other things like “ASCII code” are indexed here too.

The following sections were changed by the change file: 1, 8, 72, 115, 121, 142, 145, 147, 189.

: 167. : 167. : 167. a: \underline{74}, \underline{87}, \underline{165}. abs : 103, 157. accumulator : \underline{157}, 158, 159. add in: \underline{157}, 158. : 69. and sign: \underline{15}, 114. app: \underline{99}, 101, 102, 103, 111. app repl : \underline{93}, 165, 166, 167, 168, 169. app val : \underline{99}, 103, 111. ASCII code: 11, 72* . ASCII code: \underline{11}, 13, 27, 28, 38, 50, 65, 94, 95,

100, 126, 139, 141, 165. b: \underline{87}, \underline{97}, \underline{165}. bad case: \underline{107}, 109, 110. bal : \underline{87}, 93, \underline{141}, 142* , \underline{165}, 166. banner : \underline{1*} , 182. begin: 3. begin comment : \underline{72*} , 76, 121* , 139. begin Pascal : \underline{139}, 156, 158, 167, 175. boolean: 28, 29, 124, 127, 143, 179. brace level : \underline{82}, 83, 98, 121* . break : 22. break ptr : \underline{94}, 95, 96, 97, 98, 101, 102, 106, 107,

109, 110, 111, 122. breakpoint : 179, \underline{181}. buf size: \underline{8*} , 27, 28, 31, 50, 53, 124, 126, 127,

128, 132. buffer : \underline{27}, 28, 31, 32, 50, 53, 54, 56, 57, 58, 61,

64, 127, 129, 131, 132, 133, 134, 135, 136, 137, 138, 140, 141, 142* , 145* , 147* , 148, 149, 150, 153, 154, 167, 168, 169, 181.

byte field : \underline{78}, 79. byte mem: 37, \underline{38}, 39, 40, 41, 48, 49, 53, 56, 61,

63, 66, 67, 68, 69, 75, 87, 90, 113, 116. byte ptr : 39, \underline{40}, 42, 61, 67, 90, 91, 186. byte start : 37, \underline{38}, 39, 40, 42, 49, 50, 56, 61, 63,

67, 68, 75, 78, 81, 90, 116, 143. c: \underline{53}, \underline{66}, \underline{69}, \underline{139}, \underline{140}, \underline{141}, \underline{145*} . : 113. carriage return: \underline{15}, 17, 28. : 130, 132, 137. : 138. change buffer : \underline{126}, 127, 128, 131, 132, 136, 138.

change changing : \underline{125}, 132, 134, 137.
change file: \underline{2}, \underline{23}, 24, 32, 124, 126, 129, 130,

132, 137. change limit : \underline{126}, 127, 128, 131, 132, 136, 138. changing : 32, \underline{124}, 125, 126, 128, 132, 134,

135, 138. char : 12, 14. check break : \underline{97}, 101, 102, 103, 111. check change: \underline{132}, 136. check sum: \underline{72*} , 76, 119, 139. check sum prime: \underline{64}. chop hash: \underline{50}, 52, 60, 62. chopped id : \underline{50}, 53, 58, 63. chr : 12, 13, 17, 18. compress : \underline{147*} . confusion: \underline{35}, 89. : 119. continue: \underline{5}, 113, 128, 129, 165, 167, 172, 173, 174. control code: \underline{139}, 140, 143, 150. control text : \underline{139}, 150. count : \underline{69}. cur byte: 78, \underline{79}, 83, 84, 85, 87, 90, 93. cur char : \underline{113}, 116, 117, 119, 120. cur end : 78, \underline{79}, 83, 84, 85, 87, 90. cur mod : 78, \underline{79}, 83, 84, 87. cur module: \underline{143}, 151, 167, 175. cur name: 78, \underline{79}, 83, 84, 85. cur repl : 78, \underline{79}, 80, 83, 84, 85. cur repl text : \underline{164}, 165, 170, 175, 178. cur state: \underline{79}, 84, 85. cur val : \underline{86}, 87, 89, 116, 119, 121* . d: \underline{145*} . dd : \underline{179}, 181. ddt : \underline{179}, 181. debug: \underline{3}, \underline{4}, \underline{30}, \underline{31}, \underline{74}, \underline{87}, \underline{90}, \underline{91}, \underline{145*} , \underline{179},

\underline{180}, \underline{181}. debug cycle: \underline{179}, 180, 181. debug help: \underline{30}, 31, 87, 145* , 179, \underline{181}. debug skipped : \underline{179}, 180, 181. decr : \underline{6}, 28, 85, 91, 93, 99, 116, 121* , 142* , 148,

§189  MANGLE  INDEX 191

153, 165, 166. define macro: \underline{170}, 173, 174. definition: \underline{139}, 156, 158, 167, 173. : 173. digits : \underline{119}, 158. do nothing : \underline{6}, 93, 102, 113, 145* , 158, 165. done: \underline{5}, 87, 93, 128, 129, 140, 145* , 153, 154, 157,

158, 159, 165, 167, 172, 173. : 149. double chars : \underline{50}, 64, 143, 149. double dot : \underline{72*} , 114, 147* . EBCDIC: 115* . eight bits : \underline{37}, 38, 53, 82, 87, 95, 101, 113, 139,

140, 141, 145* , 156, 165, 170. else: 7. end: 3, 7. end comment : \underline{72*} , 76, 121* , 139. end field : \underline{78}, 79. end of definition: \underline{156}, 159. end of TANGLE : \underline{2}, 34, 182. endcases: \underline{7}. eof : 28. eoln: 28. equal : \underline{66}, 67, 68. equiv : 37, \underline{38}, 47, 48, 50, 60, 62, 63, 64, 67, 84,

88, 89, 90, 157, 158, 170, 178. equivalence sign: \underline{15}, 114, 147* , 173, 174, 176. err print : \underline{31}, 59, 64, 66, 69, 97, 98, 108, 113, 117,

118, 119, 120, 121* , 125, 129, 130, 132, 133, 137, 138, 141, 142* , 149, 150, 153, 154, 157, 158, 159, 165, 166, 167, 168, 169, 173, 174, 176.

error : 28, \underline{31}, 34, 63, 88, 90. error message: \underline{9}, 187. exit : \underline{5}, 6, 85, 107, 127, 128, 132, 141, 172, 181. extension: \underline{66}, 68, 69. : 165. : 121* . f: \underline{28}. false: 28, 29, 125, 126, 127, 132, 134, 144,

146, 180, 183. fatal error : \underline{34}, 35, 36. fatal message: \underline{9}, 187. final limit : \underline{28}. first text char : \underline{12}, 18. flush buffer : \underline{97}, 98, 122. force line: \underline{72*} , 76, 113, 139. form feed : \underline{15}, 28. format : \underline{139}, 156, 158, 167, 173. forward : 30. found : \underline{5}, 53, 55, 56, 66, 87, 89, 145* , 146, 165, 168. frac: \underline{100}, 101, 102, 104, 113, 120. : 120. get : 28, 180. get fraction: \underline{113}, 119, 120. get line: 124, \underline{135}, 140, 141, 145* , 153. get next : 143, \underline{145*} , 156, 158, 159, 160, 161, 162,

165, 173, 174, 176. get output : 86, \underline{87}, 94, 112, 113, 117, 118, 119, 120. greater : \underline{66}, 68, 69. greater or equal : \underline{15}, 114, 147* . gubed: \underline{3}. h: \underline{51}, \underline{53}. harmless message: \underline{9}, 187. hash: 39, \underline{50}, 52, 55. hash size: \underline{8*} , 50, 51, 52, 53, 54, 58. hex : \underline{72*} , 76, 119, 139, 150, 158. history : \underline{9}, 10, 187. : 133. i: \underline{16}, \underline{53}. id first : \underline{50}, 53, 54, 56, 57, 58, 61, 64, 143, 148, 149. id loc: \underline{50}, 53, 54, 56, 58, 61, 64, 143, 148, 149. id lookup: 50, \underline{53}, 143, 158, 167, 170, 173. ident : \underline{100}, 101, 102, 105, 114, 116. identifier : \underline{86}, 89, 116, 143, 148, 149, 158, 167, 173. : 63. ignore: \underline{139}, 140, 150. ilk : 37, \underline{38}, 47, 48, 50, 57, 59, 60, 61, 64, 85,

89, 90, 158. : 150. : 159. : 66. incr : \underline{6}, 28, 54, 56, 58, 61, 63, 64, 67, 68, 69, 74, 75, 84, 87, 90, 93, 97, 99, 116, 117, 118, 120, 121* , 129, 130, 132, 136, 137, 140, 141, 142* , 145* , 147* , 148, 149, 150, 153, 154, 165, 168, 169, 172, 181.

initialize: \underline{2}, 182.

: 141. : 153. : 28. input has ended : \underline{124}, 132, 134, 136, 140, 141,

145* , 153, 183. input ln: \underline{28}, 129, 130, 132, 136, 137. integer : 14, 40, 86, 95, 99, 106, 107, 113, 124,

132, 157, 179, 181. j: \underline{31}, \underline{66}, \underline{69}, \underline{113}, \underline{145*} .

join: \underline{72*} , 101, 113, 139.
jump out : 2, 31, \underline{34}.

k: \underline{31}, \underline{49}, \underline{53}, \underline{66}, \underline{69}, \underline{74}, \underline{87}, \underline{97}, \underline{99}, \underline{101}, \underline{113},

\underline{127}, \underline{128}, \underline{132}, \underline{145*} , \underline{181}.

l: \underline{31}, \underline{53}, \underline{66}, \underline{69}.
last sign: \underline{95}, 103, 106, 107.
last text char : \underline{12}, 16, 18.
last unnamed : \underline{70}, 71, 178.
left arrow : \underline{15}, 114, 147* .
length: \underline{39}, 55.
less : \underline{66}, 67, 68, 69.
less or equal : \underline{15}, 114, 147* .

limit : 28, 32, \underline{124}, 127, 129, 130, 131, 133, 134, 135, 136, 137, 138, 140, 141, 145* , 147* , 149, 153, 168, 169. line: 32, 33, 96, 97, \underline{124}, 125, 129, 130, 132,

134, 136, 137, 138. line feed : \underline{15}, 28. line length: \underline{8*} , 94, 97, 100, 101, 113, 117, 118,

120, 122. lines dont match: \underline{127}, 132. link : 37, \underline{38}, 39, 48, 50, 55, 70. llink : \underline{48}, 66, 67, 69. loc: 28, 32, \underline{124}, 129, 133, 134, 135, 137, 138,

140, 141, 142* , 145* , 147* , 148, 149, 150, 153, 154, 159, 167, 168, 169, 173.

: 97. longest name: \underline{8*} , 65, 66, 69, 145* , 153, 155. loop: \underline{6}. mark error : \underline{9}, 31. mark fatal : \underline{9}, 34. mark harmless : \underline{9}, 112, 155. max bytes : \underline{8*} , 38, 40, 49, 53, 61, 66, 67, 69,

87, 90, 113. max id length: \underline{8*} , 116. max names : \underline{8*} , 38, 39, 61, 67, 69, 90. max texts : \underline{8*} , 38, 43, 70, 90, 165. max tok ptr : \underline{44}, 91, 182, 186. max toks : \underline{8*} , 38, 44, 73, 74, 93. misc: \underline{95}, 96, 100, 101, 102, 105, 107, 111, 113,

119, 121* , 122. : 166. mod: 94. mod field : \underline{78}, 79. mod lookup: 65, \underline{66}, 151, 152. mod text : \underline{65}, 66, 67, 68, 69, 145* , 151, 152, 153,

154, 155, 181. module count : 139, \underline{171}, 172, 177, 183. module flag : \underline{70}, 85, 178. module name: \underline{139}, 143, 150, 156, 158, 159, 164,

167, 173, 175. module number : \underline{86}, 87, 121* . n: \underline{113}, \underline{132}. : 69. name field : \underline{78}, 79. name pointer : \underline{39}, 40, 49, 53, 66, 69, 78, 84,

143, 157, 170, 172. name ptr : 39, \underline{40}, 42, 49, 53, 55, 57, 59, 61, 67,

90, 91, 92, 93, 186. new line: \underline{20}, 31, 32, 34. new module: \underline{139}, 140, 145* , 156, 158, 167, 176, 183. next control : \underline{156}, 158, 159, 160, 161, 162, 164,

165, 173, 174, 175, 176, 183. next sign: \underline{157}, 158. nil: 6. : 112. : 90. normal : \underline{47}, 50, 53, 57, 59, 60, 61, 89, 158, 167. : 88. not equal : \underline{15}, 114, 147* . not found : \underline{5}, 53, 63. not sign: \underline{15}, 114. num or id : \underline{95}, 101, 102, 107, 111. number : \underline{86}, 89, 119. numeric: \underline{47}, 53, 64, 89, 158, 173. octal : \underline{72*} , 76, 119, 139, 158. : 158. open input : \underline{24}, 134. or sign: \underline{15}, 114. ord : 13. other line: \underline{124}, 125, 134, 138. othercases: \underline{7}. others : 7. out app: \underline{95}, 102, 104, 106, 108. out buf : 31, 33, \underline{94}, 95, 96, 97, 99, 100, 109,

110, 181, 184. out buf size: \underline{8*} , 31, 94, 97, 99. out contrib: \underline{100}, 101, 105, 113, 114, 116, 117,

118, 119, 120, 121* , 181. out ptr : 33, \underline{94}, 95, 96, 97, 98, 99, 101, 102, 106,

107, 109, 110, 111, 122, 181. out sign: \underline{95}, 103, 104, 107, 108. out state: \underline{95}, 96, 101, 102, 104, 106, 107, 108,

111, 113, 117, 122. out val : \underline{95}, 103, 104, 106, 107, 108. output state: \underline{78}, 79. overflow : \underline{36}, 61, 67, 73, 84, 90, 93, 165. p: \underline{49}, \underline{53}, \underline{66}, \underline{69}, \underline{74}, \underline{84}, \underline{157}, \underline{170}, \underline{172}. pack : 61. param: \underline{72*} , 76, 87, 93, 165. parametric: \underline{47}, 53, 85, 89, 164, 165, 174. : 176. Pascal file: \underline{2}, \underline{25}, 26, 97. phase one: \underline{29}, 31, 183. pool : \underline{2}, \underline{25}, 26, 64, 184. pool check sum: \underline{40}, 42, 64, 119, 184. pop level : \underline{85}, 87, 90, 91. prefix : \underline{66}, 68. prefix lookup: \underline{69}, 151. : 64. preprocessed strings: 64, 149. prime the change buffer : \underline{128}, 134, 137. print : \underline{20}, 31, 32, 33, 34, 49, 63, 74, 75, 76, 88,

93, 97, 139, 155, 181, 186. print id : \underline{49}, 75, 88, 90, 181. print ln: \underline{20}, 32, 33, 182. print nl : \underline{20}, 28, 63, 88, 90, 112, 155, 184, 186, 187. print repl : \underline{74}, 181. : 98. push level : \underline{84}, 88, 89, 92. q: \underline{53}, \underline{66}, \underline{69}, \underline{157}. r: \underline{69}. read : 181. read ln: 28. repl field : \underline{78}, 79. reset : 24, 180. restart : \underline{5}, 87, 88, 89, 90, 92, 101, 102, 104,

135, 145* , 147* , 150. reswitch: \underline{5}, 113, 117, 119, 120, 157, 158. return: 5, \underline{6}. rewrite: 21, 26. rlink : \underline{48}, 66, 67, 69. s: \underline{53}. scan module: 171, \underline{172}, 183. scan numeric: 156, \underline{157}, 173. scan repl : 164, \underline{165}, 170, 175. scanning hex : \underline{143}, 144, 145* , 146, 150. : 142* . : 154. : 155. semi ptr : \underline{94}, 96, 97, 98, 101. send left comment : \underline{121*} . send out : 100, \underline{101}, 112, 113, 114, 116, 117, 118,

119, 120, 121* , 122. send right comment : \underline{121*} . send sign: 100, \underline{106}, 112, 113. send the output : 112, \underline{113}. send val : 100, \underline{107}, 112, 119, 121* . set element sign: \underline{15}, 114. sign: \underline{95}, 102, 106, 108. sign val : \underline{95}, 102, 104, 106, 107, 108. sign val sign: \underline{95}, 102, 106, 108. sign val val : \underline{95}, 102, 106, 108. simple: \underline{47}, 53, 89, 90, 164, 173. sixteen bits : \underline{37}, 38, 50, 66, 69, 73, 74, 78, 87,

101, 165. skip ahead : \underline{140}, 150, 159, 173, 176, 183. skip comment : \underline{141}, 147* . : 36. spotless : \underline{9}, 10, 187. stack : 78, \underline{79}, 84, 85. stack ptr : 78, \underline{79}, 83, 84, 85, 87, 90, 113, 117, 118. stack size: \underline{8*} , 79, 84. stat: \underline{3}. store two bytes : \underline{73}, 93, 177. str : \underline{100}, 101, 114, 117, 118, 119, 121* , 122. : 149. : 168. : 117. string ptr : 39, \underline{40}, 42, 64, 182, 184.

system dependencies: \underline{1*} , 2, 4, 7, 12, 17, 20, 21,

22, 24, 26, 28, 32, 34, 115* , 116, 121* , 180, 181, 182, 187, 188.

t: \underline{53}, \underline{101}, \underline{165}, \underline{170}.

tab mark : \underline{15}, 32, 139, 142* , 145* , 153, 154.
TANGLE : \underline{2}.
tats: \underline{3}.
temp line: \underline{124}, 125.
term in: \underline{179}, 180, 181.
term out : \underline{20}, 21, 22, 181.
text char : \underline{12}, 13, 20.
text file: \underline{12}, 20, 23, 25, 28, 179.

text link : 37, \underline{38}, 43, 70, 71, 83, 85, 90, 112,

170, 178. text pointer : \underline{43}, 44, 70, 74, 78, 164. text ptr : 43, \underline{44}, 46, 74, 81, 90, 91, 165, 186. : 35. : 59. : 59. tok mem: 37, \underline{38}, 43, 44, 45, 70, 73, 74, 75, 78,

79, 80, 81, 87, 90, 93, 165. tok ptr : 43, \underline{44}, 46, 73, 81, 90, 91, 93, 165, 182. tok start : 37, \underline{38}, 43, 44, 46, 70, 74, 78, 83, 84,

85, 90, 91, 165. trouble shooting : 87, 145* , \underline{179}, 180. true: 6, 28, 29, 124, 125, 127, 132, 134, 136, 138,

143, 150, 179, 180, 183. : 108. unambig length: \underline{8*} , 47, 50, 53, 58, 63. unbreakable: \underline{95}, 102, 113, 117. up to: \underline{116}, 145* . update terminal : \underline{22}, 31, 97, 112, 139, 181. uppercase: 58, 63, 105, 110, 114, 116, 119, 120. : 174. v: \underline{99}, \underline{101}, \underline{106}, \underline{107}. val : \underline{157}, 158, 160, 161, 162. : 157. verbatim: \underline{72*} , 76, 113, 118, 139, 167, 169. : 169. : 118. w: \underline{49}, \underline{53}, \underline{66}, \underline{69}, \underline{87}, \underline{113}. : 132. web file: \underline{2}, \underline{23}, 24, 32, 124, 126, 132, 136, 138. : 129, 133, 137. wi : \underline{41}, 42. wo: \underline{185}, 186. write: 20, 64, 97, 181, 184. write ln: 20, 64, 97, 184. ww : 8* , \underline{38}, 39, 40, 41, 42, 43, 49, 53, 56, 61, 63, 66, 67, 68, 69, 75, 87, 90, 91, 113, 116, 185, 186.

x: \underline{73}. xchr : \underline{13}, 14, 16, 17, 18, 32, 33, 49, 63, 64, 75,

76, 97, 155, 167, 181, 184. xclause: 6. xord : \underline{13}, 16, 18, 28. : 168, 169. z: \underline{44}. zi : \underline{45}, 46. zo: \underline{80}, 83, 84, 85, 87, 90, 93, 182, 186. zp: \underline{74}, 75. zz : 8* , \underline{38}, 43, 44, 45, 46, 74, 80, 83, 84, 85, 90,

91, 165, 182, 186.

§189  MANGLE  NAMES OF THE SECTIONS 195

⟨ Append out val to buffer 103 ⟩ Used in sections 102 and 104.

⟨ Append the decimal value of v, with parentheses if negative 111 ⟩ Used in section 107.

⟨ Cases involving and 121* ⟩ Used in section 113. ⟨ Cases like and 114 ⟩ Used in section 113.

⟨ Cases related to constants, possibly leading to get fraction or reswitch 119 ⟩ Used in section 113. ⟨ Cases related to identifiers 116 ⟩ Used in section 113. ⟨ Check for ambiguity and update secondary hash 62 ⟩ Used in section 61. ⟨ Check for overlong name 155 ⟩ Used in section 153. ⟨ Check if q conflicts with p 63 ⟩ Used in section 62. ⟨ Check that all changes have been read 138 ⟩ Used in section 183. ⟨ Check that = or ≡ follows this module name, otherwise return 176 ⟩ Used in section 175. ⟨ Compare name p with current identifier, goto found if equal 56 ⟩ Used in section 55. ⟨ Compiler directives 4 ⟩ Used in section 2. ⟨ Compress two-symbol combinations like ‘ ’ 147* ⟩ Used in section 145*. ⟨ Compute the hash code h 54 ⟩ Used in section 53. ⟨ Compute the name location p 55 ⟩ Used in section 53. ⟨ Compute the secondary hash code h and put the first characters into the auxiliary array chopped id 58 ⟩

Used in section 57.

⟨ Constants in the outer block 8* ⟩ Used in section 2. ⟨ Contribution is or or or 105 ⟩ Used in section 104. ⟨ Copy a string from the buffer to tok mem 168 ⟩ Used in section 165. ⟨ Copy the parameter into tok mem 93 ⟩ Used in section 90. ⟨ Copy verbatim string from the buffer to tok mem 169 ⟩ Used in section 167. ⟨ Define and output a new string of the pool 64 ⟩ Used in section 61. ⟨ Display one-byte token a 76 ⟩ Used in section 74. ⟨ Display two-byte token starting with a 75 ⟩ Used in section 74. ⟨ Do special things when c = , , , ; return at end 142* ⟩ Used in section 141. ⟨ Empty the last line from the buffer 98 ⟩ Used in section 112. ⟨ Enter a new identifier into the table at position p 61 ⟩ Used in section 57. ⟨ Enter a new module name into the tree 67 ⟩ Used in section 66. ⟨ Error handling procedures 30, 31, 34 ⟩ Used in section 2. ⟨ Expand macro a and goto found , or goto restart if no output found 89 ⟩ Used in section 87.

⟨ Expand module a − ´ 24000 , goto restart 88 ⟩ Used in section 87.

⟨ Finish off the string pool file 184 ⟩ Used in section 182.

⟨ Force a line break 122 ⟩ Used in section 113.

⟨ Get a preprocessed string 149 ⟩ Used in section 145*.

⟨ Get an identifier 148 ⟩ Used in section 145*.

⟨ Get control code and possible module name 150 ⟩ Used in section 145*. ⟨ Get the buffer ready for appending the new information 102 ⟩ Used in section 101. ⟨ Give double-definition error and change p to type t 59 ⟩ Used in section 57.

⟨ Globals in the outer block 9, 13, 20, 23, 25, 27, 29, 38, 40, 44, 50, 65, 70, 79, 80, 82, 86, 94, 95, 100, 124, 126, 143, 156,

164, 171, 179, 185 ⟩ Used in section 2.

⟨ Go to found if c is a hexadecimal digit, otherwise set scanning hex ← false 146 ⟩ Used in section 145*. ⟨ Handle cases of send val when out state contains a sign 108 ⟩ Used in section 107.

⟨ If end of name, goto done 154 ⟩ Used in section 153.

⟨ If previous output was or , goto bad case 109 ⟩ Used in section 107. ⟨ If previous output was or , goto bad case 110 ⟩ Used in section 107. ⟨ If the current line starts with , report any discrepancies and return 133 ⟩ Used in section 132. ⟨ If the next text is ‘(#) ≡’, call define macro and goto continue 174 ⟩ Used in section 173. ⟨ In cases that a is a non-ASCII token (identifier , module name, etc.), either process it and change a to a

byte that should be stored, or goto continue if a should be ignored, or goto done if a signals the end of this replacement text 167 ⟩ Used in section 165.

196  NAMES OF THE SECTIONS  MANGLE §189

⟨ Initialize the input system 134 ⟩ Used in section 182. ⟨ Initialize the output buffer 96 ⟩ Used in section 112. ⟨ Initialize the output stacks 83 ⟩ Used in section 112. ⟨ Insert the module number into tok mem 177 ⟩ Used in section 175. ⟨ Local variables for initialization 16, 41, 45, 51 ⟩ Used in section 2. ⟨ Make sure the parentheses balance 166 ⟩ Used in section 165.

⟨ Move buffer and limit to change buffer and change limit 131 ⟩ Used in sections 128 and 132.

⟨ Other printable characters 115* ⟩ Used in section 113. ⟨ Phase I: Read all the user’s text and compress it into tok mem 183 ⟩ Used in section 182. ⟨ Phase II: Output the contents of the compressed tables 112 ⟩ Used in section 182. ⟨ Print error location based on input buffer 32 ⟩ Used in section 31. ⟨ Print error location based on output buffer 33 ⟩ Used in section 31. ⟨ Print statistics about memory usage 186 ⟩ Used in section 182.

⟨ Print the job history 187 ⟩ Used in section 182.

⟨ Put a parameter on the parameter stack, or goto restart if error occurs 90 ⟩ Used in section 89. ⟨ Put module name into mod text [1 . . k] 153 ⟩ Used in section 151. ⟨ Read from change file and maybe turn off changing 137 ⟩ Used in section 135. ⟨ Read from web file and maybe turn on changing 136 ⟩ Used in section 135.

⟨ Reduce sign val val to sign val and goto restart 104 ⟩ Used in section 102.

⟨ Remove a parameter from the parameter stack 91 ⟩ Used in section 85. ⟨ Remove p from secondary hash table 60 ⟩ Used in section 59. ⟨ Scan the definition part of the current module 173 ⟩ Used in section 172. ⟨ Scan the module name and make cur module point to it 151 ⟩ Used in section 150. ⟨ Scan the Pascal part of the current module 175 ⟩ Used in section 172.

⟨ Send a string, goto reswitch 117 ⟩ Used in section 113.

⟨ Send verbatim string 118 ⟩ Used in section 113. ⟨ Set accumulator to the value of the right-hand side 158 ⟩ Used in section 157. ⟨ Set c to the result of comparing the given name to name p 68 ⟩ Used in sections 66 and 69.

⟨ Set initial values 10, 14, 17, 18, 21, 26, 42, 46, 48, 52, 71, 144, 152, 180 ⟩ Used in section 2.

⟨ Set val to value of decimal constant, and set next control to the following token 160 ⟩ Used in section 158. ⟨ Set val to value of hexadecimal constant, and set next control to the following token 162 ⟩

Used in section 158.

⟨ Set val to value of octal constant, and set next control to the following token 161 ⟩ Used in section 158. ⟨ Signal error, flush rest of the definition 159 ⟩ Used in section 158. ⟨ Skip over comment lines in the change file; return if end of file 129 ⟩ Used in section 128. ⟨ Skip to the next nonblank line; return if end of file 130 ⟩ Used in section 128. ⟨ Special code to finish real constants 120 ⟩ Used in section 113. ⟨ Start scanning current macro parameter, goto restart 92 ⟩ Used in section 87.

⟨ Types in the outer block 11, 12, 37, 39, 43, 78 ⟩ Used in section 2.

⟨ Update the data structure so that the replacement text is accessible 178 ⟩ Used in section 175. ⟨ Update the tables and check for possible errors 57 ⟩ Used in section 53.

The MANGLE processor

(Version 2.8)

Section Page

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 124 The character set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 127 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 131 Reporting errors to the user . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 133 Data structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 135 Searching for identifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 138 Searching for module names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 143 Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 145 Stacks for output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 148 Producing the output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 153 The big output switch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 160 Introduction to the input phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 165 Inputting the next token . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 172 Scanning a numeric definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 176 Scanning a macro definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 179 Scanning a module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 182 Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 185 The main program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 187 System-dependent changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 189 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 190