Függvények kezelése¶

Feladat (f06)

Í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 (+),
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 számológép soronként olvas és értékel ki.

Egy sorban egy kifejezés vagy függvénydefiníció szerepel.
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, returns és a kifejezés.
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 a számológépet.

Példa bemenet

function answer() returns 42
answer()
function add(x, y) returns x + y
add (24, 18)
6 + 12 + 24
6 * 7
6 + 6 * 6
6 * (3 + 4)
84 / 2
12 + (3 * (25 / 5)) - 9 + (2*3*4)
6 + 2*6 + 2^2*6
A = add ( (5 + 18 / 9 - 1) ^ 2 , abs -12 / 2 )
A * 3 / (1 - -2)
# Komment

M = A / 2 / 3
M * (M - 1)

Ki lehet indulni az előző órai megoldásból is, de használható egy másik AST megvalósítás is:

A nyelvtan

Functions.g4

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); } )? COMMENT? LF)* EOF
    ;

line [ ast.Program p ] returns [ ast.Line node ]
    : expr { $node = new ast.Line($p, $expr.node); }
    | MEM '=' expr { $node = new ast.Line($p, $expr.node, $MEM.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
    | OPADD fct { $node = new ast.Unary($OPADD.text, $fct.node); }
    | OPABS LPAR expr { $node = new ast.Unary($OPABS.text, $expr.node); } RPAR
    | MEM { $node = new ast.Memory($MEM.text); }
    | OPMINMAX LPAR fstop=expr { $node = new ast.MultiArg($OPMINMAX.text, $fstop.node); }
        (OPLST nxtop=expr  { ((ast.MultiArg)$node).addArgument($nxtop.node); }) * RPAR
    ;

LF       : '\n' ;
WS       : [ \t\r]+ ->skip ;
SZAM     : [0-9]+('.' [0-9]+)? ;
OPADD    : '+' | '-' ;
OPMUL    : '*' | '/' ;
OPPWR    : '^' ;
OPABS    : 'abs' ;
OPMINMAX : 'min' | 'max' ;
OPLST    : ',' ;
LPAR     : '(' ;
RPAR     : ')' ;
MEM      : 'M' ;
COMMENT  : '#' (~[\n])* ->skip ;

A ''Főprogram'' és a sorok AST node-jai

Program.java

package ast;

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

public class Program {
    private List<Line> lines = new ArrayList<Line>();
    private double memory;
    public void addLine(Line l) {
        lines.add(l);
    }
    public void setMemory(double val) {
        memory = val;
    }
    public double getMemory() {
        return memory;
    }
    public void evaluate() {
        for (Line l: lines) {
            l.evaluate();
        }
    }
    public String toString() {
        StringBuilder str = new StringBuilder();
        for (Line l: lines) {
            str.append(l.toString());
        }
        return str.toString();
    }
}

Line.java

package ast;

public class Line {
    private String assignee = null;
    private Expression expr = null;
    private Program program = null;
    public Line(Program p, Expression e) {
        this.program = p;
        this.expr = e;
    }
    public Line(Program p, Expression e, String a) {
        this.program = p;
        this.expr = e;
        this.assignee = a;
    }
    public void evaluate() {
        double value = expr.evaluate(this.program);
        if (this.assignee != null) {
            program.setMemory(value);
        }
        System.out.println(value);
    }
    public String toString() {
        if (assignee != null) {
            return assignee + " = " + expr.toString() + "\n";
        }
        return expr.toString() + "\n";
    }
}

A kifejezések AST node-jainak ősosztálya

Expression.java

package ast;

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

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

Const.java

package ast;

public class Const extends Expression {
    private double value;
    private String literal;
    public Const(String token) {
        this.literal = token;
        this.value = Double.parseDouble(token);
    }
    public double evaluate(Program p) {
        return value;
    }
    public String toString() {
        return literal;
    }
}

Memory.java

package ast;

public class Memory extends Expression {
    private String id;
    public Memory(String id) {
        this.id = id;
    }
    public double evaluate(Program p) {
        return p.getMemory();
    }
    public String toString() {
        return id;
    }
}

Unáris kifejezések node-jai

Parens.java

package ast;

public class Parens extends Expression {
    private Expression exp;
    public Parens(Expression exp) {
        this.exp = exp;
    }
    public double evaluate(Program p) {
        return exp.evaluate(p);
    }
    public String toString() {
        return "(" + exp.toString() + ")";
    }
}

Unary.java

package ast;

public class Unary extends Expression {
    private enum UnaryOperator {
        PLS("+"), NEG("-"), ABS("abs");
        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 double evaluate(Program p) {
        double val = this.node.evaluate(p);
        switch (this.op) {
            case PLS: return val;
            case NEG: return -val;
            case ABS: return (val < 0) ? -val : val;
        }
        return 0.0;
    }
    public String toString() {
    if (this.op == UnaryOperator.ABS) {
            return this.op.toString() + "(" + this.node.toString() + ")";
        } else {
            return this.op.toString() + this.node.toString();
        }
    }
}

Bináris kifejezések node-jai

Binary.java

package ast;

public class Binary extends Expression {
    private enum BinaryOperator {
        ADD("+"), SUB("-"), MUL("*"), DIV("/"), PWR("^");
        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;
    }
    public double evaluate(Program p) {
        double lhs = this.lhsNode.evaluate(p);
        double rhs = this.rhsNode.evaluate(p);
        switch (this.op) {
            case ADD: return lhs + rhs;
            case SUB: return lhs - rhs;
            case MUL: return lhs * rhs;
            case DIV: return lhs / rhs;
            case PWR: return Math.pow(lhs, rhs);
        }
        return 0.0;
    }
    public String toString() {
        return lhsNode.toString() + " " + op.toString() + " " + rhsNode.toString();
    }
}

Többargumentumú kifejezések node-jai

MultiArg.java

package ast;

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

public class MultiArg extends Expression {
    private enum MultiArgOperator {
        MIN("min"), MAX("max");
        private String text;
        private MultiArgOperator(String text) {
            this.text = text;
        }
        public static MultiArgOperator getMultiArgOperator(String text) {
            for (MultiArgOperator b : MultiArgOperator.values()) {
                if (b.toString().equals(text)) {
                    return b;
                }
            }
            return null;
        }
        public String toString() {
            return this.text;
        }
    }
    private MultiArgOperator op = null;
    private List<Expression> arguments;
    public MultiArg(String op, Expression first) {
        this.op = MultiArgOperator.getMultiArgOperator(op);
        arguments = new ArrayList<Expression>();
        arguments.add(first);
    }
    public void addArgument(Expression arg) {
        arguments.add(arg);
    }
    public double evaluate(Program prog) {
        Iterator<Expression> args = arguments.iterator();
        double retval = args.next().evaluate(prog);
        while (args.hasNext()) {
            switch (this.op) {
                case MIN:
                    retval = Math.min(retval, args.next().evaluate(prog));
                    break;
                case MAX:
                    retval = Math.max(retval, args.next().evaluate(prog));
                    break;
            }
        }
        return retval;
    }
    public String toString() {
        StringBuffer str = new StringBuffer("(");
        Iterator<Expression> args = arguments.iterator();
        str.append(args.next());
        while (args.hasNext()) {
            str.append(", ");
            str.append(args.next());
        }
        str.append(")");
        return str.toString();
    }
}

A nyelvtant kicsit át kell alakítani. Egyrészt a szimpla memória helyett most már azonosítókat fogunk használni (az AST-ben ezt már előkészítettük). Másrészt az abs operátor lesz, tehát a eltűnik a kötelező zárójel, és összevonható az előjel operátorokkal. Harmadrészt a min és max eltűnnek, helyettük viszont megjelenik a függvényhívás, külön argumentumlistával. Ehhez kapcsolódóan pedig bejön a függvénydeklaráció lehetősége, formális paraméterlistával (ami tulajdonképpen azonosítók sorozata), visszatérési értéket számoló kifejezéssel.

A nyelvtan

Functions.g4

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 ;

Az AST programot és sort reprezentáló node-jaiban két fontosabb változás lesz. Az egyik, hogy megjelennek a függvények (függvénydeklarációk), amiket külön, kereshető módon is nyilván kell tartanunk. A másik, hogy a függvények paraméterlistájában deklarált paraméterek lokális azonosítóként fognak működni, tehát nem elég a globális változókat nyilvántartani. (Ezt egyelőre nem bonyolítjuk túl, mert a nyelvünk még gyakorlatilag alkalmatlan a rekurzióra: csak végtelen rekurziót lehetne csinálni benne.)

A ''Főprogram'', a sorok és a függvények AST node-jai

Program.java

package ast;

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

public class Program {
    private List<Line> lines = new ArrayList<Line>();
    private Map<String, Function> functions = new HashMap<String, Function>();
    private Map<String, Double> variables = new HashMap<String, Double>();
    public void addLine(Line l) {
        lines.add(l);
    }
    public void addFunction(Function f) {
        functions.put(f.getFname(), f);
    }
    public Function getFunction(String name) {
        return functions.get(name);
    }
    public void setVariable(String name, double val) {
        variables.put(name, new Double(val));
    }
    public double getVariable(String name) {
        return variables.get(name).doubleValue();
    }
    public void evaluate() {
        for (Line l: lines) {
            l.evaluate();
        }
    }
    public String toString() {
        StringBuilder str = new StringBuilder();
        for (Line l: lines) {
            str.append(l.toString());
        }
        return str.toString();
    }
}

Line.java

package ast;

public class Line {
    private String assignee = null;
    private Expression expr = null;
    private Function fndecl = null;
    private Program program = null;
    public Line(Program p, Expression e) {
        this.program = p;
        this.expr = e;
    }
    public Line(Program p, Expression e, String a) {
        this.program = p;
        this.expr = e;
        this.assignee = a;
    }
    public Line(Program p, Function f) {
        this.program = p;
        this.fndecl = f;
    }
    public void evaluate() {
        if (expr == null) {
            return;
        }
        double value = expr.evaluate(this.program, null);
        if (this.assignee != null) {
            program.setVariable(this.assignee, value);
        }
        System.out.println(value);
    }
    public String toString() {
        if (fndecl != null) {
            return fndecl.toString() + "\n";
        }
        if (assignee != null) {
            return assignee + " = " + expr.toString() + "\n";
        }
        return expr.toString() + "\n";
    }
}

Function.java

package ast;

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

public class Function {
    private String fname;
    private List<String> pnames;
    private Expression exp;

    public Function(String fname, List<String> pnames, Expression exp) {
        this.fname = fname;
        this.pnames = pnames;
        this.exp = exp;
    }
    public String getFname() {
        return fname;
    }
    public List<String> getParameterNames() {
        return pnames;
    }
    public Expression getExpr() {
        return exp;
    }
    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(") returns ");
        str.append(exp.toString());
        return str.toString();
    }
}

Az előbb említett lokális azonosítók miatt a kifejezések kiértékeléséhez már nem egy, hanem két garnitúra változóra lesz szükség.

A kifejezések AST node-jainak ősosztálya

Expression.java

package ast;

import java.util.Map;

public abstract class Expression {
    public abstract double evaluate(Program p, Map<String, Double> locals);
}

A konstans csak formailag változik (lásd fentebb), a memóriaérték keresése viszont érdemben: ha valamit nem találunk a lokális változók között (vagy nincsenek lokális változóink, mert nem függvényben vagyunk), akkor megnézzük a globális változók között.

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

Const.java

package ast;

import java.util.Map;

public class Const extends Expression {
    private double value;
    private String literal;
    public Const(String token) {
        this.literal = token;
        this.value = Double.parseDouble(token);
    }
    public double evaluate(Program p, Map<String, Double> locals) {
        return this.value;
    }
    public String toString() {
        return literal;
    }
}

Memory.java

package ast;

import java.util.Map;

public class Memory extends Expression {
    private String id;
    public Memory(String id) {
        this.id = id;
    }
    public double evaluate(Program p, Map<String, Double> locals) {
        if (locals != null && locals.containsKey(this.id)) {
            return locals.get(this.id).doubleValue();
        }
        return p.getVariable(this.id);
    }
    public String toString() {
        return id;
    }
}

A zárójelezés szintén csak formailag változik, az abs-nál viszont már nincs szükség a zárójelekre.

Unáris kifejezések node-jai

Parens.java

package ast;

import java.util.Map;

public class Parens extends Expression {
    private Expression exp;
    public Parens(Expression exp) {
        this.exp = exp;
    }
    public double evaluate(Program p, Map<String, Double> locals) {
        return exp.evaluate(p, locals);
    }
    public String toString() {
        return "(" + exp.toString() + ")";
    }
}

Unary.java

package ast;

import java.util.Map;

public class Unary extends Expression {
    private enum UnaryOperator {
        PLS("+"), NEG("-"), ABS("abs");
        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 double evaluate(Program p, Map<String, Double> locals) {
        double val = this.node.evaluate(p, locals);
        switch (this.op) {
            case PLS: return val;
            case NEG: return -val;
            case ABS: return (val < 0) ? -val : val;
        }
        return 0.0;
    }
    public String toString() {
        return this.op.toString() + ((this.op == UnaryOperator.ABS) ? " " : "") + this.node.toString();
    }
}

A bináris kifejezéseken sem kell sokat alakítani.

Bináris kifejezések node-jai

Binary.java

package ast;

import java.util.Map;

public class Binary extends Expression {
    private enum BinaryOperator {
        ADD("+"), SUB("-"), MUL("*"), DIV("/"), PWR("^");
        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;
    }
    public double evaluate(Program p, Map<String, Double> locals) {
        double lhs = this.lhsNode.evaluate(p, locals);
        double rhs = this.rhsNode.evaluate(p, locals);
        switch (this.op) {
            case ADD: return lhs + rhs;
            case SUB: return lhs - rhs;
            case MUL: return lhs * rhs;
            case DIV: return lhs / rhs;
            case PWR: return Math.pow(lhs, rhs);
        }
        return 0.0;
    }
    public String toString() {
        return lhsNode.toString() + " " + op.toString() + " " + rhsNode.toString();
    }
}

A többargumentumú kifejezések viszont eltűnnek, helyettük bejön a függvényhívás. Kiértékeléskor először sorban kiértékeljük az argumentumokat és értéket adunk a megfelelő lokális változóknak, majd kiértékeljük a függvényhívást.

Függvényhívás kifejezések node-jai

FunctionCall.java

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;
    }
    public double evaluate(Program p, Map<String, Double> locals) {
        Function f = p.getFunction(this.fname);
        Map<String, Double> params = new HashMap<String, Double>();
        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, new Double(e.evaluate(p, locals)));
        }
        return f.getExpr().evaluate(p, params);
    }
    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();
    }
}

Utolsó frissítés: 2023-02-02 13:09:36