Tsükli transleerimine Antlri abil

Pisi-Algoli määratud arvu kordustega tsüklkäsk oli kirjeldatud produktsiooniga

Tsükkel FOR Omistamine UNTIL Avaldis DO Programm ENDLOOP

Selle semantika on lihtne: osas Omistamine antakse mingile täisarvulisele muutujale väärtus (s.t. siin on omistamiskäsk) ja selle muutuja väärust suurendatakse tsükli lõpus, st. enne lekseemi ENDLOOP; käske Programm korratakse, kui selle muutuja väärtus on ≤ Avaldis; kui muutuja väärtus enam pole ≤ Avaldis, siirdutakse programmi järgmise käsu täimisele.

Transleerimisel tuleb mitteterminali Avaldis arvutamise (transleerimise) järel ilmselt kaks GOTO käsku: esimene, tingimuskäsk (IF...GOTO...) suunab osa Programm esimese käsu arvutamisele; teine (täidetakse juhul kui esimeses olev tingimus enam pole tõene) - kogu tsüklikäsu transleerimisel saadud viimasele käsule järgnevale reale; osa Programm transleerimisel saadud käsud lõpetab suunamiskäsk GOTO esimesele IF...GOTO... käsule.

Tingimuslikus suunamises IF...GOTO võrreldakse osas Omistamine algväärtustatud muutujat, seega selle kirjutamiseks peab teadma, millisele muutujale osas Omistamine väärus anti. Selle info saamiseks ja kasutamiseks on otstarbekas kogu tsüklile vastava abstraktse süntaksi puusse moodustada tipp Rajad, mis ühendab alampuud Omistamine ja Avaldis.

Et transleeritud kolmeaadressilises koodis ei tuleks suunamisi olematule reale (GOTO-d if- ja tsüklilauses), on kogu programmi lõppu lisatud rida käsuga END ja lisatud vaheaste: mitteterminal programm genereerib käsu END ja teiseneb mitteterminaliks programm1, mida seejärel kasutatakse if-lauses ja tsüklis.

Sellise arvutusskeemi realiseerivad Antlr-i grammatikakirjeldus ja puukonstruktor: 

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';
}

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

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

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

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

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

tegur:   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* '}'!
	;

ID  	:  LET(LET|NUM)* ;
INT 	:  NUM+;
fragment NUM :   '0'..'9' ;
fragment LET : ('a'..'z'|'A'..'Z') ;	
SEMICOLON : ';';
SUUREM 	: '>';
VAIKSEM : '<';
VORDNE 	: '==';
NEWLINE:'\r'? '\n' ;
WS  :   (' '|'\t')+ {skip();} ;
;
ja puuläbija: 
tree grammar Eval;
options {
    tokenVocab=p_algol;
    ASTLabelType=CommonTree;
}

@header {
import java.util.TreeMap;
}
@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 java.util.Map codeLine = new java.util.TreeMap();
public static String getTempVariable()
{
	return ("T"+(i++));
};
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)
{
	return (var1 + ":=" + left + op + right);
};
public static String getomist(String left, String right)
{
	return ( left + ":=" + right);
};
}
prog : prog1 {out(getLineNumber(),"END");};
prog1:   statement+ ;

statement: omist
	| if_lause
	| tsykkel
	;	

