Lab 1: Implement a two-pass linker in C, C++, or Java

Lab 1
You are to implement a two-pass linker in C, C++, or Java and submit the source code, which we compile and run.
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 (1) an immediate operand, which is unchanged; (2) an absolute address, which is unchanged; (3) a relative address, which is relocated; or (4) an external address, which is resolved. Relocating relative addresses and resolving external references were discussed in class and are in the notes.
Input consists of a series of object modules, each of which contains three parts: definition list, use list, and program text.
The linker processes the input twice (that is why it is called two-pass). Pass one determines the base address for each module and the absolute address for each external symbol, storing the later in the symbol table it produces. The first module has base address zero; the base address for module I+1 is equal to the base address of module I plus the length of module I. 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 twouses 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. The first entry in the pair is an external symbols used in the module. The second entry is a list of relative addresses in the module in which the symbol is used. The list is terminated by a sentinel of -1. Forexample, if the use list is ‘‘2 f 3 1 4 -1 xyg 0 -1’’, then the symbol f is used in instructions 1, 3, and 4, and the symbol xyg is used in instruction 0.
The program text consists of a count NT followed by NT pairs (type, word), where word is a 4-digit instruction described above and type is a single character indicating if the address in the word is Immediate, Absolute, Relative,o r External. NT is thus the length of the module.
Other requirements: error detection and arbitrary limits.
To receivedfull credit, you must check the input for various errors. All error messages produced must be informative,e.g., ‘‘Error: The symbol ‘diagonal’ was used but not defined. It has been giventhe value 0’’. You should continue processing after encountering an error and should be able to detect multiple errors in the same run.
•Ifasymbol is multiply defined, print an error message and use the value given in the first definition. •Ifasymbol is used but not defined, print an error message and use the value zero. •Ifasymbol is defined but not used, print a warning message and continue. •Ifmultiple symbols are listed as used in the same instruction, print an error message and ignore all but the first usage given. •If an address appearing in a definition exceeds the size of the module, print an error message and treat the address given as 0 (relative). •If an address appearing in a use list exceeds the size of the module, print an error message and ignore this particular use. •If an absolute address exceeds the size of the machine, print an error message and use the value zero. •Ifarelative address exceeds the size of the module, print an error message and use the value zero (absolute).
Youmay need to set “arbitrary limits”, for example you may wish to limit the number of characters in a symbol to (say) 8. Anysuch limits should be clearly documented in the program and if the input fails to meet your limits, your program must print an error message and continue if possible. Naturally,the limits must be large enough for all the inputs on the web.Under no circumstances should your program reference an array out of bounds, etc.
Lab 1—Linker Page 2 CSCI-GA.02250 2016-17 Spring
There are several sample input sets on the web.The first is the one belowand the second is an re-formatted version of the first. Some of the input sets contain errors that you are to detect as described above.Wewill run your lab on these (and other) input sets. Please submit the SOURCE code for your lab, together with a README file (required) describing how to compile and run it. Your program must either read an input set from standard input, i.e., the keyboard, or accept a command line argument giving the name of the input file. Youmay develop your lab on any machine you wish, but must insure that it compiles and runs on the NYU system assigned to the course. The expected output is also on the web.Let me knowright away if you find anyerrors in the output.
4 1 xy 2 2 z 2 -1 xy 4 1 5R1004 I 5678 E 2000 R 8002 E 7001 0 1z1231 6R8001 E 1000 E 1000 E 3000 R 1002 A 1010 0 1z11 2R5001 E 4000 1z2 2 xy 2 -1 z 1 1 3A8000 E 1001 E 2000
The following is output annotated for clarity and class discussion. Your output is not expected to be this fancy.
Symbol Table xy=2 z=15
Memory Map
+0 0: R 1004 1004+0 =1004 1: I 5678 5678 2: xy: E2000 -z 2015 3: R 8002 8002+0 =8002 4: E 7001 -xy 7002 +5 0R8001 8001+5 =8006 1E1000 -z 1015 2E1000 -z 1015 3E3000 -z 3015 4R1002 1002+5 =1007 5A1010 1010 +11 0R5001 5001+11= 5012 1E4000 -z 4015 +13 0A8000 8000 1E1001 -z 1015 2z:E2000 -xy 2002