Antlr: if-lause

Kui lähtetekst ei ole lineaarne, s.t. järjestikku täidetavate käskude jada, vaid esineb ka suunamisi (näiteks tingimuslause), tekib vajadus muuta käskude sooritamise järjekorda ka transleerimise tulemusena saadavas objektekstis, s.t. seal tuleb kasutada suunamisi GOTO, IF...GOTO. Et suunamiskäske saaks kasutada, tuleb väljundtekst varustada märgenditega; need on lihtsalt täisarvud. Märgendite genereerimiseks käivitatakse mingi alamprotseduur, mis iga uue käsu genereerimisel annab muutujale ln (järgmise käsu reanumber) uue väärtuse.

Kõige "põhilisem" suunamiskäsk on if-käsk, mis tavaliselt esineb kahes versioonis: ilma else-osata ja koos else-osaga. Kui süntaksianalüüsis kasutatakse LL(1) grammatikat, kirjeldatakse mõlemad versioonid tavaliselt koos ühe produktsioonina:

if-lause IF tingimus THEN laused (ELSE laused)? ENDIF

Vaatame algul informatsiooni liikumist if-käsu puus, kui else- osa puudub:

Puuläbija genereerib puud lõppjärjestuses läbides kõige enne tingimus-alampuule vastava koodi. Seejärel jõuab ta tingimus-alampuu tippu (ellips) ja genereerib kaks suunamiskäsku: n IF tingimus GOTO (täidetakse kui puu läbimisel arvutatud loogiline muutuja tingimus on tõene) ja n+1 GOTO ..., mis peab suunama if-käsust edasi, s.t. kogu if-käsu poolt genereeritud koodiosale järgnevale reale. Kuna pärast tingimusele vastava alampuu läbimist hakkab puuläbija töötlema then-lausetele vastavat alampuud (lõppjärjestus!), tuleb esimese, tingimusliku suunamise n IF tingimus GOTO märgendiks ilmselt n+2. Kuid järgmise käsu n+1 GOTO ... märgendit pole siin üldse veel võimalik teada, sest pole teada, kuipalju väljundteksti ridu genereeritakse then-lausete alampuu läbimisel. See info tekib alles siis, kui puuläbija jõuab then-lausetele vastava alampuu läbimise järel then-osa tippu (ellips). Kokku saab viia varem poolikuks jäänud GOTO-käsu reanumbri ja sellesse tuleva märgendi (see on muutuja ln väärtus, kui puuläbija jõuab then-osale vastava alampuu tippu) alles kogu if-lause tipus IF . Tingimusele vastava alampuu tipp saadab sinna reanumbri n+1, then-osale vastava alampuu tipp - märgendi ln ja tipp IF genereerib nüüd täieliku käsu n+1 GOTO ln .

Kui if-käsul on ka else-osa, muutub info liikumine veidi - then-osa lõppu tuleb genereerida veel üks GOTO-käsk, mis juhib else-osast üle, kogu if-lause poolt genereeritud koodile järgnevale reale. Ka selle GOTO-käsu märgendit pole then-osa lõppedes võimalik teada, sest pole teada, kui palju ridu genereeritakse else-osas. Pole isegi teada, kas seda GOTO-käsku on üldse tarvis, sest then-alampuud läbides puuläbija ei "näe", kas else-osa üldse on olemas - kui else-osa pole, pole ka GOTO-käsku tarvis, väljundkoodi täitmine läheb niigi järgmisele reale. Vajaliku info saab kokku alles else-osa läbimisel või (kui seda pole) if-lause kõige ülemises tipus IF, s.t. if-käsu transleerimise lõpetamisel. Tipp IF kontrollib else-osa tipust saadud märgendit ln (string); kui see on tühi, siis else-osa pole ja then-osa lõppu pole GOTO-käsku tarvis genereerida. Kuna selle jaoks rida (s.t. märgend) on siiski varutud, genereerivad paljud puuläbijad siiski selle GOTO-käsu, mis else-osa puudumisel juhib lihtsalt järgnevale reale.

