"Write an Assembler in C." Why writing a machine code translator for a low level language in a higher level language?

Question

My Microprocessor class instructor gave us an assignment and said:

"Write an Assembler in C." - My beloved Professor

So it seemed a little bit illogical to me.

If I'm not wrong Assembly Language is the first step from Machine Code to the journey of higher level languages. I mean C is a higher level language than Assembly. So what is the point of writing an Assembler in C? What were they doing in the past while the absence of C language? Were they writing Assembler in Machine Code?

It doesn't make sense to me writing a machine code translator for a low level language in a higher level language.

Let's say we have created a brand new microprocessor architecture that there is not even a C compiler for that architecture. Will our Assembler that written in C be able simulate the new architecture? I mean will it be useless or not?

By the way I'm aware that GNU Assembler and Netwide Assembler have been written in C. I am also wondering why are they written in C?

Lastly, this is the example source code for a simple assembler that our Professor gave to us:

// to compile, gcc assembler.c -o assembler
// No error check is provided.
// Variable names cannot start with 0-9.
// hexadecimals are twos complement.
// first address of the code section is zero, data section follows the code section.
//fout tables are formed: jump table, ldi table, label table and variable table.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


//Converts a hexadecimal string to integer.
int hex2int( char* hex)  
{
    int result=0;

    while ((*hex)!='\0')
    {
        if (('0'<=(*hex))&&((*hex)<='9'))
            result = result*16 + (*hex) -'0';
        else if (('a'<=(*hex))&&((*hex)<='f'))
            result = result*16 + (*hex) -'a'+10;
        else if (('A'<=(*hex))&&((*hex)<='F'))
            result = result*16 + (*hex) -'A'+10; 
        hex++;
    }
    return(result);
}


