Kihagyás

Függvények kezelése

Feladat (f07)

Írjunk nyelvtant egy egyszerű programnyelvhez. A programnyelv egyszerű kifejezéseket értékel ki, amelyekben értelmezett

  • a 4 matematikai alapművelet,
  • a hatványozás (^),
  • a zárójelezés,
  • az előjelváltás (-) és megtartás (+),
  • logikai operátorokat (not, and, or),
  • relációs operátorokat,
  • mindezek megfelelő prioritással kezelve,
  • az abs operátor,
  • a függvényhívás nulla vagy több bemenő módú argumentummal, és
  • az angol ábécé betűjével kezdődő, a továbbiakban aláhúzást, számot és/vagy az angol ábécé betűit tartalmazó azonosító mint változó (amiknek kezdetben 0 az értéke).

A program a következőképpen néz ki:

  • Egy sorban egy utasítás vagy változódeklaráció szerepelhet.
  • Egy utasítás lehet egy szimpla kifejezés.
  • A nyelv ismeri az if-then-else-end, while-do-end, és for-in-do-end vezérlési szerkezeteket (összetett utasításokat).
  • A for egy adott intervallum elemein megy végig egyesével növekvő sorrendben (a szintaxisért lásd a példa inputot).
  • Az összetett vezérléseknél bizonyos helyeken megengedett a sortörés.
  • A kiértékelés során nincs automatikus kiíratás, van viszont a nyelvben print(.) utasítás.
  • A változókat a var kulcsszó segítségével első használatuk előtt deklarálni kell.
  • Ha a sor egy azonosítóval és az = tokennel lezdődik, akkor az = után szerplő kifejezés értékét el kell menteni a megfelelő memóriarekeszbe.
  • A függvénydefiníció a function tokennel kezdődik, majd függvénynév, pereméterlista, az utasításai (amelyekben szerepelhet a return utasítás is), végül az end kulcsszó.
  • A függvényen belül deklarált változók lokálisak, és "eltakarják" a globális változókat.
  • Az üres sor megengedett.
  • Egy sorban a # utáni rész komment, eldobható.
  • A sorvége jelen kívül az egyéb whitespace karakterek bárhol megengedettek.

Készítsünk egy ANTLR4 nyelvtant, ami megvalósítja az ilyen programok kiértékelését.

Példa bemenet

input.txt

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function answer()
    return 42
end
answer()
function diff(x, y)
    if x < y
    then return y - x
    else return x - y
    end
end
diff (24, 18)
var A
var M
M = 1
A = diff ( (5 + 18 / 9 - 1) ^ 2 , abs -12 / 2 )
while A > 0 do
    A = A - 1
    M = A / M
    print (A)
end
A * 3 / (1 - -2)
# Komment

M = A / 2 / 3
var I
for I in (A, 10) do
    print ( M * (M - 1))
end

Induljunk ki az előző órai megoldásból:

A nyelvtan

Functions.g4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
grammar Functions;

options {
    language = Java;
}

@header {
    import java.util.ArrayList;
    import java.util.List;
}

@members {
    public static void main(String[] args) throws Exception {
         FunctionsLexer lex = new FunctionsLexer(new ANTLRFileStream(args[0]));
         CommonTokenStream tokens = new CommonTokenStream (lex);
         FunctionsParser parser = new FunctionsParser(tokens);
         parser.start(args.length > 1 && "--generate".equals(args[1]));
    }
}

start [ boolean genSrc ]
    @init{ ast.Program p = new ast.Program(); }
    @after{ if (genSrc) {
                System.out.println(p);
            } else {
                p.evaluate();
            }
    }
    : ((line[p] { p.addLine($line.node); } )? LF)* EOF
    ;

line [ ast.Program p ] returns [ ast.Line node ]
    : expr { $node = new ast.Line($p, $expr.node); }
    | ID '=' expr { $node = new ast.Line($p, $expr.node, $ID.text); }
    | function { $p.addFunction($function.node); $node = new ast.Line($p, $function.node); }
    ;

