Приведенный ниже интерпретатор строит промежуточное представление
подлежащей исполнению программы в виде дерева и выполняет его.
Для тестирования можно использовать ту же нерекурсивную
программу вычисления числа Фибоначчи с заданным номером
(в тексте с номером 29). На компьютере с процессором
Intel Core i5-4690S/3200МГц она выполняется около
полутора секунд. Это более чем в десять раз быстрее,
чем непосредственная интерпретация,
но все равно очень медленно.
Примерно с такой же скоростью работает интерпретатор P-кода Pascal-S.
int S[100],
C[100],
P,
M,
N,
F;
begin
P = 0;
S[P] = 29;
C[P] = 0;
P = P + 1;
while P > 0 do
P = P - 1;
F = 0;
if C[P] = 0 then
if S[P] < 2 then
C[P] = 1;
P = P + 1;
F = 1;
end
if F = 0 then
N = S[P];
S[P] = N - 1;
C[P] = 0;
P = P + 1;
S[P] = N - 2;
C[P] = 0;
P = P + 1;
F = 1;
end
end
if F = 0 then
if P > 0 then
M = S[P];
P = P - 1;
if C[P] = 0 then
N = S[P];
S[P] = M;
C[P] = 1;
P = P + 1;
S[P] = N;
C[P] = 0;
P = P +1;
F = 1;
end
if F = 0 then
S[P] = S[P] + M;
P = P + 1;
end
end
end
end
write S[0];
blank
end
Текст интерпретатора:
include "sys4lnx.inc"
define @emSIZE "Name too long"
define @emEOF "End of file"
define @emNUMBER "Digit expected"
define @emNAME "Name expected"
define @emEMPTY "Empty array"
define @emBRACKET "Bracket expected"
define @emCOMMA "Comma expected"
define @emSEMICOLON "Semicolon expected"
define @emBEGIN "begin expected"
define @emDUP "Duplicate name usage"
define @emLVALUE "Variable expected"
define @emTYPE "Incompatible types"
define @emPRTY "Two operators together"
define hpSIZE 4096
define tbSIZE 4096
define ntSIZE 1024
define dtSIZE 128
define idSIZE 16
define opOR 1
define opAND 2
define opLT 3
define opLE 4
define opEQ 5
define opNE 6
define opGE 7
define opGT 8
define opADD 9
define opSUB 10
define opMUL 11
define opDIV 12
define opNOT 13
define opNEG 14
/*enum NODE_ID
idNUMBER,
idVARIABLE,
idADDRESS,
idBOOL,
idCOMP,
idCALC,
idCOND,
idIF,
idCASE,
idWHILE,
idREPEAT,
idPRINT,
idDATA,
idASSIGN,
idMOVE
end*/
define idNUMBER 1
define idVARIABLE 2
define idADDRESS 3
define idBOOL 4
define idCOMP 5
define idCALC 6
define idCOND 7
define idIF 8
define idCASE 9
define idWHILE 10
define idREPEAT 11
define idPRINT 12
define idBLANK 13
define idDATA 14
define idASSIGN 15
define idMOVE 16
struct NODE
//NODE_ID ID;
int ID;
int Value;
int Left;
int Right;
end
struct DATA
char Name [idSIZE];
int Ofs;
int Index;
end
NODE Node [ntSIZE];
int nNode;
int Heap [hpSIZE];
DATA Data [dtSIZE];
int nData;
char Text [tbSIZE];
word pText;
word nText;
char Name [128];
word Line;
word F;
/*void @Ptr(word Seg, Ofs)
void @P1=@Ofs;
void @@P2=@P1;
return @P2;
end*/
word isalpha(char Ch)
if 'a'<=Ch & Ch<='z' then
return 0;
end
if 'A'<=Ch & Ch<='Z' then
return 0;
end
if Ch='_' then
return 0;
end
return 1;
end
word isdigit(char Ch)
if '0'<=Ch & Ch<='9' then
return 0;
end
return 1;
end
word strlen(char @Buff)
word P=0;
while Buff[P]!=#0 do
inc P;
end
return P;
end
word strcmp(char @St1, @St2)
word P=0;
/*while TRUE*/ do
if St1[P]!=St2[P] then
return 1;
end
if St1[P]=#0 then
return 0;
end
inc P;
end
end
char @strcpy(char @Dst, @Src)
word P=0;
while Src[P]!=#0 do
Dst[P]=Src[P];
inc P;
end
Dst[P]=#0;
return @Dst;
end
char @strcat(char @Dst, @Src)
word P=strlen(@Dst);
word Q=0;
while Src[Q]!=#0 do
Dst[P]=Src[Q];
inc P;
inc Q;
end
Dst[P]=#0;
return @Dst;
end
/*word GetPSP()
asm mov AH,62H
asm int 21H
asm mov AX,BX
end
word open(char @Name)
asm push DS
asm mov AH,3DH
asm mov AL,00H
asm mov DX,SS:[BP+6]
asm mov DS,DX
asm mov DX,SS:[BP+4]
asm int 21H
asm db 73H, 03H
asm mov AX,0FFFFH
asm pop DS
end
word read(word F; void @Buff; word N)
asm push DS
asm mov AH,3FH
asm mov BX,SS:[BP+10]
asm mov CX,SS:[BP+4]
asm mov DX,SS:[BP+8]
asm mov DS,DX
asm mov DX,SS:[BP+6]
asm int 21H
asm pop DS
end
void close(word F)
asm mov AH,3EH
asm mov BX,SS:[BP+4]
asm int 21H
end
void putc(char Ch)
asm mov AH,2
asm mov DL,SS:[BP+4]
asm int 21H
end
void puts(char @St)
word P=0;
while St[P]!=#0 do
putc(St[P]);
inc P;
end
end*/
word str(word N; word S; char @Buff)
if S>0 then
dec S;
end
word P=0;
if N>=10 then
P=str(N/10,S,@Buff);
else
while P<S do
Buff[P]=' ';
inc P;
end
end
char @D = "0123456789";
Buff [P]=D[N%10];
return P+1;
end
char @Str(word N; word S)
char @P="00000";
P[str(N,S,@P)]=#0;
return @P;
end
void Stop(char @EM)
//putc(#13);
puts("~r");
puts(@Name);
//putc('(');
puts("(");
puts(@Str(Line,0));
//putc(')');
puts(")");
if (strlen(@EM)>0) then
puts(": ");
puts(@EM);
end
close (F);
//asm mov AX,4C00H
//asm int 21H
halt(0);
end
word Val(char @Buff)
char @D = "0123456789";
word P = 0;
word L = 0;
word H = 0;
while (Buff[P]!=#0) do
word S=0;
/*while TRUE*/ do
if D[S]=#0 then
Stop(@emNUMBER);
end
if D[S]=Buff[P] then
exit
end
inc S;
end
S=10*L+S;
L=S%256;
S=10*H+S/256;
H=S%256;
S=S/256;
if S>0 then
Stop(@emNUMBER);
end
inc P;
end
return 256*H+L;
end
char Read()
if pText>=nText then
nText=read(F,@Text,tbSIZE);
if nText<1 then
Stop(@emEOF);
end
pText=0;
end
return Text[pText];
end
void Next()
inc pText;
end
char @Scan(char @Buff)
word N=0;
/*while TRUE*/ do
while Read()=#09 | Read()=#10 | Read()=#13 | Read()=#32 do
if Read()=#10 then
inc Line;
if Line%100=0 then
//putc(#13);
puts("~r");
puts(@strcat(@strcat(@strcat(@strcpy(@Buff,@Name),"("),@Str(Line,0)),")"));
end
end
Next();
end
if Read()='/' then
Next();
if Read()='*' then
Next();
inc N;
end
if N>0 then
loop
end
if Read()='/' then
while Read()!=#10 do
Next();
end
loop
end
return @strcpy(@Buff,"/");
end
if N=0 then
exit
end
if Read()='*' then
Next();
if Read()='/' then
Next();
dec N;
end
loop
end
Next();
end
word P=0;
while isalpha(Read())=0 | isdigit(Read())=0 do
Buff[P]=Read();
inc P;
if P>=idSIZE then
Stop(@emSIZE);
end
Next();
end
if P>0 then
Buff[P]=#0;
return @Buff;
end
if Read()='!' then
Next();
if Read()='=' then
Next();
return @strcpy(@Buff,"!=");
end
return @strcpy(@Buff,"!");
end
if Read()='<' then
Next();
if Read()='=' then
Next();
return @strcpy(@Buff,"<=");
end
return @strcpy(@Buff,"<");
end
if Read()='>' then
Next();
if Read()='=' then
Next();
return @strcpy(@Buff,">=");
end
return @strcpy(@Buff,">");
end
if Read()=':' then
Next();
if Read()='=' then
Next();
return @strcpy(@Buff,":=");
end
return @strcpy(@Buff,":");
end
Buff[0]=Read();
Buff[1]=#0;
Next();
return @Buff;
end
int Find(char @Name)
int P=0;
while P<nData do
if strcmp(@Data[P].Name,@Name)=0 then
return P;
end
inc P;
end
return -1;
end
int Expr(int Prty; char @Buff)
int P1=nNode;
select
case strcmp(@Buff,"(")=0:
P1=Expr(0,@Scan(@Buff));
if strcmp(@Buff,")")!=0 then
Stop(@emBRACKET);
end
Scan(@Buff);
case strcmp(@Buff,"!")=0:
P1=Expr(5,@Scan(@Buff));
if Node[P1].ID!=idBOOL then
Stop(@emTYPE);
end
if Node[P1].ID!=idBOOL & Node[P1].ID!=idCOMP then
Stop(@emTYPE);
end
Node[nNode].ID = idBOOL;
Node[nNode].Value= opNOT;
Node[nNode].Left = P1;
Node[nNode].Right=-1;
P1 = nNode;
inc nNode;
case strcmp(@Buff,"-")=0:
P1=Expr(5,@Scan(@Buff));
if Prty>0 then
Stop(@emPRTY);
end
if Node[P1].ID=idBOOL | Node[P1].ID=idCOMP then
Stop(@emTYPE);
end
Node[nNode].ID = idCALC;
Node[nNode].Value= opNEG;
Node[nNode].Left = P1;
Node[nNode].Right=-1;
P1 = nNode;
inc nNode;
case isdigit(Buff)=0:
Node[nNode].ID = idNUMBER;
Node[nNode].Value= Val(@Buff);
Node[nNode].Left =-1;
Node[nNode].Right=-1;
inc nNode;
Scan(@Buff);
default:
int N=Find(@Buff);
if N<0 then
Stop(@emNAME);
end
Node[nNode].ID = idVARIABLE;
Node[nNode].Value= Data[N].Ofs;
Node[nNode].Left =-1;
Node[nNode].Right=-1;
inc nNode;
if Data[N].Index>0 then
if strcmp(@Scan(@Buff),"[")!=0 then
Stop(@emBRACKET);
end
Node[P1].Left=Expr(0,@Scan(@Buff));
if strcmp(@Buff,"]")!=0 then
Stop(@emBRACKET);
end
end
Scan(@Buff);
end
/*while TRUE*/ do
//NODE_ID ID;
int ID;
int Op;
int P;
select
case strcmp(@Buff,"|")=0:
ID=idBOOL;
Op=opOR;
P =1;
case strcmp(@Buff,"&")=0:
ID=idBOOL;
Op=opAND;
P =1;
case strcmp(@Buff,"<")=0:
ID=idCOMP;
Op=opLT;
P =2;
case strcmp(@Buff,"<=")=0:
ID=idCOMP;
Op=opLE;
P =2;
case strcmp(@Buff,"=")=0:
ID=idCOMP;
Op=opEQ;
P =2;
case strcmp(@Buff,"!=")=0:
ID=idCOMP;
Op=opNE;
P =2;
case strcmp(@Buff,">=")=0:
ID=idCOMP;
Op=opGE;
P =2;
case strcmp(@Buff,">")=0:
ID=idCOMP;
Op=opGT;
P =2;
case strcmp(@Buff,"+")=0:
ID=idCALC;
Op=opADD;
P =3;
case strcmp(@Buff,"-")=0:
ID=idCALC;
Op=opSUB;
P =3;
case strcmp(@Buff,"*")=0:
ID=idCALC;
Op=opMUL;
P =4;
case strcmp(@Buff,"/")=0:
ID=idCALC;
Op=opDIV;
P =4;
default:
P =0;
end
if P<=Prty then
exit
end
int P2=Expr(P,@Scan(@Buff));
select
case ID=idBOOL:
if Node[P1].ID!=idBOOL & Node[P1].ID!=idCOMP then
Stop(@emTYPE);
end
if Node[P2].ID!=idBOOL & Node[P2].ID!=idCOMP then
Stop(@emTYPE);
end
case ID=idCOMP | ID=idCALC:
if Node[P1].ID=idBOOL | Node[P1].ID=idCOMP then
Stop(@emTYPE);
end
if Node[P2].ID=idBOOL | Node[P2].ID=idCOMP then
Stop(@emTYPE);
end
end
Node[nNode].ID =ID;
Node[nNode].Value=Op;
Node[nNode].Left =P1;
Node[nNode].Right=P2;
P1 = nNode;
inc nNode;
end
return P1;
end
int Ctrl(char @Buff)
int P1=nNode;
select
case strcmp(@Buff,"if")=0:
strcpy(@Buff,"elseif");
int @P2=@Node[nNode].Left;
Node[nNode].ID=idIF;
inc nNode;
while strcmp(@Buff,"end")!=0 do
select
case strcmp(@Buff,"elseif")=0:
P2 =nNode;
@P2=@Node[nNode].Right;
Node[nNode].ID =idCASE;
Node[nNode].Left=nNode+1;
inc nNode;
int P3 =nNode;
int @P4=@Node[nNode].Right;
Node[nNode].ID=idCOND;
inc nNode;
Node[P3].Left=Expr(0,@Scan(@Buff));
/*while TRUE*/ do
Scan(@Buff);
if strcmp(@Buff,"elseif")=0 then
exit
end
if strcmp(@Buff,"else")=0 then
exit
end
if strcmp(@Buff,"end")=0 then
exit
end
P4 =Ctrl(@Buff);
@P4=@Node[P4].Right;
end
P4=-1;
case strcmp(@Buff,"else")=0:
P2 =nNode;
@P2=@Node[nNode].Right;
Node[nNode].ID =idCASE;
Node[nNode].Left=nNode+1;
inc nNode;
int @P4=@Node[nNode].Right;
Node[nNode].ID = idCOND;
Node[nNode].Left=-1;
inc nNode;
while strcmp(@Scan(@Buff),"end")!=0 do
P4 =Ctrl(@Buff);
@P4=@Node[P4].Right;
end
P4=-1;
end
end
P2=-1;
case strcmp(@Buff,"while")=0:
Node[nNode].ID =idWHILE;
Node[nNode].Left=nNode+1;
inc nNode;
int P2=nNode;
int @P3=@Node[nNode].Right;
Node[nNode].ID=idCOND;
inc nNode;
Node[P2].Left=Expr(0,@Scan(@Buff));
while strcmp(@Scan(@Buff),"end")!=0 do
P3 = Ctrl(@Buff);
@P3=@Node[P3].Right;
end
P3=-1;
case strcmp(@Buff,"repeat")=0:
int @P2=@Node[nNode].Left;
Node[nNode].ID=idREPEAT;
inc nNode;
while strcmp(@Scan(@Buff),"until")!=0 do
P2=Ctrl(@Buff);
@P2=@Node[P2].Right;
end
P2 =nNode;
@P2=@Node[nNode].Left;
Node[nNode].ID = idCOND;
Node[nNode].Right=-1;
inc nNode;
P2=Expr(0,@Scan(@Buff));
if strcmp(@Buff,";")!=0 then
Stop(@emSEMICOLON);
end
case strcmp(@Buff,"print")=0 | strcmp(@Buff,"write")=0:
inc nNode;
Node[P1].ID =idPRINT;
int @P2=@Node[P1].Left;
/*while TRUE*/ do
int P3=Expr(0,@Scan(@Buff));
P2 =nNode;
@P2=@Node[nNode].Right;
Node[nNode].ID =idDATA;
Node[nNode].Left=P3;
inc nNode;
if strcmp(@Buff,";")=0 then
exit
end
if strcmp(@Buff,",")!=0 then
Stop(@emCOMMA);
end
end
P2=-1;
case strcmp(@Buff,"blank")=0:
inc nNode;
Node[P1].ID =idBLANK;
Node[P1].Left =-1;
default:
Node[nNode].ID=idASSIGN;
inc nNode;
int P2=Expr(5,@Buff);
if strcmp(@Buff,":=")!=0 then
if strcmp(@Buff,"=")!=0 then
Stop(@emSEMICOLON);
end
end
int P3=Expr(0,@Scan(@Buff));
if strcmp(@Buff,";")!=0 then
Stop(@emSEMICOLON);
end
if Node[P2].ID!=idVARIABLE then
Stop(@emLVALUE);
end
Node[P2] .ID =idADDRESS;
Node[P1] .Left =nNode;
Node[nNode].ID =idMOVE;
Node[nNode].Left =P2;
Node[nNode].Right=P3;
inc nNode;
end
return P1;
end
int Exec(int P)
select
case Node[P].ID=idNUMBER:
return Node[P].Value;
case Node[P].ID=idVARIABLE:
int Ofs=Node[P].Value;
if Node[P].Left>=0 then
Ofs=Ofs+Exec(Node[P].Left);
end
return Heap[Ofs];
case Node[P].ID=idADDRESS:
int Ofs=Node[P].Value;
if Node[P].Left>=0 then
Ofs=Ofs+Exec(Node[P].Left);
end
return Ofs;
case Node[P].ID=idBOOL:
select
case Node[P].Value=opOR:
if Exec(Node[P].Left)!=0 then
return 1;
end
return Exec(Node[P].Right);
case Node[P].Value=opAND:
if Exec(Node[P].Left)=0 then
return 0;
end
return Exec(Node[P].Right);
case Node[P].Value=opNOT:
if Exec(Node[P].Left)=0 then
return 1;
else
return 0;
end
end
case Node[P].ID=idCOMP:
int A=Exec(Node[P].Left);
int B=Exec(Node[P].Right);
select
case Node[P].Value=opLT:
if A<B then
return 1;
else
return 0;
end
case Node[P].Value=opLE:
if A<=B then
return 1;
else
return 0;
end
case Node[P].Value=opEQ:
if A=B then
return 1;
else
return 0;
end
case Node[P].Value=opNE:
if A!=B then
return 1;
else
return 0;
end
case Node[P].Value=opGE:
if A>=B then
return 1;
else
return 0;
end
case Node[P].Value=opGT:
if A>B then
return 1;
else
return 0;
end
end
case Node[P].ID=idCALC:
if Node[P].Value=opNEG then
return -Exec(Node[P].Left);
end
int A=Exec(Node[P].Left);
int B=Exec(Node[P].Right);
select
case Node[P].Value=opADD:
return A+B;
case Node[P].Value=opSUB:
return A-B;
case Node[P].Value=opMUL:
return A*B;
case Node[P].Value=opDIV:
return A/B;
end
case Node[P].ID=idIF:
P=Node[P].Left;
while P>=0 do
if Node[Node[P].Left].Left<0 then
P=Node[Node[P].Left].Right;
while P>=0 do
Exec(P);
P=Node[P].Right;
end
exit
end
if Exec(Node[Node[P].Left].Left)!=0 then
P=Node[Node[P].Left].Right;
while P>=0 do
Exec(P);
P=Node[P].Right;
end
exit
end
P=Node[P].Right;
end
case Node[P].ID=idWHILE:
P=Node[P].Left;
while Exec(Node[P].Left)!=0 do
int P1=Node[P].Right;
while P1>=0 do
Exec(P1);
P1=Node[P1].Right;
end
end
case Node[P].ID=idREPEAT:
repeat
int P1=Node[P].Left;
while Node[P1].Right>=0 do
Exec(P1);
P1=Node[P1].Right;
end
until Exec(Node[P1].Left)=1;
case Node[P].ID=idPRINT:
P=Node[P].Left;
while P>=0 do
int N=Exec(Node[P].Left);
if N<0 then
N=-N;
//putc('-');
puts("-");
else
//putc(' ');
puts(" ");
end
puts(@Str(N,5));
P=Node[P].Right;
end
//putc(#13);
//putc(#10);
//puts("~r~n");
case Node[P].ID=idBLANK:
puts("~r~n");
case Node[P].ID=idASSIGN:
P=Node[P].Left;
Heap[Exec(Node[P].Left)]=Exec(Node[P].Right);
end
return 0;
end
begin
//byte @Size=@Ptr(GetPSP(),128);
//char @Parm=@Ptr(GetPSP(),129);
//char @Parm=@GetCommandLine();
word nArg;
inline 0x8B, 0x45, 0x04; // mov EAX, [EBP+ 4]
inline 0x89, 0x45, 0xFC; // mov [nArg], EAX
char @Parm="";
if nArg>=2 then
inline 0x8B, 0x45, 0x0C; // mov EAX, [EBP+12]
inline 0x89, 0x45, 0xF8; // mov [Parm], EAX
end
int I=0;
/*while /*I<Size*/ Parm[I]!='~0' & Parm[I]!=' ' do
inc I;
end
while /*I<Size &*/ Parm[I] =' ' do
inc I;
end*/
int K=0;
while /*I<Size*/ Parm[I]!='~0' & Parm[I]!=' ' do
Name[K]=Parm[I];
inc K;
inc I;
end
Name[K]=#00;
if K<1 then
return
end
F=open(@Name);
//if F=$FFFF then
if F=0xFFFFFFFF then
puts("Can't oen file");
return
end
Line =1;
pText=0;
nText=0;
nNode=0;
nData=0;
//Compilation
char Buff [128];
int Ofs=0;
while strcmp(@Scan(@Buff),"int")=0 do
/*while TRUE*/ do
if isalpha(Scan(@Buff))!=0 then
Stop(@emNAME);
end
if Find(@Buff)>=0 then
Stop(@emDUP);
end
strcpy(@Data[nData].Name,@Buff);
Data [nData].Ofs =Ofs;
Data [nData].Index=0;
int N=1;
if strcmp(@Scan(@Buff),"[")=0 then
N=Val(@Scan(@Buff));
if N=0 then
Stop(@emEMPTY);
end
Data[nData].Index=N;
if strcmp(@Scan(@Buff),"]")!=0 then
Stop(@emBRACKET);
end
Scan(@Buff);
end
Ofs=Ofs+N;
inc nData;
if strcmp(@Buff,";")=0 then
exit
end
if strcmp(@Buff,",")!=0 then
Stop(@emCOMMA);
end
end
end
if strcmp(@Buff,"begin")!=0 then
Stop(@emBEGIN);
end
int Root;
int @P1=@Root;
while strcmp(@Scan(@Buff),"end")!=0 do
P1 =Ctrl(@Buff);
@P1=@Node[P1].Right;
end
P1=-1;
close(F);
//Interpretation
int P2 =0;
while P2>=0 do
Exec (P2);
P2=Node[P2].Right;
end
end