Pisi-Algol HLA assemblerkoodiks

Pisi-Algoli transleerimiseks HLA assemblerkoodiks on tarvis muuta vaid väljundi genereerimise tegevusi getExpr ja getomist, kogu programmi loogika jääb täpselt samaks.

Pisi-Algoli suunamiskäskude GOTO-de asemele tulevad assembleri suunamiskäsud jmp. Ka aritmeetiliste avaldiste arvutamine muutub veidi: assembleris peab üks operand olema register ja ka tulemus saadakse registris, seega kolmeaadressilise koodi omistuskäsk X := Y op Z, kus op element {+, -, *} muutub HLA koodiridadeks:

mov(y, eax);
m_op(z, eax);
mov(eax, x);

kus m_op on operatsiooni op kolmetäheline mnemooniline tähistus: + asemel tuleb add, - asemel sub ja * asemel mul. Veidi keerulisem on jagamise sooritamine, kolmeaadressilise koodi omistamine X := Y / Z teiseneb ridadeks:

mov(y, eax);
cdq();
idiv(z, edx:eax);
mov(eax, x);

Kolmeaadressilise koodi jaoks polnud väljundkäskudel mõtet, kuid HLA-s on, sellepärast on Pisi-Algolile lisatud ka väljundkäsk kujul PRINT arg; kus arg on kas identifikaator (transleerimisel määratakse sellele HLA-s kümne sümboli pikkune tekstiväli), tekstistring või reavahetusmärk RV (transleeritakse HLA reavahetussümboliks nl).

Järgnevas on Antlr-i sisndfail, mis genereerib Pisi-Algoli translaatori HLA-ks. Kuna HLA-s peab muutujad deklareerima, siis tuleb moodustada ka nimede (siin vaid identifikaatorid) tabel. Kuna Pisi-Algol-is deklaratsioone ei ole, kogutakse omistamislauses vasakul olevad identifikaatorid puu läbimise ajal Java klassi java.util.Set andmestruktuuri idents - see ongi siin nimede tabel. Nimede tabeli moodustamine võimaldab teha ka semantilist kontrolli: kas omistamislauses paremal pool olevatel identifikaatoritel on juba väärtus? Pisi-Algolis võis identifikaator saada väärtuse vaid siis, kui ta enne seda esines kusagil omistamislause vasakul pool, s.t. on juba kantud nimede tabelisse; kui teda seal pole, teatatakse veast. Järgnevas on süntaksigrammatika ja puuläbija grammatika tekstid.

grammar p_algol;
options {
    output=AST;
    ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}

tokens {
IF='IF';
THEN = 'THEN';
ELSE = 'ELSE';
ENDIF = 'ENDIF';
FOR = 'FOR';
DO = 'DO';
UNTIL = 'UNTIL';
ENDLOOP = 'ENDLOOP';
PRINT = 'PRINT';
RV = 'RV';
}

prog :	(NEWLINE!)* prog1 ;
prog1:   ( statement  (NEWLINE!)* )+ ;

statement 
	: omist SEMICOLON!
	| if_lause SEMICOLON!
	| tsykkel SEMICOLON!
	| print_lause SEMICOLON!
	| blokk
	;

omist:   ID '='^ avald   //-> ^('=' ID expr)
        //->
    ;

avald:   yksl (('+'^|'-'^) yksl)*
    ; 

yksl
    :   tegur ('*'^ tegur)*
    ; 

tegur : atom (ASTE^ atom)? ;
atom :  INT 
	| ID 
	| '('! avald ')'! ;

if_lause : IF^ tingimus then_osa
	;
then_osa :
	THEN^ then_laused else_osa
	;
tingimus: 
	avald (SUUREM^|VAIKSEM^|VORDNE^) avald
	;
then_laused: 
	statement 
	;
else_osa : 
	ELSE^ statement ENDIF!
	| ENDIF!
	;

tsykkel : FOR^ rajad DO! prog ENDLOOP! ;
rajad : algv UNTIL^ loppv;
algv : omist;
loppv : avald;	 
blokk 	: '{'! statement* '}'!
	;
print_lause: PRINT^  pavald;
pavald : ID | TEKST | RV  ;

ID  	:  LET(LET|NUM)* ;
INT 	:  NUM+;
fragment NUM :   '0'..'9' ;
fragment LET : ('a'..'z'|'A'..'Z') ;	
SEMICOLON : ';';
SUUREM 	: '>';
VAIKSEM : '<';
VORDNE 	: '==';
ASTE : '^' ; 
TEKST 	:'"' (LET|NUM|' '|'-'|'_')* '"';	
NEWLINE:'\r'? '\n' ;
WS  :   (' '|'\t')+ {skip();} ;