function returns [ ast.Function node ]
    : KW_FUNC fname=ID LPAR parlist RPAR KW_RET expr {
        $node = new ast.Function($fname.text, $parlist.list, $expr.node);
      }
    ;

parlist returns [ List<String> list ]
    : { $list = new ArrayList<String>(); }
        ( fstpar=ID { $list.add($fstpar.text); }
            ( OPLST nxtpar=ID { $list.add($nxtpar.text); } )*
        )?
    ;

expr returns [ ast.Expression node ]
    : fstop=addop { $node = $fstop.node; } (OPADD nxtop=addop {
        $node = new ast.Binary($OPADD.text, $node, $nxtop.node);
      })*
    ;

addop returns [ ast.Expression node ]
    : fstop=mulop { $node = $fstop.node; } (OPMUL nxtop=mulop {
        $node = new ast.Binary($OPMUL.text, $node, $nxtop.node);
      })*
    ;

mulop returns [ ast.Expression node ]
    : fstop=fct { $node = $fstop.node; } (OPPWR nxtop=mulop {
        $node = new ast.Binary($OPPWR.text, $node, $nxtop.node);
      })?
    ;

fct returns [ ast.Expression node ]
    : SZAM { $node = new ast.Const($SZAM.text); }
    | LPAR expr { $node = new ast.Parens($expr.node); } RPAR
    | op=(OPADD|OPABS) fct { $node = new ast.Unary($op.text, $fct.node); }
    | ID { $node = new ast.Memory($ID.text); }
    | ID LPAR arglist RPAR { $node = new ast.FunctionCall($ID.text, $arglist.list); }
    ;

arglist returns [ List<ast.Expression> list ]
    : { $list = new ArrayList<ast.Expression>(); }
        ( fstarg=expr { $list.add($fstarg.node); }
            ( OPLST nxtarg=expr { $list.add($nxtarg.node); } )*
        )?
    ;

LF       : '\n' ;
WS       : [ \t\r]+ ->skip ;
KW_FUNC  : 'function' ;
KW_RET   : 'returns' ;
SZAM     : [0-9]+('.' [0-9]+)? ;
OPADD    : '+' | '-' ;
OPMUL    : '*' | '/' ;
OPPWR    : '^' ;
OPABS    : 'abs' ;
OPLST    : ',' ;
LPAR     : '(' ;
RPAR     : ')' ;
ID       : [A-Za-z][_0-9A-Za-z]* ;
COMMENT  : '#' (~[\n])* ->skip ;

Jó pár dolgon változtatni kell. Egyrészt, a plusz műveletek miatt a kifejezésnek új szintjei jönnek be: a logikai kifejezések alacsonyabb prioritásúak a numerikus kifejezéseknél.

A másik dolog, ami megváltozik, hogy sorokat lecseréljük utasításokra/utasítássorozatokra. Erre azért lesz szükség, mert mind a program, mind a függvény utasítássorozatokat fog tartalmazni, és a vezérlő utasításokban is utasítássorozatokat tudunk majd megadni. Az utasítások listája kiegészül a fent tárgyalt vezérlő utasításokkal (bizonyos pontokon beszúrható sortörésekkel).

Mivel a függvények és változók logikai és numerikus tényezőként is megjelenhetnek, külön szabályba szerveztük ki őket. Pár apróbb simítástól (ami az új/módosított AST miatt szükséges) eltekintve a nyelvtannal készen vagyunk.

A nyelvtan

Functions.g4

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
grammar Functions;

options {
    language = Java;
}

@header {
    import java.util.ArrayList;
    import java.util.List;
}

@members {
    public static void main(String[] args) throws Exception {
         FunctionsLexer lex = new FunctionsLexer(new ANTLRFileStream(args[0]));
         CommonTokenStream tokens = new CommonTokenStream (lex);
         FunctionsParser parser = new FunctionsParser(tokens);
         parser.start(args.length > 1 && "--generate".equals(args[1]));
    }
}