omist:   ^('=' ID e=avald)
        {out(getLineNumber(),getomist($ID.text,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 = (String)($ID.text);
        }
    |   INT  {s = (String)($INT.text);}
    ;
if_lause : 
	^(IF nr=tingimus lnr=then_osa)
	{out(nr, "GOTO "+lnr);}
	;
then_osa returns [String lnr] : 
	^(THEN nr=then_statements lnr1=else_osa)
	{if (lnr1=="")
	{lnr=Integer.toString(ln+1);}
	else
	{out(nr, "GOTO "+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+" GOTO "+(n+2));
	nr=getLineNumber();}
	|^(VAIKSEM e1=avald e2=avald)
	{n=getLineNumber();
	out(n,"IF "+e1+"<"+e2+" GOTO "+(n+2));
	nr=getLineNumber(); }
	|^(VORDNE e1=avald e2=avald)
	{n=getLineNumber();
	out(n,"IF "+e1+"=="+e2+" GOTO "+(n+2));
	nr=getLineNumber();}
	;
tsykkel : 
	^(FOR nr=rajad prog1)
	{
		n=getLineNumber();
		out(n,getExpr(tsykli_id,tsykli_id,"+","1")); //tsyklimuutuja suurendamine
		n=getLineNumber();
		out(n, "GOTO "+(nr)); //tagasipöördumine tsykli lõpus
		out(nr+1, "GOTO "+(n+1)); //tsyklist välja ! (nr+1 jaoks jättis rajad rea!)
	}
;
rajad returns [int nr=0;] : 
	^(UNTIL id=algv e=avald)
	{
		n=getLineNumber();
		out(n, "IF "+id+"<"+e+" GOTO "+(n+2));
		nr=n;
		n=getLineNumber(); // tsyklist välja viiva GOTO-jaoks ruum
	}
; 
algv returns [String var="";] : 
	^('=' id=ID e=avald)
	{
		var = $ID.text; 
		tsykli_id=var;  //tsyklimuutuja väljastatakse (return) lõpetamise kontrolliks!
		out(getLineNumber(), getomist(var,e)); //tsyklimuutuja algväärtustamine
	}
;
See sisend genereerib translaatori, mis teisendab Pisi-Algolis kirjutatud Fibonacci arvude arvutamise programmi 
F0 := 0;
F1 := 1;
FOR I := 2 UNTIL 10 DO 
F2 := F0 + F1;
F0 := F1;
F1 := F2;
ENDLOOP;
kolmeaadressiliseks koodiks: 
1:	 F0:=0
2:	 F1:=1
3:	 I:=2
4:	 IF I<10 GOTO 6
5:	 GOTO 12
6:	 T0:=F0+F1
7:	 F2:=T0
8:	 F0:=F1
9:	 F1:=F2
10:	 I:=I+1
11:	 GOTO 4
12:	 END
Ülesandeid:
1. switchKoosta transleerimisskeem switch-lause transleerimiseks; switch-lause (konkreetne) süntaks on nagu Java-keeles:

switch(Choise)
{ case Opt1:
...
break;
case Opt2:
...
break;
...
default :
...
break; }

kus Opt1, Opt2, ... on kas täisarvud või stringid; switch-lause semantikat selgitab kõrvalolev skeem.
2. Ülal on vaadeldud nn määratud tsüklit - tsükli keha kordamiste arv on määratud (ülalvaadeldud tsüklikäsu analoog Basic-us oleks näiteks FOR I=1 UNTIL I=10 DO ... ). Koosta transleerimiskeem määramata tsüklilausete WHILE tingimus block ja DO block WHILE tingimus; nende semantika on nagu Java-s: blokki täidetakse kuni tingimus on tõene, kuid esimesel juhul on kontroll enne bloki täitmist (kui tingimus on kohe tõene, ei täideta blokki üldse) ja teisel juhul - pärast bloki täitmist (seega blokk täidetakse vähemalt kord).
3. Koosta transleerimisskeemid if-then(else) ja tsüklikäskude transleerimiseks, kui loogilise tingimuse koostamisel võib kasutada ka loogilisi operaatoreid AND, OR.
4. AND-optimiseerimineKoosta transleerimisskeemid if-then(else) ja tsüklikäskude transleerimiseks, kui loogilise tingimuse koostamisel võib kasutada ka loogilisi operaatoreid AND, OR ja skeem peab operaatorite AND, OR transleerimisel kasutama loogiliste avaldiste optimiseerimisi, näiteks käsu IF (a OR b) THEN block transleerimise semantika on esitatud kõrvaloleval skeemil - kui a on tõene, on kogu tingimus a OR b tõene ja b-d pole enam vaja kontrollida.
Küsimused, probleemid: ©2004 Jaak Henno