编译原理——函数！

前言：函数的实现又是一个难点，我们一点一点攻破！

0X00 函数调用

按照惯例我们写出函数调用的「文法」：

unary → ( "!" | "-" ) unary | call ;
call  → primary ( "(" arguments? ")" )* ;
arguments → expression ( "," expression )* ;

这样的文法可以匹配这样的函数调用：

A();
A()()();
A(a, b);

符合我们的语言。

接着，写出函数调用「抽象语法树」的格式：

static class Call extends Expr {
    Call(Expr callee, Token paren, List<Expr> arguments) {
        this.callee = callee;
        this.paren = paren;
        this.arguments = arguments;
    }

    <R> R accept(Visitor<R> visitor) {
        return visitor.visitCallExpr(this);
    }

    final Expr callee;
    final Token paren;
    final List<Expr> arguments;
}

然后在 parser 中，实现生成抽象语法树的代码：

private Expr unary() {
    // unary → ( "!" | "-" ) unary
    // | primary ;
    if (match(BANG, MINUS)) {
        Token operator = previous();
        Expr right = unary();
        return new Expr.Unary(operator, right);
    }

    return call();
}

private Expr call() {
    // 匹配 primary ( "(" arguments? ")" )* ;
    Expr expr = primary();
    // A() 中 A 的部分叫做 callee
    // A()() 中 A() 的部分也可以叫做 callee
    // 所以我们要，不断的匹配左侧 callee 的部分，并生成抽象语法树
    Expr callee = expr;
    while (true) {
        if (match(LEFT_PAREN)) {
            callee = getCallee(callee);
        } else {
            expr = callee;
            break;
        }
    }

    return expr;
}

private Expr getCallee(Expr callee) {
    // 匹配所有的参数
    List<Expr> arguments = new ArrayList<>();
    if (!check(RIGHT_PAREN)) {
        do {
            if (arguments.size() >= 255) {
                error(peek(), "Cannot have more than 255 arguments.");
            }
            arguments.add(expression());
        } while (match(COMMA));
    }

    Token paren = consume(RIGHT_PAREN, "Expect ')' after arguments.");

    return new Expr.Call(callee, paren, arguments);
}

最后执行这个「抽象语法树」

@Override
public Object visitCallExpr(Expr.Call expr) {
    // 首先执行 callee
    Object callee = evaluate(expr.callee);
    // 计算所有参数
    List<Object> arguments = new ArrayList<>();
    for (Expr argument : expr.arguments) {
        arguments.add(evaluate(argument));
    }
    
    // 如果最后的 primary 是 "" 之类的东西，要报错，不能执行
    if (!(callee instanceof LoxCallable)) {
        throw new RuntimeError(expr.paren, "Can only call functions and classes.");
    }

    // 判断有没有超过最大参数
    LoxCallable function = (LoxCallable) callee;
    if (arguments.size() != function.arity()) {
        throw new RuntimeError(expr.paren,
                               "Expected " + function.arity() + " arguments but got " + arguments.size() + ".");
    }
    
    // 函数如何执行的暂时不表
    return function.call(this, arguments);
}

其中 LoxCallable 的接口如下：

interface LoxCallable {
    int arity();
    Object call(Interpreter interpreter, List<Object> arguments);
}

0X01 实现一个内嵌函数

按照上面的步骤我们生成了调用函数的「抽象语法树」，以及执行这个「抽象语法树」。

由于我们现在没有实现如何定义一个函数，所以我们没有函数可调用。

但是我们可以实现一个简单的「内嵌函数」clock()，原理如下：

  • 实现一个全局环境 global
  • 在这个全局环境中定义一个 clock 的函数接口，实现

代码如下：

private Environment environment = globals;

    Interpreter() {
        globals.define("clock", new LoxCallable() {
            @Override
            public int arity() {
                return 0;
            }

            @Override
            public Object call(Interpreter interpreter, List<Object> arguments) {
                return (double) System.currentTimeMillis() / 1000.0;
            }

            @Override
            public String toString() {
                return "<native fn>";
            }
        });
    }

这样就能使用 clock 函数了。

var a = clock();
print a;

0X02 函数的声明

现在我们写一下函数声明的「文法」：

declaration → funDecl
            | varDecl
            | statement ;
funDecl  → "fun" function ;
function → IDENTIFIER "(" parameters? ")" block ;

接着我们写出「函数声明」的「抽象语法树」的格式：

static class Function extends Stmt {
    Function(Token name, List<Token> params, List<Stmt> body) {
        this.name = name;
        this.params = params;
        this.body = body;
    }

    <R> R accept(Visitor<R> visitor) {
        return visitor.visitFunctionStmt(this);
    }

    final Token name;
    final List<Token> params;
    final List<Stmt> body;
}

然后在 parser 中，实现生成「抽象语法树」的代码：

    private Stmt declaration() {
        // 在这里抓错误
        try {
            if (match(VAR)) {
                return varDeclaration();
            }
            if (match(FUN)) {
                return function("function");
            }
            return statement();
        } catch (ParseError e) {
            // 进入 panic mode
            synchronize();
            return null;
        }
    }

    private Stmt.Function function(String kind) {
        Token name = consume(IDENTIFIER, "Expect " + kind + " name.");
        consume(LEFT_PAREN, "Expect '(' after " + kind + " name.");
        List<Token> parameters = new ArrayList<>();
        if (!check(RIGHT_PAREN)) {
            do {
                if (parameters.size() >= 255) {
                    error(peek(), "Cannot have more than 255 parameters.");
                }

                parameters.add(consume(IDENTIFIER, "Expect parameter name."));
            } while (match(COMMA));
        }
        consume(RIGHT_PAREN, "Expect ')' after parameters.");

        consume(LEFT_BRACE, "Expect '{' before " + kind + " body.");
        List<Stmt> body = block();
        return new Stmt.Function(name, parameters, body);
    }