start [ boolean genSrc ]
    @init{ ast.Program p = new ast.Program(); }
    @after{ if (genSrc) {
                System.out.println(p);
            } else {
                p.execute();
            }
    }
    : sequence[p] { p.addStatements($sequence.node); } EOF
    ;

sequence [ ast.Program prog ] returns [ ast.Sequence node ]
    : { $node = new ast.Sequence(prog); } (statement[prog] LF+ { $node.addStatement($statement.node); })+
    ;

statement [ ast.Program prog ] returns [ ast.Statement node ]
    : expr
        { $node = new ast.ExprStmt($prog, $expr.node); }
    | ID '=' expr
        { $node = new ast.Assignment($prog, $ID.text, $expr.node); }
    | { ast.Statement fbnode = null; }
      KW_IF ic=logical_expr LF*
      KW_THEN LF* tb=sequence[prog] LF*
      ( KW_ELSE LF* fb=sequence[prog] LF* { fbnode = $fb.node; } )?
      KW_END
        { $node = new ast.If($prog, $ic.node, $tb.node, fbnode); }
    | KW_WHILE wc=logical_expr LF*
      KW_DO LF* wb=sequence[prog] LF*
      KW_END
        { $node = new ast.While($prog, $wc.node, $wb.node); }
    | KW_FOR ID KW_IN LPAR beg=expr OPLST end=expr RPAR LF*
      KW_DO LF* lb=sequence[prog] LF*
      KW_END
        { $node = new ast.For($prog, $ID.text, $beg.node, $end.node, $lb.node); }
    | KW_RET expr
        { $node = new ast.Return($prog, $expr.node); }
    | KW_VAR ID
        { $node = new ast.VarDecl($prog, $ID.text); }
    | KW_FUNC fname=ID LPAR parlist RPAR LF sequence[prog] KW_END
        { ast.Function fnc = new ast.Function($fname.text, $parlist.list);
          fnc.addStatements($sequence.node);
          $prog.addFunction(fnc);
          $node = new ast.FncDecl($prog, fnc);
        }
    | KW_PRINT LPAR expr RPAR
        { $node = new ast.Print($prog, $expr.node); }
    ;

parlist returns [ List<String> list ]
    : { $list = new ArrayList<String>(); }
        ( fstpar=ID { $list.add($fstpar.text); }
            ( OPLST nxtpar=ID { $list.add($nxtpar.text); } )*
        )?
    ;

expr returns [ ast.Expression node ]
    : logical_expr { $node=$logical_expr.node; }
    | num_expr { $node=$num_expr.node; }
    ;

logical_expr returns [ ast.Expression node ]
    : fstop=logical_tag { $node = $fstop.node; }
        (OPOR nxtop=logical_tag { $node = new ast.Binary($OPOR.text, $node, $nxtop.node); })*
    ;

logical_tag returns [ ast.Expression node ]
    : fstop=logical_fct { $node = $fstop.node; }
        (OPAND nxtop=logical_fct { $node = new ast.Binary($OPAND.text, $node, $nxtop.node); })*
    ;

logical_fct returns [ ast.Expression node ]
    : rel=num_expr op=(OPEQ|OPREL) rer=num_expr { $node = new ast.Binary($op.text, $rel.node, $rer.node); }
    | OPNOT logical_fct { $node = new ast.Unary($OPNOT.text, $logical_fct.node); }
    | LPAR logical_expr RPAR { $node = new ast.Parens($logical_expr.node); } RPAR
    | vr=variable { $node = $vr.node; }
    | fr=functioncall { $node = $fr.node; }
    ;

num_expr returns [ ast.Expression node ]
    : fstop=addop { $node = $fstop.node; }
        (OPADD nxtop=addop { $node = new ast.Binary($OPADD.text, $node, $nxtop.node); })*
    ;

