Translating Computer Languages

Assemblers & compilers translate for later execution by real hardware or by software interpreters. They are just like any other applications, and are best written in HLLs, especially those specific to the application area.

Assembler

Simplifies the task of writing machine code programs

$\begin{picture}(12,1)% put(0,0)\{ framebox(12,1)\{\}\} \put(0,0.4){assembly prog... ...7,0.0){error messages, listings etc.} \put(6,0.1){\vector(1,0){1}} \end{picture}$

1) build words from characters, discard spaces & comments
e.g. $\fbox{loop: LDA fred ;a comment}$ $\rightarrow$ $\fbox{loop}$ $\fbox{:}$ $\fbox{LDA}$ $\fbox{fred}$
2) check statements are legal
e.g. LDA is a mnemonic, that takes one operand, etc.
3) check user-defined names (e.g. labels),
keep list of names & addresses
4) translate [one-to-one]

Formally:
1) Lexical (word) analysis
2) Syntactic (sentence structure) analysis
3) Semantic (meaning) analysis
4) Code generation

(1) + (2) usually defined by a grammar (BNF) e.g.

instruction: mnemonic1 operand | mnemonic0 ;
mnemonic1  : LDA | ADD | SUB  | STO | JMP | JNE | JGE ;
mnemonic0  : STP ;

and then we would need to say that statements can have labels and comments, or just be numbers (for initialising variables) etc.

Compiler

Makes it seem as if the computer can understand high-level language programs, as well as machine code programs.

$\begin{picture}(12,1)% put(0,0)\{ framebox(12,1)\{\}\} \put(0.5,0.4){HLL program... ...7,0.0){error messages, listings etc.} \put(6,0.1){\vector(1,0){1}} \end{picture}$

e.g.

/* division by repeated subtraction */
/* declarations */
 Label again;
 Var ans=-1, a=99, b=6;
/* commands */
 again:
   ans=ans+1; a=a-b;
 If a>=0 JumpTo again;
 Stop;

Same first 4 steps, but each is more complicated:
1) identify words (names, numbers, operators, punctuation, types, etc.) e.g
$\fbox{Label}$ $\fbox{again}$ $\fbox{;}$ $\fbox{Var}$ $\fbox{ans}$ $\fbox{=}$ $\fbox{--}$ $\fbox{1}$ $\fbox{,}$ $\fbox{a}$ $\fbox{=}$ $\fbox{99}$ $\fbox{,}$ $\fbox{b}$ $\fbox{=}$ $\fbox{6}$ $\fbox{;}$ $\fbox{again}$ $\fbox{:}$ $\fbox{ans}$ $\fbox{=}$ $\fbox{ans}$ $\fbox{+}$ $\fbox{1}$ $\fbox{;}$ $\fbox{a}$ $\fbox{=}$ $\fbox{a}$ $\fbox{--}$ $\fbox{b}$ $\fbox{;}$ $\fbox{If}$ $\fbox{a}$ $\fbox{$>=$}$ $\fbox{0}$ $\fbox{JumpTo}$ $\fbox{again}$ $\fbox{;}$ $\fbox{Stop}$ $\fbox{;}$
2) check sentences are legal (expressions, declarations, statements, blocks, etc.)
3) check user-defined names (declared/not, var/label, int/real etc.)
keep list of names, addresses, types etc.
4) translate [one-to-many] to assembly code (need to run assembler as well) or to machine code e.g.

 0  again:        LDA ans          100B
 1                ADD one          200C
 2                STO ans          000B
 3                LDA a            1009
 4                SUB b            300A
 5                STO a            0009
 6                LDA a            1009
 7                JGE again        5000
 8                STP              7000
 9      a:        99               0063
10      b:        6                0006
11    ans:        -1               FFFF
12    one:        1                0001

and:
5) Code optimisation

Libraries & Linker

Library: increases set of operations available to programmer, allows access to facilities provided by system etc.
e.g. MU0 - provide multiplication and division
Compile these operations once, so users don't need to keep recompiling them.
Include list of operation names & addresses.

Linker: searches list(s) of names & addresses in libraries to locate operations needed
Copies requested operations from the library into the user program.

In practice, there are lots of complications that mean libraries have to contain extra information and linkers have to do extra work:

e.g. when a library is being compiled, the compiler doesn't know where exactly it is going to be within each user program that needs it, so what addresses should it use? - the library includes extra information for the linker, which has to finalise (relocate) the addresses in the library.

e.g. what if one library needs to use the facilities provided by another library (e.g. a graphics library using sine and cosine functions from the maths library)? - the library includes extra information telling the linker what it needs, and the linker has to make extra searches to find them.

Next: About this document ... Up: ho Previous: Computer Languages

Pete Jinks 2003-09-25