Mõlema juhu koos käsitlemine lihtsustub, kui muuta grammatikaga puu struktuuri - viia (valikuline, s.t. võib olla, võib ka puududa) else-alampuu then-alampuu kõige ülemise tipu alla. Kuna puuläbija jõuab sellesse tippu pärast else-alampuu läbimist (kui seda pole, siis kohe pärast then-lausete alampuu läbimist), on selles tipus kohe olemas muutuja ln väärtus ja selle toimetamine IF-tippu jääb ära.

if then [else]

Puu teisendamiseks, s.t. else-alampuu "allanihutamiseks" tuleb teisendada ülaltoodud if-then-lauset kirjeldavat produktsiooni.

Järgnevas tekstis on abstraktse süntaksi puu (AST-puu) moodustamisel kasutatatud modifikaatoreid ^(tõstab eelneva tipu üles, s.t. teeb sellest alampuu juure) ja ! (jätab eelneva tipu ära), näiteks järgnevad reeglid genereerivad lausest IF a>b THEN x=1; ELSE y=2; ENDIF if_puu sellise abstraktse süntaksi puu:

if_lause :
		"IF"^ tingimus then_osa ;
then_osa :
		"THEN"^ then_laused else_osa ;
else_osa : 
	ELSE^ statement ENDIF!
	| ENDIF!

Tavaliselt võib AST-puu moodustamisel sisendteksti lekseemid ("if", "then", "else") ära jätta (! tipu järel näitab, et seda tippu AST-puu moodustamisel ei kasutata), kuid siin on neid tarvis, sest just nendes tippudes hakkavad toimuma AST-puu läbimisel semantilised tegevused, sellepärast nihutatakse siin need lekseemid vastavate alampuude juureks.

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

Märgendeid ja genereeritud käsuridu on loomulik käsitleda vastavusena märgend käsurida ja salvestada Java andmestruktuuris treemap. Kuna Java järjestab treemap-struktuurid nende indeksi (märgendi) järgi, võimaldab see lisada vajalikud GOTO-käsud hiljem (pole tarvis algul genereerida aukudega käske, kuhu märgend lisatakse hiljem). Selleks lisame puuläbija deklaratsioonidele deklaratsiooni :

public static java.util.Map codeLine = new java.util.TreeMap();

Vastavalt tuleb muuta ka väljundrida genereerivat funktsiooni:

public static java.util.Map out(int Nr, String s)
{
codeLine.put(new Integer(Nr), new String(s));
return codeLine;
};

Info saatmiseks tingimuse, then-osa ja else-osa alampuudest IF-tippu tuleb need deklareerida funktsioonideks, mis väljastavad Java String-tüüpi muutuja.

if_lause
{int nr=0; String lnr="";} :
^('IF' nr=tingimus lnr=then_osa)
{out(nr, "GOTO "+lnr+"\n");
}
;
then_osa returns [String lnr=""]
{int nr=0; String lnr1="";} :
^('THEN' nr=then_statements lnr1=else_osa)
{if (lnr1=="")
{lnr=Integer.toString(ln+1);}
else
{out(nr, "GOTO "+lnr1+"\n");
lnr = Integer.toString(nr+1);}
}
;
else_osa returns [String lnr=""] :
^('ELSE' statement)
{lnr=Integer.toString(ln+1);}
|
; then_statements returns [int nr=0] :
statement
{nr=getLineNumber();
}
; tingimus returns [int nr=0]
{ String e1 = "", e2=""; int n=0;} :
^(SUUREM e1=expr e2=expr)
{n=getLineNumber();
out(n,"IF "+e1+">"+e2+" GOTO "+(n+2)+"\n");
nr=getLineNumber();
}
|^(VAIKSEM e1=expr e2=expr)
{n=getLineNumber();
out(n,"IF "+e1+"<"+e2+" GOTO "+(n+2)+"\n");
nr=getLineNumber();
}
; omist { String e = ""; } :
^(OMIST id:ID e=expr)
{ out(getLineNumber(),getomist((String)id.getText(),e)); }
;

