Implement a two-pass linker in Java and submit the source code. The target machine is word addressable and has a memory of 200 words, each consisting of 4 decimal digits. The first (leftmost) digit is the opcode, which is unchanged by the linker. The remaining three digits (called the address field) are either An immediate operand, which is unchanged. An absolute address, which is unchanged. A relative address, which is relocated. An external address, which is resolved.

Input consists of a series of object modules, each of which contains three lists: definitions of symbol that are used in other modules, uses of symbols defined in other modules, and the program text. The format of the lists is given below and a complete sample input is on the next page. The linker processes the input twice (that is why it is called two-pass). Pass one determines the base address for each module and produces a symbol table containing the absolute address for each defined symbol. The first module has base address zero; the base address for module M+1 is equal to the base address of module M plus the length of module M. The absolute address for symbol S defined in module M is the base address of M plus the relative address of S within M. Pass two uses the base addresses and the symbol table computed in pass one to generate the actual output by relocating relative addresses and resolving external references. The definition list is a count ND followed by ND pairs (S, R) where S is the symbol being defined and R is the relative address to which the symbol refers. Pass one relocates R forming the absolute address A and stores the pair (S, A) in the symbol table. The use list is a count NU followed by NU pairs (S, R), where S is the symbol being used and R is a relative address where S is used. The address initially in R is the relative address the next use of S in this module.. This linked list of uses ends with a sentinel of 777. The program text consists of a count NT followed by NT 5-digit numbers, where the first 4 digits form an instruction as described above and the last digit gives the type of the address component: 1=immediate, 2=absolute, 3=relative, and 4=external. NT, the number of instructions, is thus the length of the module.