Description
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 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. 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. For example, 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, or External. NT is thus the length of the module.
Other requirements: error detection and arbitrary limits.
To received full 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 given the 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.
• If multiple 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).
You may need to set “arbitrary limits”, for example you may wish to limit the number of characters in a symbol to
(say) 8. Any such 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 below and 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. We will 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. You may 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 know right away if you find any errors in the output.
4
1 xy 2
2 z 2 -1 xy 4 -1
5R1004 I 5678 E 2000 R 8002 E 7001
0
1z123-1
6R8001 E 1000 E 1000 E 3000 R 1002 A 1010
0
1z1-1
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: E 2000 ->z 2015
3: R 8002 8002+0 = 8002
4: E 7001 ->xy 7002
+5
0 R 8001 8001+5 = 8006
1 E 1000 ->z 1015
2 E 1000 ->z 1015
3 E 3000 ->z 3015
4 R 1002 1002+5 = 1007
5 A 1010 1010
+11
0 R 5001 5001+11= 5012
1 E 4000 ->z 4015
+13
0 A 8000 8000
1 E 1001 ->z 1015
2 z: E 2000 ->xy 2002
