Avaldiste transleerimine väljundtekstiks

Aritmeetiliste avaldiste interpreteerimisel "sööb" interpretaator avaldist, asendades alamavaldised nende väärtusega, mida seejärel kasutatakse ülemise, s.t. avaldise puus seda alamavaldist sisaldava (alam)avaldise arvutamisel, seega abstraktse süntaksi puu (AST-puu) läbimisel lõppjärjestuses saadaksegi lõpuks kogu avaldise väärtus, ilma et vahepeal midagi oleks tarvis salvestada (puust väljaspool); informatsioon (alamavaldiste väärtused) liigub puud mööda üles, kuni puu kõige ülemises tipus (puu juures) saadaksegi kogu avaldise väärtus.

Kui avaldist ei ole tarvis arvutada, vaid väljastada avaldist arvutav kood (avaldise transleerimine), muutuvad ainult puuläbija tegevused puu tippudes - alampuu väärtuse arvutamise asemel tuleb väljastada alampuud arvutav avaldis. Et seda järgmises tipus kasutada saaks, tuleb see ka kuidagi tähistada. Tähistamiseks peab genereerima uusi muutujaid: T0, T1, T2 jne; neid genereeriv kood tuleb lisada teeläbija klassi deklaratsiooni järel valikute-osas:

public static int i = 0; // abimuutuja indeks
public static String getTempVariable()
{
return ("T"+(i++));
};

Genereeritud kood on tarvis ka salvestada; kasutame selleks stringimuutujat tulemus; ka selle deklaratsioon ja sellele uue käsu lisamise funktsioon kirjeldatakse teeläbija klassi deklaratsiooni järel valikute-osas

public static String tulemus = "";
public static String out(String str)
{
tulemus += str;
return tulemus;
};

Kuna avaldise puu tippudes sooritatakse kõikjal sama tegevus - moodustatakse väljundkoodi omistuslause, mis annab vastava tipu abimuutujale väärtuseks avaldise, mis saadakse vasak- ja parempoolse alamavaldise tähiseid operatsioonimärgiga (väljundkeele operatsioonimärk!) ühendamisel uueks transleeritud koodi käsu paremaks pooleks, defineerima ka selle operatsiooni jaoks funktsiooni: 

	public static String getRida(String var1, String left, String op, String right)
    {return (var1 + ":=" + left + op + right+"\n"); }

Abstrakse süntaksi puu läbimise reeglid teisendab Antlr Java-keele funktsioonideks. Alamavaldiste tähised on nende funktsioonide poolt väljastatavad stringid; vasak- ja parempoolse alampuu tähised (s.t. vastavates tippudes käivitatud funktsioonide väljastatud väärtused) on tipu jaoks genereeritud funktsiooni lokaalsed muutujad, mis tuleb deklareerida kohe reegli vasaku poole järel. Seega avaldise produktsioonid puuläbijas oleksid sellised: 

	expr returns [String s]
    :   ^('+' a=expr b=expr)  { s=getTempVariable();
    				rida = getRida(s,a,"+",b);
				out(rida);}
    |   ^('-' a=expr b=expr)  { s=getTempVariable();
				rida = getRida(s,a,"-",b);
				out(rida);}   
    |   ^('*' a=expr b=expr)  { s=getTempVariable();
				rida = getRida(s,a,"*",b);
				out(rida);}
    |   ID 
        {s = (String)($ID.text); }
    |   INT  {s = (String)($INT.text);}
    ;

Järgnevas kasutataksegi seda teisendust ainult omistamislauseid sisaldava programmiteksti transleerimisel väljundtekstiks. Kogu sisendi algussümboliks on mitteterminal programm, mis kirjeldab mitmeid omistamisi sisaldava sisendi (iga omistamine eraldi real). Algul genereerib grammatikaga Avald.g kirjeldatud parser abstraktse süntaksi puu (AST - Abstract Syntax Tree). Puu loomisel jäetakse ebaolulised tipud (näiteks sulud) välja, lisades vastavate lekseemide või tekstiosade järele märgi !; märk ^ tähendab, et talle eelnev lekseem, literal või mitteterminal tõstetakse vastava alampuu juureks.

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