addop returns [ ast.Expression node ]
    : fstop=mulop { $node = $fstop.node; } (OPMUL nxtop=mulop {
        $node = new ast.Binary($OPMUL.text, $node, $nxtop.node);
      })*
    ;

mulop returns [ ast.Expression node ]
    : fstop=num_fct { $node = $fstop.node; } (OPPWR nxtop=mulop {
        $node = new ast.Binary($OPPWR.text, $node, $nxtop.node);
      })?
    ;

num_fct returns [ ast.Expression node ]
    : SZAM { $node = new ast.Const($SZAM.text); }
    | LPAR num_expr { $node = new ast.Parens($num_expr.node); } RPAR
    | op=(OPADD|OPABS) num_fct { $node = new ast.Unary($op.text, $num_fct.node); }
    | vr=variable { $node = $vr.node; }
    | fr=functioncall { $node = $fr.node; }
    ;

variable returns [ ast.Expression node ]
    : ID { $node = new ast.Variable($ID.text); }
    ;

functioncall returns [ ast.Expression node ]
    : ID LPAR arglist RPAR { $node = new ast.FunctionCall($ID.text, $arglist.list); }
    ;

arglist returns [ List<ast.Expression> list ]
    : { $list = new ArrayList<ast.Expression>(); }
        ( fstarg=expr { $list.add($fstarg.node); }
            ( OPLST nxtarg=expr { $list.add($nxtarg.node); } )*
        )?
    ;

LF       : '\n' ;
WS       : [ \t\r]+ ->skip ;
KW_DO    : 'do' ;
KW_ELSE  : 'else' ;
KW_END   : 'end' ;
KW_FOR   : 'for' ;
KW_FUNC  : 'function' ;
KW_IF    : 'if' ;
KW_IN    : 'in' ;
KW_PRINT : 'print' ;
KW_RET   : 'return' ;
KW_THEN  : 'then' ;
KW_VAR   : 'var' ;
KW_WHILE : 'while' ;
SZAM     : [0-9]+('.' [0-9]+)? ;
OPOR     : 'or' ;
OPAND    : 'and' ;
OPNOT    : 'not' ;
OPREL    : '<' | '<=' | '>' | '>=' ;
OPEQ     : '==' | '!=' ;
OPADD    : '+' | '-' ;
OPMUL    : '*' | '/' ;
OPPWR    : '^' ;
OPABS    : 'abs' ;
OPLST    : ',' ;
LPAR     : '(' ;
RPAR     : ')' ;
ID       : [A-Za-z][_0-9A-Za-z]* ;
COMMENT  : '#' (~[\n])* ->skip ;

Amit ügyesen kell majd megoldani, az a változók és függvényhívások kezelése. Most ugye nem csak arról van szó, hogy a függvény egyetlen paraméterezhető kifejezés, hanem utasítások sorozata (mint egy program), saját változókkal. Mivel most már rendes függvényeink vannak, amibe a rekurzió is bele kell, hogy férjen, kénytelenek vagyunk vermet kezelni függvényhívások és return utasítások során. Továbbra is megtartjuk a globális változókat (ha az adott scope-ban nem találjuk a változót, akkor nem a verem további szintjein, hanem a globálisak között kell keresni), és a függvénylista is marad.

A ''Főprogram'' és a függvények osztálya, valamint a kettő ősosztályának AST node-jai

Body.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package ast;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public abstract class Body {
    private List<Statement> statements = new ArrayList<Statement>();

    public void addStatements(Sequence s) {
        statements = s.getStatements();
    }

    public void execute() {
        for (Statement s: statements) {
            s.execute();
        }
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        for (Statement s: statements) {
            str.append(s.toString());
        }
        return str.toString();
    }
}

