2-pass linker

This is a discussion on 2-pass linker within the C++ Programming forums, part of the General Programming Boards category; Hi , i have to create a 2 pass linker but i need some help. The target machine has a ...

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    10

    2-pass linker

    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

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    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.

  4. #4
    coder
    Join Date
    Feb 2008
    Posts
    127
    I'd try to help you if you may explain what a "2 pass linker" is.

    Quote Originally Posted by kmel
    I have thought of the solution but i do not know how to implement it.
    tell us your idea

  5. #5
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    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

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    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

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    coder
    Join Date
    Feb 2008
    Posts
    127
    Quote 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/

  10. #10
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    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

  11. #11
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    read faq why this while (! myfile.eof() )
    is bad

    for storing pairs "name,value" you probably want to use std::map
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    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;
    }
    Last edited by kmel; 02-09-2008 at 10:39 AM.

  14. #14
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    I found out how to take integer from the stream, so no worries

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linker problem... no idea
    By cyreon in forum C Programming
    Replies: 2
    Last Post: 04-03-2009, 02:53 PM
  2. Speed test result
    By audinue in forum C Programming
    Replies: 4
    Last Post: 07-07-2008, 05:18 AM
  3. linker
    By George2 in forum C++ Programming
    Replies: 6
    Last Post: 02-23-2008, 12:25 AM
  4. Linker errors in VC++ 2005
    By C+/- in forum C++ Programming
    Replies: 0
    Last Post: 05-18-2007, 07:42 AM
  5. pass be reference versus pass by value
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 08-01-2002, 01:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21