tree grammar Eval;
options {
    tokenVocab=p_algol;
    ASTLabelType=CommonTree;
}

@header {
import java.util.TreeMap;
import java.util.HashSet;
}
@members {
public static int i = 0; // variables counter
public static int ln = 0; // line number
public static int label = 0; // label number
public static int n = 0;
public static String tsykli_id = "";
public static String id="";
public static java.util.Map codeLine = new java.util.TreeMap();
public static java.util.Set nimed = new java.util.HashSet();
public static String getTempVariable()
{
	String var = "T"+(i++);
	nimed.add(var);
	return(var);
};
public static int getLineNumber()
{
	return (++ln);
};
public static java.util.Map out(int Nr,String s)
	{codeLine.put(new Integer(Nr), new String(s));
	return codeLine;
	};
public static String getExpr(String var1, String left, String op, String right)
	{String lns="";
	if (op.equals("+")){
	lns = "mov("+left+", eax);\nadd("+right+", eax);\nmov(eax,"+ var1 +");";}
	else if ("-".equals(op)) {
	lns = "mov("+left+", eax);\nsub"+right+", eax);\nmov(eax,"+ var1 +");";}
	else if ("*".equals(op)) {
	lns = "mov("+left+", eax);\nmul"+right+", eax);\nmov(eax,"+ var1 +");";}
	else if ("/".equals(op)) {
	lns = "mov("+left+", eax);\ncdq();\nidiv("+right+", edx:eax);\nmov(eax,"+ var1 +");";}
	return(lns);
	}; 
public static String getomist(String left, String right)
	{return ( "mov("+right+", "+left+");");	}; 
}
prog : prog1 ;
prog1:   statement+ ;

statement: omist
	| if_lause
	| tsykkel
	| print_lause
	;	

omist:   ^('=' ID e=avald)
        {id=$ID.text; 
	nimed.add(id);
	out(getLineNumber(),getomist(id,e));}
   	 ;

avald returns [String s] :   
        ^('+' a=avald b=avald) 	{ s=getTempVariable();
    				out(getLineNumber(),getExpr(s,a,"+",b));}
    |   ^('-' a=avald b=avald)  { s=getTempVariable();
				out(getLineNumber(),getExpr(s,a,"-",b));}   
    |   ^('*' a=avald b=avald)  { s=getTempVariable();
				out(getLineNumber(),getExpr(s,a,"*",b));}
    |   ID 
        {s = $ID.text;
         try
		{nimed.contains(s);}
		catch (Exception e) {
        System.err.println("Identifikaator pole vaartust "+s+ e);}
        }
		
    |   INT  {s = (String)($INT.text);}
    ;
if_lause : 
	^(IF nr=tingimus lnr=then_osa)
	{out(nr, "jmp L"+lnr+";");}
	;
then_osa returns [String lnr] : 
	^(THEN nr=then_statements lnr1=else_osa)
	{if (lnr1=="")
	{lnr=Integer.toString(ln+1);}
	else
	{out(nr, "jmp L"+lnr1+";");
	lnr = Integer.toString(nr+1);}
	}
	;
else_osa returns [String lnr=""]:
	^(ELSE prog1)
	{lnr=Integer.toString(ln+1);}
	|
	;
then_statements returns [int nr]: 
	prog1
	{nr=getLineNumber();}
	;
	
tingimus returns [int nr] : 
	^(SUUREM e1=avald e2=avald)
	{n=getLineNumber();
	out(n,"if ("+e1+"+>"+e2+") then \njmp L"+(n+2)+";\nendif;");
	nr=getLineNumber();}
	|^(VAIKSEM e1=avald e2=avald)
	{n=getLineNumber();
	out(n,"if ("+e1+"<"+e2+") then\n jmp L"+(n+2)+";\nendif;");
	nr=getLineNumber(); }
	|^(VORDNE e1=avald e2=avald)
	{n=getLineNumber();
	out(n,"if ("+e1+"=="+e2+") then\n jmp L"+(n+2)+";\nendif;");
	nr=getLineNumber();}
	;