Program.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package ast;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class Program extends Body {
    private Map<String, Function> functions = new HashMap<String, Function>();
    private Map<String, Value> globals = new HashMap<String, Value>();
    private Stack<Map<String, Value>> locals = new Stack<Map<String, Value>>();

    public void addFunction(Function f) {
        functions.put(f.getFname(), f);
    }

    public Function getFunction(String name) {
        return functions.get(name);
    }

    public void addVariable(String name) {
        Map<String, Value> table = globals;
        if (!locals.empty()) {
            table = locals.peek();
        }
        if (table.containsKey(name)) {
            throw new RuntimeException("Double declaration of variable " + name);
        }
        table.put(name, null);
    }

    public void setVariable(String name, Value val) {
        if (!locals.empty() && locals.peek().containsKey(name)) {
            locals.peek().put(name, val);
            return;
        }
        if (!globals.containsKey(name)) {
            throw new RuntimeException("No variable " + name);
        }
        globals.put(name, val);
    }

    public Value getVariable(String name) {
        if (!locals.empty() && locals.peek().containsKey(name)) {
            return locals.peek().get(name);
        }
        if (!globals.containsKey(name)) {
            throw new RuntimeException("No variable " + name);
        }
        return globals.get(name);
    }

    public void newStackFrame() {
        locals.push(new HashMap<String, Value>());
    }

    public void freeStackFrame() {
        if (locals.empty()) {
            throw new RuntimeException("Returning to void");
        }
        locals.pop();
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("## Program\n")
           .append(super.toString())
           .append("## End\n");
        return str.toString();
    }
}

Function.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package ast;

import java.util.Iterator;
import java.util.List;

public class Function extends Body {
    private String fname;
    private List<String> pnames;

    public Function(String fname, List<String> pnames) {
        this.fname = fname;
        this.pnames = pnames;
    }

    public String getFname() {
        return fname;
    }

    public List<String> getParameterNames() {
        return pnames;
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("function ");
        str.append(fname);
        str.append("(");
        Iterator<String> parit = pnames.iterator();
        if (parit.hasNext()) {
            str.append(parit.next());
            while (parit.hasNext()) {
                str.append(", ");
                str.append(parit.next());
            }
        }
        str.append(")\n");
        str.append(super.toString());
        str.append("end\n");
        return str.toString();
    }
}

Új node-okként bejönnek az utasítások és utasításként a vezérlési szerkezetek (többek között a "szimpla" utasítássorozat).

Ne feletkezzünk meg arról, hogy a függvényekből a return hatására vissza is kell térni! Mivel (a főprogramban és) a függvényekben az utasítássorozatokat egyszerűen sorban kiértékeljük, a visszatérésre valami speciális mechanizmus szükséges. Mi most a Java kivételkezelését fogjuk arra használni, hogy egy függvényből a végrehajtása során bárhonnan visszatérhessünk. Vagyis a return utasítás vissza fogja "dobni" a kiszámított eredményt.

Az utasítások AST node-jainak ősosztálya és a konkrét utasítások

Statement.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
package ast;

import java.util.ArrayList;
import java.util.List;

public abstract class Statement {
    protected Program program = null;

    protected Statement(Program prog) {
        program = prog;
    }

    public abstract void execute();

    public abstract String toString();
}

Assignment.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package ast;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Assignment extends Statement {
    private String varName;
    private Expression expr;

    public Assignment(Program prog, String varName, Expression expr) {
        super(prog);
        this.varName = varName;
        this.expr = expr;
    }

    @Override
    public void execute() {
        program.setVariable(varName, expr.evaluate(program));
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append(varName)
           .append(" = ")
           .append(expr.toString())
           .append("\n");
        return str.toString();
    }
}

ExprStmt.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
package ast;

public class ExprStmt extends Statement {
    private Expression expr;

    public ExprStmt(Program prog, Expression expr) {
        super(prog);
        this.expr = expr;
    }

    @Override
    public void execute() {
        expr.evaluate(program);
    }

    @Override
    public String toString() {
        return expr.toString() + "\n";
    }
}

FncDecl.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
package ast;

public class FncDecl extends Statement {
    private Function f = null;