最后执行「抽象语法树」（定义函数）：

@Override
public Void visitFunctionStmt(Stmt.Function stmt) {
    LoxFunction function = new LoxFunction(stmt);
    environment.define(stmt.name.lexeme, function);
    return null;
}

这里的 LoxFunction 如下：

class LoxFunction implements LoxCallable {
    private final Stmt.Function declaration;

    LoxFunction(Stmt.Function declaration) {
        this.declaration = declaration;
    }

    @Override
    public int arity() {
        return declaration.params.size();
    }

    @Override
    public String toString() {
        return "<fn " + declaration.name.lexeme + ">";
    }

    @Override
    public Object call(Interpreter interpreter, List<Object> arguments) {
        Environment environment = new Environment(interpreter.globals);
        for (int i = 0; i < declaration.params.size(); i++) {
            environment.define(declaration.params.get(i).lexeme, arguments.get(i));
        }

        interpreter.executeBlock(declaration.body, environment);
        return null;
    }
}

而当我们执行函数的时候，会执行 function 的 call 函数，我们来看看 call 函数做了什么：

// 创建了一个新的环境，并把全局环境给了他
// 在新的环境中定义传过来的参数
public Object call(Interpreter interpreter, List<Object> arguments) {
    Environment environment = new Environment(interpreter.globals);
    for (int i = 0; i < declaration.params.size(); i++) {
        environment.define(declaration.params.get(i).lexeme, arguments.get(i));
    }

    interpreter.executeBlock(declaration.body, environment);
    return null;
}

这样我们就实现了一个可定义，可调用的函数。最后我们再来看看如何返回值

0X03 函数的返回

首先，我们写出 return 的文法：

statement  → exprStmt
           | forStmt
           | ifStmt
           | printStmt
           | returnStmt
           | whileStmt
           | block ;

returnStmt → "return" expression? ";" ;

在我们实现的语言中，不管有没有写 return 函数，其实都有返回值等价于：

return nil;

写出 return 的「抽象语法树」的格式：

    static class Return extends Stmt {
        Return(Token keyword, Expr value) {
            this.keyword = keyword;
            this.value = value;
        }

        <R> R accept(Visitor<R> visitor) {
            return visitor.visitReturnStmt(this);
        }

        final Token keyword;
        final Expr value;
    }

实现生成抽象语法树的代码：


private Stmt returnStatement() {
    Token keyword = previous();
    Expr value = null;
    if (!check(SEMICOLON)) {
        value = expression();
    }

    consume(SEMICOLON, "Expect ';' after return value.");
    return new Stmt.Return(keyword, value);
}

if (match(RETURN)) {
    return returnStatement();
}

执行抽象语法树：

@Override
public Void visitReturnStmt(Stmt.Return stmt) {
    Object value = null;
    if (stmt.value != null)
        value = evaluate(stmt.value);

    throw new Return(value);
}

并在 call 中抓住这个 Return exception：

try {
    interpreter.executeBlock(declaration.body, environment);
} catch (Return returnValue) {
    return returnValue.value;
}

这样就实现了 return 的语法

0X04 局部函数的实现

对于函数我们还有一个点没有实现：

fun makeCounter() {
  var i = 0;
  fun count() {
    i = i + 1;
    print i;
  }

  return count;
}

var counter = makeCounter();
counter(); // "1".
counter(); // "2".

这个叫做「闭包」

原理如下：

  • 当执行一个函数的时候，会产生一个属于这个函数的新环境，比如调用 makeCounter() 会产生一个新的环境，这个新的环境，会保存定义的所有变量

  • 当在外面执行内部函数的时候，由于内部函数保存了，定义它时的环境，所以就能够，访问之前环境定义的变量

代码如下：

@Override
public Void visitFunctionStmt(Stmt.Function stmt) {
    // environment 是当前环境
    LoxFunction function = new LoxFunction(stmt, environment);
    environment.define(stmt.name.lexeme, function);
    return null;
}

class LoxFunction implements LoxCallable {
    private final Stmt.Function declaration;
    private final Environment closure;

    LoxFunction(Stmt.Function declaration, Environment closure) {
        this.declaration = declaration;
        this.closure = closure;
    }

    @Override
    public int arity() {
        return declaration.params.size();
    }

    @Override
    public String toString() {
        return "<fn " + declaration.name.lexeme + ">";
    }

    @Override
    public Object call(Interpreter interpreter, List<Object> arguments) {
        Environment environment = new Environment(closure);
        for (int i = 0; i < declaration.params.size(); i++) {
            environment.define(declaration.params.get(i).lexeme, arguments.get(i));
        }

        try {
            interpreter.executeBlock(declaration.body, environment);
        } catch (Return returnValue) {
            return returnValue.value;
        }
        return null;
    }
}

至此我们「函数」相关知识的与代码已完成！

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 217,826评论 6赞 506
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,968评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,234评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,562评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,611评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,482评论 1赞 302
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,271评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,166评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,608评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,814评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,926评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,644评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,249评论 3赞 329
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,866评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,991评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,063评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,871评论 2赞 354