tsykkel : 
	^(FOR nr=rajad prog1)
	{
		n=getLineNumber();
		out(n,"add(1,"+tsykli_id+");");//tsyklimuutuja suurendamine
		n=getLineNumber();
		out(n, "jmp L"+(nr-1)+";");		
		out(nr, "jmp L"+(n+1)+";");  //tsyklist valja ! (nr+1 jaoks jättis rajad rea!)
	}
;
rajad returns [int nr=0] : 
	^(UNTIL id=algv e=avald)
	{
		n=getLineNumber();
		out(n, "if ("+id+"<="+e+") then\n jmp L"+(n+2)+";\nendif;");
		nr=getLineNumber(); // tsyklist valja viiva GOTO-jaoks ruum
	}
	; 
	
algv returns [String var=""] : 
	^('=' id=ID e=avald)
	{
	var = $ID.text; 
	tsykli_id=var;
	nimed.add(var);  //tsyklimuutuja lisatakse nimede tabelisse!
	out(getLineNumber(), getomist(var,e)); //tsyklimuutuja algvaartustamine
	}
	; 
		
print_lause :
	 ^(PRINT  out_str=pavald)
	 { out(getLineNumber(),"stdout.put("+out_str+");");
	 }
	 ;
pavald  returns [String s=""]:
	 TEKST
	{s = (" "+$TEKST.text+" ") ;}
	| ID   {s=$ID.text+":10"; }
	| RV  	{s ="nl";}
	;

Veidi muutub peaprogramm Generate - ta loeb töö algul nimede tabelist nimed identifikaatorid ja lisab igale identifikaatorile deklaratsiooni (siin deklareeritakse nad kõik 32-bitisteks täisarvudeks); peale selle lisab programm transleeritud tekstile esimese ja viimase rea. Kuna HLA märgendid peavad olema kirjutatud identifikaatoritega analoogiliselt (algama kas tähe või allkriipsuga _), on teksti väljastamisel (peaprogrammis Generate) reanumbrite ette lisatud täht L (Label): 

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import java.util.Iterator;
import java.io.*;
 
public class Generate {
    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        p_algolLexer lexer = new p_algolLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        p_algolParser parser = new p_algolParser(tokens);
        p_algolParser.prog_return r = parser.prog();

        // walk resulting tree
        CommonTree t = (CommonTree)r.getTree();
        CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
        Eval walker = new Eval(nodes);
        walker.prog();
        int n = walker.codeLine.size();
     		System.out.println("program proge;");
     		System.out.println("#include( \"stdlib.hhf\" );");
     		System.out.println("static");
     		for (Iterator i = walker.nimed.iterator(); i.hasNext(); ) 
       { System.out.println(i.next()+":  int32;"); }
     	System.out.println("begin proge;");
         for (Iterator it= walker.codeLine.keySet().iterator(); it.hasNext( ); ) {
		Object ckey = it.next();
		System.out.println("L"+ckey+":\t "+ walker.codeLine.get(ckey));
}
    System.out.println("L"+Integer.toString(n+1)+":\t end proge;");    
    }
}

Selle sisendiga genereeritud translaator teisendab Pisi-Algoli programmi

F0 = 1;
F1 = 1;
FOR I = 1 UNTIL 40 DO
F2 = F0 + F1;
F0 = F1;
F1 = F2;
PRINT I;
PRINT "-s arv on ";
PRINT F1;
PRINT RV;
ENDLOOP;
järgnevaks HLA assemblerteksiks:
program proge;
#include( "stdlib.hhf" );
static
I:  int32;
F0:  int32;
F1:  int32;
T0:  int32;
F2:  int32;
begin proge;
L1:	 mov(1, F0);
L2:	 mov(1, I);
L3:	 if (I<=40) then
 jmp L5;
endif;
L4:	 jmp L15;
L5:	 mov(F0, eax);
add(F1, eax);
mov(eax,T0);
L6:	 mov(T0, F2);
L7:	 mov(F1, F0);
L8:	 mov(F2, F1);
L9:	 stdout.put(I:10);
L10:	 stdout.put(" -s Fibonacci arv on " );
L11:	 stdout.put(F1:10);
L12:	 stdout.put(nl);
L13:	 add(1,I);
L14:	 jmp L3;
L15:	 end proge;

Kui see tekst salvestada näiteks failis fib.hla ja transleerida HLA translaatoriga:

HLA fib.hla

saame transleeritud faili fib.exe käivitamisel täpselt samasuguse Fibonacci arvude loetelu, nagu kõigi teiste siin vaadeldud keeltes koostatud programmidega, s.t. meil on nüüd töötav Pisi-Algol-i translaator: 
1 -s Fibonacci arv on          1
         2 -s Fibonacci arv on          1
         3 -s Fibonacci arv on          2
          ...
        39 -s Fibonacci arv on  102334155
        40 -s Fibonacci arv on  165580141