    public FncDecl(Program prog, Function f) {
        super(prog);
        this.f = f;
    }

    @Override
    public void execute() {
    }

    @Override
    public String toString() {
        return f.toString();
    }
}

For.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package ast;

public class For extends Statement {
    private String idxVar = null;
    private Expression start = null;
    private Expression stop = null;
    private Statement stmt = null;

    public For(Program prog, String v, Expression l, Expression h, Statement s) {
        super(prog);
        idxVar = v;
        start = l;
        stop = h;
        stmt = s;
    }

    @Override
    public void execute() {
        double b = start.evaluate(program).getNumericValue();
        double e = stop.evaluate(program).getNumericValue();
        while (b <= e) {
            program.setVariable(idxVar, new Value(b));
            stmt.execute();
            b += 1.0;
        }
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("for ")
           .append(idxVar)
           .append(" in (")
           .append(start.toString())
           .append(", ")
           .append(stop.toString())
           .append(")\ndo\n")
           .append(stmt.toString())
           .append("end\n");
        return str.toString();
    }
}

If.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package ast;

public class If extends Statement {
    private Expression cond = null;
    private Statement trueBranch = null;
    private Statement falseBranch = null;

    public If(Program prog, Expression cond, Statement trus, Statement fals) {
        super(prog);
        this.cond = cond;
        this.trueBranch = trus;
        this.falseBranch = fals;
    }

    @Override
    public void execute() {
        Value v = cond.evaluate(program);
        if (v.getLogicValue()) {
            trueBranch.execute();
        } else if (falseBranch != null) {
            falseBranch.execute();
        }
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("if ")
           .append(cond.toString())
           .append("\nthen\n")
           .append(trueBranch.toString());
        if (falseBranch != null) {
            str.append("else\n")
               .append(falseBranch.toString());
        }
        str.append("end\n");
        return str.toString();
    }
}

Print.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
package ast;

public class Print extends Statement {
    private Expression expr;

    public Print(Program prog, Expression expr) {
        super(prog);
        this.expr = expr;
    }

    @Override
    public void execute() {
        System.out.println(expr.evaluate(program));
    }

    @Override
    public String toString() {
        return "print (" + expr.toString() + ")\n";
    }
}

Return.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package ast;

public class Return extends Statement {
    private Expression expr = null;

    public Return(Program prog, Expression expr) {
        super(prog);
        this.expr = expr;
    }

    @Override
    public void execute() {
        throw new Returning(expr.evaluate(program));
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("return ")
           .append(expr.toString())
           .append("\n");
        return str.toString();
    }
}

Sequence.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package ast;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Sequence extends Statement {
    private List<Statement> statements = new ArrayList<Statement>();

    public Sequence(Program prog) {
        super(prog);
    }

    public void addStatement(Statement s) {
        statements.add(s);
    }

    public List<Statement> getStatements() {
        return statements;
    }

    @Override
    public void execute() {
        for (Statement s: statements) {
            s.execute();
        }
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        for (Statement s: statements) {
            str.append(s.toString()).append("\n");
        }
        return str.toString();
    }
}

VarDecl.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package ast;

public class VarDecl extends Statement {
    private String varName;

    public VarDecl(Program prog, String name) {
        super(prog);
        varName = name;
    }

    @Override
    public void execute() {
        program.addVariable(varName);
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("var ")
           .append(varName)
           .append("\n");
        return str.toString();
    }
}

While.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package ast;

public class While extends Statement {
    private Expression cond = null;
    private Statement stmt = null;

    public While(Program prog, Expression e, Statement s) {
        super(prog);
        cond = e;
        stmt = s;
    }

    @Override
    public void execute() {
        boolean b; 
        while (b = cond.evaluate(program).getLogicValue()) {
            stmt.execute();
        }
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("while ")
           .append(cond.toString())
           .append("\ndo\n")
           .append(stmt.toString())
           .append("end\n");
        return str.toString();
    }
}