main()
{   
    FILE *fp;
        char line[100];
        char *token = NULL;
    char *op1, *op2, *op3, *label;
    char ch;
    int  chch;

    int program[1000];
    int counter=0;  //holds the address of the machine code instruction




// A label is a symbol which mark a location in a program. In the example 
// program above, the string "lpp", "loop" and "lp1" are labels.
    struct label  
    {
        int location;
        char *label;
    };
    struct label labeltable[50]; //there can be 50 labels at most in our programs
    int nooflabels = 0; //number of labels encountered during assembly.




// Jump instructions cannot be assembled readily because we may not know the value of 
// the label when we encountered a jump instruction. This happens if the label used by
// that jump instruction appear below that jump instruction. This is the situation 
// with the label "loop" in the example program above. Hence, the location of jump 
// instructions must be stored.
    struct jumpinstruction   
    {
        int location;
        char *label;
    };
    struct jumpinstruction jumptable[100]; //There can be at most 100 jumps
    int noofjumps=0;  //number of jumps encountered during assembly.    




// The list of variables in .data section and their locations.
    struct variable
    {
        int location;
        char *name;
    };
    struct variable variabletable[50]; //There can be 50 varables at most.
    int noofvariables = 0;




//Variables and labels are used by ldi instructions.
//The memory for the variables are traditionally allocated at the end of the code section.
//Hence their addresses are not known when we assemble a ldi instruction. Also, the value of 
//a label may not be known when we encounter a ldi instruction which uses that label.
//Hence, the location of the ldi instructions must be kept, and these instructions must be 
//modified when we discover the address of the label or variable that it uses.
    struct ldiinstruction   
    {
        int location;
        char *name;
    };
    struct ldiinstruction lditable[100];
    int noofldis=0;


            
    
    fp = fopen("name_of_program","r");
    
    if (fp != NULL)
    {
        while(fgets(line,sizeof line,fp)!= NULL)  //skip till .code section
        {
            token=strtok(line,"\n\t\r ");
            if (strcmp(token,".code")==0 )
                break;
        } 
        while(fgets(line,sizeof line,fp)!= NULL)
        {
            token=strtok(line,"\n\t\r ");  //get the instruction mnemonic or label

//========================================   FIRST PASS  ======================================================
            while (token)
            {
                if (strcmp(token,"ldi")==0)        //---------------LDI INSTRUCTION--------------------
                {
                    op1 = strtok(NULL,"\n\t\r ");                                //get the 1st operand of ldi, which is the register that ldi loads
                    op2 = strtok(NULL,"\n\t\r ");                                //get the 2nd operand of ldi, which is the data that is to be loaded
                    program[counter]=0x1000+hex2int(op1);                        //generate the first 16-bit of the ldi instruction
                    counter++;                                                   //move to the second 16-bit of the ldi instruction
                    if ((op2[0]=='0')&&(op2[1]=='x'))                            //if the 2nd operand is twos complement hexadecimal
                        program[counter]=hex2int(op2+2)&0xffff;              //convert it to integer and form the second 16-bit 
                    else if ((  (op2[0])=='-') || ((op2[0]>='0')&&(op2[0]<='9')))       //if the 2nd operand is decimal 
                        program[counter]=atoi(op2)&0xffff;                         //convert it to integer and form the second 16-bit 
                    else                                                           //if the second operand is not decimal or hexadecimal, it is a laber or a variable.
                    {                                                               //in this case, the 2nd 16-bits of the ldi instruction cannot be generated.
                        lditable[noofldis].location = counter;                 //record the location of this 2nd 16-bit  
                        op1=(char*)malloc(sizeof(op2));                         //and the name of the label/variable that it must contain
                        strcpy(op1,op2);                                        //in the lditable array.
                        lditable[noofldis].name = op1;
                        noofldis++;                                             
                    }       
                    counter++;                                                     //skip to the next memory location 
                }                                       

                else if (strcmp(token,"ld")==0)      //------------LD INSTRUCTION---------------------         
                {
                    op1 = strtok(NULL,"\n\t\r ");                //get the 1st operand of ld, which is the destination register
                    op2 = strtok(NULL,"\n\t\r ");                //get the 2nd operand of ld, which is the source register
                    ch = (op1[0]-48)| ((op2[0]-48) << 3);        //form bits 11-0 of machine code. 48 is ASCII value of '0'
                    program[counter]=0x2000+((ch)&0x00ff);       //form the instruction and write it to memory
                    counter++;                                   //skip to the next empty location in memory
                }
                else if (strcmp(token,"st")==0) //-------------ST INSTRUCTION--------------------
                {
                    //to be added
                }
                else if (strcmp(token,"jz")==0) //------------- CONDITIONAL JUMP ------------------
                {
                    //to be added
                }
                else if (strcmp(token,"jmp")==0)  //-------------- JUMP -----------------------------
                {
                    op1 = strtok(NULL,"\n\t\r ");           //read the label
                    jumptable[noofjumps].location = counter;    //write the jz instruction's location into the jumptable 
                    op2=(char*)malloc(sizeof(op1));         //allocate space for the label                  
                    strcpy(op2,op1);                //copy the label into the allocated space
                    jumptable[noofjumps].label=op2;         //point to the label from the jumptable
                    noofjumps++;                    //skip to the next empty location in jumptable
                    program[counter]=0x5000;            //write the incomplete instruction (just opcode) to memory
                    counter++;                  //skip to the next empty location in memory.
                }               
                else if (strcmp(token,"add")==0) //----------------- ADD -------------------------------
                {
                    op1 = strtok(NULL,"\n\t\r ");    
                    op2 = strtok(NULL,"\n\t\r ");
                    op3 = strtok(NULL,"\n\t\r ");
                    chch = (op1[0]-48)| ((op2[0]-48)<<3)|((op3[0]-48)<<6);  
                    program[counter]=0x7000+((chch)&0x00ff); 
                    counter++; 
                }
                else if (strcmp(token,"sub")==0)
                {
                    //to be added
                }
                else if (strcmp(token,"and")==0)
                {
                    //to be added
                }
                else if (strcmp(token,"or")==0)
                {
                    //to be added
                }
                else if (strcmp(token,"xor")==0)
                {
                    //to be added
                }                       
                else if (strcmp(token,"not")==0)
                {
                    op1 = strtok(NULL,"\n\t\r ");
                    op2 = strtok(NULL,"\n\t\r ");
                    ch = (op1[0]-48)| ((op2[0]-48)<<3);
                    program[counter]=0x7500+((ch)&0x00ff);  
                    counter++;
                }
                else if (strcmp(token,"mov")==0)
                {
                    //to be added
                }
                else if (strcmp(token,"inc")==0)
                {
                    op1 = strtok(NULL,"\n\t\r ");
                    ch = (op1[0]-48)| ((op1[0]-48)<<3);
                    program[counter]=0x7700+((ch)&0x00ff);  
                    counter++;
                }
                else if (strcmp(token,"dec")==0)
                {
                                    //to be added
                }
                else //------WHAT IS ENCOUNTERED IS NOT AN INSTRUCTION BUT A LABEL. UPDATE THE LABEL TABLE--------
                {
                    labeltable[nooflabels].location = counter;  //buraya bir counter koy. error check
                    op1=(char*)malloc(sizeof(token));
                    strcpy(op1,token);
                    labeltable[nooflabels].label=op1;
                    nooflabels++;
                } 
                token = strtok(NULL,",\n\t\r ");  
            }
        }


//================================= SECOND PASS ==============================
    
                //supply the address fields of the jump and jz instructions from the 
        int i,j;         
        for (i=0; i<noofjumps;i++)                                                                   //for all jump/jz instructions
        {
            j=0;
            while ( strcmp(jumptable[i].label , labeltable[j].label) != 0 )             //if the label for this jump/jz does not match with the 
                j++;                                                                // jth label in the labeltable, check the next label..
            program[jumptable[i].location] +=(labeltable[j].location-jumptable[i].location-1)&0x0fff;       //copy the jump address into memory.
        }                                                     

    


                // search for the start of the .data segment
        rewind(fp);  
        while(fgets(line,sizeof line,fp)!= NULL)  //skip till .data, if no .data, also ok.
        {
            token=strtok(line,"\n\t\r ");
            if (strcmp(token,".data")==0 )
                break;

        }


                // process the .data segment and generate the variabletable[] array.
        int dataarea=0;
        while(fgets(line,sizeof line,fp)!= NULL)
        {
            token=strtok(line,"\n\t\r ");
            if (strcmp(token,".code")==0 )  //go till the .code segment
                break;
            else if (token[strlen(token)-1]==':')
            {               
                token[strlen(token)-1]='\0';  //will not cause memory leak, as we do not do malloc
                variabletable[noofvariables].location=counter+dataarea;
                op1=(char*)malloc(sizeof(token));
                strcpy(op1,token);
                variabletable[noofvariables].name=op1;
                token = strtok(NULL,",\n\t\r ");
                if (token==NULL)
                    program[counter+dataarea]=0;
                else if (strcmp(token, ".space")==0)
                {
                    token=strtok(NULL,"\n\t\r ");
                    dataarea+=atoi(token);
                }
                else if((token[0]=='0')&&(token[1]=='x')) 
                    program[counter+dataarea]=hex2int(token+2)&0xffff; 
                else if ((  (token[0])=='-') || ('0'<=(token[0])&&(token[0]<='9'))  )
                    program[counter+dataarea]=atoi(token)&0xffff;  
                noofvariables++;
                dataarea++;
            }
        }






// supply the address fields for the ldi instructions from the variable table
        for( i=0; i<noofldis;i++)
        {
            j=0;
            while ((j<noofvariables)&&( strcmp( lditable[i].name , variabletable[j].name)!=0 ))
                j++;
            if (j<noofvariables)
                program[lditable[i].location] = variabletable[j].location;              
        } 

// supply the address fields for the ldi instructions from the label table
        for( i=0; i<noofldis;i++)
        {
            j=0;
            while ((j<nooflabels)&&( strcmp( lditable[i].name , labeltable[j].label)!=0 ))
                j++;
            if (j<nooflabels){
                program[lditable[i].location] = (labeltable[j].location)&0x0fff;
                printf("%d %d %d\n", i, j, (labeltable[j].location));   
            }           
        } 

//display the resulting tables
        printf("LABEL TABLE\n");
        for (i=0;i<nooflabels;i++)
            printf("%d %s\n", labeltable[i].location, labeltable[i].label); 
        printf("\n");
        printf("JUMP TABLE\n");
        for (i=0;i<noofjumps;i++)
            printf("%d %s\n", jumptable[i].location, jumptable[i].label);   
        printf("\n");
        printf("VARIABLE TABLE\n");
        for (i=0;i<noofvariables;i++)
            printf("%d %s\n", variabletable[i].location, variabletable[i].name);    
        printf("\n");
        printf("LDI INSTRUCTIONS\n");
        for (i=0;i<noofldis;i++)
            printf("%d %s\n", lditable[i].location, lditable[i].name);  
        printf("\n");
        fclose(fp);
        fp = fopen("RAM","w");
        fprintf(fp,"v2.0 raw\n");
        for (i=0;i<counter+dataarea;i++)
            fprintf(fp,"%04x\n",program[i]);
    }   
}

