Note on Rapid Instruction Analysis by Table Lookup

USERCODE, the assembly language for the English Electric KDF9 (1964), differs from most one-to-one languages by not making a clear separation of the operation code and operand(s). For example, the instruction "jump to reference 40 if the contents of the nesting store is zero" would be written "J40=Z;". Such constructions make the problem of order decoding a non-trivial one. The assembly program distributed by the manufacturers employs a scan of the input text in which each character is used to select the routine to process the next character. This approach is unsatisfactory for two reasons: (1) the character scan requires a great deal of time, and (2) the program must be rigidly tied to the orginal specification of the language. The rigidity of the program is a direct result of the slow scan—in order to make compilation time reasonable, one must take advantage of every detail of the language specification. Thus virtually every instruction uses some special processor, and the program is extremely complex and difficult to modify. The problem of instruction decoding in USERCODE is similar to that of sentence analysis in natural languages. The program should be able to match a character string of variable length, the length being a priori unknown. Moreover, this should be done in a general way —one which is not tied to any peculiarities of the particular statements involved. Finally, the technique should allow easy alteration of the matching strings to accommodate growth of the language. A table-lookup approach to natural language translation has been developed (King, 1961) which meets all of the above criteria. As described, the system uses special-purpose hardware to perform a lookup and extract from a dictionary the longest possible match to the input string. We have used this method, without the special hardware, in a new USERCODE assembler for KDF9. The resulting program is faster, shorter and far more flexible than the distributed one.