prog:   ( omist {System.out.println($omist.tree.toStringTree());} )+ ;

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

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

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

tegur:   INT 
    |   ID
    |   '('! avald ')'!
    ;
ID  :   ('a'..'z'|'A'..'Z')+ ;
INT :   '0'..'9'+ ;
NEWLINE:'\r'? '\n' ;
WS  :   (' '|'\t')+ {skip();} ;

Puuläbija ja väljundkoodi genereerimine on kirjeldatud grammatikas Eval.g; siin grammatikareeglid kirjeldavad juba eelnevas loodud abstraktse süntaksi puud, tähistades alampuid sümboliga ^ ja loetledes see järel alampuu eeljärjestuses, s.t. juur ja seejärel tipud vasakult paremale, seega näit ^('+' a=avald b=avald) tähistab kõrvalolevat alapuud.

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

@members {
public static String tulemus = "";
public static int i = 0; // abimuutuja indeks
public static String rida = "";
public static String getTempVariable()  {
return ("T"+(i++)); };
public static String out(String rida)
{tulemus += rida;
return tulemus; };

public static String getRida(String id, String left, String op, String right)
{return (id + ":=" + left + op + right+"\n"); }

}

prog:   omist+ ;

omist:   ^('=' ID e=avald)
        {out($ID.text + ":="+ e +"\n");}
    ;

avald returns [String s]
    :   ^('+' a=avald b=avald)  { s=getTempVariable();
    				rida = getRida(s,a,"+",b);
				out(rida);}
    |   ^('-' a=avald b=avald)  { s=getTempVariable();
				rida = getRida(s,a,"-",b);
				out(rida);}   
    |   ^('*' a=avald b=avald)  { s=getTempVariable();
				rida = getRida(s,a,"*",b);
				out(rida);}
    |   ID 
        {
        s = (String)($ID.text);
        }
    |   INT  {s = (String)($INT.text);}
    ;

Translaatorit käivitav protseduur on kirjeldatud failis Generate.java, see väljastab ka muutuja tulemus väärtuse:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;

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();
        CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
        Eval walker = new Eval(nodes);
        walker.prog();
        System.out.println("Tulemus:\n" + walker.tulemus);
    }
}

Genereerime programmis ANTLRWorks grammatikale Avald.g vastava Java-koodi, siis grammatikale Eval.g vastava koodi ja kompileerime koos peaprogrammiga lis Generate.java (kõik need failid peavad olema samas kataloogis):

javac *.java

Loome translaatori testimiseks näiteks faili test.txt:

a=3+2*5
b=2*(7-a)

ja anname selle translaatori sisendiks:

java Generate <%f

Saame järgmise väljundi:

Tulemus:
T0:=2*5
T1:=3+T0
a:=T1
T2:=7-a
T3:=2*T2
b:=T3

Et näha, millised AST-puud genereeriti, lisame grammatika Avald.g omistuskäsu produktsioonile semantilise tegevuse puu väljatrükiks tippude loeteluna (eeljärjestuses), s.t. täiendame vastavat produktsiooni: 

prog:   ( omist {System.out.println($omist.tree.toStringTree());} )+ ;

Nüüd saame väljundisse ka testfaili omistamiskäskude AST-puude kirjeldused: 
(= a (+ 3 (* 2 5)))
(= b (* 2 (- 7 a)))
Tulemus:
T0:=2*5
T1:=3+T0
...
Ülesandeid:
1. Täienda ülalesitatud väljundi genereerimist nii, et lähtetekstis oleks lubatud ka multiomistamised süntaksitega a = b = ... ja a, b, c = ....
Küsimused, probleemid: ©2004 Jaak Henno