Answer 1

People have written assemblers in machine code. They've also written then in assembly language--often a subset of the language they translate themselves, so they start with a simple "bootstrap" version of the assembler, then add features to it as they need them for the assembler itself.

However, none of this is particularly a necessity. In the end, an assembler is a (usually fairly) simple translation program. It takes in a file in one (text) format, and writes out a file in another (usually an object file format).

The fact that the text that's input represents machine instructions in a textual format and the result represents the same instructions in binary format doesn't make much difference to the language that's used to implement the assembler--in fact, even higher languages than C such as SNOBOL and Python can work quite nicely--I (fairly) recently worked on an assembler written in Python, and it worked pretty well for the job.

As far as how you bootstrap things initially: typically on another machine that has decent development tools and such. If you're developing new hardware, you usually start by writing a simulator (or at least emulator) for the new machine anyway, so at first you're building and running the code on some host system in any case.

Answer 2

You are seeing connections that don't exist.

"Write an assembler" is a programming task just like any other programming task. You use the tools to handle that task that are best for that task. There is nothing special about writing an assembler; there is no reason at all not to write it in a high level language. C is actually at a quite low level, and I would probably prefer C++ or some other higher level language.

Assembly language is actually totally unsuitable for a task like this. The cases where you would reasonably use assembly language are very, very rare. Only when you need to do things that cannot be expressed in a higher level language.

