2-pass linker

**kmel** · 02-05-2008

Hi , i have to create a 2 pass linker but i need some help. The target machine has a memory of 600 words with each word consisting of 4 decimal digits. The linker processes one module at a time. The module consists of a definition list, a use list and program text. Can anyone give me a hint, a link or sth to start?

Thank you in advance

**CornedBee** · 02-05-2008

Pass one: for each module, add the definitions to the linker's internal definition list.
Pass two: for each module, resolves the uses against the linker's definitions.

**kmel** · 02-05-2008

Thanks for your response. I didn't specify that i know the specification about the 2 passes. My problem is how to code it. I have thought of the solution but i do not know how to implement it. . My problem is the implementation code wise. I am searching the web for example or sth that can help me, but nothing yet.

**carlorfeo** · 02-06-2008

I'd try to help you if you may explain what a "2 pass linker" is.

Originally Posted by kmel

I have thought of the solution but i do not know how to implement it.

tell us your idea

**kmel** · 02-06-2008

Well in the first pass the linker 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 of a symbol is the base address of the module (that the symbol is used) plus the relative address of the symbol in that module.

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.

Thanks for your help

**matsp** · 02-06-2008

So, given your description, which part of writing a linker is it that you struggle to do?

If you can explain which portion, maybe we can suggest something. But describing how to write the entire linker, in sufficient detail to actually "just implement it", doesn't make much sense.

--
Mats

**kmel** · 02-06-2008

I am using a file that contains my input. In that file the data are the actual modules. Each module will consists of 3 rows. The first row - definition will have a number (the number of variables) and sets of variables - relative address like this : 2 x 2 xy 3 . The second row will have the use list that will contain a number (number of external symbols) and the external symbols : 1 z . The third row will be the program text that will have a number (number of words) and sets of type- word like this : 3 R 1004 I 5678 E 2000. So the file has a number of rows and each set of 3 rows is a module.

In the first pass I am trying to read that file 3 rows at a time. I have to do it this way so i can compute the size of each module. Also in this pass i have to compute the absolute address of the definition list symbols and store them in the symbol table.

In the second pass i will print the words according to their address and use the absolute address of the symbols in the use list where necessary.

My first problem is in pass 1. Suppose i have an input file with 9 rows, how do i read 3 rows at a time? I mean who can i tell where to stop reading? Then i will have to read each row of the first module lets say and store the definition symbols along with their absolute address (which ll have to compute) to the symbol table. I am thinking to use an array as a symbol table, but i do not know how to read a row word by word.

Thanks

**matsp** · 02-06-2008

Seems pretty obvious to me:

Code:

void read3lines(ifstream &fin)
{
   string line[3]
   for(int i = 0; i < 3; i++)
   {
       fin.getline(line[i]);
   }
}

Of course, you really need to do some parsing of those three lines, but as a principle, that's how you would do it.

--
Mats

**carlorfeo** · 02-06-2008

Originally Posted by kmel

Suppose i have an input file with 9 rows, how do i read 3 rows at a time?

First you need to create a file stream:
http://www.cplusplus.com/reference/i...m/fstream.html

Then you can read from it:
http://www.cplusplus.com/reference/i...m/getline.html

Here is the complete reference about:
look at the examples
http://www.cplusplus.com/reference/iostream/fstream/

**kmel** · 02-07-2008

So far i have made my code read an input file line by line, split each line to tokens and keep a track of each module. Now, i am trying to store the base address of each module and the absolute address of the external symbols. What should i use to store these addresses ? Any suggestions?

The input file i am using is the following:

1 xy 2 //definition list
2 z xy //use list
5 R 1004 I 5678 E 2000 R 8002 E 7001 //program text
0
1 z
6 R 8001 E 1000 E 1000 E 3000 R 1002 A 1010
0
1 z
2 R 5001 E 4000
1 z 2
2 xy z
3 A 8000 E 1001 E 2000

Code:

#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
using namespace std;

