| |
|
|
|
Transleerimise tulemus kirjeldatakse sageli mingi lihtsa magasini abil arvutusi sooritava abstraktse masina koodina. Sellise masina toimimine peaks olema kõigile arusaadav, nii et sellist esitust kasutatakse sageli ka programmeerimiskeele semantika esitamiseks: (kõrgtaseme) keele käskude tulemus kirjeldatakse sellise magasinmasina abil - mida nende käskude sooritamise tulemusena magasinmasin peaks tegema.
Järgnevas on kirjeldatud lihtne magasinmasin S-masin (see on N. Wirthi poolt Pascali transleerimiseks kasutatud masina lihtsustatud versioon), mille koodiks transleeritakse hiljem Pisi-Algol. Kuna ka protsessor sooritab arvutused magasini abil, selgitab transleerimine magasinmasina koodiks hästi ka paljusid masinkoodiks transleerimisel esinevaid probleeme.
S-masin koosneb kolmest mälualast:
C - programmi instruktsioonide massiiv (array);
NT (NameTable) - nimede tabel;
S - arvutamiseks kasutatav magasin; selle iga element on kas instruktsioon või arv.
Peale nende on veel neli fikseeritud registrit:
IR (Instruction Register) - interpreteeritavat instruktsiooni salvestav register;
T (Top )- magasini tipus oleva elemendi aadressi salvestav register;
PC (Program Counter) - järgmise instruktsiooni aadressi salvestav register;
AR (Activation Record) - salvestab interpreteeritava protseduuri baasaadressi (base address).
Instruktsioonid (S-koodid) on kahest täisarvust koosnevad paarid paarid <instruktsiooni kood, arg>, kus täisarvu arg tõlgendus (sõltuvalt esimesel kohal olevast operatsiooni koodist) on kas arv, nimede tabeli indeks või instruktsiooni indeks (märgend) massivis C.
Instruktsioonid ja nende argumendid on järgmised:
| READ | Var | Muutuja Var väärtuseks saab sisendist INPUT loetud arv |
| WRITE | Var | Muutuja Var väärtus kirjutatakse väljundisse OUTPUT |
|
ADD |
Magasini tipus olevad kaks viimast arvu asendatakse operatsiooni või võrdluse (LT - Less Than, GT - Greater Than) tulemusega | |
| MOV | Ind | Magasini tipus olnud arv salvestatakse muutujas, mille indeks nimede tabelis on Ind |
| LOAD_INT | Int | Magasini tippu lisatakse arv Int |
| LOAD_VAR | Ind | Muutuja, mille indeks nimede tabelis on Ind, väärtus lisatakse magasini tippu |
| GOTO | Lbl | Järgmisena täidetakse käsk märgendiga Lbl |
| JMP_FALSE | Lbl | Kui magasini tipus on väärtus väär (0), täidetakse järgmisena käsk märgendiga Lbl |
Siin on instruktsioonid esitatud sõnaga (nn "väline" esitusviis), masinas kasutatakse kõikjal instruktsiooni indeksit, s.t. täisarvulist koodi; koodid ja neid esitavad stringid on salvestatud (samas järjekorras) kahes loetlustüüpi massiivis code_ops ja op_name. Translaatoris on kõik kodeeritud täisarvudena (ka loetlustüübi enum elemendid on määratud nende täisarvulise indeksiga), stringid (väline esitus) ilmuvad alles genereetitud koodi väljastamisel - see teeb translaatori kiiremaks. Järgnevas on kogu magasinmasina kirjeldus failis SM.h; selle lõpus on magasinmasina tööd imiteeriv protseduur fetch_execute_cycle().
/******** Magasinmasin ********/
/** OPERATSIOONID: Sisemine esitus (loetlustyyp) **/
enum code_ops
{ HALT, MOV, JMP_FALSE, GOTO,
LOAD_INT, LOAD_VAR,
READ_INT, WRITE_INT,
LT, EQ, GT, ADD, SUB, MULT, DIV, PWR
};
/** OPERATSIOONID: Väline esitus **/
char *op_name[] =
{ "halt", "mov", "jmp_false", "goto",
"load_int", "load_var",
"in_int", "out_int",
"lt", "eq", "gt", "add", "sub", "mult", "div", "pwr"
};
/* MAGASINMASINA käsk on paar: op arg */
struct instruction
{
enum code_ops op;
int arg;
};
/** Koodide massiv **/
struct instruction code[999];
/* Magasin */
int stack[999];
/** Registrid **/
int pc = 0;
struct instruction ir;
int ar = 0;
int top = 0;
char ch;
/* integer power function */
int power(int m, int e)
{
int temp =1;
for(e ; e > 0; e--)
temp = temp * m;
return temp;
}
/***** Magasinmasina simuleerimine ******/
void fetch_execute_cycle()
{
do
{ printf( "PC = %3d IR.arg = %8d AR = %3d Top = %3d,%8d\n",
pc, ir.arg, ar, top, stack[top]);
/* Fetch */
ir = code[pc++];
/* Execute */
switch (ir.op)
{
case HALT : printf( "halt\n" ); break;
case READ_INT : printf( "Input: " );
scanf( "%ld", &stack[ar+ir.arg] ); break;
case WRITE_INT : printf( "Output: %d\n", stack[top--] ); break;
case MOV : stack[ir.arg] = stack[top--]; break;
case JMP_FALSE : if ( stack[top--] == 0 )
pc = ir.arg;break;
case GOTO : pc = ir.arg; break;
case LOAD_INT : stack[++top] = ir.arg; break;
case LOAD_VAR : stack[++top] = stack[ar+ir.arg]; break;
case LT : if ( stack[top-1] < stack[top] )
stack[--top] = 1;
else stack[--top] = 0;
break;
case EQ : if ( stack[top-1] == stack[top] )
stack[--top] = 1;
else stack[--top] = 0;
break;
case GT : if ( stack[top-1] > stack[top] )
stack[--top] = 1;
else stack[--top] = 0;
break;
case ADD : stack[top-1] = stack[top-1] + stack[top];
top--;
break;
case SUB : stack[top-1] = stack[top-1] - stack[top];
top--;
break;
case MULT : stack[top-1] = stack[top-1] * stack[top];
top--;
break;
case DIV : stack[top-1] = stack[top-1] / stack[top];
top--;
break;
case PWR : stack[top-1] = power(stack[top-1] * stack[top]);
top--;
break;
default : printf( "Jama: Memory Dump\n" );
break;
}
}
while (ir.op != HALT);
}
/*************************** Magasinmasin lopp **************************/
Nimede tabel (fail ST.h) on nagu magasinmäluga kalkulaatoriski kirjete lingitud nimistu:
/********* Nimede tabel - SymbolTable ***********/
struct symrec
{
char *name; /* identifikaatori nimekuju */
int offset; /* indeks */
struct symrec *next; /* link jargmisele */
};
typedef struct symrec symrec;
symrec *identifier;
/******** Nimede tabel: kirjete lingitud nimistu **********/
symrec *sym_table = (symrec *)0; /* Viit nimede tabelile */
/******** Operatsioonid: Putsym, Getsym - lisa, leia *******/
symrec * putsym (char *sym_name)
{
symrec *ptr;
ptr = (symrec *) malloc (sizeof(symrec));
ptr->name = (char *) malloc (strlen(sym_name)+1);
strcpy (ptr->name,sym_name);
ptr->offset = data_location();
ptr->next = (struct symrec *)sym_table;
sym_table = ptr;
return ptr;
}
symrec * getsym (char *sym_name)
{
symrec *ptr;
for ( ptr = sym_table;
ptr != (symrec *) 0;
ptr = (symrec *)ptr->next )
if (strcmp (ptr->name,sym_name) == 0)
return ptr;
return 0;
}
/********** Nimede tabel lopp ********/
Et kogu programm oleks paremini arusaadav, on ka koodi genereerimine kirjeldatud eraldi failis CG.h:
/******* Koodigenereerija *********/
/******* Andmesegment *********/
int data_offset = 0; /* Initsialiseerimine */
int data_location() /* Reserveerib yhe salvestuspaiga */
{
return data_offset++;
}
/******* Koodisegment *************/
int code_offset = 0; /* Initial offset */
int gen_label() /* Praeguse kasu number */
{
return code_offset;
}
int reserve_loc() /* Reserves a code location */
{
return code_offset++;
}
/***** Instruktsiooni genereerimine, massiiv code on dekl-d SM.h-s */
void gen_code( enum code_ops operation, int arg )
{ code[code_offset].op = operation;
code[code_offset++].arg = arg;
}
/**** Operatsioon BACK - kirjutab antud aadressile operatsiooni */
void back_patch( int addr, enum code_ops operation, int arg )
{
code[addr].op = operation;
code[addr].arg = arg;
}
/******* Koodi valjastamine ********/
void print_code()
{
int i = 0;
while (i < code_offset) {
printf("%3ld: %-10s%4ld\n",i,op_name[(int) code[i].op], code[i].arg );
i++;
}
}
/***** Koodigeneraatori lopp *******/
Lihtne leksikaanalüsaator on kirjeldatud failis pisi.lex:
/****** Pisi-Algoli skanner ********/
%{
#include <string.h> /* strdup */
#include <stdlib.h> /* atoi */
#include "pisi.tab.c" /* translator */
%}
DIGIT [0-9]
ID [A-Za-z][A-Za-z0-9_]*
/***** Lekseeme kirjeldavad regulaarsed avaldised ******/
%%
":=" { return(ASSGNOP); }
{DIGIT}+ { yylval.intval = atoi( yytext );
return(NUMBER); }
DO { return(DO); }
ELSE { return(ELSE); }
END { return(END); }
FOR { return(FOR); }
UNTIL {return(UNTIL); }
ENDLOOP {return(ENDLOOP); }
ENDFOR {return(ENDFOR); }
ENDIF { return(ENDIF); }
IF { return(IF); }
READ { return(READ); }
SKIP { return(SKIP); }
THEN { return(THEN); }
WHILE { return(WHILE); }
WRITE { return(WRITE); }
{ID} { yylval.id = (char *) strdup(yytext);
return(IDENTIFIER); }
[ \t\r\n]+ /* eat up whitespace */
. { return(yytext[0]);}
%%
int yywrap(void){}
/************************** Skanner lopp *****************************/
Kõige olulisem osa translaatorist, süntaksianalüsaator koos väljundit genereerivate tegevustega, on kirjeldatud failis pisi.y . Kuna siin avaldisi ei arvutata (vastavad arvutused sooritab iga operatsiooni lugemise ajal magasinmasin), pole aritmeetilise avaldise läbimisele lisatud mingeid semantilisi tegevusi; ka avaldise struktuur on kirjeldatud väga primitiivselt, operatsioonide sooritamise järjekorra määravad operatsioonide prioriteedid. Veidi tuleb aga "nipitada" if- ja while-käskudele märgendite lisamisel - nende esmakordsel läbimisel pole teada, kuhu suunamised tuleb teha, sellepärast jäetakse algul käskude massiivi protseduuriga reserve_loc() tühi koht (käsuindeksit suurendatakse käsku genereerimata) ja alles if- või while- käsu lõpus täidab protseduur back_patch() need augud.
/******* Pisi-Algoli süntaksianalüsaator ja translaator ********/
%{
#include <stdio.h> /* For I/O */
#include <stdlib.h> /* For malloc here and in symbol table */
#include <string.h> /* For strcmp in symbol table */
#include "ST.h" /* Nimede tabel - SymbolTable */
#include "SM.h" /* Magasinmasin */
#include "CG.h" /* Koodigenereerija */
#define YYDEBUG 1 /* silumiseks */
int errors; /* vigade loendaja */
int i;
symrec *nextid;
/*-------------------------------------------------------------------------
BACK - paigutab märgendid
-------------------------------------------------------------------------*/
struct lbs /* Labels for data, if and while */
{
int for_goto;
int for_jmp_false;
};
struct lbs * newlblrec() /* Viitadele mälu reserveerimine */
{
return (struct lbs *) malloc(sizeof(struct lbs));
}
/*-------------------------------------------------------------------------
Identikaatori kandmine nimede tabelisse ja kontroll - kas on juba seal?
-------------------------------------------------------------------------*/
install ( char *sym_name )
{
symrec *s;
s = getsym (sym_name);
if (s == 0)
s = putsym (sym_name);
else { errors++;
printf( "%s on juba defineeritud\n", sym_name );
}
}
/**** Kui identifikaator pole nimede tabelis,
lisatakse see sinna ! *********/
check_n_gen( enum code_ops operation, char *sym_name )
{ symrec *identifier;
identifier = getsym( sym_name );
if ( identifier == 0 )
{
identifier = putsym( sym_name );
}
gen_code( operation, identifier->offset );
}
%}
/******* SEMANTIKA ******/
%union semrec
{
int intval; /* Integer values */
char *id; /* Identifiers */
struct lbs *lbls; /* For backpatching */
}
/******** LEKSEEMIDE TYYP *********/
%start program
%token<intval> NUMBER
%token<id> IDENTIFIER /* Simple identifier */
%token<lbls> IF WHILE /* For backpatching labels */
%token SKIP THEN ELSE ENDIF DO ENDLOOP END FOR UNTIL ENDFOR
%token READ WRITE
%token ASSGNOP
%left '-' '+'
%left '*' '/'
%right '^'
/******* GRAMMATIKAREEGLID ja TEGEVUSED *******/
%%
program :
commands
END { gen_code( HALT, 0 ); YYACCEPT; }
;
commands : /* tyhi */
| command ';' commands
;
command : SKIP
| READ IDENTIFIER { check_n_gen( READ_INT, $2 ); }
| WRITE exp { gen_code( WRITE_INT, 0); }
| IF exp { $1 = (struct lbs *) newlblrec();
$1->for_jmp_false = reserve_loc(); }
THEN commands { $1->for_goto = reserve_loc(); }
ELSE { back_patch( $1->for_jmp_false,
JMP_FALSE,
gen_label() ); }
commands
ENDIF { back_patch( $1->for_goto, GOTO, gen_label() ); }
| WHILE { $1 = (struct lbs *) newlblrec();
$1->for_goto = gen_label(); }
exp { $1->for_jmp_false = reserve_loc(); }
DO
commands
ENDLOOP { gen_code( GOTO, $1->for_goto );
back_patch( $1->for_jmp_false,
JMP_FALSE,
gen_label() ); }
| IDENTIFIER ASSGNOP exp { check_n_gen( MOV, $1 ); }
;
exp : NUMBER { gen_code( LOAD_INT, $1 ); }
| IDENTIFIER { check_n_gen( LOAD_VAR, $1 ); }
| exp '<' exp { gen_code( LT, 0 ); }
| exp '=' exp { gen_code( EQ, 0 ); }
| exp '>' exp { gen_code( GT, 0 ); }
| exp '+' exp { gen_code( ADD, 0 ); }
| exp '-' exp { gen_code( SUB, 0 ); }
| exp '*' exp { gen_code( MULT, 0); }
| exp '/' exp { gen_code( DIV, 0 ); }
| exp '^' exp { gen_code( PWR, 0 ); }
| '(' exp ')'
;
%%
/******* MAIN *******/
main( int argc, char *argv[] )
{ extern FILE *yyin;
++argv; --argc;
yyin = fopen( argv[0], "r" );
/* yydebug = 1; */
errors = 0;
yyparse ();
if ( errors == 0 )
{ printf("/**** Nimede tabel ****/\n");
extern symrec *sym_table;
nextid = sym_table;
do
{
printf( " %s : int32;\n", nextid->name );
nextid = nextid->next;
} while ( nextid->next != NULL );
printf( " %s : int32;\n", nextid->name ); /* viimane! */
printf("/**** Programm ****/\n");
print_code ();
fetch_execute_cycle();
}
}
/***** YYERROR ******/
yyerror ( char *s ) /* yyparse on error */
{
errors++;
printf ("%s\n", s);
}
/**************************** Translaator lopp ***************************/
Et jälgida, mida analüsaator teeb, tuleks maha võtta kommentaarid realt yydebug = 1; - siis väljastab Bison rida realt, kuidas sisendi töötlemine toimus. Kuna Bison-i poolt loodud fail pisi.tab.y on lingitud failis pisi.lex, toimub translaatori loomine järjekorras (Bison-i teatatud konfliktid pole olulised!)
bison pisi.y
flex pisi.lex
gcc lex.yy.c -opisi.exe
Kui käivitada loodud translaator Pisi-Algolis kirjutatud Fibonacci arvude programmiga:
f0 := 1;saame väljundi (magasinmasina simuleerimist kirjeldavad read on ära jäetud):
f1 := 1;
n := 40;
i :=1;
WHILE i < n DO
f2 := f1;
f1 := f1 + f0;
f0 := f2;
WRITE i;
WRITE f1;
i := i+1;
ENDLOOP;
END
/**** Nimede tabel - tagurpidi järjekorras !****/
f2 : int32;
i : int32;
n : int32;
f1 : int32;
f0 : int32;
/**** Programm ****/
0: load_int 1
1: mov 0
2: load_int 1
3: mov 1
4: load_int 40
5: mov 2
6: load_int 1
7: mov 3
8: load_var 3
9: load_var 2
10: lt 0
11: jmp_false 29
12: load_var 1
13: mov 4
14: load_var 1
15: load_var 0
16: add 0
17: mov 1
18: load_var 4
19: mov 0
20: load_var 3
21: out_int 0
22: load_var 1
23: out_int 0
24: load_var 3
25: load_int 1
26: add 0
27: mov 3
28: goto 8
29: halt 0
PC = 0 IR.arg = 0 AR = 0 Top = 0, 0
PC = 1 IR.arg = 1 AR = 0 Top = 1, 1
PC = 2 IR.arg = 0 AR = 0 Top = 0,
Selle uurimisel peab arvesse võtma, et nimede tabel on väljastatud tagurpidi järjekorras, s.t. indeksiga 0 on kõige viimane identifikaator f0, seega selle programmi alguse interpretatsioon on selline:
| load_int 1 mov 0 |
f0 := 1 |
| load_int 1 mov 1 |
f1 := 1 |
| load_var 3 load_var 2 lt 0 |
i < n |
| ... | |
FOR omistamine UNTIL avaldis DO programm ENDFOR
Selle semantika oleks nagu C-s: omistamine annab tsüklimuutujale algväärtuse, avaldis - lõppväärtuse (lihtsustamiseks võib lugeda, et algväärtus <= lõppväärtus) ja tsüklit täidetakse kuni tsüklimuutuja saab suuremaks lõppväärtusest; tsüklimuutujat suurendatakse tsükli lõpus, just enne tagasipöördumise kontrolli.
2. Täienda
transleerimiskeemi nii, et transleeritavas keeles saaks kasutada ka
operaatorit ++ (argumendi järel); selle semantika on nagu C-s, näiteks
2++ väärtus tuleb 3.
3. Täienda
ülalesitatud programmi nii et Pisi-Algolis võiks kasutada avaldistes ka
C-keele tingimusoperaatorit tingimus ? a
: b - kui tingimus on
tõene, on tulemuseks a, kui ei,
siis b, näit 3=5?4:6 väärtuseks on 6; tingimuse
moodustamisel kasutatakse samu loogilisi operaatoreid kui if-lauseski.