Mõnikord on tarvis puud rohkem modifitseerida, näiteks lisada uusi tippe või muuta tippude järjekorda. Seda saab teha, näidates süntaksigrammatikas AST-puu struktuuri operaatori -> abil (selle kasutamisel ei või samas produktsioonis kasutada modifikaatoreid ! ^). Kui näiteks tingimusoperaatori (tingimus)?then_osa : else_osa jaoks tahetakse analoogilist puud, tuleb süntaksigrammatika tokens-sektsioonis koos tavalises IF-lauses kasutatava lekseemiga IF deklareerida n.õ. "imaginaarne" lekseem IM_IF (token, mida sisendtekstis pole):

tokens {
IF='IF';
IM_IF;
...
}

ja kirjeldada puu moodustamine produktsioonidega (operaatori -> abil puu kirjelduses, s.t. ^ järel esitatakse kõige enne juur, siis selle alluvad):

if_lause : IF^ tingimus then_osa
	|'('tingimus')''?' then_osa -> ^(IM_IF tingimus then_osa)
	...

Selliste uute "imaginaarsete" tippude lisamisega võib moodustada mõlema if-lause vormi jaoks sama struktuuriga puud, s.t. saab kasutada samu semantikareegleid. Näiteks lausetest

IF a>b THEN x=1; ELSE y=2; ENDIF
(a>b)?x=1:y=2;

moodustatakse samasuguse struktuuriga puud (need on väljastatud peapgrogrammile puu tekstina esitamise käsu System.out.println(t.toStringTree()); lisamisega, allesitatud tekstis välja kommenteeritud):

(IF (> a b) (THEN (= x 1) (ELSE (= y 2)))) 
(IM_IF (> a b) (IM_THEN (= x 1) (IM_ELSE (= y 2))))

Järgnevas on if-lause AST-puud moodustav grammatika Avald.g. Programmi tekstis esinevad transleeritava programmeerimiskeele reserveeritud sõnad IF, THEN, ELSE, ENDIF on kirjeldatud osas tokens - siis proovib Antlr mingi tähejada (näit identifikaatori) puhul kasutada kõigepealt neid. Et programmi lõpus (kui lõpus on mingi if-lause) ei tekiks suunamist olematule reale, genereeritakse kogu programmi lõppu käsk END. Kuna mitteterminal programm on tegelikult käskude blokk ja esineb ka if-lauses ja tsüklis (kuid nendesse pole käsku END tarvis), on lisatud vaheaste: mitteterminal programm genereerib käsu END ja teiseneb mitteterminaliks programm1, mida seejärel kasutatakse if-lauses ja tsüklis. :

   grammar Avald;
options {
    output=AST;
    ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}
tokens {
IF='IF';
THEN = 'THEN';
ELSE = 'ELSE';
ENDIF = 'ENDIF';
}
prog :	 prog1;
prog1:   ( statement  (NEWLINE!)* )+ ;

statement 
	: omist SEMICOLON!
	| if_lause 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!
;	 
blokk 	: '{'! statement* '}'!;
ID  :   ('a'..'z'|'A'..'Z')+ ;
INT :   '0'..'9'+ ;
SEMICOLON : ';';
SUUREM 	: '>';
VAIKSEM : '<';
VORDNE 	: '==';
NEWLINE:'\r'? '\n' ;
WS  :   (' '|'\t')+ {skip();} ;

Väljundkoodi genereerib puuläbija, mis on kirjeldatud puugrammatikaga Eval.g:

tree grammar Eval;
options {
    tokenVocab=Avald;
    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 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
	;	

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();}
	;