Answer 3

What were they doing in the past while the absence of C language? Were they writing Assembler in Machine Code?

Assembly is essentially a mnemonic for machine code; each opcode in the machine language is given an assembly mnemonic i.e. in x86 NOP is 0x90. This makes assembler's rather simple (n.b. most assemblers have two passes, one to translate, and a second to generate/resolve addresses/references.) The first assembler was written and translated by hand (likely on paper) into machine code. A better version is written and assembled with the hand 'assembled' assembler, new features are added this way. Compilers for new languages can be built this way; in the past it was common for compilers to output assembly, and use an assembler for their back end!

It doesn't make sense to me writing a machine code translator for a low level language in a higher level language. ... [existing assemblers] have been written in C. I am also wondering why they are written in C?

• It is generally easier to write an more complicated piece of software in a higher level language.
• It generally takes more code, and more mental effort to track what you are doing in a lower level language than a higher one.
  • A single line of C could translate into many instructions ex. a simple assignment in C++ (or C) usually generates at least 3 assembly instructions (load,modify,store;) it could take twenty instructions or more (possibly hundreds,) to do what can be done with a single line in a higher level language (like c++ or c.) One would generally want to spend their time on solving the problem, and not spending time figuring out how to implement the solution in machine code.

While self-hosting is a common milestone/desirable feature for a programming language, assembly is so low level that most programmers would prefer to work at a higher level. I.e no one wants to write an assembler in assembly (or anything else really)

Let's say we have created a brand new microprocessor architecture that there is not even a C compiler for that architecture.

Bootstrapping is the process of getting a tool-chain on a new architecture.

the basic process is:

• write a new back end that understands how to generate code for your new CPU (or MCU)
• compile and test your back end
• cross-compile your desired compiler (and os, etc.) using your new back-end
• transfer these binaries to the new system

Not once do you need to write in assembly (new or old) to do this, one should choose the best language to write your assembler/back-end/code-generator.

Will our Assembler that written in C be able simulate the new architecture?

Assemblers don't simulate!

If one was developing a new CPU with a new (or existing) machine language, a simulator is usually necessary for testing; i.e run random instructions and data through the simulator, and compare the output with the same instructions and data on your prototype CPU. Then find bugs, fix bugs, repeat.

Answer 4

Addressing specifically this part of the question only:

