§1  PROFILE  INTRODUCTION 1

1. Introduction. The purpose of is to annotate a PASCAL program with data about the estimated computer time ascribed to each line of code. If the PASCAL program has been produced by , the accumulated run time estimates for each section of the source code will also be determined.

Running time is estimated roughly by assigning an integer weight to each feature of PASCAL. For example, the statement ‘A[i] := x + 2/n’ will be weighted by the time to fetch i, x, 2, and n, plus the time to compute the location of A[i] given i, plus the time to add, to convert n from integer to real, to divide, and to store in memory. Approximate costs of each primitive operation appear in macro definitions like int real cost that are grouped together in one of the sections below; thus, they are not hard to change.

The program includes a PASCAL parser, so it can probably be modified to do other operations on PASCAL source code. Indeed, this program intentionally deals with PASCAL in more generality than it needs to, so that it can be used as a starting point for programs that translate subsets of PASCAL to other higher-level languages.

Don Knuth wrote the first version of in October, 1983, for the purpose of analyzing bottlenecks in the TEX processor. (He apologizes for having written the program in haste, without adequate time to test whether it works on features of PASCAL that he doesn’t actually use in his own programs.)

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

define banner ≡ ´ ␣ ␣ ␣ ␣ ´

2. The program begins with a fairly normal header, made up of pieces that will mostly be filled in later. There are two input files:

pascal file is a syntactically correct PASCAL source program, preferably (but not necessarily) output by . The entire PASCAL language is permitted except for with statements, which require additional symbol table manipulations that have not been implemented (since the portable programs of the TEX project don’t use with).

count file is a text file containing integer counts, one per line, representing the number of times that key statements of the PASCAL program were executed. There should be one count for the first statement in each block and for the first statement following do, then, else, repeat, plus one count for each colon following a label. An artificial count of ‘-1’ should also appear at the very end of the file. (Dave Fuchs has modified the PASCAL debugger at Stanford so that such a count file can be obtained.)

The output file will receive a “pretty printed” version of the PASCAL source code, with frequency counts and weights accompanying each statement. A summary of the total weight for each section will also be

appended to the output, if the source file contains comments like ‘  ’ and ‘  ’ around the code
for section 123. Comments like ‘  ’ or ‘  ’ will add 10 or subtract 5 from the weight that

ordinarily computes at a particular place in the source file. The special comment ‘ ’ in a procedure heading indicates that the procedure in question does not exit.

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

define end of PROFILE = 9999 { go here to wrap it up } ⟨ Compiler directives 4 ⟩ program PROFILE (pascal file, count file, output );

label end of PROFILE ; { go here to finish }

const ⟨ Constants in the outer block 8 ⟩

type ⟨ Types in the outer block 14 ⟩

var ⟨ Globals in the outer block 9 ⟩ ⟨ Error handling procedures 32 ⟩ ⟨ Memory management procedures 40 ⟩

2  INTRODUCTION  PROFILE §3

procedure initialize; var ⟨ Local variables for initialization 11 ⟩ 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.

define debug ≡ { change this to ‘debug ≡ ’ when debugging } define gubed ≡ { change this to ‘gubed ≡ ’ when debugging } format debug ≡ begin format gubed ≡ end

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 done1 = 31 { go here to exit another loop } define done2 = 32 { and another } define done3 = 33 { and another } define done4 = 34 { in case of five loops in one big procedure } define found = 40 { go here when you’ve found it } define not found = 41 { 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.)

When the PASCAL source program being processed by has default cases, we assume below that the default case is labeled with some recognizable keyword, and that the count file contains a count for this label just like any other.

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 ⟩ ≡

max names = 4999; { maximum number of identifiers and reserved words; should be a prime number } pool size = 30000; { maximum total length of identifiers and reserved words } max modules = 2000; { greater than the total number of sections } buf size = 100; { maximum length of input line } line length = 50; { lines of unannotated PASCAL output } weight length = 6; { columns of annotation for weight data } freq length = 12; { columns of annotation for frequency data } out buf size = 128; { output lines before breaking to line length } mem size = 30000; { largest index in the dynamic memory array; must be less than max halfword } max comment = 20; { comments are truncated to this many characters } save size = 500; { number of entries on the save stack }

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 16, 21, 24, 26, 29, 38, 43, 45, 53, 56, 57, 64, 70, 72, 75, 78, 83, 87, 102, 107, 110, 143, 175, 179, and 189. This code is used in section 2.

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

See also sections 17, 18, 19, 22, 25, 30, 39, 44, 46, 59, 60, 61, 73, 76, 84, 88, 103, 108, 111, and 176. This code is used in section 2.

11. A lot of initialization needs to be done, and it’s convenient to have an integer variable for iteration. ⟨ Local variables for initialization 11 ⟩ ≡ i: integer ; { all-purpose index for initialization loops }

See also section 58. This code is used in section 2.

§12  PROFILE  OPERATION COSTS 5

12. Operation costs. Here we define the assumed cost of each operation. The numbers are expressed in terms of a unit that essentially represents a memory access. The numbers aren’t extremely precise, because the goal is simply to give a ballpark estimate of running time. On the KL-10 computer, each unit supposedly represents about 400 nanoseconds.

define fetch cost = 1 { time to load a variable or constant } define store cost = 1 { time to store into a variable } define jump cost = 1 { time to goto a (local) label } define index cost = 1 { extra time for array-address computation } define packed index cost = 10 { ditto, for packed arrays } define pointer cost = 1 { cost of ↑ in pointers } define add cost = 1 { integer addition or subtraction } define mult cost = 5 { integer multiplication } define div cost = 10 { integer div and mod } define real add cost = 5 { floating point addition or subtraction } define real mult cost = 6 { floating point multiplication } define real div cost = 12 { floating point division } define compare cost = 1 { equality or inequality tests } define in cost = 3 { in } define set cost = 1 { set union, intersection, difference } define and or cost = 1 { and, or } define unary cost = 1 { abs and odd and pred and succ and not and negation } define ord chr cost = 0 { ord or chr } define int real cost = 25 { trunc,round , or fix-to-float } define char string cost = 15 { read or write a char } define int string cost = 100 { read or write an integer } define real string cost = 300 { read or write a real } define string string cost = 5 { setup time for reading and writing a string } define string string tax = 5 { ditto, extra cost per character } define array string cost = 250 { reading characters into an array } define transcendental cost = 100 { sin, exp, etc. (guesstimate) } define new cost = 50 { new , dispose (guesstimate) } define pack cost = 250 { pack , unpack (guesstimate) } define packed surcharge = 1 { packed record field cost added to fetch cost } define var surcharge = 1 { extra cost for fetching or storing a var parameter } define call overhead = 10 { push or pop stack and transfer to or from procedure or function } define open cost = 3000 { reset or rewrite } define close cost = 600 { close } define break in cost = 100 { breakin } define get put cost = 10 { get or put on a file } define eof cost = 10 { eof or eoln }

13. Besides the costs of basic operations, there are costs associated with changes of control. define if cost = 1 { setup time for if … then … else } define for cost = 5 { for loop setup time } define for tax = 5 { extra charge per iteration } define while cost = 1 { setup time for while loop } define while tax = 1 { extra charge per iteration of while loop } define repeat tax = 1 { extra time per iteration of repeat loop } define case cost = 5 { setup time for branching in case statement }

6  THE CHARACTER SET  PROFILE §14

14. The character set. Most programs convert their input 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.

Here we use code conversion identical to that done by and . ⟨ Types in the outer block 14 ⟩ ≡

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

See also sections 15, 37, and 42. This code is used in section 2.

15. 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. 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 14 ⟩ +≡

text file = packed file of text char ;

16. Conversion between ASCII code and the user’s external character set is done 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 }

§17  PROFILE  THE CHARACTER SET 7

17. If we assume that 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. ⟨ 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 }

18. Here now is the system-dependent part of the character set. (Changes are appropriate only if nonstandard characters might be used in strings.) ⟨ Set initial values 10 ⟩ +≡

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

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

8  INPUT AND OUTPUT  PROFILE §20

for i ← first text char to last text char do xord [chr (i)] ← ´ 40 ; for i ← 1 to ´ 176 do xord [xchr [i]] ← i; 20. Input and output. The input and output conventions of this program have been copied from those

of  and  . Therefore people who need to make modifications should already know how to do it.

21. 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 }

22. 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 }

23. 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 }

24. The main input comes from pascal file and count file, as explained earlier. ⟨ Globals in the outer block 9 ⟩ +≡ pascal file: text file; { the PASCAL source code } count file: text file; { frequency counts }

25. 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. ⟨ Set initial values 10 ⟩ +≡

reset (pascal file); reset (count file);

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

§27  PROFILE  INPUT AND OUTPUT 9

27. 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 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. 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;

28. Input from the count file is trivial; we simply ask for a count, whenever it’s time to know a new one. If count file has the wrong number of counts, the discrepancy will be reported later; such problems will usually also be caught by the redundancy check that is made at the time of every ‘else’ count. function get count : integer ;

begin if last count ≥ 0 then begin read ln(count file, last count ); if last count < 0 then

begin last count ← −1; get count ← 0;

end else get count ← last count ; end

else begin decr (last count ); get count ← 0;

end; end;

29. Here are two global variables associated with get count . ⟨ Globals in the outer block 9 ⟩ +≡ last count : integer ; { the last count read from count file, or −n if that file is n counts short } n: integer ; { a temporary counter }

30. ⟨ Set initial values 10 ⟩ +≡ last count ← 0; 31. The proper number of counts is checked at the end, thusly: ⟨ Check that count file had the right number of counts 31 ⟩ ≡

if last count < 0 then begin print nl (´ ␣ ␣ ␣ ␣´ , (−last count ) : 1, ´ ␣ ␣ ␣ ´ ); error ; end

else begin n ← −1; repeat incr (n); read ln(count file, last count ); until last count < 0; if n > 0 then

begin print nl (´ ␣ ␣ ␣ ␣´ , n : 1, ´ ␣ ␣ ␣ ´ ); mark harmless ; end;

end

This code is used in section 193.

§32  PROFILE  REPORTING ERRORS TO THE USER 11

32. Reporting errors to the user. The command ‘err print (´ ␣ ␣ ´ )’ will report a syntax error to the user, by printing the error message at the beginning of a new line and then giving 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.

The actual error indications are provided by a procedure called error . Since is supposedly working from a running PASCAL program, its error messages have not been

jazzed up for super error recovery. The main purpose of the many possible calls to err print in this program is merely to give some assurance that knows what it is doing.

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

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

var k, l: 0 . . buf size; { indices into buffer } begin ⟨ Print error location based on input buffer 33 ⟩; update terminal ; mark error ; end;

See also section 34. This code is used in section 2.

33. The error locations can be indicated by using the global variables loc and line, which tell respectively the first unlooked-at position in buffer and the current line number. This routine should be modified on systems whose standard text editor has special line-numbering conventions. ⟨ Print error location based on input buffer 33 ⟩ ≡

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

if buffer [k − 1] = ´ 10 then print (´ ␣´ ) { tab becomes space } 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 dots } end

This code is used in section 32.

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 PROFILE 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 32 ⟩ +≡ procedure jump out ;

begin goto end of PROFILE ; end;

12  REPORTING ERRORS TO THE USER  PROFILE §35

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  PROFILE  THE DYNAMIC MEMORY 13

37. The dynamic memory. A large array called mem is used for general-purpose list manipulations. Each word of this array contains either a single integer or two halfwords. Halfwords are used to hold pointers or numeric data, as is usual in list processing. As in TEX82, halfwords are assumed to contain values between min halfword and max halfword ; these quantities should be defined so that PASCAL packs two halfwords into the space of an integer . A null pointer is represented by null , which is defined to be min halfword , the index of the smallest word in mem.

define min halfword ≡ 0

define max halfword ≡ 65535

define null ≡ min halfword ⟨ Types in the outer block 14 ⟩ +≡

halfword = min halfword . . max halfword ;

pointer = null . . mem size;

two halves = packed record lh, rh: halfword ;

end; memory word = record case boolean of

false: (int : integer ); true: (hh : two halves ); end;

38. We use the notations info(p) and link (p) to stand for the halfwords in mem[p]; or val (p) to stand for the fullword integer value stored there.

The largest mem index used so far is called mem end . Available locations ≤ mem end are maintained in a list avail , link (avail ), link (link (avail )), …; when this list is empty, we have avail = null .