. Loomulikult on see veel väga algeline (puudub sisend, puuduvad reaalarvud jne jne), kuid seda kõike on juba lihtsam teha ehk nagu paarkümmend aastat tagasi öeldi - edasi on kõik "Дело техники!"

Viimasest näitest on ka näha, et "tagant mitmeharulise", s.t. mitmesse väljundkeelde transleeriva translaatori (nagu on Microsoft .net ja gcc translaatorite süsteemid) tegemine on suhteliselt lihtne, kui "esimene ots", s.t. analüüs kuni AST-i saamiseni on juba tehtud (AST on vahekeel) ja need keeled on sama tüüpi, s.t. imperatiivsed - piisab vaid väljundit genereerivate funktsioonide muutmisest. Seda ideed on Antlr-is edasi arendatud nn tekstimustrite (string templates) kasutuselevõtuga. Tekstimustrid on eraldi failid, milles on kirjas translaatori "tagumise otsa" keel, s.t. see, mis genereeritakse AST-ist. See võib olla C++, Python-i, Java VM assemblerkäskude genereerimine (tekst), kuid võib olla ka üsna keerukas süsteem, kus loetakse eraldi failides (või serveritel) olevatest tabelitest, formateeritakse HTML-i ja genereeritakse veebisaidi kasutajaliides (vt näiteks Amazon-i ülikomplitseeritud lehekülgi); Antlr-i tekstimustrite abil on juba aastaid ülal peetud näiteks saiti http://www.jguru.com.

Ülesandeid:
1. Ülalesitatud identifikaatorite väljastamine oli väga primitiivne: kõigile identifikaatoritele määrati samasuur 10 täheruumi pikune märgijada. Täienda Pisi-Algoli trükikäsku nii, et selles võib koos identifikaatoriga määrata ka väljatrükiks kasutatava välja pikkuse, s.t. lubatud oleks näiteks sellised käsud PRINT F:10; PRINT I:2, s.t. F väljastatakse kümnele täheruumi pikkusena ja I - kahe ja HLA-s määratakse samad pikkused; kui kasutaja pole formaati määranud, kasutatakse alati kümmet täheruumi.
2. Täienda Pisi-Algoli väljatrükikäsku ja transleerimist HLA-sse nii, et samas PRINT lauses võiks trükkida suvalise identifikaatorite (formaatidega) ja tekstistringide jada, s.t. et näiteks võiks kirjutada PRINT I:2, "-s Fibonacci arv on ", F1:10;
 3. Täienda Pisi-Algoli omistuslauset ja transleerimist HLA-ks nii, et korraga saaks omistada mitmele identifikaatorile, s.t. Pisi-Algolis oleks lubataud näiteks konstruktsioon
a = b = 10*c + 1
  4. Täienda Pisi-Algolit operaatoritega ++, -- (postfix-kujul, s.t. lubatud oleks näiteks a++, a--, kuid mitte ++a, --a).
  5. Assembleris HLA peab programmil olema nimi (programm algab ja lõpeb nime kasutava reaga; ülalesitatud näiteks on programmi nimeks pandud proge). Täienda Pisi-Algoli grammatikat ja ülalesitatud transleerimisskeemi nii, et ka Pisi-Algoli programm algaks ja lõpeks nime kasutava reaga 
programm Fibo
F0 = 1;
...
end Fibo
ja see nimi muutub ka transleeritud HLA-programmi nimeks.
6. Täienda Pisi-Algoli süntaksit nii, et käsu lõpus võiks eraldaja ; puududa, kui see käsk on oma real ainuke (s.t. seda asendab reavahetus); real võiks olla ka mitu käsku, kuid siis peaks nende vahel olema (vähemalt üks) eraldaja ; ja mitu eraldaja ; järjest poleks ka viga.
7. Täienda Pisi-Algoli nii, et selles saaks kasutada ka reaalarve; reaalarvude operatsioonide transleerimine HLA-sse on kirjeldatud HLA veebisaidil.
8. Täienda Pisi-Algoli nii, et selle tsüklites võiks kasutada ka käsku break (lõpetab kohe tsükli); ka HLA-s saab kasutada tsüklist väljumiseks käske 
break;
breakif( boolean_expression );
Küsimused, probleemid: ©2004-2013 Jaak Henno