A kifejezések AST node-jainak ősosztálya, és a bináris és számértékek tárolására alkalmas közös érték típus.

Expression.java

1
2
3
4
5
package ast;

public abstract class Expression {
    public abstract Value evaluate(Program p);
}

Value.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package ast;

public class Value {
    private final boolean isBool;
    private final double dVal;
    private final boolean bVal;

    public Value(double v) {
        this.isBool = false;
        this.dVal = v;
        this.bVal = false;
    }

    public Value(boolean v) {
        this.isBool = true;
        this.dVal = 0.0;
        this.bVal = v;
    }

    public boolean getLogicValue() {
        if (!this.isBool) {
            throw new RuntimeException("Not a logic value!");
        }
        return this.bVal;
    }

    public double getNumericValue() {
        if (this.isBool) {
            throw new RuntimeException("Not a numeric value!");
        }
        return this.dVal;
    }

    public String toString() {
        if (this.isBool) {
            return this.bVal ? "true" : "false";
        }
        return new Double(dVal).toString();
    }

}

''Levelek'', 0 operandusú kifejezések

Const.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
package ast;

public class Const extends Expression {
    private String literal;
    private Value value;

    public Const(String literal) {
        this.literal = literal;
        this.value = new Value(Double.parseDouble(literal));
    }

    @Override
    public Value evaluate(Program p) {
        return this.value;
    }

    @Override
    public String toString() {
        return this.literal;
    }
}

Variable.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
package ast;

public class Variable extends Expression {
    private String id;

    public Variable(String id) {
        this.id = id;
    }

    @Override
    public Value evaluate(Program p) {
        return p.getVariable(this.id);
    }

    @Override
    public String toString() {
        return id;
    }
}

Unáris kifejezések node-jai

Parens.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
package ast;

public class Parens extends Expression {
    private Expression exp;
    public Parens(Expression exp) {
        this.exp = exp;
    }

    @Override
    public Value evaluate(Program p) {
        return exp.evaluate(p);
    }

    @Override
    public String toString() {
        return "(" + exp.toString() + ")";
    }
}

Unary.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package ast;

public class Unary extends Expression {
    private enum UnaryOperator {
        PLS("+"), NEG("-"), ABS("abs"), NOT("not");
        private String text;
        private UnaryOperator(String text) {
            this.text = text;
        }
        public static UnaryOperator getUnaryOperator(String text) {
            for (UnaryOperator b : UnaryOperator.values()) {
                if (b.toString().equals(text)) {
                    return b;
                }
            }
            return null;
        }
        public String toString() {
            return this.text;
        }
    }

    private UnaryOperator op = null;
    private Expression node;
    public Unary(String op, Expression e) {
        this.op = UnaryOperator.getUnaryOperator(op);
        this.node = e;
    }
    public Value evaluate(Program p) {
        Value val = this.node.evaluate(p);
        switch (this.op) {
            case PLS: return val;
            case NEG: return new Value(-val.getNumericValue());
            case ABS: {
                double v = val.getNumericValue();
                if (v < 0) {
                    return new Value(-val.getNumericValue());
                } else {
                    return val;
                }
            }
            case NOT: return new Value(!val.getLogicValue());
        }
        return null;
    }
    public String toString() {
        return op.toString() + " " + node.toString();
    }
}

Bináris kifejezések node-jai

Binary.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package ast;

import java.io.*;

public class Binary extends Expression {
    private enum BinaryOperator {
        ADD("+"), SUB("-"), MUL("*"), DIV("/"), PWR("^"),
        LT("<"), LTE("<="), GT(">"), GTE(">="),
        EQ("=="), NE("!=");
        private String text;
        private BinaryOperator(String text) {
            this.text = text;
        }
        public static BinaryOperator getBinaryOperator(String text) {
            for (BinaryOperator b : BinaryOperator.values()) {
                if (b.toString().equals(text)) {
                    return b;
                }
            }
            return null;
        }
        public String toString() {
            return this.text;
        }
    }