"By the way I'm aware that GNU Assembler and Netwide Assembler have been written in C. I am also wondering why they are written in C?"

Speaking as part of the team that originally wrote the Netwide Assembler, the decision seemed so obvious to us at the time that we basically didn't consider any other options, but had we done so we would have come to the same conclusion, based on the following reasons:

• Writting it in a lower level language would have been harder and much more time-consuming.
• Writing it in a higher level language might have been faster, but there were performance considerations (an assembler used as a back end to a compiler, particularly, needs to be very fast in order to prevent slowing the compiler down too much, as it can end up handling very large amounts of code, and this was a use case that we specifically wanted to allow) and I don't believe the primary authors had any higher level languages in common (this was before Java became popular, so the world of such languages was rather fragmented back then). We did use perl for some metaprogramming tasks (generating tables of instructions in a useful format for the code generator back end), but it wouldn't really have been suitable for the entire program.
• We wanted operating-system portability
• We wanted hardware platform portability (for producing cross-compilers)

This made the decision quite easy: ANSI-compliant C (aka C89 these days) was the only language at the time that really hit all of those points. Had there been a standardized C++ back then we may have considered that, but C++ support between different systems was rather patchy back then, so writing portable C++ was a bit of a nightmare.

Answer 5

Among the reasons to write an assembler in C (or any other higher level language) are all the reasons you might use to justify writing any other program in that higher level language. Chief among those in this case are probably portability and usability.

Portability: If you write your assembler in a native language you have an assembler on that platform. If you write it in C you have an assembler on any platform with a C compiler. This lets you, for example, compile code for your embedded platform on your workstation and move the binary rather than needing to do it all directly on the target device.

Usability: For most people, reading, reasoning about, and modifying programs is far more natural when the program is in a higher level language than when it's in assembler or (worse) raw machine code. Therefore, it's easier to develop and maintain the assembler in a higher level language because you can think in terms of the abstractions afforded to you by the higher level languages rather than having to think about the minutiae for which you're responsible in lower ones.

Answer 6

One thing has absolutely nothing to do with the other. Are web browsers strictly to be written using html or php or some other web content language? No, why would they? Can cars only be driven by other cars and not by humans?

Converting one blob of bits (some ascii) to another blob of bits (some machine code) is just a programming task, the programming language you use for that task is whatever one you want. You can and there have been assemblers written in many different languages.

New languages cannot be written in their own language initially as there is no compiler/assembler yet for them. If there is no existing compiler for a new language you have to write the first one in some other language and then you eventually bootstrap if that even makes sense to bootstrap. (html and a web browser, a program that takes some bits in and spits some bits out will never be written in html, cant be).

Doesnt have to be a new language, can be an existing one. New C or C++ compilers dont automatically compile themselves right out of the gate.

For assembly language and C the first two languages for almost all new or modified instruction sets. We are not in the past, we are in the present. We can easily generate an assembler in C or java or python or whatever for any instruction set and assembly language we want even if it doesnt yet exist. Likewise there are many retargettable C compilers that we can output assembly language for any assembly language we want even if the assembler doesnt yet exist.

That is exactly what we do with a new instruction set. Take some computer not running on our new instruction set with its C compiler that was compiled not for our new instruction set nor its assembler, create a cross assembler and cross compiler. Develop and use that while creating and simulating the logic. Go through the normal development cycles of find a bug and fix a bug and test again, until ideally all the tools and the logic are deemed ready. And depending on the target, say it is a microcontroller incapable of running an operating system, you would never have a reason to bootstrap that such that the toolchain generates and runs using the native instruction set. You would always cross compile. Other than in a wayback machine it never makes sense to write the assembler in assembler.

Yes if you could go back or pretend to go back, the first assembler was a human with a pencil and paper, that wrote something that made sense to them and then write the bits next to it that made sense to the logic. Then used switches or some other way to get the bits into the machine (google pdp8 or pdp11 or altair 8800) and making it do something. There were no computer simulators initially you just had to get the logic right by staring at it long enough or also spinning several revs of the chip. The tools are good enough today that you can get A0 success in that the thing is more than just a big resistor, a lot of it works you may still need a spin for things you couldnt simulate completely, but you can often boot now on the first spi without having to wait for the third or fourth spin, simply because we have a vast array of verlog and vhdl tools (not written in verilog nor vhdl nor running on the newly not yet created processor).