define info(#) ≡ mem[#].hh.lh { the “left” halfword in a given node }

define link (#) ≡ mem[#].hh.rh { the “right” halfword in a given node }

define val (#) ≡ mem[#].int { the memory word as a (possibly signed) integer } ⟨ Globals in the outer block 9 ⟩ +≡ mem: array [pointer ] of memory word ; { dynamic all-purpose memory } mem end : pointer ; { we haven’t touched mem[mem end + 1 . . mem size] } avail : pointer ; { head of available space stack }

39. ⟨ Set initial values 10 ⟩ +≡ mem end ← null ; avail ← null ;

40. The function get avail returns a pointer to a new word whose link field is null. An overflow stop occurs if no room is left. ⟨ Memory management procedures 40 ⟩ ≡ function get avail : pointer ; { allocation }

var p: pointer ; { the new node }

begin p ← avail ; { get top location in avail stack }

if p ≠ null then avail ← link (p) { and pop it off }

else if mem end < mem size then { or go into virgin territory } begin incr (mem end ); p ← mem end ; end

else overflow (´ ´ ); link (p) ← null ; get avail ← p; end;

This code is used in section 2.

14  THE DYNAMIC MEMORY  PROFILE §41

41. Conversely, word p can be recycled by calling free avail (p). ( doesn’t bother to free up everything it could, but it does use free avail for things that are likely to consume a lot of memory.)

§42  PROFILE  IDENTIFIERS 15

define free avail (#) ≡ { liberation } begin link (#) ← avail ; avail ← #; end 42. Identifiers. There’s a separate memory for identifier names; such names will never be deleted after they’ve been inserted. ’s name memory is implemented essentially as TEX’s string pool: Name number k consists of characters id start [k] through id start [k+1]−1, inclusive, of the id pool array. Uppercase letters have been converted to their lowercase counterparts before being stored in id pool . ⟨ Types in the outer block 14 ⟩ +≡

id pointer = 0 . . max names ; pool pointer = 0 . . pool size;

43. The variables pool ptr and id ptr are used to allocate space in id pool and id start , respectively. The “meaning” of identifier number k is stored in equiv [k]; it consists of two halfwords called id code(k)

and id aux (k).

define length(#) ≡ (id start [# + 1] − id start [#])

define id code(#) ≡ equiv [#].lh

define id aux (#) ≡ equiv [#].rh ⟨ Globals in the outer block 9 ⟩ +≡ id pool : packed array [pool pointer ] of ASCII code; { the characters } id start : array [id pointer ] of pool pointer ; { the starting pointers } pool ptr : pool pointer ; { the first unused position in id pool } id ptr : id pointer ; { the highest used position in id start } equiv : array [id pointer ] of two halves ; { the equivalents }

44. The first 128 “identifiers” are one character long, and they represent themselves. (This is an exception to the lowercase-only convention stated earlier.) Undefined entries have id code = undefined and id aux = 0.

define undefined = 34 { this should be greater than reserved word codes that follow! } ⟨ Set initial values 10 ⟩ +≡

id code(0) ← undefined ; id aux (0) ← 0; { set up equiv [0] }

for i ← 0 to 127 do begin id start [i] ← i; id pool [i] ← i; equiv [i] ← equiv [0]; end;

id start [128] ← 128; id ptr ← 128; pool ptr ← 128;

45. A hash table is used to help locate identifiers that are more than one character long. If hash[k] is nonzero, it points to such an identifier.

Two global variables called id first and id loc are used to specify buffer locations when an identifier needs to be located. ⟨ Globals in the outer block 9 ⟩ +≡ hash: array [id pointer ] of id pointer ; { hash table for linear probing } id first , id loc: 0 . . buf size; { starting and ending locations in buffer }

46. ⟨ Set initial values 10 ⟩ +≡ for i ← 0 to max names do hash[i] ← 0;

16  IDENTIFIERS  PROFILE §47

47. The id lookup procedure finds a given identifier and returns a pointer to its index in id start . The identifier to be found appears in locations id first through id loc − 1, inclusive, of the buffer array.

It is possible to overflow the pool capacity or the name capacity. But the hash table will never fill up, because the first 128 names have been kept out of that table. function id lookup: id pointer ; { finds the current identifier }

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

h: id pointer ; { hash code }

k: pool pointer ; { index into id pool }

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

p: id pointer ; { where it is being sought } begin l ← id loc − id first ; if l = 1 then p ← buffer [id first ] else begin ⟨ Compute the hash code, h 48 ⟩;

⟨ Compute the id pointer, p 49 ⟩;

end; id lookup ← p; end;

48. 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 max names .

(That’s why max names is supposed to be prime.) ⟨ Compute the hash code, h 48 ⟩ ≡

h ← buffer [id first ]; i ← id first + 1; while i < id loc do

begin h ← (h + h + buffer [i]) mod max names ; incr (i);

end

This code is used in section 47.

49. ⟨ Compute the id pointer, p 49 ⟩ ≡

loop begin p ← hash[h]; if p = 0 then ⟨ Enter a new name into the hash table at position h and goto found 50 ⟩; if length(p) = l then ⟨ Compare name p with the current identifier; goto found if equal 51 ⟩; if h = 0 then h ← max names else decr (h); end;

found :

This code is used in section 47.

50. ⟨ Enter a new name into the hash table at position h and goto found 50 ⟩ ≡ begin if pool ptr + l > pool size then overflow (´ ␣ ´ ); if id ptr = max names then overflow (´ ´ ); i ← id first ; while i < id loc do

begin id pool [pool ptr ] ← buffer [i]; incr (i); incr (pool ptr );

end; p ← id ptr ; hash[h] ← p; equiv [p] ← equiv [0]; { the new identifier is undefined } incr (id ptr ); id start [id ptr ] ← pool ptr ; goto found ; end

This code is used in section 49.

51. ⟨ Compare name p with the current identifier; goto found if equal 51 ⟩ ≡ begin i ← id first ; k ← id start [p]; while (i < id loc) ∧ (buffer [i] = id pool [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 49.

18  INITIALIZING THE TABLE OF RESERVED WORDS  PROFILE §52

52. Initializing the table of reserved words. The reserved words of PASCAL (e.g., ‘begin’) are given distinctive id code values (e.g., ‘begin code’). All reserved words whose code value is between min blank left and max blank left will be preceded by a blank space in ’s output; all reserved words whose code value is between min blank right and max blank right will be followed by a blank space.

define array code = 1 { array } define file code = 2 { file } define nil code = 3 { nil } define set code = 4 { set } define end code = 5 { end } define min blank left = 6 define do code = 6 { do } define then code = 7 { then } define min blank right = 8 define and code = 8 { and } define div or mod code = 9 { div, mod } define to or downto code = 10 { downto, to } define in code = 11 { in } define of code = 12 { of } define or code = 13 { or } define max blank left = 13 define begin code = 14 { begin } define case code = 15 { case } define const code = 16 { const } define else code = 17 { else } define for code = 18 { for } define function code = 19 { function } define procedure code = function code + 1 { procedure } define goto code = 21 { goto } define if code = 22 { if } define label code = 23 { label } define not code = 24 { not } define packed code = 25 { packed } define program code = 26 { program } define record code = 27 { record } define repeat code = 28 { repeat } define type code = 29 { type } define until code = 30 { until } define var code = 31 { var } define while code = 32 { while } define with code = 33 { with—not currently implemented } define max blank right = 33 define aa = 34 { the next code defined below will be aa + 1 }

{ note that undefined = 34 }

§53  PROFILE  INITIALIZING THE TABLE OF RESERVED WORDS 19

53. We have to get PASCAL’s reserved words into the hash table, and the simplest way to do this is to insert them every time is run. A few macros permit us to do the initialization with a compact program.

define sid tail tail (#) ≡ id aux (cur name) ← # define sid tail (#) ≡ id code(cur name) ← #; sid tail tail define sid9 (#) ≡ buffer [9] ← #; cur name ← id lookup; sid tail define sid8 (#) ≡ buffer [8] ← #; sid9 define sid7 (#) ≡ buffer [7] ← #; sid8 define sid6 (#) ≡ buffer [6] ← #; sid7 define sid5 (#) ≡ buffer [5] ← #; sid6 define sid4 (#) ≡ buffer [4] ← #; sid5 define sid3 (#) ≡ buffer [3] ← #; sid4 define sid2 (#) ≡ buffer [2] ← #; sid3 define sid1 (#) ≡ buffer [1] ← #; sid2 define id2 ≡ id first ← 8; sid8 define id3 ≡ id first ← 7; sid7 define id4 ≡ id first ← 6; sid6 define id5 ≡ id first ← 5; sid5 define id6 ≡ id first ← 4; sid4 define id7 ≡ id first ← 3; sid3 define id8 ≡ id first ← 2; sid2 define id9 ≡ id first ← 1; sid1

⟨ Globals in the outer block 9 ⟩ +≡ cur name: id pointer ; { points to the identifier just inserted } 54. The intended use of the macros above might not be immediately obvious, but the riddle is answered by the following: ⟨ Set up all the reserved words and predefined identifiers 54 ⟩ ≡

id loc ← 10; { the longest word has 9 characters } id3 ( )( )( )(and code)(0); id5 ( )( )( )( )( )(array code)(0); id5 ( )( )( )( )( )(begin code)(0); id4 ( )( )( )( )(case code)(0); id5 ( )( )( )( )( )(const code)(0); id3 ( )( )( )(div or mod code)(0); id2 ( )( )(do code)(0); id6 ( )( )( )( )( )( )(to or downto code)(1); id4 ( )( )( )( )(else code)(0); id3 ( )( )( )(end code)(0); id4 ( )( )( )( )(file code)(0); id3 ( )( )( )(for code)(0); id8 ( )( )( )( )( )( )( )( )(function code)(0); id4 ( )( )( )( )(goto code)(0); id2 ( )( )(if code)(0); id2 ( )( )(in code)(0); id5 ( )( )( )( )( )(label code)(0); id3 ( )( )( )(div or mod code)(1); id3 ( )( )( )(nil code)(0); id3 ( )( )( )(not code)(0); id2 ( )( )(of code)(0); id2 ( )( )(or code)(0); id6 ( )( )( )( )( )( )(packed code)(0); id9 ( )( )( )( )( )( )( )( )( )(procedure code)(0); id7 ( )( )( )( )( )( )( )(program code)(0); id6 ( )( )( )( )( )( )(record code)(0); id6 ( )( )( )( )( )( )(repeat code)(0); id3 ( )( )( )(set code)(0); id4 ( )( )( )( )(then code)(0); id2 ( )( )(to or downto code)(0); id4 ( )( )( )( )(type code)(0); id5 ( )( )( )( )( )(until code)(0); id3 ( )( )( )(var code)(0); id5 ( )( )( )( )( )(while code)(0); id4 ( )( )( )( )(with code)(0);

See also sections 55, 63, 66, 68, 69, and 188. This code is used in section 193.

55. A large number of other predeclared identifiers also need to be entered into the hash table. Most of these will be discussed later; the word forward is entered here: ⟨ Set up all the reserved words and predefined identifiers 54 ⟩ +≡

id7 ( )( )( )( )( )( )( )(undefined )(0); fwd loc ← cur name;

56. ⟨ Globals in the outer block 9 ⟩ +≡ fwd loc: id pointer ; { location of forward in the lookup table }

§57  PROFILE  REPRESENTATION OF TYPES 21

57. Representation of types. The rich type structures of PASCAL must be represented inside of since it is necessary to understand all of the identifiers and variables that come along. We represent a type by a memory word whose info field identifies a particular sort of type; the link field is an auxiliary argument in case the type has further structure.

The rules for each type are given below, assuming that t points to a memory word representing the type in question. Predefined types are placed into mem locations real loc, etc. ⟨ Globals in the outer block 9 ⟩ +≡ real loc: pointer ; { where real type lives in mem } char loc: pointer ; { char type } int loc: pointer ; { integer type } bool loc: pointer ; { boolean type } text loc: pointer ; { text type } nil loc: pointer ; { nil type } file loc: pointer ; { file type } string loc: pointer ; { string type } zero loc: pointer ; { the value 0 } one loc: pointer ; { the value 1 } extra loc: pointer ; { extra parameters }

58. The initialize procedure is declared after get avail , and we have already specified the initialization of get avail ; therefore it’s possible to allocate words of mem as part of the work of initialization. Pointer variables p and q are used for this purpose. ⟨ Local variables for initialization 11 ⟩ +≡ p, q: pointer ; { used to construct predeclared information }

59. First come the standard simple types real and char , which are represented by info(t) = real type and info(t) = char type, respectively; in both cases link (t) = null .

A subrange type of integers a . . b is represented by info(t) = int type, val (info(link (t))) = a, and val (link (link (t))) = b. An enumerated type such as (red , yellow , blue) is effectively replaced by a subrange type red . . blue, accompanied by the constant definitions red = 0, yellow = 1, blue = 2. The standard simple types integer and boolean are treated as −max int . . max int and (false, true), respectively.

define real type = 1 { identifies real type }

define char type = 2 { identifies char type }

define int type = 3 { identifies integer subrange type } ⟨ Set initial values 10 ⟩ +≡

real loc ← get avail ; info(real loc) ← real type;

char loc ← get avail ; info(char loc) ← char type;

int loc ← get avail ; info(int loc) ← int type; p ← get avail ; link (int loc) ← p;

q ← get avail ; val (q) ← −max int ; info(p) ← q;

q ← get avail ; val (q) ← max int ; link (p) ← q;

bool loc ← get avail ; info(bool loc) ← int type; p ← get avail ; link (bool loc) ← p;

zero loc ← get avail ; val (zero loc) ← 0; info(p) ← zero loc;

one loc ← get avail ; val (one loc) ← 1; link (p) ← one loc;

22  REPRESENTATION OF TYPES  PROFILE §60

60. Structured types are represented by info(t) = array type, record type, set type, or file type codes, or these same codes plus 1 if the structure is packed. The value of link (t) is null if the type is not further specified (e.g., if a standard procedure takes any file as a parameter).

Otherwise, in the case of an array, info(link (t)) points to the index type (which will be a special case of int type or char type), and link (link (t)) points to the component type (which might be another array).

In the case of a record, we retain only the names and types of fields that might be used, not the particular way they might occur as variants. For example,

record a: real ; case b: boolean of false: (c, d: integer ; case integer of 0: (e : real )); true: (f: packed file of set of char ) end

will have the same representation as

record a: real ; b: boolean; c, d: integer ; e: real ; f: packed file of set of char ; end

inside of . A list of fields starts at link (t). If u points to a node of this field list, info(info(u)) points to the field name, link (info(u)) to the field type, and link (u) to the next node in the list.

For set and file types, link (t) points to the base type involved. Thus, for example, a packed file of set of char would have info(t) = packed file type, info(link (t)) = set type, and info(link (link (t))) = char type. The standard file type text is considered to yield a file of char , as far as is concerned.

A more-or-less standard type string is introduced to represent ‘packed array [1 . . n] of char ’ where n is unspecified.

define array type = 4 define packed array type = array type + 1 define record type = 6 define packed record type = record type + 1 define set type = 8 define packed set type = set type + 1 define file type = 10 define packed file type = file type + 1

⟨ Set initial values 10 ⟩ +≡ text loc ← get avail ; info(text loc) ← file type; link (text loc) ← char loc; file loc ← get avail ; info(file loc) ← file type; { link (file loc) = null } string loc ← get avail ; info(string loc) ← packed array type; p ← get avail ; link (string loc) ← p; q ← get avail ; info(p) ← q; link (p) ← char loc; p ← get avail ; info(q) ← int type; link (q) ← p; info(p) ← one loc; { link (q) = null }

61. Finally, a pointer type like ‘↑person’ is represented by info(t) = pointer type, with link (t) pointing to the identifier, ‘person’. Or link (t) = null , in the case of the type corresponding to the standard pointer value nil.

define pointer type = 12 ⟨ Set initial values 10 ⟩ +≡

§62  PROFILE  IDENTIFIER INTERPRETATION 23

nil loc ← get avail ; info(nil loc) ← pointer type; 62. Identifier interpretation. The equivalent of each identifier consists of two halfwords called the id code and id aux , as we have seen. When an identifier is declared, its equivalent is redefined; and the old value is saved for future restoration if this declaration is not in the outer block.

The id code might be undefined or it might be one of the codes like while code for a reserved word; or it might be one of the codes for non-reserved words that we are about to discuss.

63. A constant declaration like ‘const a = 3’ will be recorded as id code = small const and id aux = 3. But if the constant is negative or greater than 9999, the id code will be int const and the id aux will point to a mem word whose val is the constant value.

Real constants simply have id code = real const and id aux = null ; string constants simply have id code = string const and id aux the string length. doesn’t keep track of the precise values of real and string constants.

A type definition like ‘type b = array [1 . . 3] of char ’ will be recorded as id code = defined type; id aux will point to the type representation (in this case a node whose info is array type and whose link points to a node whose info points to a type specification of 1 . . 3 and whose link is char loc).

A var declaration like ‘var c: integer ’ will be recorded as id code = variable and id aux = int loc. define min case label = aa + 1 { the following codes have been carefully ordered! } define small const = aa + 1 define int const = aa + 2 define plus or minus = aa + 3 { this occurs in front of case-label constants } define string const = aa + 4 define bool const = aa + 5 define max case label = aa + 5 define real const = aa + 6 define defined type = aa + 7 define variable = aa + 8

⟨ Set up all the reserved words and predefined identifiers 54 ⟩ +≡ id5 ( )( )( )( )( )(bool const )(0); id4 ( )( )( )( )(bool const )(1); p ← get avail ; val (p) ← max int ; id6 ( )( )( )( )( )( )(int const )(p); id7 ( )( )( )( )( )( )( )(defined type)(int loc); id7 ( )( )( )( )( )( )( )(defined type)(bool loc); id4 ( )( )( )( )(defined type)(real loc); id4 ( )( )( )( )(defined type)(char loc); id6 ( )( )( )( )( )( )(defined type)(string loc); id4 ( )( )( )( )(defined type)(text loc); id5 ( )( )( )( )( )(variable)(text loc); id6 ( )( )( )( )( )( )(variable)(text loc); id3 ( )( )( )(variable)(text loc); id6 ( )( )( )( )( )( )(small const )(6969); { label for othercases }

24  IDENTIFIER INTERPRETATION  PROFILE §65

64. ⟨ Globals in the outer block 9 ⟩ +≡ p, q, r: pointer ; { for list manipulation } 65. A procedure declaration causes id code to be procedure id , and id aux will point to a list of nodes that specify the parameters. A function declaration is similar, but id aux points to a word whose info points to the result type and whose link points to the parameter specification list.

For each node q on the parameter specification list, info(q) points to a node whose info and link fields correspond to the id code and id aux of the parameter itself.

This is best explained by an example. Consider the procedure heading

procedure b(function f(x : char ) : boolean; x, y : integer ; var z : real ).

This defines the identifier b, and (one level deeper) also f, x, y, and z. The x inside f is a dummy name of no importance. The id code for f will be function id ; and its id aux will point to p, where info(p) = bool loc and link (p) = q, and where info(q) = r and link (q) = null , and where info(r) = variable and link (r) = char loc. The id code for x and y will be variable and the id aux will be int loc. The id code for z will be var param and the id aux will be real loc. Finally, the id code for b will be procedure id , and its id aux will point to a list of four items, pointing to nodes that copy the equiv table entries of f, x, y, and z.

If we had a more complex definition like

procedure big (procedure b [as above])

the data structure for b would be the same, but no declarations of f, x, y, or z would be made. define function id = aa + 9 define procedure id = function id + 1 define terminal procedure id = procedure id + 1 { declared with ‘ ’ } define var param = aa + 12

66. As an example of procedure representation, let us put call i into the symbol table. This is a nonstandard procedure available in Hedrick’s PASCAL; it calls an arbitrary monitor routine. The calling sequence is essentially the same as if the declaration had been

procedure call i (c, lh, rh : integer ; var v, s : integer )

and adds no extra run time for execution of call i . ⟨ Set up all the reserved words and predefined identifiers 54 ⟩ +≡

q ← get avail ; info(q) ← variable; link (q) ← int loc; { integer parameter }

r ← get avail ; { this will be the argument list head }

p ← r; info(p) ← q; link (p) ← get avail ; { first argument }

p ← link (p); info(p) ← q; link (p) ← get avail ; { second argument }

p ← link (p); info(p) ← q; link (p) ← get avail ; { third argument }

q ← get avail ; info(q) ← var param; link (q) ← int loc; { var integer parameter }

p ← link (p); info(p) ← q; link (p) ← get avail ; { fourth argument }

p ← link (p); info(p) ← q; { fifth and last argument }

id5 ( )( )( )( )( )(procedure id )(r); 67. Standard procedures like ‘read ’ can have two other sorts of parameters not available to ordinary programmers. If the info field of an argument is optional file param, it means that a default file variable will be inserted as an argument if the procedure call does not have a file argument in the current position; the link field contains the runtime estimate. If the info field is spec param, the argument is allowed to be of any type; in this case the link field points to a list of extra runtime weights that apply if the actual parameter is of type char , integer , real , array, or other, respectively. (These weights include the store cost ; and if the first parameter is a spec param, the weight also includes the calling overhead.) A spec param is optional; if info(info(p)) = spec param in a procedure’s argument list, then link (p) = p; i.e., the argument list is arbitrarily long.

If the result type of a function is null , the function returns the type of its last argument. define optional file param = aa + 13 define spec param = aa + 14 define bb = aa + 14 { the next code defined below will be bb + 1 }

68. Here are the standard functions of PASCAL, and a few nonstandard ones needed for system programming (available in Hedrick’s PASCAL system). We set things up so that, e.g., abs , looks like a function call (even though the compiler expands it in-line).

define constant spec(#) ≡ r ← get avail ; q ← get avail ; info(q) ← spec param; info(r) ← q;

link (r) ← r; p ← get avail ; link (q) ← p; link (p) ← p; info(p) ← # define file spec(#) ≡ p ← get avail ; q ← get avail ; info(p) ← q; link (p) ← extra loc;

info(q) ← optional file param; link (q) ← #

⟨ Set up all the reserved words and predefined identifiers 54 ⟩ +≡

constant spec(fetch cost + store cost ); extra loc ← r; constant spec(unary cost );

{ now r represents spec param with unary cost } p ← get avail ; info(p) ← null ; link (p) ← r; { unspecified result type } id3 ( )( )( )(function id )(p); id4 ( )( )( )( )(function id )(p); id4 ( )( )( )( )(function id )(p); p ← get avail ; info(p) ← bool loc; link (p) ← r; { boolean result } id3 ( )( )( )(function id )(p); constant spec(real mult cost ); p ← get avail ; info(p) ← null ; link (p) ← r; { unspecified result type } id3 ( )( )( )(function id )(p); constant spec(ord chr cost ); p ← get avail ; info(p) ← int loc; link (p) ← r; { integer result } id3 ( )( )( )(function id )(p); p ← get avail ; info(p) ← char loc; link (p) ← r; { char result } id3 ( )( )( )(function id )(p); constant spec(int real cost ); p ← get avail ; info(p) ← int loc; link (p) ← r; { integer result } id5 ( )( )( )( )( )(function id )(p); id5 ( )( )( )( )( )(function id )(p); constant spec(transcendental cost ); p ← get avail ; info(p) ← real loc; link (p) ← r; { real result } id6 ( )( )( )( )( )( )(function id )(p); id3 ( )( )( )(function id )(p); id3 ( )( )( )(function id )(p); id3 ( )( )( )(function id )(p); id2 ( )( )(function id )(p); id4 ( )( )( )( )(function id )(p); constant spec(eof cost ); p ← get avail ; info(p) ← bool loc; link (p) ← r; { boolean result } id3 ( )( )( )(function id )(p); id4 ( )( )( )( )(function id )(p); q ← get avail ; info(q) ← file loc; p ← get avail ; info(p) ← int loc; link (p) ← q; { maps file to integer } id6 ( )( )( )( )( )( )(function id )(p); 69. Similarly, here are the standard procedures. ⟨ Set up all the reserved words and predefined identifiers 54 ⟩ +≡

constant spec(new cost ); id3 ( )( )( )(procedure id )(r); id7 ( )( )( )( )( )( )( )(procedure id )(r); file spec(open cost ); id5 ( )( )( )( )( )(procedure id )(p); id7 ( )( )( )( )( )( )( )(procedure id )(p); file spec(close cost ); id5 ( )( )( )( )( )(procedure id )(r); file spec(0); id5 ( )( )( )( )( )(procedure id )(p); file spec(break in cost ); id7 ( )( )( )( )( )( )( )(procedure id )(p); constant spec(get put cost ); id3 ( )( )( )(procedure id )(r); id3 ( )( )( )(procedure id )(r); constant spec((pack cost div 3)); id4 ( )( )( )( )(procedure id )(r); id6 ( )( )( )( )( )( )(procedure id )(r); p ← get avail ; info(p) ← optional file param; link (p) ← 0; r ← get avail ; info(r) ← p; p ← get avail ; link (r) ← p; link (p) ← p; q ← get avail ; info(p) ← q; info(q) ← spec param; link (q) ← get avail ; q ← link (q); info(q) ← char string cost ; link (q) ← get avail ; q ← link (q); info(q) ← int string cost ; link (q) ← get avail ; q ← link (q); info(q) ← real string cost ; link (q) ← get avail ; q ← link (q); info(q) ← array string cost ; link (q) ← get avail ; q ← link (q); info(q) ← int string cost ; id4 ( )( )( )( )(procedure id )(r); id6 ( )( )( )( )( )( )(procedure id )(r); id5 ( )( )( )( )( )(procedure id )(r); id7 ( )( )( )( )( )( )( )(procedure id )(r); id4 ( )( )( )( )(procedure id )(r);

70. Identifier equivalents are saved and restored by means of ‘save stack ’. The variable save ptr points to the first unused location on this stack; and save ptr = save base + 2n, when n equivalents are to be restored at the end of the current block. Location save base − 1 contains the previous value of save base, if save base > 0; we have save base > 0 if and only if definitions are to be saved, i.e., if and only if we are not making a definition at the outermost level. A saved definition occupies two words on the save stack: First comes the old value of equiv [n] and then the value of n. ⟨ Globals in the outer block 9 ⟩ +≡ save stack : array [0 . . save size] of memory word ; save ptr : 0 . . save size; { number of locations used in save stack } save base: 0 . . save size; { bottom of current level } 71. The three operations we need for save stack maintenance are really simple. procedure save(n : id pointer );

begin if save base > 0 then begin if save ptr + 2 > save size then overflow (´ ␣ ´ ); save stack [save ptr ].hh ← equiv [n]; save stack [save ptr + 1].int ← n; save ptr ← save ptr + 2; end;

end; procedure push save stack ;

begin if save ptr + 1 > save size then overflow (´ ␣ ´ ); save stack [save ptr ].int ← save base; incr (save ptr ); save base ← save ptr ; end;

procedure unsave; var n: id pointer ; begin while save ptr > save base do

begin save ptr ← save ptr − 2; n ← save stack [save ptr + 1].int ; equiv [n] ← save stack [save ptr ].hh; end;

28  FREQUENCIES AND WEIGHTS  PROFILE §72

decr (save ptr ); save base ← save stack [save ptr ].int ; end; 72. Frequencies and weights. An operation of weight w that is performed f times contributes a total of w · f to the running time. Both w and f are integers, but the product w · f will be recorded as a floating-point quantity. (This avoids the need for multiple precision arithmetic; after all, the weights are only approximate.)

If we are currently in sections m_{1}, …, m_{k} (from the “outside in”), the product w · f is be added to the explicit cost of section m_{k} and to the implicit cost of sections m_{1}, …, m_{k−1}. By convention, m_{1} is always zero; hence the dummy section 0 will be credited with all accumulated costs. A stack is maintained with info(sec ptr ) = m_{k}, info(link (sec ptr )) = m_{k−1}, etc. ⟨ Globals in the outer block 9 ⟩ +≡ impl cost , expl cost : array [0 . . max modules ] of real ;

{ accumulated implicit and explicit runtime estimates }

static weight : array [0 . . max modules ] of integer ; { accumulated weight without regard to frequency } max section: 0 . . max modules ; { maximum section number whose weight has been recorded } sec ptr : pointer ; { top of the stack of current section numbers }

73. ⟨ Set initial values 10 ⟩ +≡

for i ← 0 to max modules do begin impl cost [i] ← 0.0; expl cost [i] ← 0.0; static weight [i] ← 0; end;

sec ptr ← get avail ; info(sec ptr ) ← 0; max section ← 0;

74. The stack of section numbers is kept up to date by two fairly simple procedures. Mismatched numbers (e.g., ) are not permitted. procedure push section(m : halfword );

var p: pointer ;

begin if m > max section then begin if m > max modules then overflow (´ ´ ); max section ← m; end;

p ← get avail ; info(p) ← m; link (p) ← sec ptr ; sec ptr ← p;

end; procedure pop section(m : halfword );

var p: pointer ;

begin if (m = 0) ∨ (info(sec ptr ) ≠ m) then

fatal error (´ ␣ ␣ ´ ´ ␣ ␣ ␣ ␣´ , info(sec ptr ) : 1); p ← sec ptr ; sec ptr ← link (p); free avail (p); end;

75. If ’s frequency assumptions are correct, the program component that it is currently processing was executed cur freq times.

Another global quantity, out wt , contains the total weight that has not yet been reported in the output file. ⟨ Globals in the outer block 9 ⟩ +≡ cur freq : integer ; { the current frequency } out wt : integer ; { accumulated weight to show on the next output line }

76. ⟨ Set initial values 10 ⟩ +≡ cur freq ← 0; out wt ← 0;

§77  PROFILE  FREQUENCIES AND WEIGHTS 29

77. Here is the procedure that multiplies the current frequency by a given weight and adds it to all appropriate subtotals. procedure add weight (w : integer );

var p, q: pointer ; { for list manipulation }

wf : real ; { weight times frequency } begin out wt ← out wt + w; static weight [info(sec ptr )] ← static weight [info(sec ptr )] + w; wf ← w; wf ← wf ∗ cur freq ; expl cost [info(sec ptr )] ← expl cost [info(sec ptr )] + wf ; p ← link (sec ptr ); while p ≠ null do

begin impl cost [info(p)] ← impl cost [info(p)] + wf ; p ← link (p); end;

end;

78. After the weights have all been gathered, it’s time to massage them a bit and sort them, then publish the output. ⟨ Globals in the outer block 9 ⟩ +≡ h, i, j, k, nn: 0 . . max modules ; { variables to control sorting, etc. } x: array [0 . . max modules ] of 0 . . max modules ; { sections being sorted } factor : real ; { multiply by this to get percentage of total weight } c: real ; { temporary placeholder for a sort key } m: 0 . . max modules ; { ditto }

79. ⟨ Output the accumulated statistics 79 ⟩ ≡ begin for k ← 0 to max section do impl cost [k] ← impl cost [k] + expl cost [k]; if impl cost [0] = 0.0 then

begin print nl (´ ␣ ␣ ␣ ´ ); mark harmless ; end

else begin factor ← 100.0/impl cost [0]; page; write ln(´ ␣ ␣ ␣ ␣ ␣ ´ ); write ln; write ln(´ ´ , ´ ␣ ´ : 17, ´ %␣␣´ : 9, ´ ␣ ´ : 17, ´ %␣␣´ : 9, ´ ␣ ´ ); write ln; for k ← 0 to max section do

if (impl cost [k] ≠ 0.0) ∨ (static weight [k] ≠ 0) then write ln(k : 5, impl cost [k] : 17 : 1,

factor ∗ impl cost [k] : 9 : 4, expl cost [k] : 17 : 1, factor ∗ expl cost [k] : 9 : 4, static weight [k] : 13);

print nl (´ ´ ); update terminal ; ⟨ Sort the sections in order of implicit cost 80 ⟩; page; write ln(´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); write ln; for k ← 1 to nn do write ln(x[k] : 5, impl cost [x[k]] : 17 : 1, factor ∗ impl cost [x[k]] : 9 : 4); ⟨ Sort the sections in order of explicit cost 82 ⟩; page; write ln(´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); write ln; for k ← 1 to nn do write ln(x[k] : 5, expl cost [x[k]] : 17 : 1, factor ∗ expl cost [x[k]] : 9 : 4); print (´ ´ ); end;

end

This code is used in section 193.

80. Standard “Shellsort” is used [Art of Computer Programming, Algorithm 5.2.1D]. ⟨ Sort the sections in order of implicit cost 80 ⟩ ≡

nn ← 0; for k ← 0 to max section do

if impl cost [k] ≠ 0.0 then begin incr (nn); x[nn] ← k; end;

⟨ Choose starting increment, h, for Shellsort 81 ⟩; while h > 0 do

begin for j ← h + 1 to nn do begin i ← j − h; m ← x[j]; c ← impl cost [m]; if (c > impl cost [x[i]]) ∨ ((c = impl cost [x[i]]) ∧ (m < x[i])) then

repeat x[i + h] ← x[i]; x[i] ← m;

if i > h then i ← i − h;

until (c ≤ impl cost [x[i]]) ∧ ((c ≠ impl cost [x[i]]) ∨ (m ≥ x[i])); end;

h ← h div 3;

end

This code is used in section 79.

81. (See 5.2.1-(8) in The Art of Computer Programming.) ⟨ Choose starting increment, h, for Shellsort 81 ⟩ ≡

h ← 1; while h < nn do h ← 3 ∗ h + 1; h ← h div 9; if h = 0 then h ← 1;

This code is used in sections 80 and 82.

82. ⟨ Sort the sections in order of explicit cost 82 ⟩ ≡ nn ← 0; for k ← 0 to max section do

if expl cost [k] ≠ 0.0 then begin incr (nn); x[nn] ← k; end;

⟨ Choose starting increment, h, for Shellsort 81 ⟩; while h > 0 do

begin for j ← h + 1 to nn do begin i ← j − h; m ← x[j]; c ← expl cost [m]; if (c > expl cost [x[i]]) ∨ ((c = expl cost [x[i]]) ∧ (m < x[i])) then

repeat x[i + h] ← x[i]; x[i] ← m;

if i > h then i ← i − h;

until (c ≤ expl cost [x[i]]) ∧ ((c ≠ expl cost [x[i]]) ∨ (m ≥ x[i])); end;

h ← h div 3;

end

This code is used in section 79.

§83  PROFILE  LOW LEVEL OUTPUT 31

83. Low level output. A queue of data waiting to be output is maintained in a linked list that begins at location link (head ) and ends at tail ; the queue is empty if head = tail . We have link (tail ) = null at all times.

The entries in this list are either commands or identifier pointers; a command is recognized by the fact that it is ≤ max command . Some commands take arguments, in which case the argument follows in the queue.

We shall use the term “translation list” to refer to a sequence of commands and identifier pointers, because such lists are produced as output of the parsing routines that will be described later. ’s main activity is to parse the given PASCAL program and to translate it into a translation list.

define append (#) ≡ begin link (tail ) ← get avail ; tail ← link (tail ); info(tail ) ← #; end

⟨ Globals in the outer block 9 ⟩ +≡ head , tail : pointer ; { pointers for the main translation list }

84. ⟨ Set initial values 10 ⟩ +≡ head ← get avail ; tail ← head ;

85. The out macro puts a given item on the current translation list.

define out (#) ≡ begin link (tail ) ← get avail ; tail ← link (tail ); info(tail ) ← #; end

86. Here is a list of all the commands that might appear in a translation list.

define verbatim = 0 { entries up to the next verbatim should be output without a line break } define begin section = 1 { output ‘ m ’, where m is the next entry } define end section = 2 { output ‘ m ’, where m is the next entry } define change weight = 3 { output ‘ v ’, where the next entry points to v } define backspace = 4 { back up one character, if at the left margin } define indent = 5 { increase indentation by one } define outdent = 6 { decrease indentation by one }

define all caps = 7 { add  −  to all characters of the next identifier }
define initial cap = 8 { add  −  to the first character of the next identifier }

define max command = 8

87. A global array out buf is used to accumulate characters before they are printed. Output lines are indented by cur indent . ⟨ Globals in the outer block 9 ⟩ +≡ cur indent : 0 . . out buf size; { indentation } out buf : array [0 . . out buf size] of ASCII code; { characters to be output } out line: integer ; { serial number of the next line of output }

32  LOW LEVEL OUTPUT  PROFILE §89

88. ⟨ Set initial values 10 ⟩ +≡ cur indent ← 0; out line ← 1; 89. The flush out procedure outputs the current translation list and removes it from memory. If the list is empty, nothing happens. Otherwise one or more lines are output, with weight and frequency information placed on the final line (if out wt and/or cur freq are nonzero). procedure flush out ;

label done; var p, q: pointer ; { for list manipulation }

i, j, k: 0 . . out buf size; { indices into out buf } t: pool pointer ; { index into id pool } offset , next offset : integer ; { 0 or − } n: halfword ; { command or id pointer } v, w: integer ; { registers used in decimal output conversion }

begin if tail ≠ head then begin p ← link (head ); for k ← 1 to cur indent do out buf [k − 1] ← ␣ ; k ← cur indent ; offset ← 0; next offset ← 0; while p ≠ null do

begin ⟨ Put material corresponding to command p into out buf ; also advance p to the last node of

the command 90 ⟩; q ← link (p); free avail (p); p ← q; end;

⟨ Write out buf , out wt , and cur freq 92 ⟩; tail ← head ; end;

end;

90. Variable k represents the end of the buffer contents before a command is processed; variable j represents the buffer’s end after the command. ⟨ Put material corresponding to command p into out buf ; also advance p to the last node of the

command 90 ⟩ ≡ n ← info(p); j ← k; if n > max command then ⟨ Put an identifier into the buffer 96 ⟩

else case n of

verbatim: ⟨ Output entries verbatim 97 ⟩; begin section, end section, change weight : ⟨ Output a special comment 100 ⟩; backspace: if k > 0 then

if k = cur indent then decr (j); indent : ⟨ Increase cur indent 98 ⟩; outdent : ⟨ Decrease cur indent 99 ⟩; all caps : begin offset ← − ; next offset ← offset ;

end; initial cap: offset ← − ; { next offset = 0 } end; { there are no other cases }

if j > line length then ⟨ Write out buf [0 . . k − 1] and shift the remaining material left in the buffer 91 ⟩; k ← j { this value is ≤ line length }

This code is used in section 89.

91. Lines that exceed line length are broken, and excess material is indented by cur indent + 2. ⟨ Write out buf [0 . . k − 1] and shift the remaining material left in the buffer 91 ⟩ ≡

begin for i ← 0 to k − 1 do write(xchr [out buf [i]]); if out line mod 5 = 0 then ⟨ Fill out a broken line with leaders 93 ⟩ else write ln; incr (out line); for i ← 1 to cur indent + 2 do out buf [i − 1] ← ␣ ; i ← cur indent + 2; if j − (k − i) > line length then overflow (´ ␣ ´ ); while k < j do

begin out buf [i] ← out buf [k]; incr (i); incr (k);

end; j ← i; { k need not be reset } end;

This code is used in section 90.

92. ⟨ Write out buf , out wt , and cur freq 92 ⟩ ≡

if k > 0 then begin for j ← 0 to k − 1 do write(xchr [out buf [j]]); if out line mod 5 = 0 then ⟨ Fill out a normal line with leaders 95 ⟩ else begin if (out wt ≠ 0) ∨ (cur freq ≠ 0) then

begin if k < line length then write(´ ␣´ : line length − k); write(out wt : weight length, cur freq : freq length); end; write ln; end;

out wt ← 0; incr (out line);

end

This code is used in section 89.

93. ⟨ Fill out a broken line with leaders 93 ⟩ ≡ begin for i ← k + 1 to line length + weight length + freq length do write(´ ´ ); write ln; ⟨ Check for end of page 94 ⟩; end

This code is used in section 91.

94. ⟨ Check for end of page 94 ⟩ ≡

if out line mod 100 = 0 then begin print (´ ´ ); page; if out line mod 500 = 0 then print (out line : 1); update terminal ; { progress report } end

This code is used in sections 93 and 95.

95. ⟨ Fill out a normal line with leaders 95 ⟩ ≡

begin if (out wt = 0) ∧ (cur freq = 0) then

for i ← k + 1 to line length + weight length + freq length do write(´ ´ ) else begin for i ← k + 1 to line length do write(´ ´ );

i ← weight length − 1; v ← 10; while v ≤ out wt do

begin v ← 10 ∗ v; decr (i); end;

for j ← 1 to i do write(´ ´ ); write(out wt : 1); i ← freq length − 1; v ← 10; while v ≤ cur freq do

begin v ← 10 ∗ v; decr (i); end;

for j ← 1 to i do write(´ ´ ); write(cur freq : 1); end;

write ln; ⟨ Check for end of page 94 ⟩; end

This code is used in section 92.

96. define put out (#) ≡ begin out buf [j] ← #; incr (j); end

⟨ Put an identifier into the buffer 96 ⟩ ≡

begin for t ← id start [n] to id start [n + 1] − 1 do begin put out (id pool [t] + offset ); offset ← next offset ; end;

offset ← 0; next offset ← 0; end

This code is used in section 90.

97. Verbatim material should consist entirely of ASCII code data. Nodes are deleted from mem as they are output. ⟨ Output entries verbatim 97 ⟩ ≡

begin loop begin q ← link (p); free avail (p); p ← q; if info(p) = verbatim then goto done; put out (info(p)); end;

done: end

This code is used in section 90.

98. ⟨ Increase cur indent 98 ⟩ ≡

begin if k = cur indent then begin put out ( ␣ ); end;

incr (cur indent ); if cur indent + 10 > line length then overflow (´ ␣ ´ ); end

This code is used in section 90.

99. ⟨ Decrease cur indent 99 ⟩ ≡ begin if k = cur indent then decr (j); decr (cur indent ); { the value will not be negative } end

This code is used in section 90.

100. ⟨ Output a special comment 100 ⟩ ≡ begin q ← link (p); free avail (p); p ← q; put out ( ); if n = change weight then

begin v ← val (info(p)); free avail (info(p)); if v ≥ 0 then put out ( ) else begin put out ( ); v ← −v;

end; end

else begin v ← info(p); if n = end section then put out ( ); end;

⟨ Convert v to decimal 101 ⟩; if n = begin section then put out ( ); put out ( ); end

This code is used in section 90.

101. ⟨ Convert v to decimal 101 ⟩ ≡ w ← 10; while v ≥ w do w ← 10 ∗ w; repeat w ← w div 10; put out ( + (v div w)); v ← v mod w; until w = 1 { this is inefficient, but it works from left to right }

This code is used in section 100.

36  LEVELS OF TRANSLATION  PROFILE §102

102. Levels of translation. Translation lists are actually output only when is operating on its “outer level.” Inner levels are also possible; for example, the parsing of an arithmetic expression might involve many levels. The global variables head and tail always refer to the translation list on the current level; a stack of other head-tail pairs is accessible via head ptr . ⟨ Globals in the outer block 9 ⟩ +≡ head ptr : pointer ; { top of stack for pushed-down translation lists in progress } trans head , trans tail : pointer ; { translation list just completed }

103. ⟨ Set initial values 10 ⟩ +≡ head ptr ← null ;

104. To enter a new level of translation list building, there’s a push level subroutine: procedure push level ;

var p, q: pointer ; { two new nodes added to the stack }

begin p ← get avail ; q ← get avail ; link (p) ← q; link (q) ← head ptr ; head ptr ← p; info(p) ← head ; info(q) ← tail ; head ← get avail ; tail ← head ; end;

105. Conversely, when we lower the level, the current head and tail are placed in variables trans head and trans tail , respectively. procedure pop level ;

var p, q: pointer ; { two old nodes removed from the stack }

begin trans head ← head ; trans tail ← tail ;

p ← head ptr ; q ← link (p); head ptr ← link (q); head ← info(p); tail ← info(q); free avail (p); free avail (q); end;

106. It is a simple matter to append the trans head /trans tail list to the current list: procedure app trans ;

begin if trans tail ≠ trans head then begin link (tail ) ← link (trans head ); tail ← trans tail ; end;

free avail (trans head );

§107  PROFILE  GETTING THE NEXT TOKEN 37

end; 107. Getting the next token. A “top down” or “recursive descent” parsing strategy is used, in which the program has looked ahead one token in the input. A token is a special character like ‘ ’; or a special pair of characters like ‘ ’; or a reserved word like ‘ ’; or an identifier; or a numeric constant; or a string constant. Furthermore a token may be preceded by any number of blanks and/or comments enclosed in braces; blanks are removed, but the comments are considered to be part of the token.

Whenever a token is acceptable to the syntax, that token is swallowed (never to be put back), and the program looks ahead for another token.

This elementary lookahead is done by ’s get next routine, which sets up several global variables to show what it has found:

cur code is the id code of an identifier or reserved word, or a special code value like plus or minus for ‘ ’,

relation for ‘ ’, real const for a real constant. cur aux is the corresponding id aux ; or it’s the ASCII character that has been encoded in cur code. cur ptr is zero or points to the identifier or reserved word whose id code and id aux are in cur code and

cur aux . cur val is the value of an integer constant, if cur code is either small const or int const . new trans is the head of a translation list for the token that has just been scanned. The translation list

includes comments (interpreted if they have special forms, otherwise truncated so that the length is at most max comment ); spaces have been suppressed, except that spaces are inserted before or after reserved words as mentioned earlier. Reserved words have been preceded by an all caps command in the translation.

kludge flag has been set true if the comment ‘ ’ was sensed.

define new trans ≡ link (new trans loc) ⟨ Globals in the outer block 9 ⟩ +≡ cur code: halfword ; { id code or other code in current lookahead token } cur aux : halfword ; { id aux in current lookahead token } cur val : integer ; { integer value of current lookahead token, if appropriate } new trans loc: pointer ; { head of translation list for current lookahead token } cur ptr : id pointer ; { zero or pointer to identifier in current lookahead token } kludge flag : boolean; { set to true when get next sees an uparrow comment }

38  GETTING THE NEXT TOKEN  PROFILE §109

108. ⟨ Set initial values 10 ⟩ +≡ new trans loc ← get avail ; 109. When get next looks ahead and sees a comment like , it doesn’t immediately delete section 123 from the section stack, because the lookahead process is (by definition) one jump ahead of the parsing process. The section stack is actually updated later, when the translation list specified by new trans is appended to the parser’s current head /tail list. The get next routine does this delayed updating just before looking ahead for another token. ⟨ Append the new trans list to the end of tail , interpreting its comments 109 ⟩ ≡

if new trans ≠ null then begin link (tail ) ← new trans ; repeat tail ← link (tail ); case info(tail ) of verbatim: repeat tail ← link (tail ); until info(tail ) = verbatim;

begin section: begin tail ← link (tail ); push section(info(tail ));

end; end section: begin tail ← link (tail ); pop section(info(tail ));

end; change weight : begin tail ← link (tail ); add weight (val (info(tail )));

end;

othercases do nothing

endcases; until link (tail ) = null ; new trans ← null ; end

This code is used in section 113.

110. Three global variables help get next control the low-level activities associated with taking characters out of the input buffer: ⟨ Globals in the outer block 9 ⟩ +≡ line: integer ; { the number of the current line in the current file } 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 }

111. ⟨ Set initial values 10 ⟩ +≡ line ← 0; loc ← 1; limit ← 0;

112. 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 }

begin incr (line);

if ¬input ln(pascal file) then fatal error (´ ␣ ␣ ␣ ␣ ´ ); loc ← 0; buffer [limit ] ← ␣ ; end; 113. Here now is the program for get next . Remember that a call of get next means, essentially, “I accept the previous token. Look ahead for another, because I will want to look at it later.”

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, #

define app(#) ≡ begin link (get tail ) ← get avail ; get tail ← link (get tail ); info(get tail ) ← #; end

procedure get next ; label restart , continue, not found , done; var get tail : pointer ; { tail of the new trans list being built }

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

c: ASCII code; { character found in the buffer }

sign: integer ; { ±1 } begin ⟨ Append the new trans list to the end of tail , interpreting its comments 109 ⟩; cur ptr ← 0; get tail ← new trans loc;

restart : if loc > limit then get line; c ← buffer [loc]; incr (loc); cur aux ← c;

case c of

, up to( ), , up to( ): ⟨ Get an identifier or reserved word 115 ⟩; ´ : ⟨ Get a string 116 ⟩; , , , , , , , , , : ⟨ Get a constant 117 ⟩; : ⟨ Get a comment, then goto restart 119 ⟩;

⟨ Translate a special character, compressing two-symbol combinations like ‘ ’ into a single symbol 114 ⟩ 0, ␣ , ´ 11 : goto restart ; { ignore nulls, spaces, and tabs } othercases begin err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); app(verbatim);

app(c); app(verbatim); goto restart ;

end endcases; end; 114. define up arrow = bb + 1

define asterisk = bb + 2

define slash = bb + 3

define comma = bb + 4

define semicolon = bb + 5 define left paren = bb + 6 define right paren = bb + 7 define left bracket = bb + 8 define right bracket = bb + 9 define colon = bb + 10 define colon equal = bb + 11 define dot = bb + 12 define double dot = bb + 13 define relation = bb + 14 define app code(#) ≡

begin app(c); cur code ← #;

end

define compress (#) ≡ begin app(c); app(buffer [loc]); incr (loc); cur code ← #; end

⟨ Translate a special character, compressing two-symbol combinations like ‘ ’ into a single symbol 114 ⟩ ≡ , : app code(plus or minus ); : app code(asterisk ); : app code(slash); : app code(comma); : app code(semicolon); : app code(left paren); : app code(right paren); : app code(left bracket ); : app code(right bracket ); : app code(up arrow ); : app code(relation); : if buffer [loc] = then compress (colon equal ) else app code(colon); : if buffer [loc] = then compress (double dot ) else app code(dot ); : if (buffer [loc] = ) ∨ (buffer [loc] = ) then compress (relation) else app code(relation); : if buffer [loc] = then compress (relation) else app code(relation);

This code is used in section 113.

115. ⟨ Get an identifier or reserved word 115 ⟩ ≡ begin decr (loc); id first ← loc; repeat if c ≤ then

if c ≥ then buffer [loc] ← c + − ; incr (loc); c ← buffer [loc];

until (c < ) ∨ ((c > ) ∧ (c < )) ∨ ((c > ) ∧ (c < )) ∨ (c > ); id loc ← loc; cur ptr ← id lookup; cur code ← id code(cur ptr ); cur aux ← id aux (cur ptr ); if cur code ≤ max blank left then

if cur code ≥ min blank left then app( ␣ ); if cur code < undefined then app(all caps ); app(cur ptr ); if cur code ≤ max blank right then

if cur code ≥ min blank right then app( ␣ ); if cur code = int const then cur val ← val (cur aux ) else if cur code = small const then cur val ← cur aux ; end

This code is used in section 113.

116. ⟨ Get a string 116 ⟩ ≡ begin app(verbatim); app( ´ ); cur code ← string const ; cur aux ← 0;

continue: app(buffer [loc]);

if buffer [loc] = ´ then

if buffer [loc + 1] = ´ then begin app( ´ ); loc ← loc + 2; incr (cur aux ); goto continue; end

else incr (loc) else begin incr (cur aux ); incr (loc);

if loc > limit then err print (´ ␣ ␣ ␣ ´ ´ ␣ ´ )

else goto continue;

end; app(verbatim); cur code ← string const ; end

This code is used in section 113.

117. ⟨ Get a constant 117 ⟩ ≡ begin id first ← loc − 1; cur val ← c − ; cur code ← int const ; while (buffer [loc] ≥ ) ∧ (buffer [loc] ≤ ) do

begin cur val ← 10 ∗ cur val + buffer [loc] − ; incr (loc); end;

⟨ Scan to the end of a real constant, if or is present 118 ⟩; if cur code = int const then

if cur val < 10000 then begin cur code ← small const ; cur aux ← cur val ; end

else begin cur aux ← get avail ; val (cur aux ) ← cur val ;

end; app(verbatim); for i ← id first to loc − 1 do app(buffer [i]); app(verbatim); end

This code is used in section 113.

118. ⟨ Scan to the end of a real constant, if  or  is present 118 ⟩ ≡

if buffer [loc] = then

if buffer [loc + 1] ≠ then begin cur code ← real const ; cur aux ← null ; repeat incr (loc); until (buffer [loc] < ) ∨ (buffer [loc] > ); end;

if (buffer [loc] = ) ∨ (buffer [loc] = ) then begin cur code ← real const ; cur aux ← null ; incr (loc); if abs (buffer [loc] − ) = 1 then incr (loc); { or } while (buffer [loc] ≥ ) ∧ (buffer [loc] ≤ ) do incr (loc); end

This code is used in section 117.

119. ⟨ Get a comment, then goto restart 119 ⟩ ≡ begin id first ← loc − 1; ⟨ Check for , , , or ; goto restart if one of these special types is found 121 ⟩; id loc ← id first + max comment ; if id loc ≥ limit then id loc ← limit − 1; loc ← id first ; app(verbatim); while buffer [loc] ≠ do

begin app(buffer [loc]);

if loc = id loc then ⟨ Truncate the comment, goto done 120 ⟩; incr (loc); end;

done: app( ); app(verbatim); incr (loc); goto restart ;

end

This code is used in section 113.

120. ⟨ Truncate the comment, goto done 120 ⟩ ≡ begin app( ); app( ); app( ); repeat incr (loc);

if loc > limit then get line; until buffer [loc] = ; goto done; end

This code is used in section 119.

121. ⟨ Check for  ,  ,  , or  ; goto restart if one of these special types is found 121 ⟩ ≡

if (buffer [loc] ≥ ) ∧ (buffer [loc] ≤ ) then cur code ← begin section else if buffer [loc] = then

begin cur code ← end section; incr (loc); end

else if abs (buffer [loc] − ) = 1 then begin cur code ← change weight ; sign ← − buffer [loc]; incr (loc); end

else begin if buffer [loc] = then

if buffer [loc + 1] = then kludge flag ← true; goto not found ; end;

cur val ← 0; while (buffer [loc] ≥ ) ∧ (buffer [loc] ≤ ) do

begin cur val ← 10 ∗ cur val + buffer [loc] − ; incr (loc);

end; if cur code = begin section then

if buffer [loc] ≠ then goto not found

else incr (loc); if buffer [loc] ≠ then goto not found ; if cur code = change weight then

begin cur val ← cur val ∗ sign; cur aux ← get avail ; val (cur aux ) ← cur val ; cur val ← cur aux ; end

else if cur val > max halfword then goto not found ; app(cur code); app(cur val ); incr (loc); goto restart ;

not found :

This code is used in section 119.

122. Here’s a little routine that is used when an identifier had better be next: procedure skip to id ;

begin if cur ptr = 0 then begin err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); repeat get next ; until cur ptr ≠ 0; end;

end;

123. When we need to swallow a semicolon, get semi does the trick. procedure get semi ;

begin if cur code ≠ semicolon then begin err print (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); repeat get next ; until cur code = semicolon; end;

get next ; end;

124. The most common error message that occurs in typical top-down parsing routines is the following. define expected (#) ≡ err print (´ ␣ ´ , #, ´ ␣ ␣ ´ )

125. Here’s a routine that scans past a list of identifiers, separated by commas, and returns a pointer to a list of their locations (in reverse order). function get id list : pointer ;

label done; var p: pointer ; { the list }

q: pointer ; { new item to put on it } begin p ← null ; loop begin skip to id ; q ← get avail ; info(q) ← cur ptr ; link (q) ← p; p ← q; get next ;

if cur code ≠ comma then goto done; get next ; end;

§126  PROFILE  SMALL SYNTACTIC UNITS 45

done: get id list ← p; end; 126. Small syntactic units. Now that we have get next to scan tokens, the next job is to parse slightly larger entities. With luck, we’ll eventually work up to the point where we’ll be ready to parse a whole PASCAL program.

The remainder of the program can be viewed as an expansion of the syntax diagrams at the end of the PASCAL manual into a set of subroutines, as if those diagrams were “flow charts.”

127. First comes get int const , which scans an integer constant and returns its value. function get int const : integer ;

var s: integer ; begin if cur code = plus or minus then

begin s ← − cur aux ; get next ;

if s < 0 then cur val ← −cur val ;

end; if cur code ≠ int const then

if cur code ≠ small const then begin expected (´ ␣ ´ ); cur val ← 0; end;

s ← cur val ; get next ; get int const ← s; end;

128. Here now is a subroutine that scans what PASCAL calls a “simple type.” The get s type function returns a pointer to the representation of the type that was scanned.

After calling get s type (and several other subroutines below that use push level ), it’s necessary to say ‘app trans ’ to keep from losing the translation list that was formed, because the translation has been moved out of the head /tail list. function get s type: pointer ;

var p: pointer ; { the resulting type } q: pointer ; { temporary for list manipulation } m, n: integer ; { subrange boundaries }

begin push level ; if cur code = defined type then { it’s a type identifier }

begin p ← cur aux ; get next ;

end else begin if cur code = left paren then ⟨ Scan an enumerated type 129 ⟩

else ⟨ Scan a subrange type 130 ⟩;

⟨ Make p point to the subrange type m . . n 131 ⟩;

end; pop level ; get s type ← p; end;

129. ⟨ Scan an enumerated type 129 ⟩ ≡ begin m ← 0; n ← −1; repeat get next ; skip to id ;

incr (n); save(cur ptr ); id code(cur ptr ) ← small const ; id aux (cur ptr ) ← n; get next ; until cur code ≠ comma; if cur code ≠ right paren then expected (´ ´ ) else get next ; end

This code is used in section 128.

46  SMALL SYNTACTIC UNITS  PROFILE §130

130. ⟨ Scan a subrange type 130 ⟩ ≡ begin m ← get int const ; if cur code ≠ double dot then expected (´ ´ ) else get next ; n ← get int const ; end

This code is used in section 128.

131. ⟨ Make p point to the subrange type m . . n 131 ⟩ ≡ begin p ← get avail ; val (p) ← m; q ← get avail ; info(q) ← p; p ← get avail ; val (p) ← n; link (q) ← p; p ← get avail ; info(p) ← int type; link (p) ← q; end

This code is used in section 128.

132. The next procedure is similar, but it gets a general type. function get field list : pointer ; forward ; { there’s mutual recursion } function get type: pointer ;

label done; var packt : 0 . . 1; { 1 if packed }

p, q: pointer ; { for list manipulation } begin push level ; if cur code = up arrow then ⟨ Scan a pointer type 133 ⟩ else begin if cur code ≠ packed code then packt ← 0

else begin packt ← 1; get next ;

end;

case cur code of

array code: ⟨ Scan an array type 134 ⟩;

file code: ⟨ Scan a file type 135 ⟩;

set code: ⟨ Scan a set type 136 ⟩;

record code: ⟨ Scan a record type 137 ⟩;

othercases begin p ← get s type; app trans ;

end endcases; end;

pop level ; get type ← p; end;

133. ⟨ Scan a pointer type 133 ⟩ ≡ begin get next ; skip to id ; p ← get avail ; info(p) ← pointer type; link (p) ← cur ptr ; get next ; end

This code is used in section 132.

134. ⟨ Scan an array type 134 ⟩ ≡ begin get next ; p ← get avail ; info(p) ← array type + packt ; q ← get avail ; link (p) ← q; if cur code ≠ left bracket then expected (´ ´ ) else get next ; loop begin info(q) ← get s type; app trans ;

if cur code ≠ comma then goto done;

get next ; link (q) ← get avail ; q ← link (q); info(q) ← array type + packt ; link (q) ← get avail ; q ← link (q); end;

done: if cur code ≠ right bracket then expected (´ ´ ) else get next ; if cur code ≠ of code then expected (´ ´ ) else get next ; link (q) ← get type; app trans ; end

This code is used in section 132.

135. ⟨ Scan a file type 135 ⟩ ≡ begin get next ; p ← get avail ; info(p) ← file type + packt ; if cur code ≠ of code then expected (´ ´ ) else get next ; link (p) ← get type; app trans ; end

This code is used in section 132.

136. ⟨ Scan a set type 136 ⟩ ≡ begin get next ; p ← get avail ; info(p) ← set type + packt ; if cur code ≠ of code then expected (´ ´ ) else get next ; link (p) ← get s type; app trans ; end

This code is used in section 132.

137. ⟨ Scan a record type 137 ⟩ ≡ begin get next ; p ← get avail ; info(p) ← record type + packt ; link (p) ← get field list ; if cur code ≠ end code then expected (´ ´ ) else get next ; end

This code is used in section 132.

138. The get field list routine returns a pointer to a field list in the form required by a record type. function get field list ; { declared forward above }

label continue, done, done1 , done2 ; var p, q: pointer ; { for list manipulation }

h, t: pointer ; { head and tail of list } begin h ← get avail ; t ← h;

continue: if cur code = case code then ⟨ Scan variant fields 140 ⟩

else begin if (cur ptr ≠ 0) ∧ (cur code ≠ end code) then ⟨ Scan identifier list and its type 139 ⟩;

if cur code = semicolon then begin get next ; goto continue; end;

end; get field list ← link (h); free avail (h); end; 139. ⟨ Scan identifier list and its type 139 ⟩ ≡

begin q ← t; loop begin p ← get avail ; link (t) ← p; t ← p; p ← get avail ; info(t) ← p; info(p) ← cur ptr ; get next ;

if cur code ≠ comma then goto done; get next ; skip to id ; end;

done: if cur code ≠ colon then expected (´ ´ ) else get next ; p ← get type; app trans ; while q ≠ t do

begin q ← link (q); link (info(q)) ← p; end;

end

This code is used in section 138.

140. ⟨ Scan variant fields 140 ⟩ ≡ begin get next ; skip to id ; p ← cur ptr ; get next ; if cur code = colon then

begin get next ; if cur code ≠ defined type then expected (´ ␣ ´ ) else begin q ← get avail ; link (t) ← q; t ← q; q ← get avail ; info(t) ← q; info(q) ← p;

link (q) ← cur aux ; get next ;

end; end;

if cur code ≠ of code then expected (´ ´ ) else get next ; ⟨ Scan conclusion of variant fields 141 ⟩; end

This code is used in section 138.

141. ⟨ Scan conclusion of variant fields 141 ⟩ ≡

loop begin if (cur code ≥ min case label ) ∧ (cur code ≤ max case label ) then begin ⟨ Scan past case labels 142 ⟩; if cur code ≠ colon then expected (´ ´ ) else get next ; if cur code ≠ left paren then expected (´ ´ ) else get next ; link (t) ← get field list ; while link (t) ≠ null do t ← link (t); if cur code ≠ right paren then expected (´ ´ ) else get next ; end;

if cur code ≠ semicolon then goto done2 ; get next ; end;

done2 :

This code is used in section 140.

142. The following code is used twice; label done1 needs to be declared in both contexts. ⟨ Scan past case labels 142 ⟩ ≡

begin loop

begin if cur code < string const then cur val ← get int const else get next ; if cur code ≠ comma then goto done1 ; get next ; end;

done1 : end

This code is used in sections 141 and 186.

§143  PROFILE  EXPRESSIONS 49

143. Expressions. The next few subroutines are the top-down parsers for PASCAL expressions. The main routine is called get exp; it returns it result in the trans head /trans tail translation list, and it also makes cur type point to the type of expression. Meanwhile the assumed run-time cost of evaluating the expression is also taken into account. ⟨ Globals in the outer block 9 ⟩ +≡ cur type: pointer ; { the type of expression found by get exp and its friends } cur length: integer ; { the length of string, if cur type = string loc }

144. But before we get into get exp, we need a simpler routine, get variable. (If with statements were implemented, we would check for field identifiers in currently “open” record variables, at the beginning of get variable.) procedure get exp; forward ; procedure get variable;

label continue, found ;

var p, q: pointer ; { for link manipulation }

begin push level ;

if (cur code = variable) ∨ (cur code = var param) then begin if cur code = var param then add weight (var surcharge); cur type ← cur aux ; get next ; end

else begin expected (´ ␣ ´ ); if cur code = undefined then get next ; cur type ← bool loc; end;

continue: if cur code = left bracket then ⟨ Scan subscript, goto continue 145 ⟩

else if cur code = dot then ⟨ Scan field, goto continue 146 ⟩

else if cur code = up arrow then ⟨ Scan pointer, goto continue 147 ⟩; pop level ; end;

145. ⟨ Scan subscript, goto continue 145 ⟩ ≡

begin repeat get next ; if info(cur type) = packed array type then add weight (packed index cost ) else begin add weight (index cost ); if info(cur type) ≠ array type then

begin err print (´ ␣ ␣ ␣ ´ ); cur type ← string loc;

end; end;

p ← link (cur type); { now info(p) is index type, link (p) is entry type } get exp; app trans ;

{ cur type should now be compatible with info(p), but doesn’t bother to check } cur type ← link (p);

until cur code ≠ comma;

if cur code ≠ right bracket then expected (´ ´ ) else get next ; goto continue; end

This code is used in section 144.

50  EXPRESSIONS  PROFILE §146

146. ⟨ Scan field, goto continue 146 ⟩ ≡ begin get next ; skip to id ; if info(cur type) = packed record type then add weight (packed surcharge) else if info(cur type) ≠ record type then

begin err print (´ ␣ ␣ ␣ ´ ); cur type ← bool loc; goto found ; end;

p ← link (cur type); while p ≠ null do

begin q ← info(p);

if info(q) = cur ptr then begin cur type ← link (q); goto found ; end;

p ← link (p);

end; err print (´ ␣ ␣ ´ ); cur type ← bool loc;

found : get next ; goto continue;

end

This code is used in section 144.

147. ⟨ Scan pointer, goto continue 147 ⟩ ≡ begin get next ; if info(cur type) = file type then cur type ← link (cur type) else if info(cur type) = packed file type then

begin add weight (packed surcharge); cur type ← link (cur type);

end else if info(cur type) = pointer type then

begin add weight (pointer cost ); p ← link (cur type); if id code(p) ≠ defined type then

begin err print (´ ␣ ␣ ␣ ␣ ´ ); cur type ← bool loc; end

else cur type ← id aux (p);

end else err print (´ ␣ ␣ ´ );

goto continue; end

This code is used in section 144.

148. It’s time now to face the messy details of procedure and function calls, where standard procedures have nonstandard syntax. procedure get call ;

label done, continue; var t: pointer ; { final type, if known }

p: pointer ; { runs through the parameter list }

q: pointer ; { for list manipulation }

r: pointer ; { type of argument }

c: 0 . . 100; { type code of argument } begin if cur code = function id then

begin p ← link (cur aux ); t ← info(cur aux );

end else begin p ← cur aux ; t ← null ;

end; append (initial cap); get next ; if p = null then add weight (call overhead ) else if info(info(p)) ≠ spec param then add weight (call overhead ); if cur code = left paren then ⟨ Scan argument list corresponding to parameter list p 149 ⟩; if p ≠ null then

begin q ← info(p);

if info(q) = optional file param then add weight (link (q))

else if info(q) ≠ spec param then err print (´ ␣ ␣ ´ ); end;

if t ≠ null then cur type ← t; end; 149. One of the subtle things here is that our PASCAL allows empty arguments to standard functions like call i . ⟨ Scan argument list corresponding to parameter list p 149 ⟩ ≡

begin loop

begin get next ; if (cur code = comma) ∨ (cur code = right paren) then cur type ← int loc else begin get exp; app trans ;

end; continue: if p = null then

begin err print (´ ␣ ␣ ´ ); p ← extra loc; end;

q ← info(p); if info(q) = optional file param then

begin add weight (link (q));

if info(cur type) ≠ file type then

if info(cur type) ≠ packed file type then begin p ← link (p); goto continue; end;

end else if info(q) = spec param then ⟨ Process a special parameter 151 ⟩

else ⟨ Process a regular parameter 150 ⟩; p ← link (p); if cur code ≠ comma then goto done; end;

done: if cur code ≠ right paren then expected (´ ´ ) else get next ;

end

This code is used in section 148.

150. The program could check for type conflicts between argument and parameter; but it doesn’t. ⟨ Process a regular parameter 150 ⟩ ≡

begin if info(cur type) = int type then

if info(link (q)) = real type then add weight (int real cost ); add weight (store cost ); end

This code is used in section 149.

151. ⟨ Process a special parameter 151 ⟩ ≡ begin r ← cur type; if r = string loc then add weight (string string cost + cur length ∗ string string tax ); n ← 0; while cur code = colon do

begin get next ; incr (n); get exp; app trans ; add weight (store cost ); end;

if n = 2 then

if info(r) = int type then begin add weight (int real cost ); r ← real loc; end;

if r ≠ string loc then begin q ← link (q); c ← info(r); if c ≠ char type then

begin q ← link (q); if c ≠ int type then begin q ← link (q); if c ≠ real type then begin q ← link (q); if c ≠ array type then q ← link (q); end; end; end;

add weight (info(q));

end; end

This code is used in section 149.

152. The next step up from a variable is a “factor.” procedure get factor ;

label done; var p: pointer ; { list manipulation } begin push level ;

case cur code of

real const : begin get next ; cur type ← real loc; add weight (fetch cost );

end; int const , small const : begin get next ; cur type ← int loc; add weight (fetch cost );

end; bool const : begin get next ; cur type ← bool loc; add weight (fetch cost );

end; string const : begin if cur aux = 1 then cur type ← char loc

else begin cur type ← string loc; cur length ← cur aux ;

end; get next ; add weight (fetch cost ); end;

function id : get call ; left paren: begin get next ; get exp; app trans ;

if cur code ≠ right paren then expected (´ ´ ) else get next ; end;

not code: begin get next ; add weight (unary cost ); get factor ; app trans ;

end; left bracket : ⟨ Scan a set construction 153 ⟩; othercases begin get variable; app trans ; add weight (fetch cost );

end endcases; pop level ; end;

153. ⟨ Scan a set construction 153 ⟩ ≡ begin get next ; add weight (set cost ); cur type ← null ; loop begin if cur code = right bracket then goto done;

get exp; app trans ; add weight (store cost );

if cur code = double dot then begin get next ; get exp; app trans ; add weight (store cost ); end;

if cur code = comma then get next

else if cur code ≠ right bracket then begin expected (´ ´ ); goto done; end;

end; done: p ← get avail ; info(p) ← set type; link (p) ← cur type; cur type ← p;

end

This code is used in section 152.

154. Factors make terms. procedure get term;

label exit , continue, not found ; var t: pointer ; { type of the first operand } begin get factor ; app trans ; loop begin continue: t ← cur type;

case cur code of

asterisk : ⟨ Do multiplication or goto not found 155 ⟩;

slash: ⟨ Do real division or goto not found 156 ⟩;

div or mod code: ⟨ Do integer division or goto not found 157 ⟩;

and code: ⟨ Do logical and or goto not found 158 ⟩;

othercases return

endcases; goto continue; not found : err print (´ ␣ ␣ ´ );

end; exit : end;

155. ⟨ Do multiplication or goto not found 155 ⟩ ≡ begin get next ; get factor ; app trans ; if info(t) = int type then

if info(cur type) = int type then add weight (mult cost )

else if info(cur type) = real type then add weight (int real cost + real mult cost )

else goto not found

else if info(t) = real type then if info(cur type) = real type then add weight (real mult cost ) else if info(cur type) = int type then

begin add weight (int real cost + real mult cost ); cur type ← real loc; end

else goto not found

else if (info(t) = set type) ∧ (info(cur type) = set type) then add weight (set cost )

else goto not found ; end

This code is used in section 154.

156. ⟨ Do real division or goto not found 156 ⟩ ≡ begin get next ; get factor ; app trans ; if info(t) = int type then add weight (int real cost ) else if info(t) ≠ real type then goto not found ; if info(cur type) = int type then add weight (int real cost ) else if info(cur type) ≠ real type then goto not found ; cur type ← real loc; add weight (real div cost ); end

This code is used in section 154.

157. ⟨ Do integer division or goto not found 157 ⟩ ≡ begin get next ; get factor ; app trans ; if (info(t) ≠ int type) ∨ (info(cur type) ≠ int type) then goto not found ; add weight (div cost ); end

This code is used in section 154.

158. ⟨ Do logical and or goto not found 158 ⟩ ≡ begin get next ; get factor ; app trans ; if (t ≠ bool loc) ∨ (cur type ≠ bool loc) then goto not found ; add weight (and or cost ); end

This code is used in section 154.

159. Terms make simple expressions. procedure get s exp;

label exit , continue, not found ; var t: pointer ; { type of first operand } begin if cur code = plus or minus then

begin if cur aux = then add weight (unary cost );

get next ;

end; get term; loop begin continue: t ← cur type;

if cur code = plus or minus then ⟨ Do addition or goto not found 160 ⟩ else if cur code = or code then ⟨ Do logical or or goto not found 161 ⟩

else return; goto continue;

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

end; exit : end;

160. ⟨ Do addition or goto not found 160 ⟩ ≡ begin get next ; get term; if info(t) = int type then

if info(cur type) = int type then add weight (add cost )

else if info(cur type) = real type then add weight (int real cost + real add cost )

else goto not found

else if info(t) = real type then if info(cur type) = real type then add weight (real add cost ) else if info(cur type) = int type then

begin add weight (int real cost + real add cost ); cur type ← real loc; end

else goto not found

else if (info(t) = set type) ∧ (info(cur type) = set type) then add weight (set cost )

else goto not found ; end

This code is used in section 159.

161. ⟨ Do logical or or goto not found 161 ⟩ ≡ begin get next ; get term; if (t ≠ bool loc) ∨ (cur type ≠ bool loc) then goto not found ; add weight (and or cost ); end

This code is used in section 159.

162. Finally, simple expression lead us all the way up to expressions. (Once again, does not bother to verify the validity of types; but the information is present.) procedure get exp;

var t: halfword ; { code of left operand } begin push level ; get s exp; if (cur code = relation) ∨ (cur code = in code) then

begin t ← cur code; get next ; get s exp; if t = relation then add weight (compare cost ) else add weight (in cost ); cur type ← bool loc; end;

58  DECLARATIONS  PROFILE §163

pop level ; end; 163. Declarations. Our next task is to parse what PASCAL syntax calls a “block.” The get block routine declares all variables of the block; it has a lot to do.

164. Before we tackle get block , it will be helpful to get a subroutine out of the way. The following routine scans a parameter list, optionally declaring the identifiers found inside, and returns a pointer to the representation of this parameter list. function get parameter list (decl params : boolean): pointer ;

var h, t: pointer ; { head and tail of list being built } c, a: halfword ; { code and aux values } r: halfword ; { type to the right of a colon } p, q: pointer ; { the usual }

begin h ← get avail ; t ← h; if cur code = left paren then

begin repeat get next ;

if (cur code = procedure code) ∨ (cur code = function code) then

⟨ Set up for subroutine parameters 166 ⟩ else ⟨ Set up for normal parameters 165 ⟩; ⟨ Complete the current set of parameters 167 ⟩;

until cur code ≠ semicolon;

if cur code ≠ right paren then expected (´ ´ ) else get next ; end;

get parameter list ← link (h); free avail (h); end;

165. ⟨ Set up for normal parameters 165 ⟩ ≡

begin if cur code = var code then begin c ← var param; get next ; end

else c ← variable; p ← get id list ; a ← null ; end

This code is used in section 164.

166. ⟨ Set up for subroutine parameters 166 ⟩ ≡ begin c ← cur code + (procedure id − procedure code); get next ; append (initial cap); p ← get id list ; a ← get parameter list (false); end

This code is used in section 164.

§167  PROFILE  DECLARATIONS 59

167. ⟨ Complete the current set of parameters 167 ⟩ ≡

begin if c ≠ procedure id then begin if cur code ≠ colon then expected (´ ´ ) else get next ; if cur code = defined type then

begin r ← cur aux ; get next ;

end else if cur code = file code then

begin r ← file loc; get next ; end

else begin r ← null ; expected (´ ␣ ´ );

end; if c = function id then

begin q ← get avail ; link (q) ← a; a ← q; info(a) ← r; end

else a ← r; end;

while p ≠ null do begin q ← info(p);

if decl params then

begin save(q); id code(q) ← c; id aux (q) ← a;

end; link (t) ← get avail ; t ← link (t); info(t) ← p; q ← link (p); info(p) ← c; link (p) ← a; p ← q; end;

end

This code is used in section 164.

168. All right, let’s get block . procedure get statement ; forward ; procedure get block ;

label exit , found ; var p, q, r, t: pointer ; { list manipulation }

s: integer ; { sign } begin if cur code = label code then ⟨ Handle the label part of a block 169 ⟩; if cur code = const code then ⟨ Handle the const part of a block 170 ⟩; if cur code = type code then ⟨ Handle the type part of a block 172 ⟩; if cur code = var code then ⟨ Handle the var part of a block 173 ⟩; while (cur code = procedure code) ∨ (cur code = function code) do

⟨ Handle a subroutine declaration 174 ⟩; if cur code ≠ begin code then expected (´ ´ ) else get next ; cur freq ← get count ; { the number of times this block is performed } loop begin get statement ;

if cur code = end code then begin flush out ; get next ; cur freq ← next freq ; return; end;

get semi ; flush out ; cur freq ← next freq ; end;

exit : end; 169. The label part is easy. ⟨ Handle the label part of a block 169 ⟩ ≡

begin repeat get next ; cur val ← get int const ; until cur code ≠ comma; if cur code ≠ semicolon then expected (´ ´ ) else get next ; flush out ; end;

This code is used in section 168.

170. Constants are somewhat worse. ⟨ Handle the const part of a block 170 ⟩ ≡

begin get next ; append (indent ); skip to id ; while cur code ≥ undefined do

begin p ← cur ptr ; save(p); get next ;

if cur aux ≠ then expected (´ ´ ) else get next ;

⟨ Scan the constant and define p accordingly 171 ⟩;

get semi ; flush out ; skip to id ;

end; append (outdent ); end

This code is used in section 168.

171. ⟨ Scan the constant and define p accordingly 171 ⟩ ≡

if cur code = plus or minus then begin s ← − cur aux ; get next ; end;

if (cur code ≥ string const ) ∧ (cur code ≤ real const ) then { this range includes bool const } begin id code(p) ← cur code; id aux (p) ← cur aux ; end

else begin if cur code ≠ int const then

if cur code ≠ small const then begin expected (´ ´ ); cur val ← 0; end;

if s < 0 then cur val ← −cur val ;

if (cur val ≥ 0) ∧ (cur val < 10000) then begin id code(p) ← small const ; id aux (p) ← cur val ; end

else begin q ← get avail ; val (q) ← cur val ; id code(p) ← int const ; id aux (p) ← q;

end; end;

get next

This code is used in section 170.

172. Types are not too bad, since get type does the hard work. ⟨ Handle the type part of a block 172 ⟩ ≡

begin get next ; append (indent ); skip to id ; while cur code ≥ undefined do

begin p ← cur ptr ; save(p); get next ; if cur aux ≠ then expected (´ ´ ) else get next ; id code(p) ← defined type; id aux (p) ← get type; app trans ; get semi ; flush out ; skip to id ; end;

append (outdent ); end

This code is used in section 168.

173. Vars add one more twist. ⟨ Handle the var part of a block 173 ⟩ ≡

begin get next ; append (indent ); skip to id ; while cur code ≥ undefined do

begin p ← get id list ; if cur code ≠ colon then expected (´ ´ ) else get next ; t ← get type; app trans ; while p ≠ null do

begin q ← info(p); save(q); id code(q) ← variable; id aux (q) ← t; q ← link (p); free avail (p); p ← q; end;

get semi ; flush out ; skip to id ; end;

append (outdent ); end

This code is used in section 168.

174. And now comes the “fun” part. ⟨ Handle a subroutine declaration 174 ⟩ ≡

begin t ← cur code + (procedure id − procedure code); append (indent ); append (backspace); get next ; skip to id ; r ← cur ptr ; save(r); push save stack ; append (initial cap); kludge flag ← false; get next ; ⟨ If identifier r was already forward declared, goto found 177 ⟩; id code(r) ← t; p ← get parameter list (true); if t = function id then

begin if cur code ≠ colon then expected (´ ´ ) else get next ; q ← get avail ; link (q) ← p; p ← q; if cur code = defined type then

begin info(p) ← cur aux ; get next ;

end else begin expected (´ ␣ ´ );

while cur code ≠ semicolon do get next ;

info(p) ← null ;

end; end

else if kludge flag then id code(r) ← terminal procedure id ; id aux (r) ← p;

found : get semi ; flush out ; skip to id ; if cur code < undefined then get block else begin if cur ptr = fwd loc then ⟨ Put identifier r on the forward stack 178 ⟩;

get next ;

end; get semi ; flush out ; unsave; append (outdent ); cur freq ← 0; end

This code is used in section 168.

175. A simple stack is maintained of identifier pointers that have been declared forward but not yet really declared. ⟨ Globals in the outer block 9 ⟩ +≡ fwd ptr : pointer ; { head of forward stack }

176. ⟨ Set initial values 10 ⟩ +≡ fwd ptr ← null ;

177. ⟨ If identifier r was already forward declared, goto found 177 ⟩ ≡ begin q ← null ; p ← fwd ptr ; while p ≠ null do

begin if info(p) = r then begin if q = null then fwd ptr ← link (p) else link (q) ← link (p); free avail (p); goto found ; end;

q ← p; p ← link (q);

end; end

This code is used in section 174.

178. ⟨ Put identifier r on the forward stack 178 ⟩ ≡ begin p ← get avail ; info(p) ← r; link (p) ← fwd ptr ; fwd ptr ← p; end

This code is used in section 174.

§179  PROFILE  STATEMENTS 63

179. Statements. The scanning process reaches its glorious heights in the climactic get statement procedure. This subroutine sets the global variable next freq to the value that cur freq should have if another statement follows. ⟨ Globals in the outer block 9 ⟩ +≡ next freq : integer ; { the flow that emanates from the statement just got }

180. Basically, get statement is a multiway switch between ten different kinds of PASCAL statements. procedure get statement ;

label done, done1 , done2 , done3 ; { lots of things get done } var in freq , out freq : integer ; { frequencies before and after }

w: integer ; { weight of while clause }

lhs type: pointer ; { type of left-hand side of assignment } t: 0 . . 100; { type of right-hand side type } n: integer ; { number of items in assignment }

begin while cur code = small const do ⟨ Process a labelled statement 181 ⟩; in freq ← cur freq ; next freq ← cur freq ;

case cur code of

variable, var param, function id : ⟨ Process an assignment statement 192 ⟩; procedure id : get call ; terminal procedure id : begin get call ; next freq ← 0;

end; begin code: ⟨ Process a compound statement 183 ⟩; if code: ⟨ Process an if statement 184 ⟩; case code: ⟨ Process a case statement 186 ⟩; while code: ⟨ Process a while statement 191 ⟩; repeat code: ⟨ Process a repeat statement 187 ⟩; for code: ⟨ Process a for statement 190 ⟩; goto code: ⟨ Process a go to statement 182 ⟩; othercases do nothing { we just saw an empty statement } endcases; end;

181. ⟨ Process a labelled statement 181 ⟩ ≡ begin append (backspace); get next ; if cur code ≠ colon then expected (´ ´ ) else get next ; cur freq ← get count ; end

This code is used in section 180.

182. ⟨ Process a go to statement 182 ⟩ ≡ begin get next ; if cur code ≠ small const then expected (´ ´ ) else get next ; add weight (jump cost ); next freq ← 0; end

This code is used in section 180.

64  STATEMENTS  PROFILE §183

183. ⟨ Process a compound statement 183 ⟩ ≡ begin get next ; append (indent ); loop begin get statement ;

if cur code = end code then goto done;

get semi ; flush out ; cur freq ← next freq ;

end; done: flush out ; cur freq ← next freq ; append (outdent ); get next ;

end

This code is used in section 180.

184. define check boolean ≡ if cur type ≠ bool loc then err print (´ ␣ ␣ ␣ ␣ ´ )

⟨ Process an if statement 184 ⟩ ≡ begin get next ; add weight (if cost ); get exp; app trans ; check boolean; if cur code ≠ then code then expected (´ ´ ) else get next ; flush out ; cur freq ← get count ; in freq ← in freq − cur freq ; next freq ← cur freq ; if cur code ≠ end code then

if cur code ≠ semicolon then

if cur code ≠ else code then

if cur code ≠ until code then { controlled statement is nonempty } begin append (indent ); get statement ; append (outdent ); end;

if cur code = else code then begin out freq ← get count ; { this count is supposedly redundant } if in freq ≠ out freq then ⟨ Show frequency lossage in the output 185 ⟩ else flush out ; get next ; append (indent ); cur freq ← out freq ; out freq ← next freq ; get statement ; next freq ← next freq + out freq ; append (outdent ); end

else next freq ← in freq + next freq ; end

This code is used in section 180.

185. Frequency counts can be “off” for a variety of reasons (e.g., when a procedure sometimes doesn’t return, or when a user aborts the program). Such discrepancies are indicated by a ‘ ’ comment line. ⟨ Show frequency lossage in the output 185 ⟩ ≡

begin flush out ; append (lost comment ); cur freq ← in freq − out freq ; flush out ; end

This code is used in section 184.

186. ⟨ Process a case statement 186 ⟩ ≡ begin get next ; add weight (case cost ); get exp; app trans ; if cur code ≠ of code then expected (´ ´ ) else get next ; flush out ; append (indent ); out freq ← 0; loop begin if (cur code ≥ min case label ) ∧ (cur code ≤ max case label ) then

begin append (backspace); ⟨ Scan past case labels 142 ⟩; cur freq ← get count ; in freq ← in freq − cur freq ; if cur code ≠ colon then expected (´ ´ ) else get next ; get statement ; out freq ← out freq + next freq ; end;

if cur code ≠ semicolon then goto done2 ; get next ; flush out ; end;

done2 : flush out ; append (outdent ); if cur code ≠ end code then expected (´ ´ ) else get next ; cur freq ← in freq ; next freq ← out freq ; if cur freq ≠ 0 then append (lost comment ); end

This code is used in section 180.

187. The calculation of next freq after a repeat statement is slightly tricky because of the possibility of goto statements leading out of the loop. ⟨ Process a repeat statement 187 ⟩ ≡

begin get next ; append (indent ); cur freq ← get count ; out freq ← cur freq ; loop begin get statement ;

if cur code = until code then goto done3 ; get semi ; flush out ; cur freq ← next freq ; end;

done3 : flush out ; cur freq ← next freq ; append (outdent ); get next ; add weight (repeat tax ); get exp; app trans ; check boolean; next freq ← cur freq − out freq + in freq ; end

This code is used in section 180.

188. The fact that goto’s can affect the frequencies means that we don’t know how often the test of a while or for loop is performed until after the loop has been entirely scanned. therefore outputs a special line that says ‘ ’ or ‘ ’, after the necessary information has been gathered. These special comments are treated as identifiers, for simplicity. ⟨ Set up all the reserved words and predefined identifiers 54 ⟩ +≡

id9 ( )( )( )( )( )( )( )( )( )(0)(0); while comment ← cur name; id8 ( )( )( )( )( )( )( )( )(0)(0); lost comment ← cur name; id7 ( )( )( )( )( )( )( )(0)(0); for comment ← cur name;

189. ⟨ Globals in the outer block 9 ⟩ +≡ while comment , lost comment , for comment : pointer ; { locations of special comments } 190. ⟨ Process a for statement 190 ⟩ ≡

begin get next ; add weight (for cost ); get variable; app trans ; if cur code ≠ colon equal then expected (´ ´ ) else get next ; get exp; app trans ; if cur code ≠ to or downto code then expected (´ ␣ ␣ ´ ) else get next ; get exp; app trans ; if cur code ≠ do code then expected (´ ´ ) else get next ; flush out ; append (indent ); cur freq ← get count ; out freq ← cur freq ; get statement ; append (outdent ); flush out ; append (for comment ); cur freq ← next freq ; add weight (for tax ); next freq ← next freq − out freq + in freq ; end

This code is used in section 180.

191. ⟨ Process a while statement 191 ⟩ ≡ begin get next ; add weight (while cost ); get exp; app trans ; check boolean; if cur code ≠ do code then expected (´ ´ ) else get next ; w ← out wt ; flush out ; append (indent ); cur freq ← get count ; out freq ← cur freq ; get statement ; append (outdent ); flush out ; append (while comment ); cur freq ← next freq ; add weight (w + while tax ); next freq ← next freq − out freq + in freq ; end

This code is used in section 180.

192. An assignment of an array to an array is treated here as an assignment of a simple variable to a simple variable, since the author didn’t want to bother to compute the size of the array. If the user actually uses such assignments, an appropriate ‘ ’ comment should be given so that the statement is weighted properly.

define incomp ≡ err print (´ ␣ ␣ ´ ) ⟨ Process an assignment statement 192 ⟩ ≡

begin if cur code = function id then begin lhs type ← info(cur aux ); append (initial cap); get next ; end

else begin get variable; app trans ; lhs type ← cur type;

end; if cur code ≠ colon equal then expected (´ ´ ) else get next ; get exp; app trans ; add weight (store cost ); t ← info(cur type); case info(lhs type) of real type: if t = int type then add weight (int real cost )

else if t ≠ real type then incomp; packed array type, record type: begin

if (t ≠ info(lhs type)) ∨ ((link (cur type) ≠ link (lhs type)) ∧ (cur type ≠ string loc)) then incomp;

if t = packed array type then begin if cur type = string loc then n ← cur length else n ← 1; end

else begin n ← 0; lhs type ← link (lhs type);

while lhs type ≠ null do begin incr (n); lhs type ← link (lhs type); end; end;

add weight ((n − 1) ∗ (fetch cost + store cost ));

end; othercases if t ≠ info(lhs type) then incomp endcases; end

This code is used in section 180.

68  THE PROGRAM  PROFILE §193

193. The program. Now there’s only one thing left to do, namely to parse an entire PASCAL program (meanwhile doing all the profiling). This is where itself begins and ends.

begin initialize; ⟨ Set up all the reserved words and predefined identifiers 54 ⟩; print ln(banner ); { print a “banner line” } get next ; { get the first token } if cur code ≠ program code then expected (´ ´ ) else get next ; append (initial cap); skip to id ; get next ; if cur code = left paren then

begin get next ; p ← get id list ;

if cur code ≠ right paren then expected (´ ´ ) else get next ; end;

get semi ; flush out ; get block ; { this is where most of the work is done } if cur code ≠ dot then expected (´ ´ ); append ( ); flush out ; { if all went well, that’s the ‘end.’ of the program } ⟨ Check that count file had the right number of counts 31 ⟩; if max section = 0 then write ln(´ ␣ ␣ ´ , expl cost [0] : 17 : 1) else ⟨ Output the accumulated statistics 79 ⟩;

end of PROFILE : { here files should be closed if the operating system requires it } ⟨ Print the job history 194 ⟩; end.

194. 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 194 ⟩ ≡

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

§195  PROFILE  SYSTEM-DEPENDENT CHANGES 69

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

70  INDEX  PROFILE §196

196. Index. Here is a cross-reference table for the processor. All sections in which an identifier is used are listed with that identifier, except that reserved words are indexed only in unusual cases. Underlined entries correspond to where the identifier was declared. Error messages and a few other things like “system dependencies” are indexed here too.

a: \underline{164}. aa: \underline{52}, 63, 65, 67. abs : 12, 68, 118, 121. add cost : \underline{12}, 160. add weight : \underline{77}, 109, 144, 145, 146, 147, 148, 149,

150, 151, 152, 153, 155, 156, 157, 158, 159, 160, 161, 162, 182, 184, 186, 187, 190, 191, 192.

all caps : \underline{86}, 90, 107, 115. and code: \underline{52}, 54, 154. and or cost : \underline{12}, 158, 161. app: \underline{113}, 114, 115, 116, 117, 119, 120, 121. app code: \underline{114}. app trans : \underline{106}, 128, 132, 134, 135, 136, 139, 145,

149, 151, 152, 153, 154, 155, 156, 157, 158, 172, 173, 184, 186, 187, 190, 191, 192.

append : \underline{83}, 148, 166, 170, 172, 173, 174, 181, 183,

184, 185, 186, 187, 190, 191, 192, 193. : 148. array code: \underline{52}, 54, 132. array string cost : \underline{12}, 69. array type: \underline{60}, 63, 134, 145, 151. ASCII code: \underline{14}, 16, 26, 27, 43, 87, 97, 113. asterisk : \underline{114}, 154. avail : \underline{38}, 39, 40, 41. backspace: \underline{86}, 90, 174, 181, 186. banner : \underline{1}, 193. bb: \underline{67}, 114. begin: 3. begin code: \underline{52}, 54, 168, 180. begin section: \underline{86}, 90, 100, 109, 121. bool const : \underline{63}, 152, 171. bool loc: \underline{57}, 59, 63, 65, 68, 144, 146, 147, 152,

158, 161, 162, 184. boolean: 27, 37, 57, 59, 60, 65, 68, 107, 164. break : 23. break in cost : \underline{12}, 69. breakin: 12. buf size: \underline{8}, 26, 27, 32, 45, 47, 110, 113. buffer : \underline{26}, 27, 32, 33, 45, 47, 48, 50, 51, 53, 112,

113, 114, 115, 116, 117, 118, 119, 120, 121. c: \underline{78}, \underline{113}, \underline{148}, \underline{164}. call i : \underline{66}, 149. call overhead : \underline{12}, 148. case code: \underline{52}, 54, 138, 180. case cost : \underline{13}, 186. change weight : \underline{86}, 90, 100, 109, 121. char : 12, 15, 57, 59, 60, 63, 65, 67, 68. char loc: \underline{57}, 59, 60, 63, 65, 68, 152. char string cost : \underline{12}, 69. char type: \underline{59}, 60, 151. check boolean: \underline{184}, 187, 191. chr : 12, 15, 16, 19. close: 12. close cost : \underline{12}, 69. colon: \underline{114}, 139, 140, 141, 151, 167, 173, 174,

181, 186. colon equal : \underline{114}, 190, 192.

comma: \underline{114}, 125, 129, 134, 139, 142, 145,

149, 153, 169. compare cost : \underline{12}, 162. compress : \underline{114}. : 184. confusion: \underline{35}. const code: \underline{52}, 54, 168. constant spec: \underline{68}, 69. continue: \underline{5}, 113, 116, 138, 144, 145, 146, 147,

148, 149, 154, 159. : 31. count file: 2, 7, \underline{24}, 25, 28, 29, 31. cur aux : \underline{107}, 113, 115, 116, 117, 118, 121, 127, 128, 140, 144, 148, 152, 159, 167, 170, 171, 172, 174, 192.

cur code: \underline{107}, 114, 115, 116, 117, 118, 121, 123, 125, 127, 128, 129, 130, 132, 134, 135, 136, 137, 138, 139, 140, 141, 142, 144, 145, 148, 149, 151, 152, 153, 154, 159, 162, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 180, 181, 182, 183, 184, 186, 187, 190, 191, 192, 193.

cur freq : \underline{75}, 76, 77, 89, 92, 95, 168, 174, 179, 180, 181, 183, 184, 185, 186, 187, 190, 191.

cur indent : \underline{87}, 88, 89, 90, 91, 98, 99.

cur length: \underline{143}, 151, 152, 192.
cur name: \underline{53}, 55, 188.

cur ptr : \underline{107}, 113, 115, 122, 125, 129, 133, 138,

139, 140, 146, 170, 172, 174. cur type: \underline{143}, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 184, 192.

§196  PROFILE  INDEX 71

cur val : \underline{107}, 115, 117, 121, 127, 142, 169, 171. debug: \underline{3}, \underline{4}. decl params : \underline{164}, 167. decr : \underline{6}, 27, 28, 49, 71, 90, 95, 99, 115. defined type: \underline{63}, 128, 140, 147, 167, 172, 174. dispose: 12. div cost : \underline{12}, 157. div or mod code: \underline{52}, 54, 154. do code: \underline{52}, 54, 190, 191. do nothing : \underline{6}, 109, 180. done: \underline{5}, 89, 97, 113, 119, 120, 125, 132, 134, 138,

139, 148, 149, 152, 153, 180, 183. done1 : \underline{5}, 138, 142, 180. done2 : \underline{5}, 138, 141, 180, 186. done3 : \underline{5}, 180, 187. done4 : \underline{5}. dot : \underline{114}, 144, 193. double dot : \underline{114}, 130, 153. else: 7. else code: \underline{52}, 54, 184. end: 3, 7. end code: \underline{52}, 54, 137, 138, 168, 183, 184, 186. end of PROFILE : \underline{2}, 34, 193. end section: \underline{86}, 90, 100, 109, 121. endcases: \underline{7}. eof : 12, 27. eof cost : \underline{12}, 68. eoln: 12, 27. equiv : \underline{43}, 44, 50, 65, 70, 71. err print : \underline{32}, 113, 116, 122, 123, 124, 145, 146,

147, 148, 149, 154, 159, 184, 192. error : 27, 31, \underline{32}, 34. error message: \underline{9}, 194. exit : \underline{5}, 6, 154, 159, 168. exp: 12. expected : \underline{124}, 127, 129, 130, 134, 135, 136, 137,

139, 140, 141, 144, 145, 149, 152, 153, 164, 167, 168, 169, 170, 171, 172, 173, 174, 181, 182, 184, 186, 190, 191, 192, 193.

expl cost : \underline{72}, 73, 77, 79, 82, 193. : 149. : 147. extra loc: \underline{57}, 68, 149. f: \underline{27}, \underline{65}. factor : \underline{78}, 79. false: 27, 37, 59, 166, 174. fatal error : \underline{34}, 35, 36, 74, 112. fatal message: \underline{9}, 194. fetch cost : \underline{12}, 68, 152, 192. : 146. file code: \underline{52}, 54, 132, 167. file loc: \underline{57}, 60, 68, 167. file spec: \underline{68}, 69. file type: \underline{60}, 135, 147, 149. final limit : \underline{27}. first text char : \underline{15}, 19. flush out : \underline{89}, 168, 169, 170, 172, 173, 174, 183,

184, 185, 186, 187, 190, 191, 193. for code: \underline{52}, 54, 180. for comment : 188, \underline{189}, 190. for cost : \underline{13}, 190. for tax : \underline{13}, 190. forward : 55, 56, 132, 138, 144, 168, 175. found : \underline{5}, 47, 49, 50, 51, 144, 146, 168, 174, 177. free avail : \underline{41}, 74, 89, 97, 100, 105, 106, 138,

164, 173, 177. freq length: \underline{8}, 92, 93, 95. function code: \underline{52}, 54, 164, 168. function id : \underline{65}, 68, 148, 152, 167, 174, 180, 192. fwd loc: 55, \underline{56}, 174. fwd ptr : \underline{175}, 176, 177, 178. get : 12, 27. get avail : \underline{40}, 58, 59, 60, 61, 63, 66, 68, 69, 73, 74, 83, 84, 85, 104, 108, 113, 117, 121, 125, 131, 133, 134, 135, 136, 137, 138, 139, 140, 153, 164, 167, 171, 174, 178. get block : 163, 164, \underline{168}, 174, 193.

get call : \underline{148}, 152, 180.

get count : \underline{28}, 29, 168, 181, 184, 186, 187, 190, 191. get exp: 143, \underline{144}, 145, 149, 151, 152, 153, \underline{162},

184, 186, 187, 190, 191, 192. get factor : \underline{152}, 154, 155, 156, 157, 158.

get field list : \underline{132}, 137, \underline{138}, 141.
get id list : \underline{125}, 165, 166, 173, 193.
get int const : \underline{127}, 130, 142, 169.
get line: \underline{112}, 113, 120.

get next : 107, 109, 110, \underline{113}, 122, 123, 125, 126, 127, 128, 129, 130, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 144, 145, 146, 147, 148, 149, 151, 152, 153, 155, 156, 157, 158, 159, 160, 161, 162, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 181, 182, 183, 184, 186, 187, 190, 191, 192, 193.

get parameter list : \underline{164}, 166, 174.

get put cost : \underline{12}, 69.
get s exp: \underline{159}, 162.
get s type: \underline{128}, 132, 134, 136.
get semi : \underline{123}, 168, 170, 172, 173, 174, 183,

187, 193. get statement : \underline{168}, 179, \underline{180}, 183, 184, 186,

187, 190, 191. get tail : \underline{113}.

get term: \underline{154}, 159, 160, 161.
get type: \underline{132}, 134, 135, 139, 172, 173.
get variable: \underline{144}, 152, 190, 192.
goto code: \underline{52}, 54, 180.
gubed: \underline{3}.
h: \underline{47}, \underline{78}, \underline{138}, \underline{164}.
halfword : \underline{37}, 74, 89, 107, 162, 164.
harmless message: \underline{9}, 194.
hash: \underline{45}, 46, 49, 50.
head : \underline{83}, 84, 89, 102, 104, 105, 109, 128.

head ptr : \underline{102}, 103, 104, 105. hh: \underline{37}, 38, 71. history : \underline{9}, 10, 194. i: \underline{11}, \underline{47}, \underline{78}, \underline{89}, \underline{113}. id aux : \underline{43}, 44, 53, 62, 63, 65, 107, 115, 129, 147,

167, 171, 172, 173, 174. id code: \underline{43}, 44, 52, 53, 62, 63, 65, 107, 115, 129,

147, 167, 171, 172, 173, 174. id first : \underline{45}, 47, 48, 50, 51, 53, 115, 117, 119. id loc: 45, 47, 48, 50, 51, 54, 115, 119. id lookup: \underline{47}, 53, 115. id pointer : \underline{42}, 43, 45, 47, 53, 56, 71, 89, 107. id pool : 42, \underline{43}, 44, 47, 50, 51, 89, 96. id ptr : \underline{43}, 44, 50. id start : 42, \underline{43}, 44, 47, 50, 51, 96. id2 : \underline{53}, 54, 68. id3 : \underline{53}, 54, 63, 68, 69. id4 : \underline{53}, 54, 63, 68, 69. id5 : \underline{53}, 54, 63, 66, 68, 69. id6 : \underline{53}, 54, 63, 68, 69. id7 : \underline{53}, 54, 55, 63, 69, 188. id8 : \underline{53}, 54, 188. id9 : \underline{53}, 54, 188. if code: \underline{52}, 54, 180. if cost : \underline{13}, 184. impl cost : \underline{72}, 73, 77, 79, 80. in code: \underline{52}, 54, 162. in cost : \underline{12}, 162. in freq : \underline{180}, 184, 185, 186, 187, 190, 191. incomp: \underline{192}. : 192. incr : \underline{6}, 27, 31, 40, 48, 50, 51, 71, 80, 82, 91,

92, 96, 98, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 129, 151, 192.

indent : \underline{86}, 90, 170, 172, 173, 174, 183, 184,

186, 187, 190, 191. index cost : \underline{12}, 145. info: \underline{38}, 57, 59, 60, 61, 63, 65, 66, 67, 68, 69, 72,

73, 74, 77, 83, 85, 90, 97, 100, 104, 105, 109, 113, 125, 131, 133, 134, 135, 136, 137, 139, 140, 145, 146, 147, 148, 149, 150, 151, 153, 155, 156, 157, 160, 167, 173, 174, 177, 178, 192.

initial cap: \underline{86}, 90, 148, 166, 174, 192, 193. initialize: \underline{2}, 58, 193. : 27. input ln: \underline{27}, 112. int : \underline{37}, 38, 71. int const : \underline{63}, 107, 115, 117, 127, 152, 171. int loc: \underline{57}, 59, 63, 65, 66, 68, 149, 152. int real cost : \underline{12}, 68, 150, 151, 155, 156, 160, 192. int string cost : \underline{12}, 69. int type: \underline{59}, 60, 131, 150, 151, 155, 156, 157,

160, 192. integer : 11, 28, 29, 37, 57, 59, 60, 63, 65, 66,

67, 68, 72, 75, 77, 87, 89, 107, 110, 113, 127, 128, 143, 168, 179, 180.

j: \underline{78}, \underline{89}. jump cost : \underline{12}, 182. jump out : 2, \underline{34}. k: \underline{32}, \underline{47}, \underline{78}, \underline{89}. kludge flag : \underline{107}, 121, 174. l: \underline{32}, \underline{47}. label code: \underline{52}, 54, 168. last count : 28, \underline{29}, 30, 31. last text char : \underline{15}, 19. left bracket : \underline{114}, 134, 144, 152. left paren: \underline{114}, 128, 141, 148, 152, 164, 193. length: \underline{43}, 49. lh: \underline{37}, 38, 43, 66. lhs type: \underline{180}, 192. limit : 27, 33, \underline{110}, 111, 112, 113, 116, 119, 120. line: 33, \underline{110}, 111, 112. line length: \underline{8}, 90, 91, 92, 93, 95, 98. link : \underline{38}, 40, 41, 57, 59, 60, 61, 63, 65, 66, 67, 68,

69, 72, 74, 77, 83, 85, 89, 97, 100, 104, 105, 106, 107, 109, 113, 125, 131, 133, 134, 135, 136, 137, 138, 139, 140, 141, 145, 146, 147, 148, 149, 150, 151, 153, 164, 167, 173, 174, 177, 178, 192.

loc: 27, 33, \underline{110}, 111, 112, 113, 114, 115, 116,

117, 118, 119, 120, 121. loop: \underline{6}. lost comment : 185, 186, 188, \underline{189}. m: \underline{74}, \underline{78}, \underline{128}. mark error : \underline{9}, 32. mark fatal : \underline{9}, 34. mark harmless : \underline{9}, 31, 79. max blank left : \underline{52}, 115. max blank right : \underline{52}, 115. max case label : \underline{63}, 141, 186. max command : 83, \underline{86}, 90. max comment : \underline{8}, 107, 119. max halfword : 8, \underline{37}, 121. max int : 59, 63. max modules : \underline{8}, 72, 73, 74, 78. max names : \underline{8}, 42, 46, 48, 49, 50. max section: \underline{72}, 73, 74, 79, 80, 82, 193. mem: 37, \underline{38}, 57, 58, 63, 97. mem end : \underline{38}, 39, 40. mem size: \underline{8}, 37, 38, 40. memory word : \underline{37}, 38, 70. min blank left : \underline{52}, 115. min blank right : \underline{52}, 115. min case label : \underline{63}, 141, 186. min halfword : \underline{37}. mult cost : \underline{12}, 155. n: \underline{29}, \underline{71}, \underline{89}, \underline{128}, \underline{180}. new : 12. new cost : \underline{12}, 69. new line: \underline{21}, 32, 33, 34. new trans : \underline{107}, 109, 113. new trans loc: \underline{107}, 108, 113. next freq : 168, \underline{179}, 180, 182, 183, 184, 186,

187, 190, 191. next offset : \underline{89}, 90, 96. nil: 6. nil code: \underline{52}, 54. nil loc: \underline{57}, 61. nn: \underline{78}, 79, 80, 81, 82. not code: \underline{52}, 54, 152. not found : \underline{5}, 113, 121, 154, 155, 156, 157, 158,

159, 160, 161. null : \underline{37}, 38, 39, 40, 59, 60, 61, 63, 65, 67, 68, 77,

83, 89, 103, 109, 118, 125, 141, 146, 148, 149, 153, 165, 167, 173, 174, 176, 177, 192.

odd : 12. of code: \underline{52}, 54, 134, 135, 136, 140, 186. offset : \underline{89}, 90, 96. one loc: \underline{57}, 59, 60. open cost : \underline{12}, 69. optional file param: \underline{67}, 68, 69, 148, 149. or code: \underline{52}, 54, 159. ord : 12, 16. ord chr cost : \underline{12}, 68. othercases: \underline{7}, \underline{63}. others : 7. out : \underline{85}. out buf : \underline{87}, 89, 91, 92, 96. out buf size: \underline{8}, 87, 89. out freq : \underline{180}, 184, 185, 186, 187, 190, 191. out line: \underline{87}, 88, 91, 92, 94. out wt : \underline{75}, 76, 77, 89, 92, 95, 191. outdent : \underline{86}, 90, 170, 172, 173, 174, 183, 184,

186, 187, 190, 191. output : 2, 75. overflow : \underline{36}, 40, 50, 71, 74, 91, 98. p: \underline{40}, \underline{47}, \underline{58}, \underline{64}, \underline{74}, \underline{77}, \underline{89}, \underline{104}, \underline{105}, \underline{125}, \underline{128},

\underline{132}, \underline{138}, \underline{144}, \underline{148}, \underline{152}, \underline{164}, \underline{168}. pack : 12. pack cost : \underline{12}, 69. packed array type: \underline{60}, 145, 192. packed code: \underline{52}, 54, 132. packed file type: \underline{60}, 147, 149. packed index cost : \underline{12}, 145. packed record type: \underline{60}, 146. packed set type: \underline{60}. packed surcharge: \underline{12}, 146, 147. packt : \underline{132}, 134, 135, 136, 137. page: 79, 94. pascal file: 2, \underline{24}, 25, 112. plus or minus : \underline{63}, 107, 114, 127, 159, 171. pointer : \underline{37}, 38, 40, 57, 58, 64, 72, 74, 77, 83, 89,

102, 104, 105, 107, 113, 125, 128, 132, 138, 143, 144, 148, 152, 154, 159, 164, 168, 175, 180, 189.

: 147. pointer cost : \underline{12}, 147. pointer type: \underline{61}, 133, 147. pool pointer : \underline{42}, 43, 47, 89. pool ptr : \underline{43}, 44, 50. pool size: \underline{8}, 42, 50. pop level : \underline{105}, 128, 132, 144, 152, 162. pop section: \underline{74}, 109. pred : 12. : 112. print : \underline{21}, 32, 33, 34, 79, 94. print ln: \underline{21}, 33, 193. print nl : \underline{21}, 27, 31, 79, 194. procedure code: \underline{52}, 54, 164, 166, 168, 174. procedure id : \underline{65}, 66, 69, 166, 167, 174, 180. PROFILE : \underline{2}. program code: \underline{52}, 54, 193. push level : \underline{104}, 128, 132, 144, 152, 162. push save stack : \underline{71}, 174. push section: \underline{74}, 109. put : 12. put out : \underline{96}, 97, 98, 100, 101. q: \underline{58}, \underline{64}, \underline{77}, \underline{89}, \underline{104}, \underline{105}, \underline{125}, \underline{128}, \underline{132}, \underline{138},

\underline{144}, \underline{148}, \underline{164}, \underline{168}. r: \underline{64}, \underline{148}, \underline{164}, \underline{168}. read : 67. read ln: 27, 28, 31. real : 57, 59, 60, 65, 67, 68, 72, 77, 78. real add cost : \underline{12}, 160. real const : \underline{63}, 107, 118, 152, 171. real div cost : \underline{12}, 156. real loc: \underline{57}, 59, 63, 65, 68, 151, 152, 155, 156, 160. real mult cost : \underline{12}, 68, 155. real string cost : \underline{12}, 69. real type: \underline{59}, 150, 151, 155, 156, 160, 192. record code: \underline{52}, 54, 132. record type: \underline{60}, 137, 146, 192. relation: 107, \underline{114}, 162. repeat code: \underline{52}, 54, 180. repeat tax : \underline{13}, 187. reset : 12, 25. restart : \underline{5}, 113, 119, 121. reswitch: \underline{5}. return: 5, \underline{6}. rewrite: 12, 22. rh: \underline{37}, 38, 43, 66. right bracket : \underline{114}, 134, 145, 153. right paren: \underline{114}, 129, 141, 149, 152, 164, 193. round : 12. s: \underline{127}, \underline{168}. save: \underline{71}, 129, 167, 170, 172, 173, 174. save base: \underline{70}, 71. save ptr : \underline{70}, 71. save size: \underline{8}, 70, 71. save stack : \underline{70}, 71. sec ptr : \underline{72}, 73, 74, 77. semicolon: \underline{114}, 123, 138, 141, 164, 169, 174,

184, 186. set code: \underline{52}, 54, 132. set cost : \underline{12}, 153, 155, 160. set type: \underline{60}, 136, 153, 155, 160. sid tail : \underline{53}. sid tail tail : \underline{53}. sid1 : \underline{53}. sid2 : \underline{53}. sid3 : \underline{53}. sid4 : \underline{53}. sid5 : \underline{53}. sid6 : \underline{53}. sid7 : \underline{53}. sid8 : \underline{53}. sid9 : \underline{53}. sign: \underline{113}, 121. sin: 12. skip to id : \underline{122}, 125, 129, 133, 139, 140, 146, 170,

172, 173, 174, 193. slash: \underline{114}, 154. small const : \underline{63}, 107, 115, 117, 127, 129, 152,

171, 180, 182. : 36. spec param: \underline{67}, 68, 69, 148, 149. spotless : \underline{9}, 10, 194. : 122. static weight : \underline{72}, 73, 77, 79. store cost : \underline{12}, 67, 68, 150, 151, 153, 192. string : 57, 60. string const : \underline{63}, 116, 142, 152, 171. string loc: \underline{57}, 60, 63, 143, 145, 151, 152, 192. string string cost : \underline{12}, 151. string string tax : \underline{12}, 151. : 145. succ: 12. system dependencies: 4, 7, 15, 18, 21, 22, 23,

25, 27, 33, 34, 194, 195. t: \underline{89}, \underline{138}, \underline{148}, \underline{154}, \underline{159}, \underline{162}, \underline{164}, \underline{168}, \underline{180}. tail : \underline{83}, 84, 85, 89, 102, 104, 105, 106, 109, 128. term out : \underline{21}, 22, 23. terminal procedure id : \underline{65}, 174, 180. text : 57, 60. text char : \underline{15}, 16, 21. text file: \underline{15}, 21, 24, 27. text loc: \underline{57}, 60, 63. then code: \underline{52}, 54, 184. : 35. to or downto code: \underline{52}, 54, 190. : 79, 193. trans head : \underline{102}, 105, 106, 143. trans tail : \underline{102}, 105, 106, 143. transcendental cost : \underline{12}, 68. true: 6, 27, 37, 59, 107, 121, 174. trunc: 12. two halves : \underline{37}, 43. : 154, 159. type code: \underline{52}, 54, 168. unary cost : \underline{12}, 68, 152, 159. undefined : \underline{44}, 50, \underline{52}, 55, 62, 115, 144, 170,

172, 173, 174. : 113. : 146. unpack : 12. unsave: \underline{71}, 174. until code: \underline{52}, 54, 184, 187. up arrow : \underline{114}, 132, 144. up to: \underline{113}. update terminal : \underline{23}, 32, 79, 94. v: \underline{89}. val : \underline{38}, 59, 63, 100, 109, 115, 117, 121, 131, 171. var code: \underline{52}, 54, 165, 168. var param: \underline{65}, 66, 144, 165, 180. var surcharge: \underline{12}, 144. variable: \underline{63}, 65, 66, 144, 165, 173, 180. verbatim: \underline{86}, 90, 97, 109, 113, 116, 117, 119. w: \underline{77}, \underline{89}, \underline{180}. : 74. weight length: \underline{8}, 92, 93, 95. wf : \underline{77}. while code: \underline{52}, 54, 62, 180. while comment : 188, \underline{189}, 191. while cost : \underline{13}, 191. while tax : \underline{13}, 191. with: \underline{2}. with code: \underline{52}, 54. write: 21, 91, 92, 93, 95. write ln: 21, 79, 91, 92, 93, 95, 193. x: \underline{78}. xchr : \underline{16}, 17, 18, 19, 33, 91, 92. xclause: 6. xord : \underline{16}, 19, 27. zero loc: \underline{57}, 59.

76  NAMES OF THE SECTIONS  PROFILE §196

⟨ Append the new trans list to the end of tail , interpreting its comments 109 ⟩ Used in section 113.

⟨ Check for  ,  ,  , or  ; goto restart if one of these special types is found 121 ⟩

Used in section 119. ⟨ Check for end of page 94 ⟩ Used in sections 93 and 95.

⟨ Check that count file had the right number of counts 31 ⟩ Used in section 193. ⟨ Choose starting increment, h, for Shellsort 81 ⟩ Used in sections 80 and 82. ⟨ Compare name p with the current identifier; goto found if equal 51 ⟩ Used in section 49. ⟨ Compiler directives 4 ⟩ Used in section 2. ⟨ Complete the current set of parameters 167 ⟩ Used in section 164. ⟨ Compute the hash code, h 48 ⟩ Used in section 47. ⟨ Compute the id pointer, p 49 ⟩ Used in section 47. ⟨ Constants in the outer block 8 ⟩ Used in section 2.

⟨ Convert v to decimal 101 ⟩ Used in section 100. ⟨ Decrease cur indent 99 ⟩ Used in section 90. ⟨ Do addition or goto not found 160 ⟩ Used in section 159.

⟨ Do integer division or goto not found 157 ⟩ Used in section 154.

⟨ Do logical and or goto not found 158 ⟩ Used in section 154. ⟨ Do logical or or goto not found 161 ⟩ Used in section 159.

⟨ Do multiplication or goto not found 155 ⟩ Used in section 154.

⟨ Do real division or goto not found 156 ⟩ Used in section 154.

⟨ Enter a new name into the hash table at position h and goto found 50 ⟩ Used in section 49. ⟨ Error handling procedures 32, 34 ⟩ Used in section 2. ⟨ Fill out a broken line with leaders 93 ⟩ Used in section 91. ⟨ Fill out a normal line with leaders 95 ⟩ Used in section 92.

⟨ Get a comment, then goto restart 119 ⟩ Used in section 113. ⟨ Get a constant 117 ⟩ Used in section 113. ⟨ Get a string 116 ⟩ Used in section 113.

⟨ Get an identifier or reserved word 115 ⟩ Used in section 113.

⟨ Globals in the outer block 9, 16, 21, 24, 26, 29, 38, 43, 45, 53, 56, 57, 64, 70, 72, 75, 78, 83, 87, 102, 107, 110, 143, 175,

179, 189 ⟩ Used in section 2.

⟨ Handle a subroutine declaration 174 ⟩ Used in section 168. ⟨ Handle the const part of a block 170 ⟩ Used in section 168. ⟨ Handle the label part of a block 169 ⟩ Used in section 168. ⟨ Handle the type part of a block 172 ⟩ Used in section 168. ⟨ Handle the var part of a block 173 ⟩ Used in section 168. ⟨ If identifier r was already forward declared, goto found 177 ⟩ Used in section 174.

⟨ Increase cur indent 98 ⟩ Used in section 90.

⟨ Local variables for initialization 11, 58 ⟩ Used in section 2. ⟨ Make p point to the subrange type m . . n 131 ⟩ Used in section 128. ⟨ Memory management procedures 40 ⟩ Used in section 2. ⟨ Output a special comment 100 ⟩ Used in section 90. ⟨ Output entries verbatim 97 ⟩ Used in section 90. ⟨ Output the accumulated statistics 79 ⟩ Used in section 193. ⟨ Print error location based on input buffer 33 ⟩ Used in section 32.

⟨ Print the job history 194 ⟩ Used in section 193.

⟨ Process a case statement 186 ⟩ Used in section 180. ⟨ Process a compound statement 183 ⟩ Used in section 180. ⟨ Process a for statement 190 ⟩ Used in section 180. ⟨ Process a go to statement 182 ⟩ Used in section 180. ⟨ Process a labelled statement 181 ⟩ Used in section 180. ⟨ Process a regular parameter 150 ⟩ Used in section 149. ⟨ Process a repeat statement 187 ⟩ Used in section 180.

§196  PROFILE  NAMES OF THE SECTIONS 77

⟨ Process a special parameter 151 ⟩ Used in section 149. ⟨ Process a while statement 191 ⟩ Used in section 180. ⟨ Process an assignment statement 192 ⟩ Used in section 180. ⟨ Process an if statement 184 ⟩ Used in section 180. ⟨ Put an identifier into the buffer 96 ⟩ Used in section 90. ⟨ Put identifier r on the forward stack 178 ⟩ Used in section 174. ⟨ Put material corresponding to command p into out buf ; also advance p to the last node of the command 90 ⟩

Used in section 89. ⟨ Scan a file type 135 ⟩ Used in section 132. ⟨ Scan a pointer type 133 ⟩ Used in section 132. ⟨ Scan a record type 137 ⟩ Used in section 132.

⟨ Scan a set construction 153 ⟩ Used in section 152.

⟨ Scan a set type 136 ⟩ Used in section 132. ⟨ Scan a subrange type 130 ⟩ Used in section 128. ⟨ Scan an array type 134 ⟩ Used in section 132.

⟨ Scan an enumerated type 129 ⟩ Used in section 128. ⟨ Scan argument list corresponding to parameter list p 149 ⟩ Used in section 148. ⟨ Scan conclusion of variant fields 141 ⟩ Used in section 140.

⟨ Scan field, goto continue 146 ⟩ Used in section 144.

⟨ Scan identifier list and its type 139 ⟩ Used in section 138.

⟨ Scan past case labels 142 ⟩ Used in sections 141 and 186. ⟨ Scan pointer, goto continue 147 ⟩ Used in section 144. ⟨ Scan subscript, goto continue 145 ⟩ Used in section 144.

⟨ Scan the constant and define p accordingly 171 ⟩ Used in section 170.

⟨ Scan to the end of a real constant, if  or  is present 118 ⟩ Used in section 117.

⟨ Scan variant fields 140 ⟩ Used in section 138. ⟨ Set initial values 10, 17, 18, 19, 22, 25, 30, 39, 44, 46, 59, 60, 61, 73, 76, 84, 88, 103, 108, 111, 176 ⟩ Used in section 2.

⟨ Set up all the reserved words and predefined identifiers 54, 55, 63, 66, 68, 69, 188 ⟩ Used in section 193. ⟨ Set up for normal parameters 165 ⟩ Used in section 164. ⟨ Set up for subroutine parameters 166 ⟩ Used in section 164. ⟨ Show frequency lossage in the output 185 ⟩ Used in section 184. ⟨ Sort the sections in order of explicit cost 82 ⟩ Used in section 79. ⟨ Sort the sections in order of implicit cost 80 ⟩ Used in section 79. ⟨ Translate a special character, compressing two-symbol combinations like ‘ ’ into a single symbol 114 ⟩

Used in section 113.

⟨ Truncate the comment, goto done 120 ⟩ Used in section 119.

⟨ Types in the outer block 14, 15, 37, 42 ⟩ Used in section 2.

⟨ Write out buf [0 . . k − 1] and shift the remaining material left in the buffer 91 ⟩ Used in section 90.

⟨ Write out buf , out wt , and cur freq 92 ⟩ Used in section 89.

The PROFILE processor

(Version 1, October 1983)

Section Page

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Operation costs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5 The character set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 8 Reporting errors to the user . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 11 The dynamic memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 13 Identifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 15 Initializing the table of reserved words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 18 Representation of types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 21 Identifier interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 23 Frequencies and weights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 28 Low level output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 31 Levels of translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 36 Getting the next token . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 37 Small syntactic units . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 45 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 49 Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 58 Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 63 The program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 68 System-dependent changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 69 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 70

The preparation of this report was supported in part by the National Science Foundation under grants IST-8201926 and MCS-8300984, and by the System Development Foundation.