How is a 2 pass-assembler different from a one pass assembler in resolving the future symbols?

Question

These are 2 questions that I don't understand:

1. How does the One-Pass Assembler resolve the future symbol problem?

2. How is Two-Pass Assembler different from the one pass assembler in this respect?

   Does it resolve it in the first pass or the second pass? If it does it in the second pass,where does it actually differ from the one-pass-assembler? If it does it in the second-pass why doesn't it do in the first pass?

Answer 1

Read this PDF. It explains, step by step, as to how single and multi-pass assemblers work. It also explains the pros and cons of both of them and the differences between the two.

What is a single pass assembler?

It is a kind of Load-and-go type of assembler that generally generates the object code directly in memory for immediate execution! It parses through your source code only once and your done. Vroom...

Cool, if it does this magic why do we need multi-pass assemblers at all?

Forward references! ie while the one-pass assembler is trodding along your source code, it encounters some strangers in the form of undefined data symbols and undefined labels(jump addresses). Your assembler asks these strangers as to who are they? The strangers say " We'll tell you later!" (Forward reference) Your assembler gets angry and tells you to totally eliminate these strangers. But these strangers are your friends and you cant eliminate them totally. So you enter into a compromise deal with the assembler. You promise to define all your variables before using them. The assembler couldn't compromise on this because it cannot even reserve temp storage for the undefined data symbols as it doesn't know their size. Data can be of varying sizes

If its something like

PAVAN EQU SOMETHING

; Your code here
 mov register, PAVAN


; SOMETHING DB(or DW or DD) 80 ; varying size data, not known before

On its part your assembler agrees to compromise on undefined jump labels. As jump labels are nothing but addresses and address sizes can be known apriori so that assembler can reserve some definite space for the undefined symbol.

If its like this

      jump AHEAD


 AHEAD add reg,#imm

Assembler translates jump AHEAD as 0x45 **0x00 0x00**. 0x45 is the opcode of jump and 4 bytes reserved for AHEAD address

OK, now tell me how exactly one pass assembler works

Simple, while on its way, if the assembler encounters an undefined label, it puts it into a symbol table along with the address where the undefined symbol's value has to be placed, when the symbol is found in future. It does the same for all undefined labels and as and when it sees the definitions of these undefined symbols, it adds their value, both in the table ( thereby making that label defined ) and in the memory location where it had reserved temp storage earlier.

Now at the end of parsing, if there are any more poor souls still in undefined state, the assembler cries foul and errors out :( If there aren't any undefined labels, then off you go!

One sec, I forgot why we need a 2 or multi pass assembler? And how do they work?

As explained, one-pass assembler cannot resolve forward references of data symbols. It requires all data symbols to be defined prior to being used. A two-pass assembler solves this dilemma by devoting one pass to exclusively resolve all (data/label) forward references and then generate object code with no hassles in the next pass.

If a data symbol depends on another and this another depends on yet another, the assembler resolved this recursively. If I try explaining even that in this post, the post will become too big. Read this ppt for more details

Hmm.. Interesting. Does the two pass assembler have any more advantages?

Yes. It can detect redefinitions and things like that.

PS: I might not be 100% correct here. I would love to hear any suggestions in making it a better post.

Answer 2

A one pass assembler generates code and for any undefined symbols, leaves a slot to be filled in, and remembers it in a table or other data structure. Then where the symbol is defined, it fills in its value at the right place or places, using the information from the table.

The reason for using a two pass assembler traditionally has been that the target program doesn't fit in memory, leave alone the source. The gigantic source program is read, line by line, from the punch tape reader, and the table of labels is kept in internal memory. (I've actually done that, on ISIS, the first development system of Intel, with an 8080.) The second time around the source tape is again read from the beginning, but the value of all labels is known, and as each line is read, the target program is punched out to tape. On a memory starved 16 bit Intel 8086 system this was still a useful technique to have a heavily documented source file that can be much larger than 64 Kbyte, with hard disk or floppy substituted for paper tape.

Nowadays there is no need to do two passes, but this architecture is still in use. It is slightly simpler, at the expense of I/O.