    private BinaryOperator op = null;
    private Expression lhsNode = null;
    private Expression rhsNode = null;
    public Binary(String op, Expression lhs, Expression rhs) {
        this.op = BinaryOperator.getBinaryOperator(op);
        this.lhsNode = lhs;
        this.rhsNode = rhs;
    }

    @Override
    public Value evaluate(Program p) {
        final double EPS = 1e-10;
        Value lhs = this.lhsNode.evaluate(p);
        Value rhs = this.rhsNode.evaluate(p);
        switch (this.op) {
            case ADD: return new Value(lhs.getNumericValue() + rhs.getNumericValue());
            case SUB: return new Value(lhs.getNumericValue() - rhs.getNumericValue());
            case MUL: return new Value(lhs.getNumericValue() * rhs.getNumericValue());
            case DIV: return new Value(lhs.getNumericValue() / rhs.getNumericValue());
            case PWR: return new Value(Math.pow(lhs.getNumericValue(), rhs.getNumericValue()));
            case LT : return new Value( (lhs.getNumericValue() <  rhs.getNumericValue()) &&
                                        (Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) >= EPS) );
            case LTE: return new Value( (lhs.getNumericValue() < rhs.getNumericValue()) ||
                                        (Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) < EPS));
            case GT : return new Value( (lhs.getNumericValue() >  rhs.getNumericValue()) &&
                                        (Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) >= EPS) );
            case GTE: return new Value( (lhs.getNumericValue() > rhs.getNumericValue()) ||
                                        (Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) < EPS));
            case EQ : return new Value(Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) < EPS);
            case NE : return new Value(Math.abs(lhs.getNumericValue() - rhs.getNumericValue()) >= EPS);
        }
        return null;
    }

    @Override
    public String toString() {
        if (lhsNode == null) System.out.println("l.<NULL>");
        if (rhsNode == null) System.out.println("r.<NULL>");
        return lhsNode.toString() + " " + op.toString() + " " + rhsNode.toString();
    }
}

A függvényhívás kezelésének másik fele, hogy a függvényhíváskor arra számítunk, hogy a függvény "visszadobja" a kiszámított értéket.

Függvényhívás kifejezések node-jai, és a függvényhíváshoz kapcsolódó technikai AST elemek

FunctionCall.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package ast;

import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class FunctionCall extends Expression {
    private String fname;
    private List<Expression> args;
    public FunctionCall(String fname, List<Expression> args) {
        this.fname = fname;
        this.args = args;
    }

    @Override
    public Value evaluate(Program p) {
        Function f = p.getFunction(this.fname);
        Map<String, Value> params = new HashMap<String, Value>();
        Iterator<String> parameters = f.getParameterNames().iterator();
        Iterator<Expression> arguments = args.iterator();
        while (parameters.hasNext() && arguments.hasNext()) {
            String pname = parameters.next();
            Expression e = arguments.next();
            params.put(pname, e.evaluate(p));
        }
        p.newStackFrame();
        for (Map.Entry<String, Value> arg : params.entrySet()) {
            p.addVariable(arg.getKey());
            p.setVariable(arg.getKey(), arg.getValue());
        }
        Value retval = null;
        try {
            f.execute();
        } catch (Returning r) {
            retval = r.getValue();
        }
        p.freeStackFrame();
        return retval;
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append(fname);
        str.append("(");
        Iterator<Expression> argit = args.iterator();
        if (argit.hasNext()) {
            str.append(argit.next().toString());
            while (argit.hasNext()) {
                str.append(", ");
                str.append(argit.next().toString());
            }
        }
        str.append(")");
        return str.toString();
    }
}

Returning.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
package ast;

public class Returning extends RuntimeException {
    private Value retval = null;
    public Returning(Value retval) {
        this.retval = retval;
    }
    public Value getValue() {
        return retval;
    }
}


Utolsó frissítés: 2022-01-10 11:51:41