int main () {
  string line;
  char * p, * tokens;
  int i, m_count, m_line;

  ifstream myfile ("input1.txt");
  i = 0;
  m_count = 1;   //module counter
  m_line = 0;      //line counter inside module
  if (myfile.is_open())
    {
      while (! myfile.eof() )
        {
          i++;   //input file line counter
          m_line ++;

          getline (myfile,line);
          p = new char [line.size() + 1];
          strcpy (p, line.c_str());

          tokens = strtok (p, " ");
          while (tokens != NULL) {
            cout << tokens << endl;     //print tokens
            tokens = strtok(NULL," ");
          }
          cout << m_count << "." << m_line << " : " << line << endl;
          if (m_line == 3)    //each module has 3 lines, so i initialize the module line counter every 3 lines
            m_line = 0;
          if (i &#37; 3 == 0)    //each module has 3 lines
            m_count++;
        }
      myfile.close();
      cout << "modules : " << m_count - 1 << " lines : " << i << endl;
    }
    else cout << "Unable to open file";

  return 0;
}

Thank you all for your help

**vart** · 02-08-2008

read faq why this while (! myfile.eof() )
is bad

for storing pairs "name,value" you probably want to use std::map

**matsp** · 02-08-2008

Right, so you need to make your code understand what each token represents [you probably want one function to deal with each type of line, so the first function does the definition list, the second does the use list, the third function deals with the program text.

As to how you store the data, use some simple data structure - a simple array may well be sufficient [in real applications you would of course have to deal with this in a more dynamic way, but for a simple "this is how a linker works", a constant size array should be fine - just make sure it's "big enough" - and check if you go over the limit (it will save your skin at some point or another)].

--
Mats

**kmel** · 02-09-2008

Thanks for your help

. I am trying to use the Map to store the data i want. However, i have to convert the data i read from the stream to int. I have quoted in my code what i am trying to do. I tried using stringstream to convert the output from in.get(ch) to an int but i couldn't do it. I also tried to use expressions of the form in >> base where base is int, but that also didn't work. How can i make this work?

Thank you

Code:

#include <iostream>
#include <fstream>
#include <map>
using namespace std;

int  main() {
  ifstream in;  
  string fileName, words, flag, flagbase;
  char ch;

  int countL, countM, countML, i, base;
  map<int,int> baseAd;

  cout << "Enter the name of the file: ";
  cin >> fileName;
  in.open(fileName.c_str());

  i = 1;
  base = 0;
  countL = 1;  //line counter
  countML = 1; //line counter inside module
  countM = 1;  //module counter

  if (in.is_open()) {
    while (in >> words) {
      cout << words << endl;
      in.get(ch);

      if (flag == "progtext" && flagbase != "done") {
      // i am trying to find a way to convert the result from in.get(ch) to int and store it to base	  
        baseAd[countM] = base;
        cout << "test " << base << endl;
        flagbase = "done";  //the computing of the base address of the current module is done
      }
      if (ch == '\n') {
        countL ++;
        countML ++;
        cout << "new line " << countM << "." << countML << endl;

        switch (countML) {  //keep track of the current module list
        case 1:
          flag = "deflist";
          break;
        case 2:
          flag = "uselist";
          break;
        case 3:
          flag = "progtext";
          break;
        }

        if (countL &#37; 3 == 0) {   //each module has 3 lines
          countM++;
          flagbase = " ";  //i reset the flag
        }
        if (countML == 3)  //each module has 3 lines, so i initialize the module line counter every 3 lines
          countML = 0;

      }
    }
    in.close();
    for (i; i<=baseAd.size(); i++) {  //just print the contents
      cout << "size " << baseAd.size() << endl;
      cout << "base " << baseAd[i] << endl;
    }

  }
  else
    cout << "Unable to open file" << endl;
  return 0;
}

**kmel** · 02-09-2008

I found out how to take integer from the stream, so no worries

Thread: 2-pass linker

Thread Tools

Search Thread

Display

2-pass linker

Similar Threads

Linker problem... no idea

Speed test result

linker

Linker errors in VC++ 2005

pass be reference versus pass by value