Peaprogrammis peab nüüd muutuja tulemus asemel välja trükkima Codeline:

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);
        AvaldLexer lexer = new AvaldLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        AvaldParser parser = new AvaldParser(tokens);
        AvaldParser.prog_return r = parser.prog();

        // walk resulting tree
        CommonTree t = (CommonTree)r.getTree();
		//puu väljatrykk:
        //System.out.println(t.toStringTree());
        CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
        Eval walker = new Eval(nodes);
        walker.prog();
         for (Iterator it= walker.codeLine.keySet().iterator(); it.hasNext( ); ) {
		Object ckey = it.next();
		System.out.println(ckey+":\t "+ walker.codeLine.get(ckey));}
	}
}

Loome väikese testifaili test.txt, kus on mitmesuguseid if-then-else vorme:

IF a==b THEN IF c>d THEN {x=1;y=2+3*4;}ENDIF; ELSE z=0; ENDIF;
IF a<b THEN {Y = 2*(5-2);} ELSE X = 3*4 + 5; ENDIF;

Käivitame:

java Generate < test.txt

Tulemus :

1:	 IF a==b GOTO 3
2:	 GOTO 11
3:	 IF c>d GOTO 5
4:	 GOTO 10
5:	 x:=1
6:	 T0:=3*4
7:	 T1:=2+T0
8:	 y:=T1
10:	 GOTO 12
11:	 z:=0
12:	 IF a< GOTO 14
13:	 GOTO 18
14:	 T2:=5-2
15:	 T3:=2*T2
16:	 Y:=T3
17:	 GOTO 21
18:	 T4:=3*4
19:	 T5:=T4+5
20:	 X:=T5
21:	 END

Ülesandeid:

1. Ülalesitatud transleerimisskeemis peab ka bloki viimase käsu järel olema kas semikoolon või reavahetus, s.t. {x=1;y=2} ei lähe läbi, peab olema {x=1;y=2;}. Muuda transleerimisskeemi nii, et bloki viimase käsu järel võib lõpusümbol puududa (kuid võib ka olla, s.t. mõlemad eespoolesitatud näited kõlbavad); selleks tuleb bloki sisu esitada samasuguse vasakult ühekaupa alamosi "neelava" grammatikaga, nagu on kasutatud näiteks avaldise jaoks loengu "Kontekstivabade keelte süntaksianalüüs ülalt-alla" esimeses ülesandes (teine näide).

2. Sageli kasutatakse if-käsu jätkamist: if tingimus then if tingimus1 then if tingimus2 then ... else ...endif; . Koosta transleerimisskeem sellise kuitahes sügava if-lause transleerimiseks.

3. Paljudes programmeerimiskeeltes võib if-käsu esitada kujul tingimus ? then_osa:else_osa; näiteks sellised vormid oleks lubatud:

 (a>b)?x=1:z=2;
(a<b)?{x=1;y=2;}:{u=1;v=2;};

s.t. tingimus peab olema sulgudes, ? ja : vahel ning pärast : on kas üks käsk või blokk, kusjuures then-osas, s.t. ? ja : vahel olev käsk võib olla lõpumärgendita (selle lõppetab : ), kuid else osas (: järel) oleval käsul peab olema lõpumärgend ; (või kasutatakse seal blokki). Koosta sellise if-käsu transleerimisskeem.

4. Ülalesitatud näites peavad if-käsud ja omistamised lõppema semikooloniga ; . Kui real on vaid üksainus käsk (ülalesitatud grammatika järgi võib olla ka mitu), võib semikooloni käsu lõpumärgina asendada reavahetusega. Modifitseeri ülalesitatud näidet nii, et käsu lõpus võiks semikoolon ka puududa, kui see käsk on eraldi real, s.t. samal real selle järel enam teist käsku ei tule.

5. Moodusta transleerimiskeem case-lause jaoks, selle süntaks peaks olema selline, et see transleeriks (näiteks) sellise näite

case Inflation is
   when < 1 => Don't_worry; Be_Happy ;
   when 1..2 => Start_thinking ;
   when 3..4 => Convert_all_to_euro; Change_Government;
   when > 4 => Sell_Stock; Move_abroad;
   when others => Self_Destruct;
end case;

Siin when järel täidetavad osad on süntaksiga (statement ';'|Ident ';')+

Küsimused, probleemid: