§1  ERISCAL  DEFINITION OF ERISCAL 1
1. Definition of ERISCAL. This program takes input written in  , the  assembly

language, and translates it into binary files that can be loaded and executed on simulators or hardwares. is much simpler than the “industrial strength” assembly languages that computer manufacturers usually provide, because it is primarily intended for the simple demonstration programs. Yet it tries to have enough features to serve also as the back end of compilers for C and other high-level languages.

Instructions for using the program appear at the end of this document. First we will discuss the input and output languages in detail; then we’ll consider the translation process, step by step; then we’ll put everything together.

2. A program in consists of a series of lines, each of which usually contains a single instruction. However, lines with no instructions are possible, and so are lines with two or more instructions.

Each instruction has three parts called its label field, opcode field, and operand field; these fields are separated from each other by one or more spaces. The label field, which is often empty, consists of all characters up to the first blank space. The opcode field, which is never empty, runs from the first nonblank after the label to the next blank space. The operand field, which again might be empty, runs from the next nonblank character (if any) to the first blank or semicolon that isn’t part of a string or character constant. If the operand field is followed by a semicolon, possibly with intervening blanks, a new instruction begins immediately after the semicolon; otherwise the rest of the line is ignored. The end of a line is treated as a blank space for the purposes of these rules, with the additional proviso that string or character constants are not allowed to extend from one line to another.

The label field must begin with a letter or a digit; otherwise the entire line is treated as a comment. Popular ways to introduce comments, either at the beginning of a line or after the operand field, are to precede them by the character as in TEX, or by as in C^{++}; is not very particular. However, Lisp-style comments introduced by single semicolons will fail if they follow an instruction, because they will be assumed to introduce another instruction.

3. has no built-in macro capability, nor does it know how to include header files and such things. But users can run their files through a standard C preprocessor to obtain programs in which macros and such things have been expanded. (Caution: The preprocessor also removes C-style comments, unless it is told not to do so.) Literate programming tools could also be used for preprocessing.

If a line begins with the special form ‘ ⟨ integer ⟩ ⟨ string ⟩’, this program interprets it as a line directive emitted by a preprocessor. For example,

means that the following line was line 13 in the user’s source file . Line directives allow us to correlate errors with the user’s original file; we also pass them to the output, for use by simulators and debuggers.

4. deals primarily with symbols and constants, which it interprets and combines to form machine language instructions and data. Constants are simplest, so we will discuss them first.

A decimal constant is a sequence of digits, representing a number in radix 10. A hexadecimal constant is a sequence of hexadecimal digits, preceded by , representing a number in radix 16:

⟨ digit ⟩ ⟶ | | | | | | | | |

⟨ hex digit ⟩ ⟶ ⟨ digit ⟩ | | | | | | | | | | | | ⟨ decimal constant ⟩ ⟶ ⟨ digit ⟩ | ⟨ decimal constant ⟩⟨ digit ⟩ ⟨ hex constant ⟩ ⟶ ⟨ hex digit ⟩ | ⟨ hex constant ⟩⟨ hex digit ⟩

Constants whose value is 2^{32} or more are reduced modulo 2^{32}.

2  DEFINITION OF ERISCAL  ERISCAL §5

5. A character constant is a single character enclosed in single quote marks; it denotes the ASCII or Unicode number corresponding to that character. For example, represents the constant , also known as . The quoted character can be anything except the character that the C library calls or newline; that character should be represented as .

⟨ character constant ⟩ ⟶ ⟨ single byte character except newline ⟩ ⟨ constant ⟩ ⟶ ⟨ decimal constant ⟩ | ⟨ hex constant ⟩ | ⟨ character constant ⟩

Notice that  represents a single quote, the code  ; and  represents a backslash, the code  .

characters are never “quoted” by backslashes as in the C language.

In the present implementation a character constant will always be at most 255, since wyde character input is not supported. The present program does not support Unicode directly because basic software for inputting and outputting 16-bit characters was still in a primitive state at the time of writing. But the data structures below are designed so that a change to Unicode will not be difficult when the time is ripe.

6. A string constant like is an abbreviation for a sequence of one or more character constants separated by commas: . Any character except newline or the double quote mark can appear between the double quotes of a string constant.

7. A symbol in is any sequence of letters and digits, beginning with a letter. A colon ‘ ’ or underscore symbol ‘ ’ is regarded as a letter, for purposes of this definition. All extended-ASCII characters like ‘é’, whose 8-bit code exceeds 126, are also treated as letters.

⟨ letter ⟩ ⟶ | | ⋯ | | | | ⋯ | | | | ⟨ character with code value > 126 ⟩ ⟨ symbol ⟩ ⟶ ⟨ letter ⟩ | ⟨ symbol ⟩⟨ letter ⟩ | ⟨ symbol ⟩⟨ digit ⟩

In future implementations, when is used with Unicode, all wyde characters whose 16-bit code exceeds 126 will be regarded as letters; thus symbols will be able to involve Greek letters or Chinese characters or thousands of other glyphs.

8. A symbol is said to be fully qualified if it begins with a colon. Every symbol that is not fully qualified is an abbreviation for the fully qualified symbol obtained by placing the current prefix in front of it; the current prefix is always fully qualified. At the beginning of an program the current prefix is simply the single character ‘ ’, but the user can change it with the command. For example,

                     ADD     x,y          % means ADD :x,:y
                     PREFIX  Foo:         % current prefix is :Foo:
                     ADD     x,y          % means ADD :Foo:x,:Foo:y
                     PREFIX  Bar:         % current prefix is :Foo:Bar:
                     ADD     :x,y         % means ADD :x,:Foo:Bar:y
                     PREFIX  :            % current prefix reverts to :
                     ADD     x,Foo:Bar:y  % means ADD :x,:Foo:Bar:y

This mechanism allows large programs to avoid conflicts between symbol names, when parts of the program are independent and/or written by different users. The current prefix conventionally ends with a colon, but this convention need not be obeyed.

9. A local symbol is a decimal digit followed by one of the letters , , or , meaning “backward,” “forward,” or “here”:

⟨ local operand ⟩ ⟶ ⟨ digit ⟩ | ⟨ digit ⟩ ⟨ local label ⟩ ⟶ ⟨ digit ⟩

The and forms are permitted only in the operand field of instructions; the form is permitted only in the label field. A local operand such as stands for the last local label in instructions before the current one, or 0 if has not yet appeared as a label. A local operand such as stands for the first in instructions after the current one. Thus, in a sequence such as

                                        2H JMP 2F 2H JMP 2B

the first instruction jumps to the second and the second jumps to the first.

Local symbols are useful for references to nearby points of a program, in cases where no meaningful name is appropriate. They can also be useful in special situations where a redefinable symbol is needed; for example, an instruction like

will maintain a running counter.

10. Each symbol receives a value called its equivalent when it appears in the label field of an instruction; it is said to be defined after its equivalent has been established. A few symbols, like , are predefined because they refer to fixed constants associated with the hardware or its rudimentary operating system; otherwise every symbol should be defined exactly once. The two appearances of ‘ ’ in the example above do not violate this rule, because the second ‘ ’ is not the same symbol as the first.

A predefined symbol can be redefined (given a new equivalent). After it has been redefined it acts like an ordinary symbol and cannot be redefined again. A complete list of the predefined symbols appears in the program below.

Equivalents are either pure or register numbers. A pure equivalent is an unsigned wyde, but a register number equivalent is a nybble value, between 0 and 15. A dollar sign is used to change a pure number into a register number; for example, ‘ ’ means register number 15.

11. Constants and symbols are combined into expressions in a simple way:

⟨ primary expression ⟩ ⟶ ⟨ constant ⟩ | ⟨ symbol ⟩ | ⟨ local operand ⟩ | |

⟨ expression ⟩ | ⟨ unary operator ⟩⟨ primary expression ⟩

⟨ term ⟩ ⟶ ⟨ primary expression ⟩ | ⟨ term ⟩⟨ strong operator ⟩⟨ primary expression ⟩ ⟨ expression ⟩ ⟶ ⟨ term ⟩ | ⟨ expression ⟩⟨ weak operator ⟩⟨ term ⟩ ⟨ unary operator ⟩ ⟶ | | | | | ⟨ strong operator ⟩ ⟶ | | | | | | ⟨ weak operator ⟩ ⟶ | | |

Each expression has a value that is either pure, a register number or an indirect version of these. The character stands for the current location, which is always pure. The unary operators , , , , , and mean, respectively, “indirectize”, “relativize,” “subtract from zero,” “complement the bits,” “change from pure value to register number,” and “take the serial number.” Only the first of these, , can be applied to a register number. The last unary operator, , applies only to symbols, and it is of interest primarily to system programmers; it converts a symbol to the unique positive integer that is used to identify it in the binary file output by . The unusual operator make a relative value from a value subtracting the current location from it. A relative value is useful if we want to add it to the current location; it is mainly used in the field of instructions. Another unusual operator symple gives the information of the compiler that the value of this field will be used indirectly, i.e, addressing mode is 3. It main use is in instruction as $4,*$5 setting $4 from address contained in $5, but it is also used as for example $4,*xxxx meaning that $4 set from the $0 relative data contained in wyde after the instruction.

Binary operators come in two flavors, strong and weak. The strong ones are essentially concerned with multiplication or division: , , , , , , and stand respectively for (x × y) mod 2^{64} (multiplication), ⌊x/y⌋ (division), ⌊2^{64}x/y⌋ (fractional division), x mod y (remainder), (x × 2^{y}) mod 2^{64} (left shift), ⌊x/2^{y}⌋ (right shift), and x & y (bitwise and) on unsigned wydes. Division is legal only if y > 0; fractional division is legal only if x < y. None of the strong binary operations can be applied to register numbers.

The weak binary operations , , , and stand respectively for (x + y) mod 2^{64} (addition), (x − y) mod 2^{64} (subtraction), x | y (bitwise or), and x ⊕ y (bitwise exclusive-or) on unsigned wydes. These operations can be applied to register numbers only in four contexts: ⟨ register ⟩+⟨ pure ⟩, ⟨ pure ⟩+⟨ register ⟩, ⟨ register ⟩ − ⟨ pure ⟩ and ⟨ register ⟩ − ⟨ register ⟩. For example, if denotes and denotes , then and denote , and denotes the pure value .

Register numbers within expressions are allowed to be arbitrary wydes, but a register number assigned as the equivalent of a symbol should not exceed 15.

(Incidentally, one might ask why the designer of did not simply adopt the existing rules of C for expressions. The primary reason is that the designers of C chose to give , , and a lower precedence than ; but in we want to be able to write things like or or . Since the conventions of C were inappropriate, it was better to make a clean break, not pretending to have a close relationship with that language. The new rules are quite easily memorized, because has just two levels of precedence, and the strong binary operations are all essentially multiplicative by nature while the weak binary operations are essentially additive.)

12. A symbol is called a future reference until it has been defined. restricts the use of future references, so that programs can be assembled quickly in one pass over the input; therefore all expressions can be evaluated when the processor first sees them.

The restrictions are easily stated: Future references cannot be used in expressions together with unary or binary operators (except the unary , which does nothing); moreover, future references can appear as operands only in instructions that have relative addresses (namely branches, probable branches, , , ) or in wyde constants (the pseudo-operation ). Thus, for example, one can say or , but not .

13. We noted earlier that each instruction contains a label field, an opcode field, and an operand field. The label field is either empty or a symbol or local label; when it is nonempty, the symbol or local label receives an equivalent. The operand field is either empty or a sequence of expressions separated by commas; when it is empty, it is equivalent to the simple operand field ‘ ’.

⟨ instruction ⟩ ⟶ ⟨ label ⟩⟨ opcode ⟩⟨ operand list ⟩ ⟨ label ⟩ ⟶ ⟨ empty ⟩ | ⟨ symbol ⟩ | ⟨ local label ⟩ ⟨ operand list ⟩ ⟶ ⟨ empty ⟩ | ⟨ expression list ⟩ ⟨ expression list ⟩ ⟶ ⟨ expression ⟩ | ⟨ expression list ⟩ ⟨ expression ⟩

The opcode field contains either a symbolic operation name (like ), or an alias operation, or a pseudo-operation. Alias operations are alternate names for operations whose standard names are inappropriate in certain contexts. Pseudo-operations do not correspond directly to commands, but they govern the assembly process in important ways.

There are ?????? alias operations:

⟨ opcode ⟩ ⟶ ⟨ symbolic operation ⟩ | ⟨ alias operation ⟩

| ⟨ pseudo-operation ⟩

⟨ symbolic operation ⟩ ⟶ | ⋯ |

⟨ alias operation ⟩ ⟶ | ⋯ |

⟨ pseudo-operation ⟩ ⟶ |  |  |  |  |  |  |

14.  operations like  require exactly two expressions as operands.
15. In all cases when the opcode corresponds to an  operation, the  instruction tells

the assembler to carry out three steps: (1) Define the equivalent of the label field to be the current location, if the label is nonempty; (2) Evaluate the operands and assemble the specified instruction into the current location; (3) Increase the current location by 1.

16. Now let’s consider the pseudo-operations, starting with the simplest cases.

• ⟨ label ⟩ ⟨ expression ⟩ defines the value of the label to be the value of the expression, which must not be a future reference. The expression may be either pure or a register number.

• ⟨ label ⟩ ⟨ expression ⟩ first defines the label to be the value of the current location, if the label is nonempty. Then the current location is changed to the value of the expression, which must be pure.

For example, ‘ ’ will start assembling subsequent instructions or data in location whose hexadecimal value is ^{#}1000. ‘ ’ defines to be the address of the first of 500 bytes in memory; assembly will continue at location + 500. The operation of aligning the current location to a multiple of 256, if it is not already aligned in that way, can be expressed as ‘ ’.

A less trivial example arises if we want to emit instructions and data into two separate areas of memory, but we want to intermix them in the source file. We could start by defining and to be the starting addresses of the instruction and data segments, respectively. Then, a sequence of instructions could be enclosed in ‘ ; …; ’; a sequence of data could be enclosed in ‘ ; …; ’. Any number of such sequences could then be combined. Instead of the two pseudo-instructions ‘ ’ one could in fact write simply ‘ ’ when switching from instructions to data.

• ⟨ symbol ⟩ redefines the current prefix to be the given symbol (fully qualified). The label field should be blank.

17. The next pseudo-operations assemble wydes of data.

• ⟨ label ⟩ ⟨ expression list ⟩ defines the label to be the current location, if the label field is nonempty; then it assembles one wyde for each expression in the expression list, and advances the current location by the number of wydes. The expressions should all be pure numbers that fit in one wyde.

String constants are often used in such expression lists. For example, if the current location is ^{#}1000, the instruction assembles six wydes containing the constants , , , , , and into locations ^{#}1000, …, ^{#}1005, and advances the current location to ^{#}1006.

18. Global registers are important by starting in programs. We give starting values to these registers.

• ⟨ label ⟩ ⟨ expression ⟩ allocates a new global register, and assigns its number as the equivalent of the label. At the beginning of assembly, the current global threshold G is $0. Each distinct instruction increases G by 1.

The value of the expression will be loaded into the global register at the beginning of the program, except if the ABI of the given operating system and/or source language does not dictate otherwise. Register $0 is always has a defined starting value, the value of the label .

When programs use subroutines with a memory stack in addition to the built-in register stack, they usually begin with the instructions ‘ ’; these instructions allocate a stack pointer and a frame pointer . Usually with ‘ ’ we also give a name to a link pointer for return addresses. However, subroutine libraries are free to implement any conventions for registers and stacks that they like.

19. If our program will run on an processor embedded in hardware supporting Harvard architecture instead of von Neumann architecture, we need two more pseudo-instructions. (In this case we have to use the compiler option.)

• ends generating data going to the data segment and begins generate code going to the code segment; it has no effect if option is not given.

• ends generating code going to the code segment and begins generate data going to the data segment; it has no effect if option is not given.

Remark that by option there is the possibility also to generate code into the data segment, but cannot execute there (only read/write), and there is the possibility to generate data to the code segment but cannot read/write there, only execute. Nevertheless, there is one possibility to write the content of a register into the code segment by a ‘ ’ instruction and leter execute it; we does not suggest this trick to use in user programs, because some operating systems does not save the content of the code segment by pageing.

20. Finally, there are two pseudo-instructions to pass information and hints to the loading routine and/or to debuggers that will be using the assembled program.

• ⟨ expression ⟩ begins “special mode”; the ⟨ expression ⟩ should have a value that fits in two bytes, and the label field should be blank.

• ends “special mode”; the operand field is ignored, and the label field should be blank. All material assembled between and is passed directly to the output, but not loaded as

part of the assembled program. Ordinary instructions cannot appear in special mode; only the pseudo-operations , , are allowed. The operand of should have a value that fits in a wyde; this value identifies the kind of data that follows. (For example, might introduce information about subroutine calling conventions at the current location, and might introduce line numbers from a high-level-language program that was compiled into the code at the current place. System routines often need to pass such information through an assembler to the operating system, hence provides a general-purpose conduit.)

21. A program should begin at the special symbolic location (more precisely, at the address corresponding to the fully qualified symbol ). This symbol always has serial number 1, and it must always be defined.

Locations should not receive assembled data more than once. (More precisely, the loader will load the bitwise xor of all the data assembled for each wyde position; but the general rule “do not load two things into the same wyde” is safest.) All locations that do not receive assembled data are initially zero, except that the the operating system may put command-line data and debugger data into data segment above the stack. (The rudimentary operating system starts a program with the number of command-line arguments in and a pointer to the beginning of an array of argument pointers in stack pointed by $2.)

8  BINARY ERO OUTPUT  ERISCAL §22
22. Binary ERO output. When the  processor assembles a file called  , it produces
a binary output file called  . (The suffix  stands for “  symbolic,” and  stands for
“  object.”) Such  files have a simple structure consisting of a sequence of wydes. Some of the

wydes are instructions to a loading routine; others are data to be loaded.

Loader instructions are distinguished from wydes of data by their first three (most significant) nybble, which has the special escape-code value ^{#}0e5, called ero in the program below. This code value corresponds to ’s insruction , which is unlikely to occur in wydes of data. The last nybble of a loader instruction is the loader opcode, called the lopcode.

#define ero ^{#}0e5

§23  ERISCAL  BINARY ERO OUTPUT 9

23. When a wyde of the file does not begin with the escape code, it is loaded into the current location λ, and λ is increased by one. More exacly, there may be two current locations, one for code segment, and one for data segment and we may change between them. Both start with zero. The current line number is also increased by 1, if it is nonzero.

When a wyde does begin with the escape code, its last nybble is the lopcode defining a loader instruction. There are thirteen lopcodes:

• lop quote: ^{#}0. Treat the next wyde as an ordinary wyde, even if it begins with the escape code.

• lop seg : ^{#}1. Change between data and code segment.

• lop skip: ^{#}2. Increase the current location by the next wyde.

• lop fixw : ^{#}3. Load (by ) the value of the current location into wyde P, where P is the 16-bit address defined by the next wyde. (The wyde at P was previously assembled as zero because of a future reference.)

• lop fixr : ^{#}4. Load (by ) the next wyde called δ into the field of the wyde in location P, where P is the address that precedes the current location by δ. (This nybble was previously loaded by an instruction with a relative address. Its field was previously assembled as zero because of a future reference.)

• lop fixwx : ^{#}5. Proceed as in lop fixw , but load the current location to the other segment.

• lop fixrx : ^{#}6. Proceed as in lop fixr , but load the current location to the other segment.

• lop file: ^{#}9. Set the current file number to the upper half of the next wyde and the current line number to zero. The lower half of the next wyde gives the length of the filename. The following wydes are the characters of the file name. If this file number has occurred previously, the file name has length zero.

• lop line: ^{#}a. Set the current line number to the next wyde. If the line number is nonzero, the current file and current line should correspond to the source location that generated the next data to be loaded, for use in diagnostic messages. (The program gives precise line numbers to the sources of wydes in code segment, which tend to be instructions, but not to the sources of wydes assembled in data segments.)

• lop spec: ^{#}b. Begin special data of type given by the next wyde. The subsequent wydes, continuing until the next loader operation other than lop quote, comprise the special data. A lop quote instruction allows wydes of special data to begin with the escape code.

• lop pre: ^{#}c. A lop pre instruction, which defines the “preamble,” must be the first wyde of every file. The higher byte of the next wyde specifies the version number of format, currently 1; other version numbers may be defined later, but version 1 should always be supported as described in the present document. The lower byte of the next wyde specifies how many wydes following a lop pre command provide additional information that might be of interest to system routines. If it is nonzero, the first two wydes of additional information in big endian order records the time that this file was created, measured in seconds since 00:00:00 Greenwich Mean Time on 1 Jan 1970.

• lop post : ^{#}d. This instruction begins the postamble, which follows all instructions and data to be loaded. It causes $0, 1, …, $15 initially set to the values of the next 16 wydes.

• lop stab: ^{#}e. This instruction must appear immediately after the wydes following lop post . It is followed by the symbol table, which lists the equivalents of all user-defined symbols in a compact form that will be described later.

• lop end : ^{#}f. This instruction must be the very last two wydes of each file. The next wyde gives exactly, how many wydes must appear between it and the lop stab command. (Therefore a program can easily find the symbol table without reading forward through the entire file.)

A separate routine called is available to translate binary files into human-readable form. #define lop quote ^{#}0 /∗ the quotation lopcode ∗/ #define lop seg ^{#}1 /∗ the segment change lopcode ∗/ #define lop skip ^{#}2 /∗ the skip lopcode ∗/ #define lop fixw ^{#}3 /∗ the wyde-fix lopcode ∗/ #define lop fixr ^{#}4 /∗ the relative-fix lopcode ∗/ #define lop fixwx ^{#}5 /∗ extended relative-fix lopcode ∗/ #define lop fixrx ^{#}6 /∗ extended relative-fix lopcode ∗/ #define lop file ^{#}9 /∗ the file name lopcode ∗/ #define lop line ^{#}a /∗ the file position lopcode ∗/ #define lop spec ^{#}b /∗ the special hook lopcode ∗/ #define lop pre ^{#}c /∗ the preamble lopcode ∗/ #define lop post ^{#}d /∗ the postamble lopcode ∗/ #define lop stab ^{#}e /∗ the symbol table lopcode ∗/ #define lop end ^{#}f /∗ the end-it-all lopcode ∗/

24. Many readers will have noticed that has no facilities for relocatable output, nor does format support such features. Knuth’s first drafts of and did allow relocatable objects, with external linkages, but the rules were substantially more complicated and therefore inconsistent with the goals of The Art of Computer Programming. His design might actually prove to be superior to the current practice, now that computer memory is significantly cheaper than it used to be, because one-pass assembly and loading are extremely fast when relocatability and external linkages are disallowed. Different program modules can be assembled together about as fast as they could be linked together under a relocatable scheme, and they can communicate with each other in much more flexible ways. Debugging tools are enhanced when open-source libraries are combined with user programs, and such libraries will certainly improve in quality when their source form is accessible to a larger community of users.

§25  ERISCAL  BASIC DATA TYPES 11

25. Basic data types. This program for the 16-bit ELTE RISC architecture is based on 32-bit integer arithmetic, because it is essencial to be possible to rewrite to the compiler running on . The definition of type wyde should be changed. ⟨ Type definitions 25 ⟩ ≡

typedef unsigned int wyde; /∗ assumes that an int is at least 16 bits wide ∗/ typedef unsigned int tetra; /∗ assumes that an int is at exactly 32 bits wide ∗/ typedef enum {

false, true } bool;

See also sections 31, 56, 60, 64, 68, and 81. This code is used in section 137.

26. ⟨ Global variables 26 ⟩ ≡ wyde zero wyde; /∗ zero wyde = 0 ∗/ wyde neg one = −1; /∗ neg one = −1 ∗/ wyde aux ; /∗ auxiliary output of a subroutine ∗/ bool overflow ; /∗ set by certain subroutines for signed arithmetic ∗/

See also sections 34, 37, 38, 44, 47, 48, 53, 58, 62, 65, 69, 75, 82, 89, 104, 116, 134, 140, and 144. This code is used in section 137.

27. Left and right shifts are not difficult. ⟨ Subroutines 27 ⟩ ≡

wyde shift left ((wyde, int)); wyde shift left (y, s) /∗ shift left by s bits, where 0 ≤ s ≤ 16 ∗/

wyde y;

int s;

{ while (s ≥ 8) y ≪= 8, s −= 8; y ≪= s; return y &^{#}ffff;

} wyde shift right ((wyde, int, int)); wyde shift right (y, s, u) /∗ shift right, arithmetically if u = 0 ∗/

wyde y;

int s, u;

{ while (s ≥ 8) y = (y ≫ 8) + (u ? 0 : −((y ≫ 7) &^{#}ff)), s −= 8; if (s) y = (y ≫ s) + (u ? 0 : (−(y ≫ 7)) ≪ (8 − s)); return y;

}

See also sections 28, 29, 42, 43, 45, 46, 49, 50, 51, 52, 54, 57, 59, 61, 73, and 74. This code is used in section 137.

12  MULTIPLICATION  ERISCAL §28

28. Multiplication. We need to multiply two unsigned 16-bit integers, obtaining an unsigned 32-bit product. It is easy to do this on a 16-bit machine by using Algorithm 4.3.1M of Seminumerical Algorithms, with b = 2^{8}.

The following subroutine returns the lower half of the product, and puts the upper half into a global tetrabyte called aux . ⟨ Subroutines 27 ⟩ +≡

wyde wmult ((wyde, wyde)); wyde wmult (y, z)

wyde y, z; {

wyde u, v, t; wyde acc; u = y &^{#}ff; v = z &^{#}ff; t = u ∗ v; acc = t &^{#}ff; t ≫= 8; /∗ low times low ∗/ y ≫= 8; y &= ^{#}ff; v ∗= y; v += t; t = v &^{#}ff; v ≫= 8; /∗ high times low ∗/ z ≫= 8; z &= ^{#}ff; u ∗= z; u += t; t = u &^{#}ff; u ≫= 8; /∗ low times high ∗/ aux = y ∗ z; aux += u; acc += t; /∗ high times high ∗/ return acc;

}

§29  ERISCAL  MULTIPLICATION 13

29. Division inputs the high half of a dividend in the global variable aux and returns the remainder in aux . Long division of an unsigned 32-bit integer by an unsigned 16-bit integer is, of course, one of the most challenging routines needed for arithmetic. The following program, based on Algorithm 4.3.1D of Seminumerical Algorithms, computes wydes q and r such that (2^{16}x + y) = qz + r and 0 ≤ r < z, given wydes x, y, and z, assuming that x < z. (If x ≥ z, it simply sets q = x and r = y.) The quotient q is returned by the subroutine; the remainder r is stored in aux . ⟨ Subroutines 27 ⟩ +≡

wyde wdiv ((wyde, wyde, wyde)); wyde wdiv (x, y, z)

wyde x, y, z; {

int j, n; wyde zl , zh, c, q, m, t; x &= ^{#}ffff; y &= ^{#}ffff; z &= ^{#}ffff; if (x ≥ z) { aux = y &^{#}ffff; return x &^{#}ffff; } n = 0; while (¬(z & (1 ≪ 15))) {

z ≪= 1; c = y ≫ 15; x ≪= 1; x += c; y ≪= 1; ++n;

} zl = z &^{#}ff; z −= zl ; zh = z ≫ 8; aux = 0; for (j = 1; j ≥ 0; j^{−}) {

if (x ≥ z) q = ^{#}ff; else q = x/zh; /∗ approx q-digit ∗/ m = zl ∗ q; t = (m &^{#}ff) ≪ 8; m ≫ 8; /∗ q times low part ∗/ c = 0; t = y − t; if (t > y) ^{++}c; y = t; /∗ multiple back ∗/ t = x − c; c = 0; if (t > x) ^{++}c; x = t − m; if (x > t) ^{++}c; t = x; x = t − zh ∗ q; if (x > t) ^{++}c; while (c) { /∗ add back while carry ∗/

−q; t = 0; y += (zl ≪ 8); if (y < (zl ≪ 8)) ^{++}t; x += t;

if (x < t) ^{−}c;
x += zh;
if (x < zh) ^{−}c;
}
aux ≪= 8;
aux += q;
x ≪= 8;
x += y ≫ 8;
y ≪= 8;

}

x ≫= n; return x;

}

30. Here’s a rudimentary check to see if arithmetic is in trouble.

31. Future versions of this program will work with symbols formed from Unicode characters, but the present code limits itself to an 8-bit subset. The type Char is defined here in order to ease the later transition: At present, Char is the same as char, but Char can be changed to a 16-bit type in the Unicode version.

Other changes will also be necessary when the transition to Unicode is made; for example, some calls of fprintf will become calls of fwprintf , and some occurrences of will become in print formats. The switchable type name Char provides at least a first step towards a brighter future with Unicode. ⟨ Type definitions 25 ⟩ +≡

typedef char Char; /∗ bytes that will become wydes some day ∗/

32. While we’re talking about classic systems versus future systems, we might as well define the macro, which makes function prototypes available on ANSI C systems without making them uncompilable on older systems. Each subroutine below is declared first with a prototype, then with an old-style definition. ⟨ Preprocessor definitions 32 ⟩ ≡ #ifdef #define (list ) list #else #define (list ) ( ) #endif

See also section 40. This code is used in section 137.

§33  ERISCAL  BASIC INPUT AND OUTPUT 15

33. Basic input and output. Input goes into a buffer that is normally limited to 72 characters. This limit can be raised, by using the option when invoking the assembler; but short buffers will keep listings from becoming unwieldy, because a symbolic listing adds 19 characters per line. ⟨ Initialize everything 33 ⟩ ≡

if (buf size < 72) buf size = 72; buffer = (Char ∗) calloc(buf size + 1, sizeof (Char)); lab field = (Char ∗) calloc(buf size + 1, sizeof (Char)); op field = (Char ∗) calloc(buf size, sizeof (Char)); operand list = (Char ∗) calloc(buf size, sizeof (Char)); err buf = (Char ∗) calloc(buf size + 60, sizeof (Char)); if (¬buffer ∨ ¬lab field ∨ ¬op field ∨ ¬operand list ∨ ¬err buf ) panic( ␣ ␣ ␣ ␣ );

See also sections 63, 71, 83, 90, and 141. This code is used in section 137.

34. ⟨ Global variables 26 ⟩ +≡ Char ∗buffer ; /∗ raw input of the current line ∗/ Char ∗buf ptr ; /∗ current position within buffer ∗/ Char ∗lab field ; /∗ copy of the label field of the current instruction ∗/ Char ∗op field ; /∗ copy of the opcode field of the current instruction ∗/ Char ∗operand list ; /∗ copy of the operand field of the current instruction ∗/ Char ∗err buf ; /∗ place where dynamic error messages are sprinted ∗/

35. ⟨ Get the next line of input text, or break if the input has ended 35 ⟩ ≡ if (¬fgets (buffer , buf size + 1, src file)) break; ++line no; line listed = false; j = strlen(buffer ); if (buffer [j − 1] ≡ ) buffer [j − 1] = ; /∗ remove the newline ∗/ else if ((j = fgetc(src file)) ≠ ) ⟨ Flush the excess part of an overlong line 36 ⟩; if (buffer [0] ≡ ) ⟨ Check for a line directive 39 ⟩; buf ptr = buffer ;

This code is used in section 137.

36. ⟨ Flush the excess part of an overlong line 36 ⟩ ≡

{ while (j ≠ ∧ j ≠ ) j = fgetc(src file); if (¬long warning given) {

long warning given = true;

    err (  ␣          ␣  ␣    ␣     ␣     ␣    ␣    ␣  );

fprintf (stderr ,  ␣   ␣         ␣   ␣        ␣   ␣       ␣  ␣  ␣     ␣  );
} else err (  ␣          ␣  );

}

This code is used in section 35.

16  BASIC INPUT AND OUTPUT  ERISCAL §38

37. ⟨ Global variables 26 ⟩ +≡ int cur file; /∗ index of the current file in filename ∗/ int line no; /∗ current position in the file ∗/ bool line listed ; /∗ have we listed the buffer contents? ∗/ bool long warning given; /∗ have we given the hint about ? ∗/ 38. We keep track of source file name and line number at all times, for error reporting and for synchronization data in the object file. Up to 256 different source file names can be remembered. ⟨ Global variables 26 ⟩ +≡

Char ∗filename[257]; /∗ source file names, including those in line directives ∗/ int filename count ; /∗ how many filename entries have we filled? ∗/

39. If the current line is a line directive, it will also be treated as a comment by the assembler. ⟨ Check for a line directive 39 ⟩ ≡

{ for (p = buffer + 1; isspace(∗p); p^{++}) ; for (j = 0; isdigit (∗p); p^{++}) j = 10 ∗ j + ∗p − ; for ( ; isspace(∗p); p^{++}) ; if (∗p ≡ ) {

if (¬filename[filename count ]) { filename[filename count ] = (Char ∗) calloc( + 1, sizeof (Char)); if (¬filename[filename count ]) panic( ␣ ␣ ␣ ␣ ␣ );

}

for (p^{++}, k = 0; ∗p ∧ ∗p ≠  ∧ k <  ; p^{++}, k^{++}) filename[filename count ][k] = ∗p;
if (k ≡  ) panic(  ␣         ␣     ␣    ␣   ␣  );
if (∗p ≡  ∧ ∗(p − 1) ≠  ) {  /∗ yes, it’s a line directive ∗/

filename[filename count ][k] = ;

for (k = 0; strcmp(filename[k], filename[filename count ]) ≠ 0; k^{++}) ;

if (k ≡ filename count ) { if (filename count ≡ 256) panic( ␣ ␣ ␣ ␣ ␣ ␣ ); filename count^{++};

}

cur file = k; line no = j − 1;

}

} }

This code is used in section 35.

40. Archaic versions of the C library do not define . ⟨ Preprocessor definitions 32 ⟩ +≡ #ifndef #define 256 #endif

41. ⟨ Local variables 41 ⟩ ≡ register Char ∗p, ∗q; /∗ the place where we’re currently scanning ∗/

See also section 67. This code is used in section 137.

42. The next several subroutines are useful for preparing a listing of the assembled results. In such a listing, which the user can request with a command-line option, we fill the leftmost 19 columns with a representation of the output that has been assembled from the input in the buffer. Sometimes the assembled output requires more than one line, because we have room to output only a tetrabyte per line.

The flush listing line subroutine is called when we have finished generating one line’s worth of assembled material. Its parameter is a string to be printed between the assembled material and the buffer contents, if the input line hasn’t yet been echoed. The length of this string should be 19 minus the number of characters already printed on the current line of the listing. ⟨ Subroutines 27 ⟩ +≡

void flush listing line ((char ∗)); void flush listing line(s)

char ∗s; {

if (line listed ) fprintf (listing file, );

else { fprintf (listing file, , s, buffer ); line listed = true;

} }

43. Only the two least significant hex digits of a location are shown on the listing, unless the other digits have changed. The following subroutine prints an extra line when a change needs to be shown. ⟨ Subroutines 27 ⟩ +≡

void update listing loc ((void)); void update listing loc( ) {

if (cur seg ≠ listing seg ∨ ((cur loc ⊕ listing loc) &^{#}ff00)) { fprintf (listing file, , cur seg , cur loc); flush listing line( ␣␣ );

}

listing seg = cur seg ; listing loc = cur loc; }

44. ⟨ Global variables 26 ⟩ +≡ wyde cur loc; /∗ current location of assembled output ∗/ wyde cur seg = 0; /∗ current segment of assembled output ∗/ wyde cur code loc; /∗ current location of assembled output ∗/ wyde cur data loc; /∗ current location of assembled output ∗/ wyde listing loc; /∗ current location on the listing ∗/ wyde listing seg ; /∗ current segment on the listing ∗/ unsigned char hold buf [4]; /∗ assembled nybbles ∗/ unsigned char held bits ; /∗ which nybbles of hold buf are active? ∗/ unsigned char listing bits ; /∗ which of them haven’t been listed yet? ∗/ bool spec mode; /∗ are we between and ? ∗/ wyde spec mode loc; /∗ number of wydes in the current special output ∗/ 45. When nybbles are assembled, they are placed into the hold buf . Furthermore, listing bits is increased by ^{#}10 ≪ j if that nybble is a future reference to be resolved later.

The nybbles are held until we need to output them. The listing clear routine lists any that have been held but not yet shown. It should be called only when listing bits ≠ 0. ⟨ Subroutines 27 ⟩ +≡

void listing clear ((void)); void listing clear ( ) {

register int j; if (spec mode) fprintf (listing file, ␣␣␣␣␣␣␣␣␣ ); else {

update listing loc( );

fprintf (listing file, ␣ , listing loc); } for (j = 0; j < 4; j^{++})

if (listing bits & (^{#}10 ≪ j)) fprintf (listing file, );

else fprintf (listing file, , (j & 1) ? hold buf [j ≫ 1] ≫ 4 : hold buf [j ≫ 1] &^{#}f); flush listing line( ␣␣ ); listing bits = 0;

} 46. Error messages are written to stderr . If the message begins with ‘ ’ it is merely a warning; if it begins with ‘ ’ it is fatal; otherwise the error is probably serious enough to make manual correction necessary, yet it is not tragic. Errors and warnings appear also on the optional listing file. #define err (m)

{ report error (m); if (m[0] ≠ ) goto bypass ; }

#define derr (m, p)

{ sprintf (err buf , m, p);

report error (err buf ); if (err buf [0] ≠ ) goto bypass ; }

#define dderr (m, p, q)

{ sprintf (err buf , m, p, q);

report error (err buf ); if (err buf [0] ≠ ) goto bypass ; }

#define panic(m)

{ sprintf (err buf , , m); report error (err buf ); }

#define dpanic(m, p)

{ err buf [0] = ; sprintf (err buf + 1, m, p); report error (err buf ); }

⟨ Subroutines 27 ⟩ +≡ void report error ((char ∗)); void report error (message)

char ∗message; {

if (¬filename[cur file]) filename[cur file] = ; if (message[0] ≡ )

fprintf (stderr , ␣ ␣ ␣ ␣ , filename[cur file], line no, message + 1); else if (message[0] ≡ )

fprintf (stderr , ␣ ␣ ␣ ␣ ␣ , filename[cur file], line no, message + 1); else {

fprintf (stderr , ␣ ␣ ␣ , filename[cur file], line no, message);

err count^{++}; } if (listing file) {

if (¬line listed ) flush listing line( ␣ );

if (message[0] ≡ ) fprintf (listing file,  ␣         ␣  , message + 1);
else if (message[0] ≡ ) fprintf (listing file,  ␣     ␣       ␣  , message + 1);
else fprintf (listing file,  ␣      ␣  , message);

}

if (message[0] ≡ ) exit (−2); }

47. ⟨ Global variables 26 ⟩ +≡ int err count ; /∗ this many errors were found ∗/

48. Output to the binary obj file occurs four nybbles at a time. The nybbles are assembled in small buffers, not output as single wyde, because we want the output to be big-endian even when the assembler is running on a little-endian machine. #define ero write(buf ) if (fwrite(buf , 1, 2, obj file) ≠ 2) dpanic( ␣ ␣ ␣ , obj file name) ⟨ Global variables 26 ⟩ +≡

unsigned char lop quote command [2] = {(ero ≫ 4) &^{#}ff, (ero ≪ 4) &^{#}f0 + lop quote}; unsigned char ero buf [2]; int ero ptr ; 49. ⟨ Subroutines 27 ⟩ +≡

void ero clear ((void)); void ero out ((void)); void ero wyde ((wyde)); void ero lop ((char, unsigned char, unsigned char)); void ero lopp ((char, wyde)); void ero clear ( ) /∗ clears hold buf , when held bits ≠ 0 ∗/ {

if (hold buf [0] ≡ ero ≫ 4 ∧ hold buf [1] ≫ 4 ≡ ero &^{#}f) ero write(lop quote command ); ero write(hold buf ); if (listing file ∧ listing bits ) listing clear ( ); held bits = 0; hold buf [0] = hold buf [1] = 0; ++ero cur loc; if (ero line no) ^{++}ero line no;

} void ero out ( ) {

if (held bits ) ero clear ( );

ero write(ero buf ); } void ero wyde(t) /∗ output a wyde ∗/

wyde t; {

ero buf [0] = (t ≫ 8) &^{#}ff; ero buf [1] = t &^{#}ff;

ero out ( ); } void ero trie wyde(t) /∗ output a trie wyde ∗/

wyde t; {

ero buf [0] = (t ≫ 8) &^{#}ff; ero buf [1] = t &^{#}ff;

ero out ( );

++ero ptr ; } void ero lop(x, y, z) /∗ output a loader operation ∗/

char x;

unsigned char y, z; {

ero buf [0] = (ero ≫ 4) &^{#}ff; ero buf [1] = ((ero ≪ 4) &^{#}f0) + (x &^{#}f);

ero out ( );

ero buf [0] = y &^{#}ff; ero buf [1] = z &^{#}ff;

ero out ( ); } void ero lopp(x, yz ) /∗ output a loader operation with wyde operand ∗/

char x; wyde yz ;

{ ero buf [0] = (ero ≫ 4) &^{#}ff; ero buf [1] = ((ero ≪ 4) &^{#}f0) + (x &^{#}f); ero out ( ); ero buf [0] = (yz ≫ 8) &^{#}ff; ero buf [1] = yz &^{#}ff; ero out ( );

}

50. The ero seg subroutine makes the current segment in the object file equal to cur seg . ⟨ Subroutines 27 ⟩ +≡

void ero seg ((void)); void ero seg ( ) {

if (held bits ) ero clear ( );

if (ero cur seg ≠ cur seg ) ero wyde((ero ≪ 4) + lop seg ); ero cur seg = cur seg ;

}

51. The ero loc subroutine makes the current location in the object file equal to cur loc. ⟨ Subroutines 27 ⟩ +≡

void ero loc ((void)); void ero loc( ) {

wyde w;

ero seg ( );

w = (cur loc − ero cur loc) &^{#}ffff;

if (w) ero lopp(lop skip, w);

ero cur loc = cur loc; } 52. Similarly, the ero sync subroutine makes sure that the current file and line number in the output file agree with cur file and line no. ⟨ Subroutines 27 ⟩ +≡

void ero sync ((void)); void ero sync( ) {

register int j;

register unsigned char ∗p; if (cur file ≠ ero cur file) {

if (filename passed [cur file]) ero lop(lop file, cur file, 0);

else { ero lop(lop file, cur file, strlen(filename[cur file])); for (p = filename[cur file]; ∗p; p^{++}) {

ero buf [0] = (∗p ≫ 8) &^{#}ff; ero buf [1] = ∗p &^{#}ff; ero out ( );

}

filename passed [cur file] = 1; } ero cur file = cur file; ero line no = 0;

}

if (line no ≠ ero line no) { if (line no ≥ ^{#}10000) panic( ␣ ␣ ␣ ␣ ␣ ␣ ␣ ); ero lopp(lop line, line no); ero line no = line no;

} }

53. ⟨ Global variables 26 ⟩ +≡ wyde ero cur loc; /∗ current location in the object file ∗/ wyde ero cur seg ; /∗ current segment in the object file ∗/

int ero line no;  /∗ current line number in the  output so far ∗/
int ero cur file;  /∗ index of the current file in the  output so far ∗/

char filename passed [256]; /∗ has a filename been recorded in the output? ∗/ 54. Here is a basic subroutine that assembles a wyde starting at cur loc. The x bits parameter tells which wydes, if any, are part of a future reference. ⟨ Subroutines 27 ⟩ +≡

void assemble ((wyde, unsigned char)); void assemble(dat , x bits )

wyde dat ;

unsigned char x bits ; /∗ These nybbles will be listed as x ∗/ {

register int j, l; if (spec mode) l = spec mode loc; else {

l = cur loc;

⟨ Make sure cur loc and ero cur loc refer to the same wyde 55 ⟩; } hold buf [0] = (dat ≫ 8) &^{#}ff; hold buf [1] = dat &^{#}ff; listing bits |= x bits +^{#}f; held bits = ^{#}f; if (listing file) listing clear ( ); ero clear ( ); if (spec mode) ^{++}spec mode loc; else ^{++}cur loc;

}

55. ⟨ Make sure cur loc and ero cur loc refer to the same wyde 55 ⟩ ≡ if (cur seg ≠ ero cur seg ) ero seg ( ); if ((cur loc ⊕ ero cur loc) &^{#}ffff) ero loc( );

This code is used in sections 54 and 111.

24  THE SYMBOL TABLE  ERISCAL §56

56. The symbol table. Symbols are stored and retrieved by means of a ternary search trie, following ideas of Bentley and Sedgewick. (See ACM–SIAM Symp. on Discrete Algorithms 8 (1997), 360–369; R. Sedgewick, Algorithms in C (Reading, Mass.: Addison–Wesley, 1998), §15.4.) Each trie node stores a character, and there are branches to subtries for the cases where a given character is less than, equal to, or greater than the character in the trie. There also is a pointer to a symbol table entry if a symbol ends at the current node. ⟨ Type definitions 25 ⟩ +≡

typedef struct ternary trie struct { unsigned short ch; /∗ the (possibly wyde) character stored here ∗/ struct ternary trie struct ∗left , ∗mid , ∗right ; /∗ downward in the ternary trie ∗/ struct sym tab struct ∗sym; /∗ equivalents of symbols ∗/

} trie node;

57. We allocate trie nodes in chunks of 1000 at a time. ⟨ Subroutines 27 ⟩ +≡

trie node ∗new trie node ((void));

trie node ∗new trie node( )

{ register trie node ∗t = next trie node; if (t ≡ last trie node) {

t = (trie node ∗) calloc(1000, sizeof (trie node));

if (¬t) panic( ␣ ␣ ␣ ␣ ␣ ); last trie node = t + 1000;

}

next trie node = t + 1;

return t; }

§59  ERISCAL  THE SYMBOL TABLE 25

58. ⟨ Global variables 26 ⟩ +≡ trie node ∗trie root ; /∗ root of the trie ∗/ trie node ∗op root ; /∗ root of subtrie for opcodes ∗/ trie node ∗next trie node, ∗last trie node; /∗ allocation control ∗/ trie node ∗cur prefix ; /∗ root of subtrie for unqualified symbols ∗/ 59. The trie search subroutine starts at a given node of the trie and finds a given string in its middle subtrie, inserting new nodes if necessary. The string ends with the first nonletter or nondigit; the location of the terminating character is stored in global variable terminator . #define isletter (c) (isalpha(c) ∨ c ≡ ∨ c ≡ ∨ (unsigned int)(c) > 126) ⟨ Subroutines 27 ⟩ +≡

trie node ∗trie search ((trie node ∗, Char ∗)); Char ∗terminator ; /∗ where the search ended ∗/ trie node ∗trie search(t, s)

trie node ∗t; Char ∗s;

{ register trie node ∗tt = t; register Char ∗p = s; while (1) {

if (¬isletter (∗p) ∧ ¬isdigit (∗p)) {

terminator = p; return tt ; } if (tt mid ) {

tt = tt mid ;

while (∗p ≠ tt ch) {

if (∗p < tt ch) { if (tt left ) tt = tt left ; else {

tt left = new trie node( ); tt = tt left ; goto store new char ; } } else {

if (tt right ) tt = tt right ; else {

tt right = new trie node( ); tt = tt right ; goto store new char ; } }

}

p^{++}; } else {

tt mid = new trie node( ); tt = tt mid ; store new char : tt ch = ∗p^{++}; }

} } 60. Symbol table nodes hold the serial numbers and equivalents of defined symbols. They also hold “fixup information” for undefined symbols; this will allow the loader to correct any previously assembled instructions that refer to such symbols when they are eventually defined.

In the symbol table node for a defined symbol, the link field has one of the special codes or or , and the equiv field holds the defined value. The serial number is a unique identifier for all user-defined symbols.

In the symbol table node for an undefined symbol, the equiv field is ignored. The link field points to the first node of fixup information; that node is, in turn, a symbol table node that might link to other fixups. The serial number in a fixup node is either 0 or 1 or 2, meaning respectively “fixup the wyde pointed to by equiv ” or “fixup the relative address in the YZ field of the instruction pointed to by equiv ” or “fixup the relative address in the XYZ field of the instruction pointed to by equiv .”

#define  (sym node ∗) 1  /∗ code value for wyde equivalents ∗/
#define  (sym node ∗) 2  /∗ code value for register-number equivalents ∗/
#define  (sym node ∗) 3  /∗ code value for not-yet-used equivalents ∗/

#define seg bit 1 /∗ serial code bit for data segment ∗/ #define nyb bit 2 /∗ serial code bit for signed nybble fixup ∗/ #define rel bit 4 /∗ serial code bit for relative fixup ∗/ ⟨ Type definitions 25 ⟩ +≡

typedef struct sym tab struct { int serial ; /∗ serial number of symbol; type number for fixups ∗/ struct sym tab struct ∗link ; /∗ status or link to fixup ∗/ wyde equiv ; /∗ the equivalent value ∗/ wyde seg ; /∗ the segment: 0 for code, 1 for data, if it is ∗/

} sym node;

61. The allocation of new symbol table nodes proceeds in chunks, like the allocation of trie nodes. But in this case we also have the possibility of reusing old fixup nodes that are no longer needed. #define recycle fixup(pp) pp link = sym avail , sym avail = pp ⟨ Subroutines 27 ⟩ +≡

sym node ∗new sym node ((bool));

sym node ∗new sym node(serialize)

bool serialize; /∗ should the new node receive a unique serial number? ∗/ {

register sym node ∗p = sym avail ;

if (p) {

sym avail = p link ; p link = Λ; p serial = 0; p equiv = zero wyde; p seg = zero wyde; } else {

p = next sym node; if (p ≡ last sym node) {

p = (sym node ∗) calloc(1000, sizeof (sym node));

if (¬p) panic( ␣ ␣ ␣ ␣ ␣ ); last sym node = p + 1000;

}

next sym node = p + 1; } if (serialize) p serial = ^{++}serial number ; return p;

} 62. ⟨ Global variables 26 ⟩ +≡

int serial number ; sym node ∗sym root ; /∗ root of the sym ∗/ sym node ∗next sym node, ∗last sym node; /∗ allocation control ∗/ sym node ∗sym avail ; /∗ stack of recycled symbol table nodes ∗/

63. We initialize the trie by inserting all the predefined symbols. Opcodes are given the prefix , to distinguish them from ordinary symbols; this character nicely divides uppercase letters from lowercase letters. ⟨ Initialize everything 33 ⟩ +≡

trie root = new trie node( ); cur prefix = trie root ; op root = new trie node( ); trie root mid = op root ; trie root ch = ; op root ch = ; ⟨ Put the opcodes and pseudo-ops into the trie 66 ⟩; ⟨ Put other predefined symbols into the trie 70 ⟩;

64. Most of the assembly work can be table driven, based on bits that are stored as the “equivalents” of opcode symbols like . #define arg num bits ^{#}3 /∗ number of arguments: 0,1,2,¿=3? ∗/ #define immed bit ^{#}4 /∗ immediate addressing is allowed? ∗/ #define dest bit ^{#}8 /∗ destination modified addressing is allowed? ∗/ #define reg bit ^{#}10 /∗ register addressing is allowed? ∗/ #define indir bit ^{#}20 /∗ indirect addressings is allowed? ∗/ #define no label bit ^{#}40 /∗ should the label be blank? ∗/ #define spec bit ^{#}80 /∗ is this opcode allowed in mode? ∗/ ⟨ Type definitions 25 ⟩ +≡

typedef struct { Char ∗name; /∗ symbolic opcode ∗/ int bits ; /∗ treatment of operands ∗/

} op spec; typedef enum {

= ^{#}01, , , = ^{#}11, , , = ^{#}21, , } pseudo op;

65. ⟨ Global variables 26 ⟩ +≡ op spec op init table[ ] = {

{  ,^{#}003e}, {  ,^{#}e506}, {  ,^{#}e512}, {  ,^{#}f43e}, {  , ( ≪ 8) +^{#}81}, {  ,
( ≪ 8) +^{#}01}, {  , (  ≪ 8) +^{#}c1}, {  , (  ≪ 8) +^{#}83},
{  , (  ≪ 8) +^{#}81}, {  , (  ≪ 8) +^{#}00}, {  , (  ≪ 8) +^{#}00}, {  ,
(  ≪ 8) +^{#}41}, {  , (  ≪ 8) +^{#}c0}};

int op init size; /∗ the number of items in op init table ∗/

66. ⟨ Put the  opcodes and  pseudo-ops into the trie 66 ⟩ ≡

op init size = (sizeof op init table)/sizeof (op spec); for (j = 0; j < op init size; j^{++}) {

tt = trie search(op root , op init table[j].name);

pp = tt sym = new sym node(false);

pp link = ;

pp equiv = op init table[j].bits ;

pp seg = 0; }

This code is used in section 63.

67. ⟨ Local variables 41 ⟩ +≡ register trie node ∗tt ; register sym node ∗pp, ∗qq ;

68. ⟨ Type definitions 25 ⟩ +≡

typedef struct { Char ∗name; wyde h, l;

} predef spec;

69. ⟨ Global variables 26 ⟩ +≡ predef spec predefs [ ] = {{ , 1,^{#}ff00},

{  , 0, 0}, {  , 0, 1}, {  , 0, 2},
{  , 0, 0}, {  , 0, 1}, {  , 0, 2}, {  , 0, 3},
{ , 0, 4},
{  , 0, 0}, {  , 0, 1}, {  , 0, 2}, {  , 0, 3}, {  , 0, 4}, {  , 0, 5},
{  , 0, 6}, {  , 0, 7}, {  , 0, 8}, {  , 0, 9}, {  , 0, 10}};

int predef size;

70. ⟨ Put other predefined symbols into the trie 70 ⟩ ≡ predef size = (sizeof predefs )/sizeof (predef spec); for (j = 0; j < predef size; j^{++}) {

tt = trie search(trie root , predefs [j].name);

pp = tt sym = new sym node(false);

pp link = ;

pp seg = harvard & predefs [j].h, pp equiv = predefs [j].l; }

This code is used in section 63.

71. We place into the trie at the beginning of assembly, so that it will show up as an undefined symbol if the user specifies no starting point. ⟨ Initialize everything 33 ⟩ +≡

trie search(trie root , ) sym = new sym node(true); 72. At the end of assembly we traverse the entire symbol table, visiting each symbol in lexicographic order and transmitting the trie structure to the output file. We detect any undefined future references at this time.

The order of traversal has a simple recursive pattern: To traverse the subtrie rooted at t, we

traverse t left , if the left subtrie is nonempty; visit t sym, if this symbol table entry is present; traverse t mid , if the middle subtrie is nonempty; traverse t right , if the right subtrie is nonempty.

This pattern leads to a compact representation in the file, usually requiring fewer than two wydes per trie node plus the wydes needed to encode the equivalents and serial numbers. Each node of the trie is encoded as a “master wyde” followed by the encodings of the left subtrie, character, equivalent, middle subtrie, and right subtrie. If possible, we put the character ch and part or all of the equivalent into the master wyde. The master wyde is the sum of

#8000, if the left subtrie is nonempty; #4000, if the middle subtrie is nonempty; #2000, if the right subtrie is nonempty; and one of the following values: #0xyz, if the symbol’s equivalent is $0 plus x

and the character code is yz ; #1xyz, if xyz = (s ≪ 10) + ch, where sis the symbol’s segment and the character code at most 10 bits (so most significant bit of x is 0); #1xyz, if the symbol is nondefined and xyz = (1 ≪ 11) + ch, where the

character code at most 10 bits (so most significant bits of x are 10); #1c0z, if the symbol’s equivalent is $0 plus z, and ch is in a

separate wyde (so most significant bits of the second wyde are 110); #1e0z, if the symbol’s segment is z, and ch is in separate wyde;

(so bits of the second wyde are 1110); #1f0z, if the symbol is nondefined, and ch is in separate wyde;

(so bits of the second wyde are 1111);

the character is omitted if the middle subtrie and the equivalent are both empty. Symbol equivalents are followed by the serial number, represented as a wyde.

73. First we prune the trie by removing all predefined symbols that the user did not redefine. ⟨ Subroutines 27 ⟩ +≡

trie node ∗prune ((trie node ∗)); trie node ∗prune(t)

trie node ∗t; {

register int useful = 0; if (t sym) {

if (t sym serial ) useful = 1; else t sym = Λ;

} if (t left ) {

t left = prune(t left );

if (t left ) useful = 1; } if (t mid ) {

t mid = prune(t mid );

if (t mid ) useful = 1; } if (t right ) {

t right = prune(t right ); if (t right ) useful = 1;

} if (useful ) return t; else return Λ;

} 74. Then we output the trie by following the recursive traversal pattern. ⟨ Subroutines 27 ⟩ +≡

void out stab ((trie node ∗)); void out stab(t)

trie node ∗t; {

register int m = 0; /∗ master wyde ∗/ register int s = 1; /∗ defined serial? ∗/ register int c = 1; /∗ out character in separate wyde? ∗/ register sym node ∗pp; if (t ch > ^{#}3ff) m += ^{#}1f00; else m += t ch, c = 0; if (t left ) m += ^{#}8000; if (t mid ) m += ^{#}4000; if (t right ) m += ^{#}2000; if (t sym) {

if (t sym link ≡ )

if (t ch < ^{#}ff) m += ^{#}1000 + t ch + (((t sym equiv ) &^{#}f) ≪ 7), c = 0; else m += ^{#}1c00 + ((t sym equiv ) &^{#}f);

else if (t sym link ≡ )

if (t ch < ^{#}3ff) m += ^{#}1800 + (t sym seg ≪ 10) + t ch, c = 0; else m += ^{#}1e00 + t sym seg ;

else if (t sym link ∨ t sym serial ≡ 1) ⟨ Report an undefined symbol 78 ⟩ else s = 0;

} else s = 0; ero trie wyde(m); if (t left ) out stab(t left ); if (m &^{#}4000 ∨ c ∨ s) ⟨ Visit t and traverse t mid 76 ⟩; if (t right ) out stab(t right );

}

75. We make room for symbols up to 999 bytes long. Strictly speaking, the program should check if this limit is exceeded; but really! ⟨ Global variables 26 ⟩ +≡

Char sym buf [1000]; Char ∗sym ptr ; 76. A global variable called sym buf holds all characters on middle branches to the current trie node; sym ptr is the first currently unused character in sym buf . ⟨ Visit t and traverse t mid 76 ⟩ ≡

{ if (c) ero trie wyde(t ch); ∗sym ptr^{++} = (t ch > ^{#}ff ? : t ch); /∗ Unicode? not yet ∗/ if (s ∧ t sym link ) {

if (listing file) ⟨ Print symbol sym buf and its equivalent 77 ⟩; ero trie wyde(t sym serial );

} if (t mid ) out stab(t mid ); sym ptr^{−};

}

This code is used in section 74.

77. The initial ‘ ’ of each fully qualified symbol is omitted here, since most users of will probably not need the feature. One consequence of this omission is that the one-character symbol ‘ ’ itself, which is allowed by the rules of , is printed as the null string. ⟨ Print symbol sym buf and its equivalent 77 ⟩ ≡

{ ∗sym ptr = ; fprintf (listing file, ␣ ␣ ␣ , sym buf + 1); pp = t sym;

if (pp link ≡  ) fprintf (listing file,  , pp seg , pp equiv );
else if (pp link ≡  ) fprintf (listing file,  , pp equiv );

else fprintf (listing file, ); fprintf (listing file, ␣ , pp serial );

}

This code is used in section 76.

78. ⟨ Report an undefined symbol 78 ⟩ ≡

{ ∗sym ptr = (t ch > ^{#}ff ? : t ch); /∗ Unicode? not yet ∗/ ∗(sym ptr + 1) = ; fprintf (stderr , ␣ ␣ , sym buf + 1); err count^{++}, s = 0; if (t ch < ^{#}3ff) m += ^{#}1800 + t ch, c = 1; else m += ^{#}1fff;

}

This code is used in section 74.

79. ⟨ Check and output the trie 79 ⟩ ≡ op root mid = Λ; /∗ annihilate all the opcodes ∗/ prune(trie root ); sym ptr = sym buf ; if (listing file) fprintf (listing file, ␣ ); ero wyde((ero ≪ 4) + lop stab); out stab(trie root ); ero lopp(lop end , ero ptr );

This code is used in section 143.

§80  ERISCAL  EXPRESSIONS 33

80. Expressions. The most intricate part of the assembly process is the task of scanning and evaluating expressions in the operand field. Fortunately, ’s expressions have a simple structure that can be handled easily with a stack-based approach.

Two stacks hold pending data as the operand field is scanned and evaluated. The op stack contains operators that have not yet been performed; the val stack contains values that have not yet been used. After an entire operand list has been scanned, the op stack will be empty and the val stack will hold the operand values needed to assemble the current instruction.

81. Entries on op stack have one of the constant values defined here, and they have one of the precedence levels defined here.

Entries on val stack have equiv , link , and status fields; the link points to a trie node if the expression is a symbol that has not yet been subjected to any operations. ⟨ Type definitions 25 ⟩ +≡

typedef enum {

indirectize, relativize, negate, serialize, complement , registerize, plus , minus , times , over , frac, mod , shl , shr , and , or , xor , outer lp, outer rp, inner lp, inner rp

} stack op; typedef enum {

zero, weak , strong , unary } prec; typedef enum {

pure, reg val , undefined , rel undefined ,

ind pure, ind reg val , ind undefined , ind rel undefined } stat; typedef struct {

wyde equiv ; /∗ current value ∗/

trie node ∗link ; /∗ trie reference for symbol ∗/

stat status ; /∗ pure, reg val , undefined , ... ∗/ } val node;

82. #define top op op stack [op ptr − 1] /∗ top entry on the operator stack ∗/ #define top val val stack [val ptr − 1] /∗ top entry on the value stack ∗/ #define next val val stack [val ptr − 2] /∗ next-to-top entry of the value stack ∗/ ⟨ Global variables 26 ⟩ +≡

stack op ∗op stack ; /∗ stack for pending operators ∗/ int op ptr ; /∗ number of items on op stack ∗/ val node ∗val stack ; /∗ stack for pending operands ∗/ int val ptr ; /∗ number of items on val stack ∗/ prec precedence[ ] = {unary , unary , unary , unary , unary , unary ,

weak , weak , strong , strong , strong , strong , strong , strong , strong , weak , weak , zero, zero, zero, zero}; /∗ precedences of the respective stack op values ∗/

stack op rt op; /∗ newly scanned operator ∗/ wyde acc; /∗ temporary accumulator ∗/

34  EXPRESSIONS  ERISCAL §84

83. ⟨ Initialize everything 33 ⟩ +≡ op stack = (stack op ∗) calloc(buf size, sizeof (stack op)); val stack = (val node ∗) calloc(buf size, sizeof (val node)); if (¬op stack ∨ ¬val stack ) panic( ␣ ␣ ␣ ␣ ); 84. The operand field of an instruction will have been copied into a separate Char array called operand list when we reach this part of the program. ⟨ Scan the operand field 84 ⟩ ≡

p = operand list ; val ptr = 0; /∗ val stack is empty ∗/ op stack [0] = outer lp, op ptr = 1; /∗ op stack contains an “outer left parenthesis” ∗/ while (1) {

⟨ Scan opening tokens until putting something on val stack 85 ⟩; scan close: ⟨ Scan a binary operator or closing token, rt op 96 ⟩;

while (precedence[top op] ≥ precedence[rt op]) ⟨ Perform the top operation on op stack 97 ⟩; hold op: op stack [op ptr^{++}] = rt op; }

operands done:

This code is used in section 101.

85. A comment that follows an empty operand list needs to be detected here. ⟨ Scan opening tokens until putting something on val stack 85 ⟩ ≡ scan open: if (isletter (∗p)) ⟨ Scan a symbol 86 ⟩

else if (isdigit (∗p)) { if (∗(p + 1) ≡ ) ⟨ Scan a forward local 87 ⟩ else if (∗(p + 1) ≡ ) ⟨ Scan a backward local 88 ⟩ else ⟨ Scan a decimal constant 93 ⟩;

} else switch (∗p^{++}) { case : ⟨ Scan a hexadecimal constant 94 ⟩; break; case : ⟨ Scan a character constant 91 ⟩; break; case : ⟨ Scan a string constant 92 ⟩; break; case : ⟨ Scan the current location 95 ⟩; break; case : op stack [op ptr^{++}] = indirectize; goto scan open; case : op stack [op ptr^{++}] = relativize; goto scan open; case : op stack [op ptr^{++}] = negate; goto scan open; case : op stack [op ptr^{++}] = serialize; goto scan open; case : op stack [op ptr^{++}] = complement ; goto scan open; case : op stack [op ptr^{++}] = registerize; goto scan open; case : op stack [op ptr^{++}] = inner lp; goto scan open; default:

if (p ≡ operand list + 1) { /∗ treat operand list as empty ∗/ operand list [0] = , operand list [1] = , p = operand list ; goto scan open;

}

if (∗(p − 1)) derr (  ␣     ␣  ␣         ␣  ,
∗(p − 1))derr (  ␣     ␣     ␣         ␣  , ∗(p − 2))

}

This code is used in section 84.

86. ⟨ Scan a symbol 86 ⟩ ≡

{ if (∗p ≡ ) tt = trie search(trie root , p + 1); else tt = trie search(cur prefix , p); p = terminator ;

symbol found : val ptr^{++}; pp = tt sym; if (¬pp) pp = tt sym = new sym node(true); top val .link = tt , top val .equiv = pp equiv ;

if (pp link ≡  ) pp link =  ;
top val .status = (pp link ≡  ? pure : pp link ≡  ? reg val : undefined );

}

This code is used in section 85.

87. ⟨ Scan a forward local 87 ⟩ ≡

{

tt = &forward local host [∗p − ]; p += 2; goto symbol found ; }

This code is used in section 85.

88. ⟨ Scan a backward local 88 ⟩ ≡

{

tt = &backward local host [∗p − ]; p += 2; goto symbol found ; }

This code is used in section 85.

89. Statically allocated variables forward local host [j] and backward local host [j] masquerade as nodes of the trie. ⟨ Global variables 26 ⟩ +≡

trie node forward local host [10], backward local host [10]; sym node forward local [10], backward local [10];

90. Initially , , …, are defined to be zero. ⟨ Initialize everything 33 ⟩ +≡

for (j = 0; j < 10; j^{++}) { forward local host [j].sym = &forward local [j]; backward local host [j].sym = &backward local [j]; backward local [j].link = ;

}

91. We have already checked to make sure that the character constant is legal. ⟨ Scan a character constant 91 ⟩ ≡

acc = ∗p; p += 2; goto constant found ;

This code is used in section 85.

92. ⟨ Scan a string constant 92 ⟩ ≡ acc = ∗p; if (∗p ≡ ) {

p^{++};

acc = 0;

  err (  ␣      ␣  ␣       ␣  ␣  )

} else if (∗(p + 1) ≡ ) p += 2; else ∗p = , ∗^{−}p = ; goto constant found ;

This code is used in section 85.

93. ⟨ Scan a decimal constant 93 ⟩ ≡ acc = ∗p − ; for (p^{++}; isdigit (∗p); p^{++}) {

acc += (acc ≪ 2);

acc = (acc ≪ 1) + (∗p − ); }

constant found : val ptr^{++}; top val .link = Λ; top val .equiv = acc; top val .status = pure;

This code is used in section 85.

94. ⟨ Scan a hexadecimal constant 94 ⟩ ≡ if (¬isxdigit (∗p)) err ( ␣ ␣ ); acc = 0; for ( ; isxdigit (∗p); p^{++}) {

acc = (acc ≪ 4) + (∗p − );

if (∗p ≥ ) acc +=  −  + 10;
else if (∗p ≥ ) acc +=  −  + 10;

} goto constant found ;

This code is used in section 85.

95. ⟨ Scan the current location 95 ⟩ ≡ acc = cur loc; goto constant found ;

This code is used in section 85.

96. ⟨ Scan a binary operator or closing token, rt op 96 ⟩ ≡ switch (∗p^{++}) { case : rt op = plus ; break; case : rt op = minus ; break; case : rt op = times ; break; case : if (∗p ≠ ) rt op = over ;

else p^{++}, rt op = frac; break; case : rt op = mod ; break; case : rt op = shl ; goto sh check ; case : rt op = shr ; sh check : p^{++}; if (∗(p − 1) ≡ ∗(p − 2)) break;

derr ( ␣ ␣ ␣ , ∗(p − 2)); case : rt op = and ; break; case : rt op = or ; break; case : rt op = xor ; break; case : rt op = inner rp; break;

case  : case  : rt op = outer rp; break;
default: derr (  ␣     ␣  ␣  , ∗(p − 1));

}

This code is used in section 84.

97. ⟨ Perform the top operation on op stack 97 ⟩ ≡ switch (op stack [^{−}op ptr ]) { case inner lp: if (rt op ≡ inner rp) goto scan close;

err ( ␣ ␣ ); break; case outer lp: if (rt op ≡ outer rp) {

if ((top val .status ≡ reg val ∨ top val .status ≡ ind reg val ) ∧

top val .equiv > ^{#}f) {

      err (  ␣      ␣    ␣      ␣    ␣  ␣       ␣   ␣ );

top val .equiv &= ^{#}f; } if (¬∗(p − 1)) goto operands done; else rt op = outer lp; goto hold op; /∗ comma ∗/

} else { op ptr^{++}; err ( ␣ ␣ ); goto scan close;

} ⟨ Cases for unary operators 99 ⟩ ⟨ Cases for binary operators 98 ⟩ }

This code is used in section 84.

98. Now we come to the part where equivalents are changed by unary or binary operators found in the expression being scanned.

The most typical operator, and in some ways the fussiest one to deal with, is binary addition. Once we’ve written the code for this case, the other cases almost take care of themselves. ⟨ Cases for binary operators 98 ⟩ ≡

case plus : if (top val .status ≥ ind pure) err (  ␣   ␣  ␣        ␣  );
if (next val .status ≥ ind pure) err (  ␣   ␣  ␣  ␣        ␣  );
if (top val .status ≥ undefined ) err (  ␣   ␣  ␣         ␣  );
if (next val .status ≥ undefined ) err (  ␣   ␣  ␣  ␣         ␣  );
if (top val .status ≡ reg val ∧ next val .status ≡ reg val ) err (  ␣   ␣   ␣        ␣  );

next val .equiv += top val .equiv ; fin bin: next val .status = (top val .status ≡ next val .status ? pure : reg val );

val ptr^{−}; delink : top val .link = Λ; break;

See also section 100. This code is used in section 97.

99. #define unary check (verb) if (top val .status ≠ pure) derr (  ␣  ␣    ␣      ␣  , verb)

⟨ Cases for unary operators 99 ⟩ ≡ case indirectize: if (top val .status < ind pure) top val .status += ind pure − pure; goto delink ; case relativize: if (¬(top val .status ≡ pure ∨ top val .status ≡ undefined ))

    err (  ␣          ␣     ␣    ␣      ␣   ␣       ␣  );

if (top val .status ≡ pure) top val .equiv −= cur loc;

else top val .status = rel undefined ; goto delink ; case negate: unary check ( );

top val .equiv = zero wyde − top val .equiv ; goto delink ; case complement : unary check ( );

top val .equiv = ∼top val .equiv ;

goto delink ; case registerize: unary check ( );

top val .status = reg val ; goto delink ; case serialize: if (¬top val .link ) err ( ␣ ␣ ␣ ␣ ␣ ␣ );

top val .equiv = top val .link sym serial ;

top val .status = pure; goto delink ;

This code is used in section 97.

100. #define binary check (verb)

if (top val .status ≠ pure ∨ next val .status ≠ pure) derr ( ␣ ␣ ␣ ␣ , verb)

⟨ Cases for binary operators 98 ⟩ +≡

case minus : if (top val .status ≥ ind pure) err (  ␣        ␣  ␣        ␣  );
if (top val .status ≥ undefined ) err (  ␣        ␣  ␣         ␣  );
if (next val .status ≥ ind pure) err (  ␣        ␣     ␣  ␣        ␣  );
if (next val .status ≥ undefined ) err (  ␣        ␣     ␣  ␣         ␣  );

if (top val .status ≡ reg val ∧ next val .status ≠ reg val )

  err (  ␣        ␣        ␣      ␣    ␣     ␣  );

next val .equiv −= top val .equiv ; goto fin bin; case times : binary check ( );

next val .equiv = wmult (next val .equiv , top val .equiv ); goto fin bin; case over : case mod : binary check ( );

if (top val .equiv ≡ 0) err ( ␣ ␣ ); next val .equiv = wdiv (zero wyde, next val .equiv , top val .equiv ); if (op stack [op ptr ] ≡ mod ) next val .equiv = aux ; goto fin bin;

case frac: binary check ( ␣ ␣ ␣ ); if (next val .equiv ≥ top val .equiv ) err ( ␣ ); next val .equiv = wdiv (next val .equiv , zero wyde, top val .equiv ); goto fin bin;

case shl : case shr : binary check ( ␣ ␣ ␣ ␣ ); if (top val .equiv > 15) next val .equiv = zero wyde; else if (op stack [op ptr ] ≡ shl ) next val .equiv ≪= top val .equiv ; else next val .equiv ≫= top val .equiv ; goto fin bin;

case and : binary check ( ␣ ␣ ␣ ); next val .equiv &= top val .equiv ; goto fin bin;

case or : binary check ( ␣ ␣ ␣ ); next val .equiv |= top val .equiv ; goto fin bin;

40  ASSEMBLING AN INSTRUCTION  ERISCAL §101

case xor : binary check ( ␣ ␣ ␣ ); next val .equiv ⊕= top val .equiv ; goto fin bin; 101. Assembling an instruction. Now let’s move up from the expression level to the instruction level. We get to this part of the program at the beginning of a line, or after a semicolon at the end of an instruction earlier on the current line. Our current position in the buffer is the value of buf ptr . ⟨ Process the next instruction or comment 101 ⟩ ≡

p = buf ptr ; buf ptr = ; ⟨ Scan the label field; goto bypass if there is none 102 ⟩; ⟨ Scan the opcode field; goto bypass if there is none 103 ⟩; ⟨ Copy the operand field 105 ⟩; buf ptr = p; if (spec mode ∧ ¬(op bits & spec bit )) derr ( ␣ ␣ ␣ ␣ ␣ , op field ); if ((op bits & no label bit ) ∧ lab field [0]) {

derr ( ␣ ␣ ␣ ␣ ␣ ␣ , op field ); lab field [0] = ;

} ⟨ Scan the operand field 84 ⟩; if (opcode ≡ ) ⟨ Allocate a global register 106 ⟩; if (lab field [0]) ⟨ Define the label 107 ⟩; ⟨ Do the operation 113 ⟩;

bypass :

This code is used in section 137.

102. ⟨ Scan the label field; goto bypass if there is none 102 ⟩ ≡ if (¬∗p) goto bypass ; q = lab field ; if (¬isspace(∗p)) {

if (¬isdigit (∗p) ∧ ¬isletter (∗p)) goto bypass ; /∗ comment ∗/

for (∗q^{++} = ∗p^{++}; isdigit (∗p) ∨ isletter (∗p); p^{++}, q^{++}) ∗q = ∗p;

if (∗p ∧ ¬isspace(∗p)) derr ( ␣ ␣ ␣ ␣ , ∗p); } ∗q = ; if (isdigit (lab field [0]) ∧ (lab field [1] ≠ ∨ lab field [2]))

derr ( ␣ ␣ ␣ , lab field ); for (p^{++}; isspace(∗p); p^{++}) ;

This code is used in section 101.

103. We copy the opcode field to a special buffer because we might want to refer to the symbolic opcode in error messages. ⟨ Scan the opcode field; goto bypass if there is none 103 ⟩ ≡

q = op field ; while (isletter (∗p) ∨ isdigit (∗p)) ∗q^{++} = ∗p^{++}; ∗q = ; if (¬isspace(∗p) ∧ ∗p ∧ op field [0]) derr ( ␣ ␣ ␣ ␣ , ∗p); pp = trie search(op root , op field ) sym; if (¬pp) {

if (op field [0]) derr (  ␣         ␣     ␣  , op field );
if (lab field [0]) derr (  ␣       ␣     ␣     ␣    ␣  ␣  , lab field );

goto bypass ; } opcode = (pp equiv ≫ 8) &^{#}ff, op bits = pp equiv &^{#}ff; while (isspace(∗p)) p^{++};

This code is used in section 101.

§104  ERISCAL  ASSEMBLING AN INSTRUCTION 41

104. ⟨ Global variables 26 ⟩ +≡ wyde opcode; /∗ numeric code for operation or pseudo-op ∗/ wyde op bits ; /∗ flags describing an operator’s special characteristics ∗/ wyde arg num; /∗ number of arguments: 0,1,2,¿=3 ∗/

105. We copy the operand field to a special buffer so that we can change string constants while scanning them later. ⟨ Copy the operand field 105 ⟩ ≡

q = operand list ; while (∗p) {

if (∗p ≡ ) break;

if (∗p ≡ ) { ∗q^{++} = ∗p^{++}; if (¬∗p) err ( ␣ ␣ ); ∗q^{++} = ∗p^{++}; if (∗p ≠ ) err ( ␣ ␣ );

} else if (∗p ≡ ) { for (∗q^{++} = ∗p^{++}; ∗p ∧ ∗p ≠ ; p^{++}, q^{++}) ∗q = ∗p; if (¬∗p) err ( ␣ ␣ );

}

∗q^{++} = ∗p^{++};

if (isspace(∗p)) break; } while (isspace(∗p)) p^{++}; if (∗p ≡ ) p^{++}; else p = ; /∗ if not followed by semicolon, rest of the line is a comment ∗/ if (q ≡ operand list ) ∗q^{++} = ; /∗ change empty operand field to ‘ ’ ∗/ ∗q = ;

This code is used in section 101.

106. ⟨ Allocate a global register 106 ⟩ ≡ { if (greg ≡ 15) err ( ␣ ␣ ␣ ) else {

++greg ; greg val [greg ] = val stack [0].equiv ;

} }

This code is used in section 101.

107. If the label is, say , we will already have used the old value of when evaluating the operands. Furthermore, an operand of will have been treated as undefined, which it still is.

Symbols can be defined more than once, but only if each definition gives them the same equivalent value. A warning message is given when a predefined symbol is being redefined, if its predefined value has already

been used. ⟨ Define the label 107 ⟩ ≡

{ sym node ∗new link = ; acc = cur loc; if (opcode ≡ ) {

cur loc = val stack [0].equiv ;

if (val stack [0].status ≡ reg val ) new link = ; } else if (opcode ≡ ) cur loc = greg , new link = ; ⟨ Find the symbol table node, pp 109 ⟩; if (pp link ≡ ∨ pp link ≡ ) {

if (pp seg ≠ cur seg ∨ pp equiv ≠ cur loc ∨ pp link ≠ new link ) { if (pp serial ) derr ( ␣ ␣ ␣ ␣ , lab field ); pp serial = ^{++}serial number ; derr ( ␣ ␣ ␣ ␣ , lab field );

} } else if (pp link ≡ ) pp serial = ^{++}serial number ; else if (pp link ) {

if (new link ≡ ) err ( ␣ ␣ ␣ ␣ ␣ ␣ ); do ⟨ Fix prior references to this label 110 ⟩ while (pp link );

} if (isdigit (lab field [0])) pp = &backward local [lab field [0] − ]; pp equiv = cur loc; pp seg = cur seg ; pp link = new link ; ⟨ Fix references that might be in the val stack 108 ⟩; if (listing file ∧ (opcode ≡ ∨ opcode ≡ )) ⟨ Make special listing to show the label equivalent 112 ⟩; cur loc = acc;

}

This code is used in section 101.

108. ⟨ Fix references that might be in the val stack 108 ⟩ ≡

if (¬isdigit (lab field [0]))

for (j = 0; j < val ptr ; j^{++})

if (val stack [j].status ≡ undefined ∧ val stack [j].link sym ≡ pp) { val stack [j].status = (new link ≡ ? reg val : pure); val stack [j].equiv = cur loc;

}

This code is used in section 107.

109. ⟨ Find the symbol table node, pp 109 ⟩ ≡ if (isdigit (lab field [0])) pp = &forward local [lab field [0] − ]; else {

if (lab field [0] ≡ ) tt = trie search(trie root , lab field + 1); else tt = trie search(cur prefix , lab field ); pp = tt sym; if (¬pp) pp = tt sym = new sym node(true);

}

This code is used in section 107.

110. ⟨ Fix prior references to this label 110 ⟩ ≡

{ qq = pp link ; pp link = qq link ; ⟨ Fix a future reference 111 ⟩ recycle fixup(qq );

}

This code is used in section 107.

111. ⟨ Fix a future reference 111 ⟩ ≡ { wyde w; int s; s = qq serial ; if (s & seg bit ≠ cur seg ) /∗ different segment ∗/ dderr ( ␣ ␣ ␣ ␣ ␣ ␣ , qq seg , qq equiv ) else {

⟨ Make sure cur loc and ero cur loc refer to the same wyde 55 ⟩ if (s & rel bit ) {

k = 0; w = cur loc − qq equiv ; if (s & nyb bit ) {

if (¬(w &^{#}8000))

if (w < ^{#}8) ero lopp(lop fixr , w); else k = 1;

else if (w ≥ ^{#}fff8) ero lopp(lop fixr , w &^{#}f); else k = 1;

} else ero lopp(lop fixr , w); if (k) dderr ( ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ , qq seg , qq equiv );

} else {

k = 0; w = qq equiv ; if (s & nyb bit ) {

if (¬(w &^{#}8000))

if (w < ^{#}8) ero lopp(lop fixw , w); else k = 1;

else if (w ≥ ^{#}fff8) ero lopp(lop fixw , w &^{#}f); else k = 1;

} else ero lopp(lop fixr , w); if (k) dderr ( ␣ ␣ ␣ ␣ ␣ ␣ ␣ , qq seg , qq equiv );

} } }

This code is used in section 110.

112. ⟨ Make special listing to show the label equivalent 112 ⟩ ≡

if (new link ≡ ) { fprintf (listing file, , cur loc); flush listing line( ␣ );

} else { fprintf (listing file, , cur loc &^{#}f); flush listing line( ␣␣␣␣␣␣ );

}

This code is used in section 107.

113. ⟨ Do the operation 113 ⟩ ≡ future bits = 0; arg num = op bits & arg num bits ; if (arg num ≡ 3) ⟨ Do a many-operand operation 114 ⟩ else switch (arg num) {

case 0: if (val ptr > 1) derr ( ␣ ␣ ␣ ␣ , op field ); ⟨ Do a one-operand operation 133 ⟩; break;

case 1: if (val ptr > 1) derr ( ␣ ␣ ␣ ␣ , op field ); ⟨ Do a one-operand operation 133 ⟩; break;

case 2: if (val ptr ≠ 2) derr ( ␣ ␣ ␣ ␣ ␣ , op field ) ⟨ Do a two-operand operation 117 ⟩; break;

default: derr ( ␣ ␣ ␣ ␣ ␣ , op field ); }

This code is used in section 101.

114. The many-operand operator is . ⟨ Do a many-operand operation 114 ⟩ ≡

for (j = 0; j < val ptr ; j^{++}) { ⟨ Deal with cases where val stack [j] is impure 115 ⟩; if (val stack [j].status ≡ undefined ∨ val stack [j].status ≡ rel undefined ) assemble(0,^{#}f0); else assemble(val stack [j].equiv , 0);

}

This code is used in section 113.

115. ⟨ Deal with cases where val stack [j] is impure 115 ⟩ ≡

if (val stack [j].status ≥ ind pure) {

err (  ␣      ␣     ␣  ␣ ␣  )

val stack [j].status −= ind pure; } if (val stack [j].status ≡ reg val ) err ( ␣ ␣ ␣ ␣ ␣ ) else if (val stack [j].status ≡ undefined ) {

pp = val stack [j].link sym; qq = new sym node(false); qq link = pp link ; pp link = qq ; qq serial = cur seg ; qq equiv = cur loc;

} else if (val stack [j].status ≡ rel undefined ) {

pp = val stack [j].link sym; qq = new sym node(false); qq link = pp link ; pp link = qq ; qq serial = cur seg + rel bit ; qq equiv = cur loc;

}

This code is used in section 114.

116. Individual fields of an instruction are placed into global variables x, y, z. ⟨ Global variables 26 ⟩ +≡

wyde x, y, z; /∗ pieces for assembly ∗/ int future bits ; /∗ places where there are future references ∗/ char addr mode; /∗ places where there are the addressing mode bits ∗/ 117. ⟨ Do a two-operand operation 117 ⟩ ≡

z = 0; /∗ Presuppose one-wyde code ∗/ ⟨ Find the addressing mode 125 ⟩; switch (addr mode) { case 0: ⟨ Check if this case is allowed by this instruction 118 ⟩

⟨ Handle exceptions for 0 addr mode 120 ⟩

⟨ Do the SRC field, it have to be a constant 123 ⟩;

break; case 1: ⟨ Check if this case is allowed by this instruction 118 ⟩

⟨ Change the X and Y fields 119 ⟩

⟨ Do the SRC field, it have to be a constant 123 ⟩

break; case 2: ⟨ Check if this case is allowed by this instruction 118 ⟩

⟨ Handle exceptions for 2 addr mode 121 ⟩

⟨ Do the SRC field, it have to be a register 124 ⟩

break; case 3: ⟨ Check if this case is allowed by this instruction 118 ⟩

⟨ Handle exceptions for 3 addr mode 122 ⟩

⟨ Do the SRC field, it is indirect 126 ⟩

break; }

assemble DST : ⟨ Do the DST field 127 ⟩; assemble inst : assemble((x ≪ 12) + ((opcode + addr mode) ≪ 4) + y, future bits );

if (z) ⟨ Do the second wyde 130 ⟩;

This code is used in section 113.

118. ⟨ Check if this case is allowed by this instruction 118 ⟩ ≡

if (¬((1 ≪ (2 + addr mode)) & op bits ))

dderr (  ␣    ␣     ␣  ␣   ␣       ␣  ␣  , addr mode, op field );

This code is used in section 117.

119. ⟨ Change the X and Y fields 119 ⟩ ≡ acc = val stack [1].equiv ; val stack [1].equiv = val stack [0].equiv ; val stack [0].equiv = acc; acc = val stack [1].status ; val stack [1].status = val stack [0].status ; val stack [0].status = acc;

This code is used in section 117.

120. ⟨ Handle exceptions for 0 addr mode 120 ⟩ ≡

if (opcode ≡ ^{#}e5) { /∗ TRAP ∗/

if (val stack [0].status ≠ reg val ∨ val stack [0].equiv ≡ 0)

derr (  ␣     ␣  ␣    ␣      ␣  ␣ ␣       ␣  , op field );
if (val stack [1].status ≠ pure) derr (  ␣     ␣  ␣    ␣      ␣  ␣ ␣  , op field );
if (val stack [1].equiv > ^{#}f) err (  ␣     ␣       ␣    ␣  ␣   ␣        ␣  );

y = val stack [1].equiv &^{#}f; break; }

This code is used in section 117.

121. ⟨ Handle exceptions for 2 addr mode 121 ⟩ ≡

if (opcode ≡ ^{#}e5) { /∗ RESUME ∗/

if (val stack [0].status ≠ reg val ∨ val stack [0].equiv )

derr (  ␣     ␣  ␣    ␣      ␣  ␣   ␣    ␣  , op field );
if (val stack [1].equiv > ^{#}f) err (  ␣     ␣       ␣    ␣  ␣   ␣        ␣  );

y = val stack [1].equiv &^{#}f, x = 0, addr mode = 0; goto assemble inst ; } else if (opcode ≡ ^{#}c5) /∗ MOR ∗/

addr mode = 0; else if (opcode ≡ ^{#}e6) /∗ SADD ∗/

addr mode = 0;

This code is used in section 117.

122. ⟨ Handle exceptions for 3 addr mode 122 ⟩ ≡

{

if (opcode ≡ ^{#}d5) { /∗ PUSH ∗/

if (val stack [1].status ≠ reg val ) derr (  ␣     ␣  ␣    ␣      ␣  ␣ ␣  , op field );
if (val stack [1].equiv > ^{#}f) err (  ␣     ␣       ␣    ␣  ␣   ␣        ␣  );

y = val stack [1].equiv &^{#}f, addr mode = 0; goto assemble DST ; } else if (opcode ≡ ^{#}e7) /∗ POP ∗/

addr mode = 0; }

This code is used in section 117.

123. ⟨ Do the SRC field, it have to be a constant 123 ⟩ ≡ { if (val stack [1].status ≡ undefined ) ⟨ Assemble SRC as a future reference 128 ⟩ else if (val stack [1].status ≡ rel undefined ) ⟨ Assemble SRC as a relative future reference 129 ⟩ else if (val stack [1].status ≡ reg val ) derr ( ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ,

op field ) else {

if (val stack [1].equiv ≤ ^{#}fff8 ∧ val stack [1].equiv > ^{#}7)

    err (  ␣     ␣       ␣    ␣  ␣   ␣      ␣  );

y = val stack [1].equiv &^{#}f; } }

This code is used in section 117.

124. ⟨ Do the SRC field, it have to be a register 124 ⟩ ≡

if (val stack [1].status ≠ reg val )

derr (  ␣     ␣  ␣    ␣      ␣  ␣ ␣        ␣  , op field );
if (val stack [1].equiv > ^{#}f) err (  ␣     ␣       ␣    ␣  ␣   ␣        ␣  );

y = val stack [1].equiv &^{#}f;

This code is used in sections 117 and 126.

125. ⟨ Find the addressing mode 125 ⟩ ≡ if (val stack [1].status ≥ ind pure) addr mode = 3; else if (val stack [1].status ≡ reg val )

if (val stack [0].status ≡ reg val ) addr mode = 2; else addr mode = 1;

else addr mode = 0;

This code is used in section 117.

126. ⟨ Do the SRC field, it is indirect 126 ⟩ ≡ val stack [1].status −= ind pure; if (val stack [1].status ≡ reg val ) {

if (¬val stack [1].equiv ) derr ( ␣ ␣ ␣ ␣ ␣ ␣ ␣ , op field ); ⟨ Do the SRC field, it have to be a register 124 ⟩;

} else y = 0, z = 1;

This code is used in section 117.

127. ⟨ Do the DST field 127 ⟩ ≡

if (val stack [0].status ≠ reg val )

derr (  ␣     ␣  ␣    ␣      ␣  ␣ ␣        ␣  , op field );
if (val stack [0].equiv > ^{#}f) err (  ␣     ␣       ␣    ␣  ␣   ␣  );

x = val stack [0].equiv &^{#}f;

This code is used in section 117.

128. ⟨ Assemble SRC as a future reference 128 ⟩ ≡

{ pp = val stack [0].link sym; qq = new sym node(false); qq link = pp link ; pp link = qq ; qq serial = cur seg + nyb bit ; qq equiv = cur loc; y = 0; future bits = ^{#}80; goto assemble DST ;

}

This code is used in section 123.

129. ⟨ Assemble SRC as a relative future reference 129 ⟩ ≡

{ pp = val stack [0].link sym; qq = new sym node(false); qq link = pp link ; pp link = qq ; qq serial = cur seg + nyb bit + rel bit ; qq equiv = cur loc; y = 0; future bits = ^{#}80; goto assemble DST ;

}

This code is used in section 123.

130. ⟨ Do the second wyde 130 ⟩ ≡ if (val stack [1].status ≡ pure) assemble(val stack [1].equiv , 0); else if (val stack [1].status ≡ undefined ) ⟨ Assemble YZ as a future reference 131 ⟩ else /∗ val stack [1].status ≡ rel undefined ∗/

⟨ Assemble YZ as a relative future reference 132 ⟩;

This code is used in section 117.

131. ⟨ Assemble YZ as a future reference 131 ⟩ ≡

{ pp = val stack [1].link sym; qq = new sym node(false); qq link = pp link ; pp link = qq ; qq serial = cur seg ; qq equiv = cur loc; assemble(0,^{#}f0);

}

This code is used in section 130.

132. ⟨ Assemble YZ as a relative future reference 132 ⟩ ≡

{ pp = val stack [1].link sym; qq = new sym node(false); qq link = pp link ; pp link = qq ; qq serial = cur seg + rel bit ; qq equiv = cur loc; assemble(0,^{#}f0);

}

This code is used in section 130.

133. ⟨ Do a one-operand operation 133 ⟩ ≡ switch (opcode) { /∗ Pseudo operations ∗/ case :

if (harvard ∧ cur seg ) { cur data loc = cur loc; cur loc = cur code loc; cur seg = 0;

} goto bypass ; case :

if (harvard ∧ ¬cur seg ) { cur code loc = cur loc; cur loc = cur data loc; cur seg = harvard ;

} goto bypass ; case : cur loc = val stack [0].equiv ; case : goto bypass ; case : if (¬val stack [0].link ) err ( ␣ ␣ ␣ );

cur prefix = val stack [0].link ; goto bypass ; case : if (listing file) ⟨ Make listing for 135 ⟩;

goto bypass ; case : if (val stack [0].equiv > ^{#}ffff) err ( ␣ ␣ ␣ ␣ ␣ ␣ ␣ );

ero loc( ); ero sync( );

ero lopp(lop spec, val stack [0].equiv );

spec mode = true; spec mode loc = 0; goto bypass ; case : spec mode = false; goto bypass ; }

This code is used in section 113.

134. ⟨ Global variables 26 ⟩ +≡ wyde greg val [256]; /∗ initial values of global registers ∗/

135. ⟨ Make listing for 135 ⟩ ≡ fprintf (listing file, , greg , val stack [0].equiv ); flush listing line( ␣ );

This code is used in section 133.

§136  ERISCAL  RUNNING THE PROGRAM 51

136. Running the program. On a UNIX-like system, the command

will assemble the  program in file  , writing any error messages on the standard

error file. (Nothing is written to the standard output.) The options, which may appear in any order, are:

• Send the output to a binary file called . If no specification is given, the object file name is obtained from the input file name by changing the final letter from ‘ ’ to ‘ ’,

or by appending ‘  ’ if  doesn’t end with .
•  Output a listing of the assembled input and output to a text file called  .

• Allow Harward type architecture, assembling data to a separate space from instructions.

•  Allow up to  characters per line of input.

137. Here, finally, is the overall structure of this program. #include #include #include #include #include

⟨ Preprocessor definitions 32 ⟩ ⟨ Type definitions 25 ⟩ ⟨ Global variables 26 ⟩ ⟨ Subroutines 27 ⟩ int main(argc, argv )

int argc; char ∗argv [ ]; {

register int j, k; /∗ all-purpose integers ∗/ ⟨ Local variables 41 ⟩; ⟨ Process the command line 138 ⟩; ⟨ Initialize everything 33 ⟩; while (1) {

⟨ Get the next line of input text, or break if the input has ended 35 ⟩; while (1) {

⟨ Process the next instruction or comment 101 ⟩; if (¬∗buf ptr ) break;

}

if (listing file) { if (listing bits ) listing clear ( ); else if (¬line listed ) flush listing line( ␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣␣ );

} } ⟨ Finish the assembly 143 ⟩;

}

52  RUNNING THE PROGRAM  ERISCAL §138

138. ⟨ Process the command line 138 ⟩ ≡

for (j = 1; j < argc − 1 ∧ argv [j][0] ≡ ; j^{++})

if (¬argv [j][2]) { if (argv [j][1] ≡ ) harvard = true; else if (argv [j][1] ≡ ) j^{++}, strcpy (obj file name, argv [j]); else if (argv [j][1] ≡ ) j^{++}, strcpy (listing name, argv [j]); else if (argv [j][1] ≡ ∧ sscanf (argv [j + 1], , &buf size) ≡ 1) j^{++}; else break;

} else if (argv [j][1] ≠ ∨ sscanf (argv [j] + 2, , &buf size) ≠ 1) break; if (j ≠ argc − 1) {

fprintf (stderr ,  ␣  ␣  ␣  , argv [0],

      ␣           ␣      ␣    ␣   ␣  );

exit (−1); } src file name = argv [j];

This code is used in section 137.

139. ⟨ Open the files 139 ⟩ ≡ src file = fopen(src file name, ); if (¬src file) dpanic( ␣ ␣ ␣ ␣ ␣ , src file name); if (¬obj file name[0]) {

j = strlen(src file name);

if (src file name[j − 1] ≡ ) {

strcpy (obj file name, src file name); obj file name[j − 1] = ; } else sprintf (obj file name, , src file name);

} obj file = fopen(obj file name, ); if (¬obj file) dpanic( ␣ ␣ ␣ ␣ ␣ , obj file name); if (listing name[0]) {

listing file = fopen(listing name, );

if (¬listing file) dpanic( ␣ ␣ ␣ ␣ ␣ , listing name); }

This code is used in section 141.

140. ⟨ Global variables 26 ⟩ +≡

char ∗src file name;  /∗ name of the  input file ∗/
char obj file name[  + 1];  /∗ name of the binary output file ∗/
char listing name[  + 1];  /∗ name of the optional listing file ∗/

FILE ∗src file, ∗obj file, ∗listing file; bool harvard ; /∗ 1 if separate data memory, else 0 ∗/ int buf size; /∗ maximum number of characters per line of input ∗/ tetra present time; /∗ THE time ∗/

141. ⟨ Initialize everything 33 ⟩ +≡ ⟨ Open the files 139 ⟩; filename[0] = src file name; filename count = 1; ⟨ Output the preamble 142 ⟩; 142. ⟨ Output the preamble 142 ⟩ ≡

ero lopp(lop pre, 3); ero wyde(^{#}101); present time = time(Λ); ero wyde(present time ≫ 16); ero wyde(present time &^{#}ffff); ero cur file = −1;

This code is used in section 141.

143. ⟨ Finish the assembly 143 ⟩ ≡ ⟨ Output the postamble 145 ⟩; ⟨ Check and output the trie 79 ⟩; ⟨ Report any undefined local symbols 146 ⟩; if (err count )

if (err count > 1) fprintf (stderr ,  ␣      ␣    ␣  , err count );
else fprintf (stderr ,  ␣     ␣   ␣  );

exit (err count );

This code is used in section 137.

144. ⟨ Global variables 26 ⟩ +≡ int greg = 0; /∗ global register allocator ∗/

145. ⟨ Output the postamble 145 ⟩ ≡ ero lopp(lop post , greg + 1); greg val [0] = trie search(trie root , ) sym equiv ; for (j = 0; j ≤ greg ; j^{++}) ero wyde(greg val [j]);

This code is used in section 143.

146. ⟨ Report any undefined local symbols 146 ⟩ ≡

for (j = 0; j < 10; j^{++})

if (forward local [j].link ) ^{++}err count , fprintf (stderr ,  ␣     ␣       ␣  , j);

This code is used in section 143.

54  INDEX  ERISCAL §147

147. Index.

: 32. acc: \underline{28}, \underline{82}, 91, 92, 93, 94, 95, 107, 119. addr mode: \underline{116}, 117, 118, 121, 122, 125. and : \underline{81}, 96, 100. arg num: \underline{104}, 113. arg num bits : \underline{64}, 113. argc: \underline{137}, 138. : \underline{27}, \underline{28}, \underline{29}, \underline{32}, \underline{42}, \underline{43}, \underline{45}, \underline{46}, \underline{49}, \underline{50}, \underline{51},

\underline{52}, \underline{54}, \underline{57}, \underline{59}, \underline{61}, \underline{73}, \underline{74}. argv : \underline{137}, 138. assemble: \underline{54}, 114, 117, 130, 131, 132. assemble DST : \underline{117}, 122, 128, 129. assemble inst : \underline{117}, 121. assembly language: 1. aux : \underline{26}, 28, 29, 100. backward local : \underline{89}, 90, 107. backward local host : 88, \underline{89}, 90. Bentley, Jon Louis: 56. big-endian versus little-endian: 48. binary check : \underline{100}. : 69. : 69. : 69. bits : \underline{64}, 66. bool: \underline{25}. : 65. : 44, \underline{64}, 65, 133. buf : 48. buf ptr : \underline{34}, 35, 101, 137. buf size: 33, 35, 83, 138, \underline{140}. buffer : 33, \underline{34}, 35, 39, 42. bypass : 46, \underline{101}, 102, 103, 133. c: \underline{29}, \underline{74}. C preprocessor: 3. calloc: 33, 39, 57, 61, 83. : 99. : 100. : 100. : 100. : 99. : 99. : 99. : 99. : 139. : 48. : 98. : 100. : 101. : 39, 57, 61. ch: \underline{56}, 59, 63, 72, 74, 76, 78. Char: \underline{31}, 33, 34, 38, 39, 41, 59, 64, 68, 75.

: \underline{64}, 65, 133.

: 65.

complement : \underline{81}, 85, 99.

constant found : 91, 92, \underline{93}, 94, 95.

cur code loc: \underline{44}, 133. cur data loc: \underline{44}, 133. cur file: \underline{37}, 39, 46, 52. cur loc: 43, \underline{44}, 51, 54, 55, 95, 99, 107, 108, 111,

112, 115, 128, 129, 131, 132, 133. cur prefix : \underline{58}, 63, 86, 109, 133. cur seg : 43, \underline{44}, 50, 55, 107, 111, 115, 128, 129,

131, 132, 133. dat : \underline{54}. : \underline{64}, 65, 133. : 65. dderr : \underline{46}, 111, 118. : \underline{60}, 74, 77, 86, 90, 107, 112. delink : \underline{98}, 99. derr : \underline{46}, 85, 96, 99, 100, 101, 102, 103, 107, 113,

120, 121, 122, 123, 124, 126, 127. dest bit : \underline{64}. : 100. dpanic: \underline{46}, 48, 139. : 127. : 120. : 121. : 35, 36. equiv : \underline{60}, 61, 66, 70, 74, 77, \underline{81}, 86, 93, 97, 98,

99, 100, 103, 106, 107, 108, 111, 114, 115, 119, 120, 121, 122, 123, 124, 126, 127, 128, 129, 130, 131, 132, 133, 135, 145.

ero: \underline{22}, 48, 49, 50, 79.

ero buf : \underline{48}, 49, 52.
ero clear : \underline{49}, 50, 54.
ero cur file: 52, \underline{53}, 142.
ero cur loc: 49, 51, \underline{53}, 55.
ero cur seg : 50, \underline{53}, 55.
ero line no: 49, 52, \underline{53}.
ero loc: \underline{51}, 55, 133.
ero lop: \underline{49}, 52.
ero lopp: \underline{49}, 51, 52, 79, 111, 133, 142, 145.
ero out : \underline{49}, 52.
ero ptr : \underline{48}, 49, 79.
ero seg : \underline{50}, 51, 55.
ero sync: \underline{52}, 133.
ero trie wyde: \underline{49}, 74, 76.
ero write: \underline{48}, 49.
ero wyde: \underline{49}, 50, 79, 142, 145.

err : 36, \underline{46}, 92, 94, 97, 98, 99, 100, 105, 106, 107, 115, 120, 121, 122, 123, 124, 127, 133.

§147  ERISCAL  INDEX 55

err buf : 33, \underline{34}, 46. err count : 46, \underline{47}, 78, 143, 146. : 65. : 44, \underline{64}, 65, 133. exit : 46, 138, 143. false: \underline{25}, 35, 66, 70, 115, 128, 129, 131, 132, 133. : 69. fgetc: 35, 36. fgets : 35. : 69. : 69. filename: 37, \underline{38}, 39, 46, 52, 141. filename count : \underline{38}, 39, 141. : 39, \underline{40}, 140. filename passed : 52, \underline{53}. fin bin: \underline{98}, 100. flush listing line: \underline{42}, 43, 45, 46, 112, 135, 137. fopen: 139. : 69. forward local : \underline{89}, 90, 109, 146. forward local host : 87, \underline{89}, 90. fprintf : 31, 36, 42, 43, 45, 46, 77, 78, 79, 112,

135, 138, 143, 146. : 69. : 69. frac: \underline{81}, 96, 100. frame pointer: 18. : 69. : 69. : 69. : 107. future bits : 113, \underline{116}, 117, 128, 129. fwprintf : 31. : 69. fwrite: 48. greg : 106, 107, 135, \underline{144}, 145. : \underline{64}, 65, 101, 107, 133. : 65. greg val : 106, \underline{134}, 145. h: \underline{68}. : 69. harvard : 70, 133, 138, \underline{140}. held bits : \underline{44}, 49, 50, 54. hold buf : \underline{44}, 45, 49, 54. hold op: \underline{84}, 97. : 52. : 105. : 100. : 94. immed bit : \underline{64}. : 102. : 105. ind pure: \underline{81}, 98, 99, 100, 115, 125, 126. ind reg val : \underline{81}, 97. ind rel undefined : \underline{81}. ind undefined : \underline{81}. indir bit : \underline{64}. indirectize: \underline{81}, 85, 99. : 69. inner lp: \underline{81}, 85, 97. inner rp: \underline{81}, 96, 97. : \underline{64}, 65, 107, 133. : 65. isalpha: 59. isdigit : 39, 59, 85, 93, 102, 103, 107, 108, 109. isletter : \underline{59}, 85, 102, 103. isspace: 39, 102, 103, 105. isxdigit : 94. j: \underline{29}, \underline{45}, \underline{52}, \underline{54}, \underline{137}. : 65. k: \underline{137}. l: \underline{54}, \underline{68}. lab field : 33, \underline{34}, 101, 102, 103, 107, 108, 109. : 101. : 102. last sym node: 61, \underline{62}. last trie node: 57, \underline{58}. left : \underline{56}, 59, 72, 73, 74. line directives: 3. line listed : 35, \underline{37}, 42, 46, 137. line no: 35, \underline{37}, 39, 46, 52. link : \underline{60}, 61, 66, 70, 74, 76, 77, \underline{81}, 86, 90, 93, 98, 99, 107, 108, 110, 115, 128, 129, 131, 132, 133, 146.

link pointer: 18.

list : 32.

listing bits : \underline{44}, 45, 49, 54, 137. listing clear : \underline{45}, 49, 54, 137. listing file: 42, 43, 45, 46, 49, 54, 76, 77, 79, 107,

112, 133, 135, 137, 139, \underline{140}. listing loc: 43, \underline{44}, 45. listing name: 138, 139, \underline{140}. listing seg : 43, \underline{44}. literate programming: 3. little-endian versus big-endian: 48. : 65. : \underline{64}, 65, 107, 133. long warning given: 36, \underline{37}. lop end : \underline{23}, 79. lop file: \underline{23}, 52. lop fixr : \underline{23}, 111. lop fixrx : \underline{23}. lop fixw : \underline{23}, 111. lop fixwx : \underline{23}. lop line: \underline{23}, 52. lop post : \underline{23}, 145. lop pre: \underline{23}, 142. lop quote: \underline{23}, 48. lop quote command : \underline{48}, 49. lop seg : \underline{23}, 50. lop skip: \underline{23}, 51. lop spec: \underline{23}, 133. lop stab: \underline{23}, 79. lopcodes: 22. : 65. m: \underline{29}, \underline{74}. : 21, 71. main: \underline{137}. message: \underline{46}. mid : \underline{56}, 59, 63, 72, 73, 74, 76, 79. minus : \underline{81}, 96, 100. : 97. : 97. mod : \underline{81}, 96, 100. multiprecision division: 29. multiprecision multiplication: 28. n: \underline{29}. name: \underline{64}, 66, \underline{68}, 70. neg one: \underline{26}. negate: \underline{81}, 85, 99. new link : \underline{107}, 108, 112. new sym node: \underline{61}, 66, 70, 71, 86, 109, 115,

128, 129, 131, 132. new trie node: \underline{57}, 59, 63. next sym node: 61, \underline{62}. next trie node: 57, \underline{58}. next val : \underline{82}, 98, 100. : 103. : 33, 83. no label bit : \underline{64}, 101. : 133. : 92. nyb bit : \underline{60}, 111, 128, 129. obj file: 48, 139, \underline{140}. obj file name: 48, 138, 139, \underline{140}. object files: 22. op bits : 101, 103, \underline{104}, 113, 118. op field : 33, \underline{34}, 101, 103, 113, 118, 120, 121,

122, 123, 124, 126, 127. op init size: \underline{65}, 66. op init table: \underline{65}, 66. op ptr : \underline{82}, 84, 85, 97, 100. op root : \underline{58}, 63, 66, 79, 103. op spec: \underline{64}, 65, 66. op stack : 80, 81, \underline{82}, 83, 84, 85, 97, 100. opcode: 101, 103, \underline{104}, 107, 117, 120, 121, 122, 133. : 103.

: 113. : 133. operand list : 33, \underline{34}, 84, 85, 105. operands done: \underline{84}, 97. or : \underline{81}, 96, 100. out stab: \underline{74}, 76, 79. outer lp: \underline{81}, 84, 97. outer rp: \underline{81}, 96, 97. over : \underline{81}, 96, 100. overflow : \underline{26}. p: \underline{41}, \underline{52}, \underline{59}, \underline{61}. panic: 33, 39, \underline{46}, 52, 57, 61, 83. plus : \underline{81}, 96, 98. pp: 61, 66, \underline{67}, 70, \underline{74}, 77, 86, 103, 107, 108, 109,

110, 115, 128, 129, 131, 132. prec: \underline{81}, 82. precedence: \underline{82}, 84. predef size: \underline{69}, 70. predef spec: \underline{68}, 69, 70. : \underline{60}, 66, 70, 86, 107. predefined symbols: 10, 69. predefs : \underline{69}, 70. : \underline{64}, 65, 133. : 65. present time: \underline{140}, 142. prune: \underline{73}, 79. pseudo op: \underline{64}. pure: \underline{81}, 86, 93, 98, 99, 100, 108, 120, 130. q: \underline{29}, \underline{41}. qq : \underline{67}, 110, 111, 115, 128, 129, 131, 132. recycle fixup: \underline{61}, 110. : 107. reg bit : \underline{64}. reg val : \underline{81}, 86, 97, 98, 99, 100, 107, 108, 115, 120,

121, 122, 123, 124, 125, 126, 127. : \underline{60}, 74, 77, 86, 107, 108. : 97, 115. registerize: \underline{81}, 85, 99. rel bit : \underline{60}, 111, 115, 129, 132. rel undefined : \underline{81}, 99, 114, 115, 123, 130. relativize: \underline{81}, 85, 99. report error : \underline{46}. right : \underline{56}, 59, 72, 73, 74. rt op: \underline{82}, 84, 96, 97. s: \underline{27}, \underline{42}, \underline{59}, \underline{74}, \underline{111}. scan close: \underline{84}, 97. scan open: \underline{85}. Sedgewick, Robert: 56. seg : \underline{60}, 61, 66, 70, 74, 77, 107, 111. seg bit : \underline{60}, 111. serial : \underline{60}, 61, 73, 74, 76, 77, 99, 107, 111, 115,

128, 129, 131, 132. serial number: 11, 21. serial number : 61, \underline{62}, 107. serialize: \underline{61}, \underline{81}, 85, 99. sh check : \underline{96}. shift left : \underline{27}. shift right : \underline{27}. shl : \underline{81}, 96, 100. shr : \underline{81}, 96, 100. spec bit : \underline{64}, 101. spec mode: \underline{44}, 45, 54, 101, 133. spec mode loc: \underline{44}, 54, 133. sprintf : 46, 139. : 121, 122, 123, 124. : 120. : 122. : 123, 126. : 120. src file: 35, 36, 139, \underline{140}. src file name: 138, 139, \underline{140}, 141. sscanf : 138. stack pointer: 18. stack op: \underline{81}, 82, 83. stat: \underline{81}. status : \underline{81}, 86, 93, 97, 98, 99, 100, 107, 108,

114, 115, 119, 120, 121, 122, 123, 124, 125, 126, 127, 130.

: 69. stderr : 36, 46, 78, 138, 143, 146. : 69. : 69. store new char : \underline{59}. strcmp: 39. strcpy : 138, 139. strlen: 35, 52, 139. strong : \underline{81}, 82. sym: \underline{56}, 66, 70, 71, 72, 73, 74, 76, 77, 86, 90, 99,

103, 108, 109, 115, 128, 129, 131, 132, 145. sym avail : 61, \underline{62}. sym buf : \underline{75}, 76, 77, 78, 79. sym node: \underline{60}, 61, 62, 67, 74, 89, 107. sym ptr : \underline{75}, 76, 77, 78, 79. sym root : \underline{62}. sym tab struct: 56, \underline{60}. : 107. symbol found : \underline{86}, 87, 88. : 85, 96. system dependencies: 25. t: \underline{28}, \underline{29}, \underline{49}, \underline{57}, \underline{59}, \underline{73}, \underline{74}. terminator : \underline{59}, 86. ternary trie struct: \underline{56}. tetra: \underline{25}, 140. : 69.

: 69. time: 142. times : \underline{81}, 96, 100. : 106. : 113. top op: \underline{82}, 84. top val : \underline{82}, 86, 93, 97, 98, 99, 100. : 36. trie node: \underline{56}, 57, 58, 59, 67, 73, 74, 81, 89. trie root : \underline{58}, 63, 70, 71, 79, 86, 109, 145. trie search: \underline{59}, 66, 70, 71, 86, 103, 109, 145. true: \underline{25}, 36, 42, 71, 86, 109, 133, 138. tt : \underline{59}, 66, \underline{67}, 70, 86, 87, 88, 109. u: \underline{27}, \underline{28}. unary : \underline{81}, 82. unary check : \underline{99}. undefined : \underline{81}, 86, 98, 99, 100, 108, 114, 115,

123, 130. : 146. : 78. Unicode: 5, 6, 7, 31, 76. : 103. update listing loc: \underline{43}, 45. : 138. useful : \underline{73}. v: \underline{28}. val node: \underline{81}, 82, 83. val ptr : \underline{82}, 84, 86, 93, 98, 108, 113, 114. val stack : 80, 81, \underline{82}, 83, 84, 106, 107, 108, 114,

115, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 135.

verb: 99, 100. w: \underline{51}, \underline{111}. wdiv : \underline{29}, 100. weak : \underline{81}, 82. wmult : \underline{28}, 100. wyde: \underline{25}, 26, 27, 28, 29, 44, 49, 51, 53, 54, 60,

68, 81, 82, 104, 111, 116, 134. : \underline{64}, 65, 114. : 65. x: \underline{29}, \underline{49}, \underline{116}. x bits : \underline{54}. xor : \underline{81}, 96, 100. xyz : 72. y: \underline{27}, \underline{28}, \underline{29}, \underline{49}, \underline{116}. yz : \underline{49}, 72. z: \underline{28}, \underline{29}, \underline{49}, \underline{116}. zero: \underline{81}, 82. zero wyde: \underline{26}, 61, 99, 100. zh: \underline{29}. zl : \underline{29}.

⟨ Allocate a global register 106 ⟩ Used in section 101. ⟨ Assemble SRC as a future reference 128 ⟩ Used in section 123. ⟨ Assemble SRC as a relative future reference 129 ⟩ Used in section 123. ⟨ Assemble YZ as a future reference 131 ⟩ Used in section 130. ⟨ Assemble YZ as a relative future reference 132 ⟩ Used in section 130. ⟨ Cases for binary operators 98, 100 ⟩ Used in section 97. ⟨ Cases for unary operators 99 ⟩ Used in section 97. ⟨ Change the X and Y fields 119 ⟩ Used in section 117. ⟨ Check and output the trie 79 ⟩ Used in section 143. ⟨ Check for a line directive 39 ⟩ Used in section 35. ⟨ Check if this case is allowed by this instruction 118 ⟩ Used in section 117. ⟨ Copy the operand field 105 ⟩ Used in section 101. ⟨ Deal with cases where val stack [j] is impure 115 ⟩ Used in section 114.

⟨ Define the label 107 ⟩ Used in section 101.

⟨ Do a many-operand operation 114 ⟩ Used in section 113. ⟨ Do a one-operand operation 133 ⟩ Used in section 113. ⟨ Do a two-operand operation 117 ⟩ Used in section 113.

⟨ Do the DST field 127 ⟩ Used in section 117.

⟨ Do the SRC field, it have to be a constant 123 ⟩ Used in section 117. ⟨ Do the SRC field, it have to be a register 124 ⟩ Used in sections 117 and 126. ⟨ Do the SRC field, it is indirect 126 ⟩ Used in section 117.

⟨ Do the operation 113 ⟩ Used in section 101. ⟨ Do the second wyde 130 ⟩ Used in section 117.

⟨ Find the addressing mode 125 ⟩ Used in section 117. ⟨ Find the symbol table node, pp 109 ⟩ Used in section 107.

⟨ Finish the assembly 143 ⟩ Used in section 137.

⟨ Fix a future reference 111 ⟩ Used in section 110. ⟨ Fix prior references to this label 110 ⟩ Used in section 107. ⟨ Fix references that might be in the val stack 108 ⟩ Used in section 107. ⟨ Flush the excess part of an overlong line 36 ⟩ Used in section 35. ⟨ Get the next line of input text, or break if the input has ended 35 ⟩ Used in section 137.

⟨ Global variables 26, 34, 37, 38, 44, 47, 48, 53, 58, 62, 65, 69, 75, 82, 89, 104, 116, 134, 140, 144 ⟩ Used in section 137.

⟨ Handle exceptions for 0 addr mode 120 ⟩ Used in section 117. ⟨ Handle exceptions for 2 addr mode 121 ⟩ Used in section 117. ⟨ Handle exceptions for 3 addr mode 122 ⟩ Used in section 117.

⟨ Initialize everything 33, 63, 71, 83, 90, 141 ⟩ Used in section 137. ⟨ Local variables 41, 67 ⟩ Used in section 137. ⟨ Make listing for 135 ⟩ Used in section 133.

⟨ Make special listing to show the label equivalent 112 ⟩ Used in section 107. ⟨ Make sure cur loc and ero cur loc refer to the same wyde 55 ⟩ Used in sections 54 and 111.

⟨ Open the files 139 ⟩ Used in section 141.

⟨ Output the postamble 145 ⟩ Used in section 143.

⟨ Output the preamble 142 ⟩ Used in section 141.

⟨ Perform the top operation on op stack 97 ⟩ Used in section 84. ⟨ Preprocessor definitions 32, 40 ⟩ Used in section 137. ⟨ Print symbol sym buf and its equivalent 77 ⟩ Used in section 76. ⟨ Process the command line 138 ⟩ Used in section 137. ⟨ Process the next instruction or comment 101 ⟩ Used in section 137. ⟨ Put other predefined symbols into the trie 70 ⟩ Used in section 63. ⟨ Put the opcodes and pseudo-ops into the trie 66 ⟩ Used in section 63. ⟨ Report an undefined symbol 78 ⟩ Used in section 74. ⟨ Report any undefined local symbols 146 ⟩ Used in section 143.

ERISCAL NAMES OF THE SECTIONS 59

⟨ Scan a backward local 88 ⟩ Used in section 85. ⟨ Scan a binary operator or closing token, rt op 96 ⟩ Used in section 84. ⟨ Scan a character constant 91 ⟩ Used in section 85. ⟨ Scan a decimal constant 93 ⟩ Used in section 85. ⟨ Scan a forward local 87 ⟩ Used in section 85. ⟨ Scan a hexadecimal constant 94 ⟩ Used in section 85. ⟨ Scan a string constant 92 ⟩ Used in section 85.

⟨ Scan a symbol 86 ⟩ Used in section 85.

⟨ Scan opening tokens until putting something on val stack 85 ⟩ Used in section 84. ⟨ Scan the current location 95 ⟩ Used in section 85. ⟨ Scan the label field; goto bypass if there is none 102 ⟩ Used in section 101. ⟨ Scan the opcode field; goto bypass if there is none 103 ⟩ Used in section 101. ⟨ Scan the operand field 84 ⟩ Used in section 101.

⟨ Subroutines 27, 28, 29, 42, 43, 45, 46, 49, 50, 51, 52, 54, 57, 59, 61, 73, 74 ⟩ Used in section 137. ⟨ Type definitions 25, 31, 56, 60, 64, 68, 81 ⟩ Used in section 137.

⟨ Visit t and traverse t mid 76 ⟩ Used in section 74.

April 2, 2014 at 12:08

ERISCAL

Section Page

Definition of ERISCAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Binary ERO output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 8 Basic data types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 11 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 12 Basic input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 15 The symbol table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 24 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 33 Assembling an instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 40 Running the program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 51 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 54

\begin{matrix}c \\ ◯ \end{matrix} 1993 Stanford University

This file may be freely copied and distributed, provided that no changes whatsoever are made. All users are asked to help keep the Stanford GraphBase files consistent and “uncorrupted,” identical everywhere in the world. Changes are permissible only if the modified file is given a new name, different from the names of existing files in the Stanford GraphBase, and only if the modified file is clearly identified as not being part of that GraphBase. (The CWEB system has a “change file” facility by which users can easily make minor alterations without modifying the master source files in any way. Everybody is supposed to use change files instead of changing the files.) The author has tried his best to produce correct and useful programs, in order to help promote computer science research, but no warranty of any kind should be assumed. Preliminary work on the Stanford GraphBase project was supported in part by National Science Foundation grant CCR-86-10181.