In your wayback machine as one would expect, you then take your hand assembled code and you use it to say load a program from tape or cards. You also hand code an assembler in machine code, might not be a full blown one but one that makes programming a little bit easier. Then that tool is used to create one that can handle a more advanced or complicated langauge (a macro assembler), and that one to create one more complicated and you end up with FORTRAN or BASIC or B or whatever. And then you start to think about bootstrapping in the same language, re-writing the cross compiler to be a native compiler. of course you ideally need an environment or operating system of some sort for that.

When we are creating or testing silicon we can/do need to stare at the signals which are ones and zeros. The tools will show us binary or hex by default and it is possible with some tools to even have look ups so that the tools will display some mnemonics (assembly perhaps) but often the engineers (silicon/hardware and software) can either read enough of the machine code, or use the dissassembly/listing to "see" the instructions.

Depending on what you are doing you might just shove in some machine code into the test vectors rather than re-writing and recompiling or re-assembling the test. For example if you have a pipeline and prefetch at some depth you might need or want to fill past the end of the program some number of nops or other real instructions so that the pipe doesnt puke on undefined instructions, and you may just choose to just fill machine code in at the lowest level listing/file rather than try to get the compiler or assembler or linker to do it.

While testing the processor of course you do need to deal with undefineds and perhaps dont care bits, etc. So you would need to go into the machine code and modify one or more specific bits in an instruction in a normally working program. Is it worth writing a program to do this or just do it by hand. Likewise when testing ECC you want to flip one or more bits and see that they get corrected or trapped. Granted that is a lot easier to write a program to do or you could just do it by hand.

Then of course there are languages that dont produce code that runs on a processor, early pascal, java, python, etc. You need a VM written in some other language just to use those languages. You cant use your java compiler to make a java vm, makes no sense based on the design of the language.

(yes sure after the pure implementation of these languages eventually someone builds an unpure backend that can sometimes target real instruction sets not the vm instruction set and then in that case you can use the language to compile it self or its vm if you really felt the need. A gnu java front end to gcc for example).

Over time and perhaps likely still we dont write C compilers in C. We use things like bison/flex some other programming language that we use to generate the C for us that we didnt want to write ourselves. Some percentage is in C sure, but some percentage is in some other language that uses some other compiler that inputs bits and outputs other bits. Sometimes this approach is also used for generating an assembler. Up to the designer of the compiler/assembler (programs that have a task to input bits and then output other bits) as to how they are going to implement it. The program generated parsers could be hand programmed sure, just time consuming so folks look for a shortcut. Just like you could write an assembler in assembler but folks look for a shortcut.

A web browser is just a program that takes in some bits and spits out some other bits. An assembler is just a program that takes in some bits and spits out some other bits. A compiler is just a program that takes in some bits and spits out some other bits. Etc. For all of these there is a documented set of rules for the input bits and output bits for each programming task. These tasks and bits are generic enough that any AVAILABLE programming language can be used (that is capable of doing bit/byte manipulation and dealing with the inputs and outputs). The key here is available. Get and try the linux from scratch book/tutorial. Try a pdp8 or pdp11 or altair 8800 or other simulator with a simulated front panel.

Answer 7

A computer can be built from NOT and AND operations, or just NAND, which means we can use these operations to generate all other operations like OR, MUX, DMUX etc. In this way, electronic engineers can only build NAND chip, then use it to generate others. But you may also wonder why they don't make the chips for maybe OR, DMUX operations. They can, but they choose another way.

According to my understanding, that's the reason why we can use one language to "interprete" or "compile" the identical language. In fact, we do it all the time, such as: A computer programmer is a person whose job involves writing programs for computers. We use a person whose job involves writing programs for computers to explain computer programmer.

And, in my opinion, the most important reason why we can use a higher level language to "interprete" or "compile" a lower level language is simplicity. It's just tedious to write Assembler using Assembly Language or even Machine Code. The purpose of this task is to understand how to translate Assembly Language to Machine Code, it's fine to use higher level language such as C, python, java etc as long as you understand the theory behind it.